Stores and implements a Graph. More...

#include <Graph.hpp>

Classes
class	Edge_Iterator
	Edge_Iterator class. Used to iterate over all Edges in the Graph More...

Public Types
using	val_t = SCALAR
	Value type. More...

using	idx_t = gl::index_type
	Index type. More...

using	Edge = gl::Edge< val_t >
	Edge type. More...

using	Node = gl::Node< val_t >
	Node type. More...

using	dest_vec_t = std::vector< std::pair< idx_t, val_t >>
	Destination-Vector type. More...

using	idx_list_t = std::vector< idx_t >
	Index List type. More...

using	ordered_list_t = std::list< idx_t >
	Ordered List type. More...

using	visit_list_t = std::vector< bool >
	Visited-List type. More...

template<class info_t >
using	BFS_queue_t = std::deque< info_t >
	BFS type. More...

using	DFS_queue_t = std::stack< idx_t >
	DFS type. More...

using	matrix_t = std::vector< Edge >
	Matrix Representation type. More...

using	nodeList_t = std::list< Edge >
	ListNode Representation type. More...

using	rootList_t = std::vector< nodeList_t >
	ListRoot Representation type. More...

using	EdgeIterator = Edge_Iterator< false >
	Edge iterator type. More...

using	ConstEdgeIterator = Edge_Iterator< true >
	Edge const_iterator type. More...

using	NodeIterator = typename std::vector< Node >::iterator
	Node iterator type. More...

using	ConstNodeIterator = typename std::vector< Node >::const_iterator
	Node const_iterator type. More...

Public Member Functions
bool	operator== (const Graph< SCALAR, gl::Matrix, DIRECTION > &rhs)

bool	operator!= (const Graph< SCALAR, STORAGE_KIND, DIRECTION > &rhs)

Construction
Various functions to create/destroy a Graph.
	Graph (const idx_t &numNodes=0, const std::string &label="Graph")
	Construct Graph from node count and label. More...

	Graph (const std::string &degreeSeq, const std::string &label="Simple Undirected Graph")
	Construct Graph from node count and label. More...

	Graph (const Property &property)
	Construct Graph from property. More...

	~Graph ()

gl::Graph< SCALAR, gl::Matrix, DIRECTION >	toMatrix () const
	Outputs a graph in Adjacency Matrix storage format with the same edges as this. This function only exists for ListGraphs. More...

gl::Graph< SCALAR, gl::List, DIRECTION >	toList () const
	Outputs a graph in Adjacency List storage format with the same edges as this. This function only exists for MatrixGraphs. More...

Property interface
Provides access to the properties of the Graph.
std::string	getGraphLabel () const
	Returns the label of the graph. More...

void	setGraphLabel (const std::string &label)
	Changes the label of the graph. More...

idx_t	numNodes () const
	Returns the number of nodes currently in the graph. More...

idx_t	numEdges () const
	Returns the number of edges currently in the graph. More...

bool	isDirected () const
	Returns true if the graph is directed, false if not. More...

bool	isUndirected () const
	Returns true if the graph is undirected, false if not. More...

bool	hasCycle () const
	Checks whether the given undirected graph containes cycles using an iterative BFS approach. More...

Edge interface
Provides access to the properties of the edges in a Graph.
void	setEdge (const idx_t &start, const idx_t &end, const val_t &weight=1, const Color &color=Color())
	Sets an edge including start/end points and weight. More...

void	setEdge (const Edge &edge)
	Adds an edge directly from an Edge object. More...

void	setEdgesFromListFile (const std::string &inFile)
	Adds edges found in inFile to the graph. More...

void	setEdgesFromMatrixFile (const std::string &inFile)
	Adds edges found in inFile to the graph. More...

void	updateEdge (const idx_t &start, const idx_t &end, const val_t &weight, const gl::Color &color)
	Updates edge properties. Parameters "start" & "end" mandatory, the rest optional. More...

void	delEdge (const idx_t &start, const idx_t &end)
	Deletes the edge going from start to end. More...

bool	hasEdge (const idx_t &start, const idx_t &end) const
	Checks whether an edge exists from start to end. More...

val_t	getEdgeWeight (const idx_t &start, const idx_t &end) const
	Finds the weight of the edge going from start to end. More...

Color	getEdgeColor (const idx_t &src, const idx_t &dest) const
	Returns the color of the edge from src to dest. More...

EdgeIterator	edge_begin ()
	EdgeIterator to the first edge. More...

EdgeIterator	edge_end ()
	EdgeIterator to behind the last edge. More...

ConstEdgeIterator	edge_cbegin () const
	ConstEdgeIterator to the first edge. More...

ConstEdgeIterator	edge_cend () const
	ConstEdgeIterator to the last edge. More...

Node interface
Provides access to the properties of the nodes in the Graph.
idx_list_t	getNeighbours (const idx_t &node) const
	Returns a list of all endpoints of outgoing edges from start. More...

idx_list_t	getUnvisitedNeighbours (const idx_t &node, const std::vector< bool > &visited) const
	Returns a list of endpoints + edge weights of outgoing edges from start. More...

dest_vec_t	getNeighbourWeights (const idx_t &node) const
	Returns a list of endpoints + edge weights of outgoing edges from start. More...

dest_vec_t	getUnvisitedNeighbourWeights (const idx_t &node, const visit_list_t &visited) const
	Returns a list of endpoints + edge weights of unvisited outgoing edges from start. More...

void	updateNode (const idx_t &id, const std::string &label, const val_t &capacity, const gl::Color &color, const std::pair< float, float > &position)
	Updates node properties. Parameter "id" mandatory, the rest optional. More...

std::string	getNodeLabel (const idx_t &id) const
	Finds the label of the given node. More...

val_t	getNodeCapacity (const idx_t &id) const
	Finds the flow capacity of the given node. More...

std::pair< float, float >	getNodePosition (const idx_t &id) const
	Finds the position of the given node. More...

idx_t	getNodeDegree (const idx_t &id) const
	Finds the degree of the given node (i.e. count of all in- & outgoing edges). More...

idx_t	getNodeInDegree (const idx_t &id) const
	Gets the in-degree of a node (i.e. count of all incoming edges). More...

idx_t	getNodeOutDegree (const idx_t &id) const
	Gets the in-degree of a node (i.e. count of all outgoing edges). More...

Color	getNodeColor (const idx_t &id) const
	Returns the color of a node. More...

void	readPositionsFromFile (const std::string &inFile)
	Updates node positions in the format "<id> <x-coord> <y-coord>" found in inFile. More...

NodeIterator	node_begin ()
	NodeIterator to the first node. More...

NodeIterator	node_end ()
	NodeIterator to behind the last node. More...

ConstNodeIterator	node_cbegin () const
	ConstNodeIterator to the first node. More...

ConstNodeIterator	node_cend () const
	ConstNodeIterator to behind the last node. More...

checkRange
Asserts that the given index/indecies is within the graph.
void	checkRange (const idx_t &idx1) const
	Only one index that gets range checked. More...

void	checkRange (const idx_t &idx1, const idx_t &idx2) const
	Two indices ("edge") that get range checked. More...

Protected Attributes
Property	property_
	Stores various properties of the Graph. More...

std::vector< Node >	nodes_
	Stores information about all nodes in the Graph. More...

std::conditional_t < std::is_same_v< STORAGE_KIND, Matrix >, matrix_t, rootList_t >	edges_
	Stores information about all edges in the Graph. More...

Private Member Functions
void	construct ()
	Auxiliary function. Creates an empty Graph using the deduced storage format. More...

Detailed Description

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>
class gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >

Stores and implements a Graph.

This class has functions to create and edit the graph, as well as access certain properties of the graph.

Template Parameters

SCALAR	Number type used to store edge weights.
STORAGE_KIND	Class type used to signify that a matrix shall be stored in either Adjacency Matrix or Adjacency List format. Accepted Values: gl::Matrix, gl::List
DIRECTION	Class type used to signify that the graph is either directed or undirected. Accepted Values: gl::Directed, gl::Undirected

Member Typedef Documentation

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::val_t = SCALAR

Value type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::idx_t = gl::index_type

Index type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::Edge = gl::Edge<val_t>

Edge type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::Node = gl::Node<val_t>

Node type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::dest_vec_t = std::vector<std::pair<idx_t, val_t>>

Destination-Vector type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::idx_list_t = std::vector<idx_t>

Index List type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::ordered_list_t = std::list<idx_t>

Ordered List type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::visit_list_t = std::vector<bool>

Visited-List type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

template<class info_t >

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::BFS_queue_t = std::deque<info_t>

BFS type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::DFS_queue_t = std::stack<idx_t>

DFS type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::matrix_t = std::vector<Edge>

Matrix Representation type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::nodeList_t = std::list<Edge>

ListNode Representation type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::rootList_t = std::vector<nodeList_t>

ListRoot Representation type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::EdgeIterator = Edge_Iterator<false>

Edge iterator type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::ConstEdgeIterator = Edge_Iterator<true>

Edge const_iterator type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::NodeIterator = typename std::vector<Node>::iterator

Node iterator type.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

using gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::ConstNodeIterator = typename std::vector<Node>::const_iterator

Node const_iterator type.

Constructor & Destructor Documentation

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::Graph	(	const idx_t &	numNodes = `0`,
		const std::string &	label = `"Graph< SCALAR, STORAGE_KIND, DIRECTION >"`
	)

inline

Construct Graph from node count and label.

Parameters

[in]	numNodes	Number of nodes/vertices in the graph.
[in]	label	Label of the graph.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::Graph	(	const std::string &	degreeSeq,
		const std::string &	label = `"Simple Undirected Graph< SCALAR, STORAGE_KIND, DIRECTION >"`
	)

inline

Construct Graph from node count and label.

Parameters

[in]	degreeSeq	Degree Sequence of an undirected graph (e.g. 5 1 1 1 1 1").
[in]	label	Label of the graph.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::Graph ( const Property & property )

inline

Construct Graph from property.

Parameters

[in] property Properties for a graph.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::~Graph ( )

inline

Member Function Documentation

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

gl::Graph<SCALAR, gl::Matrix, DIRECTION> gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::toMatrix ( ) const

inline

Outputs a graph in Adjacency Matrix storage format with the same edges as this. This function only exists for ListGraphs.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

gl::Graph<SCALAR, gl::List, DIRECTION> gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::toList ( ) const

inline

Outputs a graph in Adjacency List storage format with the same edges as this. This function only exists for MatrixGraphs.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

std::string gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getGraphLabel ( ) const

inline

Returns the label of the graph.

Returns: label of the graph

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::setGraphLabel ( const std::string & label )

inline

Changes the label of the graph.

Parameters

[in] label New label of the graph

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::numNodes ( ) const

inline

Returns the number of nodes currently in the graph.

Returns: number of nodes in the graph

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::numEdges ( ) const

inline

Returns the number of edges currently in the graph.

Returns: number of edges in the graph

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

bool gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::isDirected ( ) const

inline

Returns true if the graph is directed, false if not.

Returns: true if the graph is directed, false if not.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

bool gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::isUndirected ( ) const

inline

Returns true if the graph is undirected, false if not.

Returns: true if the graph is undirected, false if not.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

bool gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::hasCycle ( ) const

inline

Checks whether the given undirected graph containes cycles using an iterative BFS approach.

Returns: true if cyclic, false if acyclic

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::setEdge	(	const idx_t &	start,
		const idx_t &	end,
		const val_t &	weight = `1`,
		const Color &	color = `Color()`
	)

inline

Sets an edge including start/end points and weight.

Parameters

[in]	start	edge origin point
[in]	end	edge end point
[in]	weight	new edge weight
[in]	color	(Optional) new edge color

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::setEdge ( const Edge & edge )

inline

Adds an edge directly from an Edge object.

Parameters

[in] edge Edge that will be copied

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::setEdgesFromListFile ( const std::string & inFile )

inline

Adds edges found in inFile to the graph.

The edges shall be in a line delimited list format, e.g.:

1 2 3

7 4 6.7

Where the three numbers per line represent the start, end and weight of the new edge. This adds the two edges (1->2 with weight 3) and (7->4 with weight 6.7) to the graph.

Warning: The start and end indices have be valid inside the graph.

Parameters

[in] inFile file name of input file

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::setEdgesFromMatrixFile ( const std::string & inFile )

inline

Adds edges found in inFile to the graph.

The edges shall be in a comma delimited adjacency matrix format, e.g.:

1, ,3,6
4,5,7, 
 , ,4,6
9, ,2,1

This adds the 11 edges (0->0 with weight 1), (0->2 with weight 3) etc. to the graph.

Warning: The matrix dimensions have to match with the number of nodes in the graph squared. If they do not match, faulty input may be generated.

Parameters

[in] inFile file name of input file

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::updateEdge	(	const idx_t &	start,
		const idx_t &	end,
		const val_t &	weight,
		const gl::Color &	color
	)

inline

Updates edge properties. Parameters "start" & "end" mandatory, the rest optional.

Parameters

[in]	start	Edge origin point
[in]	end	Edge end point
[in]	weight	(Optional) New edge weight
[in]	color	(Optional) New edge color

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::delEdge	(	const idx_t &	start,
		const idx_t &	end
	)

inline

Deletes the edge going from start to end.

Parameters

[in]	start	edge origin point
[in]	end	edge end point

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

bool gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::hasEdge	(	const idx_t &	start,
		const idx_t &	end
	)		const

inline

Checks whether an edge exists from start to end.

Parameters

[in]	start	edge origin point
[in]	end	edge end point

Returns: true if there exists an edge, false otherwise

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

val_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getEdgeWeight	(	const idx_t &	start,
		const idx_t &	end
	)		const

inline

Finds the weight of the edge going from start to end.

Parameters

[in]	start	edge origin point
[in]	end	edge end point

Returns: weight of the selected edge

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

Color gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getEdgeColor	(	const idx_t &	src,
		const idx_t &	dest
	)		const

inline

Returns the color of the edge from src to dest.

Parameters

[in]	src	edge origin point
[in]	dest	edge destination point

Returns: Color of edge src->dest

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

EdgeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::edge_begin ( )

inline

EdgeIterator to the first edge.

Returns: Iterator to the first edge

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

EdgeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::edge_end ( )

inline

EdgeIterator to behind the last edge.

Returns: Iterator to behind the last edge

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

ConstEdgeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::edge_cbegin ( ) const

inline

ConstEdgeIterator to the first edge.

Returns: Iterator to the first edge

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

ConstEdgeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::edge_cend ( ) const

inline

ConstEdgeIterator to the last edge.

Returns: Iterator to last edge

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_list_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNeighbours ( const idx_t & node ) const

inline

Returns a list of all endpoints of outgoing edges from start.

Parameters

[in] node edge origin point

Returns: List of all direct neighbours

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_list_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getUnvisitedNeighbours	(	const idx_t &	node,
		const std::vector< bool > &	visited
	)		const

inline

Returns a list of endpoints + edge weights of outgoing edges from start.

Parameters

[in]	node	edge origin point
[in]	visited	boolean list of previously visited nodes

Returns: List of all direct neighbours + weights

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

dest_vec_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNeighbourWeights ( const idx_t & node ) const

inline

Returns a list of endpoints + edge weights of outgoing edges from start.

Parameters

[in] node edge origin point

Returns: List of all direct neighbours + weights

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

dest_vec_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getUnvisitedNeighbourWeights	(	const idx_t &	node,
		const visit_list_t &	visited
	)		const

inline

Returns a list of endpoints + edge weights of unvisited outgoing edges from start.

Parameters

[in]	node	edge origin point
[in]	visited	boolean list of previously visited nodes

Returns: List of all direct neighbours + weights

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::updateNode	(	const idx_t &	id,
		const std::string &	label,
		const val_t &	capacity,
		const gl::Color &	color,
		const std::pair< float, float > &	position
	)

inline

Updates node properties. Parameter "id" mandatory, the rest optional.

Parameters

[in]	id	ID of the node that should be updated.
[in]	label	(Optional) New label for the node.
[in]	capacity	(Optional) New flow capacity for the node.
[in]	color	(Optional) New color for the node.
[in]	position	(Optional) New x/y position for the node.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

std::string gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodeLabel ( const idx_t & id ) const

inline

Finds the label of the given node.

Parameters

[in] id ID of the node whose label is to be found.

Returns: Label of node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

val_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodeCapacity ( const idx_t & id ) const

inline

Finds the flow capacity of the given node.

Parameters

[in] id node whose flow capacity is to be found

Returns: Capacity of node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

std::pair<float, float> gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodePosition ( const idx_t & id ) const

inline

Finds the position of the given node.

Parameters

[in] id node whose position is to be found

Returns: pair of floats containing position

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodeDegree ( const idx_t & id ) const

inline

Finds the degree of the given node (i.e. count of all in- & outgoing edges).

Parameters

[in] id node whose degree is to be found

Returns: Degree of node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodeInDegree ( const idx_t & id ) const

inline

Gets the in-degree of a node (i.e. count of all incoming edges).

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

idx_t gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodeOutDegree ( const idx_t & id ) const

inline

Gets the in-degree of a node (i.e. count of all outgoing edges).

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

Color gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::getNodeColor ( const idx_t & id ) const

inline

Returns the color of a node.

Parameters

[in] id Node ID

Returns: Color of node with ID "id".

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::readPositionsFromFile ( const std::string & inFile )

inline

Updates node positions in the format "<id> <x-coord> <y-coord>" found in inFile.

Parameters

[in] inFile file name of input file

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

NodeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::node_begin ( )

inline

NodeIterator to the first node.

Returns: Iterator to first node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

NodeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::node_end ( )

inline

NodeIterator to behind the last node.

Returns: Iterator to behind the last node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

ConstNodeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::node_cbegin ( ) const

inline

ConstNodeIterator to the first node.

Returns: Iterator to the first node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

ConstNodeIterator gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::node_cend ( ) const

inline

ConstNodeIterator to behind the last node.

Returns: Iterator to behind the last node

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::checkRange ( const idx_t & idx1 ) const

inline

Only one index that gets range checked.

Parameters

[in] idx1 Index that will be range checked

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::checkRange	(	const idx_t &	idx1,
		const idx_t &	idx2
	)		const

inline

Two indices ("edge") that get range checked.

Parameters

[in]	idx1	First index that will be range checked
[in]	idx2	Second index that will be range checked.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

bool gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::operator== ( const Graph< SCALAR, gl::Matrix, DIRECTION > & rhs )

inline

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

bool gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::operator!= ( const Graph< SCALAR, STORAGE_KIND, DIRECTION > & rhs )

inline

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

void gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::construct ( )

inlineprivate

Auxiliary function. Creates an empty Graph using the deduced storage format.

Member Data Documentation

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

Property gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::property_

protected

Stores various properties of the Graph.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

std::vector<Node> gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::nodes_

protected

Stores information about all nodes in the Graph.

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>

std::conditional_t<std::is_same_v<STORAGE_KIND, Matrix>, matrix_t, rootList_t> gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >::edges_

protected

Stores information about all edges in the Graph.

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

/home/travis/build/guetzli32/GraphLib/graphlib/src/structures/Graph.hpp

Classes

Public Types

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected> class gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class SCALAR = int, class STORAGE_KIND = gl::List, class DIRECTION = gl::Undirected>
class gl::Graph< SCALAR, STORAGE_KIND, DIRECTION >