#include <GraphAdjList.h>

Inheritance diagram for bridges::datastructure::GraphAdjList< K, E1, E2 >:

Detailed Description

template<typename K, typename E1 = K, typename E2 = E1>
class bridges::datastructure::GraphAdjList< K, E1, E2 >

This class provides methods to represent adjacency list based graphs.

The GraphAdjList class can be used to represent adjacency list

based graphs in BRIDGES; it takes 3 generic parameters: (1) K, which is an orderable key value used in accessing vertices (in constant time) using an STL map. This permits data sets that need to be accessed by keys that are strings, (2) E1, for maintaining vertex specific data, and (3) E2, for maintaining edge specific data. The class is a wrapper around the C++ unordered map class and, thus, derives all its operations from it. BRIDGES provides methods to visualize the graph and its contents.

The vertices of the graph are held in a C++ hashmap, for near constant time access; this enables us to use strings or integer ids for vertices. The adjacency lists are linked lists of SLelemnt type, The SLelement contains edge information (stored in its data as a generic). Each edge, of type Edge, contains the source, destination vertices and link attributes (color, opacity, thickness)

Convenience method addVertex() is provided to add vertices to the graph, and addEdge() is provided to add edges. Edges are retrieved by using the map and the adjcency list, given the vertex ids of the edge. Vertices can be styled directly from the vertex element returned by getVertex(), and edges are styled from a LinkVisualizer one can access through getLinkVisualizer(). Here is a simple example:

GraphAdjList<string, Integer, Double> graph = new GraphAdjList<string, int, double> ();
  graph.addVertex("a");
  graph.addVertex("b");
  graph.addEdge("a", "b");
  graph.getVertex("a").setShape("square");
  graph.getLinkVisualizer("a", "b").setColor("yellow");

Adjacency lists are singly linked lists using the BRIDGES SLelement. Iterators are provided for easy traversal of the adjacency lists. For instance,

GraphAdjList<string, int, double> graph = something();
for (Edge<string, double> e : graph.outgoingEdgeSetOf("a"))
  System.out.println("a -> "+e.getTo());

Graphs can have their nodes and links affected by visual attributes. Nodes can have color, size, opacity and shape and detailed in the ElementVisualizer class. Edges support attributes such as color, thickness and opacity and are detailed in the LinkVisualizer class. Element and link attributes are set using the getVisualizer() and getLinkVisualizer() methods. For instance,

GraphAdjList<string, int, double> graph = something();
  graph.addVertex("baskin");
  graph.addVertex("robins");
  graph.addEdge("baskin","robins");
  graph.getVisualizer()->setColor("cyan");
  graph.getVisualizer()->setShape("square");
  graph.getLinkVisualizer("baskin", "robins")->setColor("green");
  graph.getLinkVisualizer("baskin", "robins")->setOpacity("0.5f");

Parameters

K	used as an index to retrieve vertices,
E1	data type used to store vertex specific information,
E2	data type used to store edge specific information

Author: Kalpathi Subramanian, Erik Saule

Date: Last modified 4/22/18, 7/12/19, 12/28/20, 1/5/21

There is a tutorial about Graph Adjacency List : https://bridgesuncc.github.io/tutorials/Graph.html

There are two visualization engines available for graph. The small graph visualization supports all attributes of vertices and edges but is prohibitively slow on large graphs. The large graph visualization only supports locations (actually they are mandatory) and colors, all other attributes are ignored.

BRIDGES picks the rendering engine automatically. But it can be forced to pick one used forceLargeVizualization() and forceSmallVizualization()

Classes
class	constVertexElementSet_listhelper
	This is a helper class to return sets of vertices in a way that are iterable with range for loops. Students should not have to use this directly. More...

class	KeySet_helper

class	VertexElementSet_listhelper
	This is a helper class to return sets of vertices in a way that are iterable with range for loops. Students should have to use this directly. More...

Public Member Functions
	GraphAdjList ()=default

	GraphAdjList (GraphAdjList &&gr)=default

virtual	~GraphAdjList () override

virtual const string	getDStype () const override
	Get the string representation of this data structure type. More...

void	addVertex (const K &k, const E1 &e=E1())
	Adds a vertex to the graph. More...

void	addEdge (const K &src, const K &dest, const E2 &data=E2())

bool	isEdge (const K &src, const K &dest)

const E1 &	getVertexData (const K &src) &
	Gets vertex data for a graph vertex. More...

void	setVertexData (const K &vertID, E1 const &data)
	Loads vertex specific information for a graph vertex. More...

E2 &	getEdgeData (const K &src, const K &dest)
	Gets edge data for the edge from "src" to "dest". More...

E2 const &	getEdgeData (const K &src, const K &dest) const
	Gets edge data for the edge from "src" to "dest" - const version. More...

void	setEdgeData (const K &src, const K &dest, E2 &data)
	Loads edge specific information for the edge from "src" to "dest". More...

unordered_map< K, Element< E1 > * > *	getVertices ()
	Return the graph nodes. More...

const unordered_map< K, Element< E1 > * > *	getVertices () const
	Return the graph nodes - const version. More...

const Element< E1 > *	getVertex (const K &key) const
	Return the vertex corresponding to a key. More...

Element< E1 > *	getVertex (const K &key)

Edge< K, E2 >	getEdge (const K &src, const K &dest)
	Get the edge between src and dest vertices. More...

const unordered_map< K, SLelement< Edge< K, E2 > > * > &	getAdjacencyList () const
	Return the adjacency list. More...

SLelement< Edge< K, E2 > > *	getAdjacencyList (const K &k)
	Returns adjacency list of a vertex with name k. More...

const SLelement< Edge< K, E2 > > *	getAdjacencyList (const K &k) const

ElementVisualizer *	getVisualizer (const K &k)
	Returns the visualizer corresponding to a graph vertex. convenient method to set attributes of the graph vertex. More...

LinkVisualizer *	getLinkVisualizer (const K &k1, const K &k2)
	Returns the link visualizer corresponding to an edge. Returns the link visualizer corresponding to two graph nodes with an existing link; error returned if no link exists. More...

void	forceLargeVisualization (bool f)
	Force the rendering engine to use large graph visualization. More...

void	forceSmallVisualization (bool f)
	Force the rendering engine to use small graph visualization. More...

KeySet_helper	keySet () const

SLelement< Edge< K, E2 > >::SLelement_listhelper	outgoingEdgeSetOf (K const &k)
	This method is useful for iterating through a set of outgoing edges from a vertex. More...

SLelement< Edge< K, E2 > >::SLelement_constlisthelper	outgoingEdgeSetOf (K const &k) const
	This method is useful for iterating through a set of outgoing edges from a vertex - const version. More...

VertexElementSet_listhelper	vertexSet ()

constVertexElementSet_listhelper	vertexSet () const

Public Member Functions inherited from bridges::datastructure::DataStructure
virtual	~DataStructure ()=default

Constructor & Destructor Documentation

◆ GraphAdjList() [1/2]

template<typename K , typename E1 = K, typename E2 = E1>

bridges::datastructure::GraphAdjList< K, E1, E2 >::GraphAdjList ( )

default

◆ GraphAdjList() [2/2]

template<typename K , typename E1 = K, typename E2 = E1>

bridges::datastructure::GraphAdjList< K, E1, E2 >::GraphAdjList ( GraphAdjList< K, E1, E2 > && gr )

default

◆ ~GraphAdjList()

template<typename K , typename E1 = K, typename E2 = E1>

virtual bridges::datastructure::GraphAdjList< K, E1, E2 >::~GraphAdjList ( )

inlineoverridevirtual

Member Function Documentation

◆ addEdge()

template<typename K , typename E1 = K, typename E2 = E1>

void bridges::datastructure::GraphAdjList< K, E1, E2 >::addEdge	(	const K &	src,
		const K &	dest,
		const E2 &	data = `E2()`
	)

inline

@brief Add an edge with data.

Note that this function adds the edge regardless of the contents of the adjacency list; its the user's responsibility to ensure there are no duplicates and ensure consistency.

Parameters

src	The key of the source Vertex
dest	The key of the destination Vertex
data	The edge data

Exceptions

out_of_range	If "src" or "dest" is non-existent within this graph
bad_alloc	If allocation of a graph adjacency list item failed

◆ addVertex()

template<typename K , typename E1 = K, typename E2 = E1>

void bridges::datastructure::GraphAdjList< K, E1, E2 >::addVertex	(	const K &	k,
		const E1 &	e = `E1()`
	)

inline

Adds a vertex to the graph.

Adds a vertex of key "k" and value "e" to the graph, and initializes its adjacency list; If this key already exists then this will not create a new vertex.

Parameters

k	The vertex key
e	The vertex data

◆ forceLargeVisualization()

template<typename K , typename E1 = K, typename E2 = E1>

void bridges::datastructure::GraphAdjList< K, E1, E2 >::forceLargeVisualization ( bool f )

inline

Force the rendering engine to use large graph visualization.

This forces the rendering to a more bandwidth efficient at the cost of having less features. The large graph visualization only renders vertices that have specified locations. The only usable attribute for vertices and edges are colors.

Parameters

f	set to true to force the visualization engine to use large graphs visualization. Setting to false does not prevent large visualization to be used, just does not force it.

◆ forceSmallVisualization()

template<typename K , typename E1 = K, typename E2 = E1>

void bridges::datastructure::GraphAdjList< K, E1, E2 >::forceSmallVisualization ( bool f )

inline

Force the rendering engine to use small graph visualization.

The small visualization uses more bandwidth, have more features, and support a force directed layout for vertices which do not have a specified location.

Parameters

f	set to true to force the visualization engine to use small graphs visualization. Setting to false does not prevent small visualization to be used, just does not force it.

◆ getAdjacencyList() [1/3]

template<typename K , typename E1 = K, typename E2 = E1>

const unordered_map<K, SLelement<Edge<K, E2> >*>& bridges::datastructure::GraphAdjList< K, E1, E2 >::getAdjacencyList ( ) const

inline

Return the adjacency list.

Returns: The adjacency list of the graph

◆ getAdjacencyList() [2/3]

template<typename K , typename E1 = K, typename E2 = E1>

SLelement<Edge<K, E2> >* bridges::datastructure::GraphAdjList< K, E1, E2 >::getAdjacencyList ( const K & k )

inline

Returns adjacency list of a vertex with name k.

Parameters

k	The key of the source vertex

Exceptions

out_of_range If key is non-existent within this graph

Returns: The adjacency list of key "k"

◆ getAdjacencyList() [3/3]

template<typename K , typename E1 = K, typename E2 = E1>

const SLelement<Edge<K, E2> >* bridges::datastructure::GraphAdjList< K, E1, E2 >::getAdjacencyList ( const K & k ) const

inline

Returns adjacency list of a vertex with name k - const version

Parameters

k	The key of the source vertex

Exceptions

out_of_range If key is non-existent within this graph

Returns: The adjacency list of key "k"

◆ getDStype()

template<typename K , typename E1 = K, typename E2 = E1>

virtual const string bridges::datastructure::GraphAdjList< K, E1, E2 >::getDStype ( ) const

inlineoverridevirtual

Get the string representation of this data structure type.

Returns: The string representation of this data structure type

Implements bridges::datastructure::DataStructure.

◆ getEdge()

template<typename K , typename E1 = K, typename E2 = E1>

Edge<K, E2> bridges::datastructure::GraphAdjList< K, E1, E2 >::getEdge	(	const K &	src,
		const K &	dest
	)

inline

Get the edge between src and dest vertices.

Parameters

src	source vertex of edge
dest	destination vertex of edge

Returns: edge between the vertices

◆ getEdgeData() [1/2]

template<typename K , typename E1 = K, typename E2 = E1>

E2& bridges::datastructure::GraphAdjList< K, E1, E2 >::getEdgeData	(	const K &	src,
		const K &	dest
	)

inline

Gets edge data for the edge from "src" to "dest".

Parameters

src	The key of the source Vertex
dest	The key of the destination Vertex

Returns: edge specific data

◆ getEdgeData() [2/2]

template<typename K , typename E1 = K, typename E2 = E1>

E2 const& bridges::datastructure::GraphAdjList< K, E1, E2 >::getEdgeData	(	const K &	src,
		const K &	dest
	)		const

inline

Gets edge data for the edge from "src" to "dest" - const version.

Parameters

src	The key of the source Vertex
dest	The key of the destination Vertex

Returns: edge specific data

◆ getLinkVisualizer()

template<typename K , typename E1 = K, typename E2 = E1>

LinkVisualizer* bridges::datastructure::GraphAdjList< K, E1, E2 >::getLinkVisualizer	(	const K &	k1,
		const K &	k2
	)

inline

Returns the link visualizer corresponding to an edge. Returns the link visualizer corresponding to two graph nodes with an existing link; error returned if no link exists.

Parameters

k1	The key of the link source vertex
k2	The key of the link destination vertex

Returns: the visualizer that controls the attributes of this link

◆ getVertex() [1/2]

template<typename K , typename E1 = K, typename E2 = E1>

Element<E1>* bridges::datastructure::GraphAdjList< K, E1, E2 >::getVertex ( const K & key )

inline

Return the requested vertex corresponding to a key - non-const version

Returns: the requested vertex of this graph or nullptr if not found

◆ getVertex() [2/2]

template<typename K , typename E1 = K, typename E2 = E1>

const Element<E1>* bridges::datastructure::GraphAdjList< K, E1, E2 >::getVertex ( const K & key ) const

inline

Return the vertex corresponding to a key.

Returns: the requested vertex of this graph or nullptr if not found

◆ getVertexData()

template<typename K , typename E1 = K, typename E2 = E1>

const E1& bridges::datastructure::GraphAdjList< K, E1, E2 >::getVertexData ( const K & src ) &

inline

Gets vertex data for a graph vertex.

Parameters

src	The key of the source vertex

Returns: E1 vertex specific data

◆ getVertices() [1/2]

template<typename K , typename E1 = K, typename E2 = E1>

unordered_map<K, Element<E1>*>* bridges::datastructure::GraphAdjList< K, E1, E2 >::getVertices ( )

inline

Return the graph nodes.

Returns: The vertex list of this graph

◆ getVertices() [2/2]

template<typename K , typename E1 = K, typename E2 = E1>

const unordered_map<K, Element<E1>*>* bridges::datastructure::GraphAdjList< K, E1, E2 >::getVertices ( ) const

inline

Return the graph nodes - const version.

Returns: The vertex list of this graph

◆ getVisualizer()

template<typename K , typename E1 = K, typename E2 = E1>

ElementVisualizer* bridges::datastructure::GraphAdjList< K, E1, E2 >::getVisualizer ( const K & k )

inline

Returns the visualizer corresponding to a graph vertex. convenient method to set attributes of the graph vertex.

Parameters

k	The key of the graph vertex

Returns: the visualizer that controls the attributes of this node

◆ isEdge()

template<typename K , typename E1 = K, typename E2 = E1>

bool bridges::datastructure::GraphAdjList< K, E1, E2 >::isEdge	(	const K &	src,
		const K &	dest
	)

inline

@brief Check if there is an edge between the given vertices

Parameters

src	The key of the source Vertex
dest	The key of the destination Vertex

◆ keySet()

template<typename K , typename E1 = K, typename E2 = E1>

KeySet_helper bridges::datastructure::GraphAdjList< K, E1, E2 >::keySet ( ) const

inline

Returns a set of all keys (helper function).

Returns a set of all keys (read only) that conforms to STL list interface. That means we can use range for loops on graph vertices.

Returns: set all keys

◆ outgoingEdgeSetOf() [1/2]

template<typename K , typename E1 = K, typename E2 = E1>

SLelement<Edge<K, E2> >::SLelement_listhelper bridges::datastructure::GraphAdjList< K, E1, E2 >::outgoingEdgeSetOf ( K const & k )

inline

This method is useful for iterating through a set of outgoing edges from a vertex.

◆ outgoingEdgeSetOf() [2/2]

template<typename K , typename E1 = K, typename E2 = E1>

SLelement<Edge<K, E2> >::SLelement_constlisthelper bridges::datastructure::GraphAdjList< K, E1, E2 >::outgoingEdgeSetOf ( K const & k ) const

inline

This method is useful for iterating through a set of outgoing edges from a vertex - const version.

◆ setEdgeData()

template<typename K , typename E1 = K, typename E2 = E1>

void bridges::datastructure::GraphAdjList< K, E1, E2 >::setEdgeData	(	const K &	src,
		const K &	dest,
		E2 &	data
	)

inline

Loads edge specific information for the edge from "src" to "dest".

Parameters

src	The key of the source Vertex
dest	The key of the destination Vertex
data	edge data

◆ setVertexData()

template<typename K , typename E1 = K, typename E2 = E1>

void bridges::datastructure::GraphAdjList< K, E1, E2 >::setVertexData	(	const K &	vertID,
		E1 const &	data
	)

inline

Loads vertex specific information for a graph vertex.

Parameters

vertID	The key of Vertex
data	data to set

◆ vertexSet() [1/2]

template<typename K , typename E1 = K, typename E2 = E1>

VertexElementSet_listhelper bridges::datastructure::GraphAdjList< K, E1, E2 >::vertexSet ( )

inline

Returns a set of vertices (Element<E>) that conforms to STL list interface. That means we can use range for

◆ vertexSet() [2/2]

template<typename K , typename E1 = K, typename E2 = E1>

constVertexElementSet_listhelper bridges::datastructure::GraphAdjList< K, E1, E2 >::vertexSet ( ) const

inline

Returns a set of vertices (Element<E>) that conforms to STL list interface. That means we can use range for

The documentation for this class was generated from the following files:

/home/erik/work/bridges/bridges-cxx/src/Element.h
/home/erik/work/bridges/bridges-cxx/src/GraphAdjList.h

Detailed Description

template<typename K, typename E1 = K, typename E2 = E1> class bridges::datastructure::GraphAdjList< K, E1, E2 >

Classes

Public Member Functions

Constructor & Destructor Documentation

◆ GraphAdjList() [1/2]

◆ GraphAdjList() [2/2]

◆ ~GraphAdjList()

Member Function Documentation

◆ addEdge()

◆ addVertex()

◆ forceLargeVisualization()

◆ forceSmallVisualization()

◆ getAdjacencyList() [1/3]

◆ getAdjacencyList() [2/3]

◆ getAdjacencyList() [3/3]

◆ getDStype()

◆ getEdge()

◆ getEdgeData() [1/2]

◆ getEdgeData() [2/2]

◆ getLinkVisualizer()

◆ getVertex() [1/2]

◆ getVertex() [2/2]

◆ getVertexData()

◆ getVertices() [1/2]

◆ getVertices() [2/2]

◆ getVisualizer()

◆ isEdge()

◆ keySet()

◆ outgoingEdgeSetOf() [1/2]

◆ outgoingEdgeSetOf() [2/2]

◆ setEdgeData()

◆ setVertexData()

◆ vertexSet() [1/2]

◆ vertexSet() [2/2]

template<typename K, typename E1 = K, typename E2 = E1>
class bridges::datastructure::GraphAdjList< K, E1, E2 >