Classes
class	BFS
	Class that provides Graph traversal using the BFS scheme. More...

class	Dijkstra
	Class that computes Dijkstra's Shortest Paths algorithm. More...

class	FloydWarshall
	Class computes that Shortest Paths for all pairs of nodes in the graph using the Floyd-Warshall algorithm. More...

class	Kruskal
	Class that computes a Minimum Spanning Tree using Kruskal's algorithm. More...

Functions
template<class Graph >
Graph::idx_list_t	degrees (const Graph &graph)
	Computes the out-degrees of all nodes in a graph. More...

template<class SCALAR , class STORAGE_KIND , class DIR , GL_ENABLE_IF_UNDIRECTED_T >
Graph< SCALAR, STORAGE_KIND, DIR >::idx_list_t	degreeSequence (const Graph< SCALAR, STORAGE_KIND, DIR > &graph)
	Computes the out-degree of all nodes in an undirected graph. The resulting list is sorted by descending degree. More...

template<class GRAPH >
void	DFS_recursive (const GRAPH &graph, const typename GRAPH::idx_t node, typename GRAPH::visit_list_t &visited, typename GRAPH::ordered_list_t &out)
	Recursive call for DFS. More...

template<class Graph >
Graph::ordered_list_t	DFS (const Graph &graph, const typename Graph::idx_t node)
	Traverses the connected component of node using DFS. More...

bool	havelHakimi (std::deque< gl::index_type > degrees)
	Uses the Havel-Hakimi algorithm to determine whether a given degree sequence is graphic. More...

bool	isGraphicSequence (const std::string &degreeSeq)
	Uses the Havel-Hakimi algorithm to determine whether a given degree sequence is graphic. More...

template<class class SCALAR, class STORAGE_KIND , class DIRECTION >
std::vector< float >	LaplacianSTL (const Graph< S, STORAGE, DIR > &g)
	Compute the Laplacian Matrix of a graph in an STL vector. More...

std::pair< std::vector< float > , std::vector< float > >	PositionsFromLaplacian (std::vector< float > laplacian, double factor=5.0)
	Compute Positions from Laplacian using BLAS routine. More...

template<class Graph >
void	SpectralPlacing (Graph &g)
	Compute node 2D positions using spectral placing. More...

template<class Graph >
Graph::ordered_list_t	transitiveClosure (const Graph &graph, const typename Graph::idx_t node)
	Implements an algorithm that finds the (reachability based) transitive closure of a node. More...

Function Documentation

template<class Graph >

Graph::idx_list_t gl::algorithm::degrees ( const Graph & graph )

Computes the out-degrees of all nodes in a graph.

Parameters

graph The graph to run the algorithm on

Template Parameters

Graph Type of graph

Returns: idx_list_t containing the degree of node i at position i

template<class SCALAR , class STORAGE_KIND , class DIR , GL_ENABLE_IF_UNDIRECTED_T >

Graph<SCALAR,STORAGE_KIND,DIR>::idx_list_t gl::algorithm::degreeSequence ( const Graph< SCALAR, STORAGE_KIND, DIR > & graph )

Computes the out-degree of all nodes in an undirected graph. The resulting list is sorted by descending degree.

Parameters

graph The graph to run the algorithm on

Returns: Sorted idx_list_t of all node degrees in the graph.

template<class GRAPH >

void gl::algorithm::DFS_recursive	(	const GRAPH &	graph,
		const typename GRAPH::idx_t	node,
		typename GRAPH::visit_list_t &	visited,
		typename GRAPH::ordered_list_t &	out
	)

Recursive call for DFS.

Parameters

graph	The graph to run the algorithm on
node	Start point of the graph search
visited	list keeping track of already visited nodes
out	result list

template<class Graph >

Graph::ordered_list_t gl::algorithm::DFS	(	const Graph &	graph,
		const typename Graph::idx_t	node
	)

Traverses the connected component of node using DFS.

Parameters

graph	The graph to run the algorithm on
node	Start point of the graph search

Template Parameters

Graph Type of graph

Returns: Sequence of all nodes visited by a DFS run.

bool gl::algorithm::havelHakimi ( std::deque< gl::index_type > degrees )

Uses the Havel-Hakimi algorithm to determine whether a given degree sequence is graphic.

Parameters

[in] degrees Deque representation of a degree sequence

Returns: True if sequence is graphic, false otherwise.

bool gl::algorithm::isGraphicSequence ( const std::string & degreeSeq )

Uses the Havel-Hakimi algorithm to determine whether a given degree sequence is graphic.

Parameters

[in] degreeSeq String representation of a degree sequence: e.g. "3 3 2 1 1 0"

Returns: True if sequence is graphic, false otherwise.

template<class class SCALAR, class STORAGE_KIND , class DIRECTION >

std::vector<float> gl::algorithm::LaplacianSTL ( const Graph< S, STORAGE, DIR > & g )

Compute the Laplacian Matrix of a graph in an STL vector.

Parameters

g	Graph whose Laplacian will be computed

Returns: Laplacian Matrix in STL vector format

std::pair<std::vector<float>, std::vector<float> > gl::algorithm::PositionsFromLaplacian	(	std::vector< float >	laplacian,
		double	factor = `5.0`
	)

Compute Positions from Laplacian using BLAS routine.

Parameters

laplacian	Vector of floats containing the laplacian of the graph
factor	Stretching-factor for positions

Returns: a pair of the first two eigenvectors scaled by degree and factor

template<class Graph >

void gl::algorithm::SpectralPlacing ( Graph & g )

Compute node 2D positions using spectral placing.

Parameters

g	Graph for which to compute the positions

template<class Graph >

Graph::ordered_list_t gl::algorithm::transitiveClosure	(	const Graph &	graph,
		const typename Graph::idx_t	node
	)

Implements an algorithm that finds the (reachability based) transitive closure of a node.

Parameters

graph	The graph that will be searched
node	The node whose transitive closure we want to find

Returns: ordered_list_t of all reachable nodes.

Classes

Functions

Function Documentation