lbann::graph Namespace Reference

Functions
void	print (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges, std::ostream &os)
std::set< El::Int >	get_neighbors (El::Int node, const std::map< El::Int, std::set< El::Int >> &edges)
bool	is_closure (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges)
bool	is_topologically_sorted (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges)
bool	is_cyclic (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges)
std::map< El::Int, std::set< El::Int > >	transpose (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges)
std::map< El::Int, std::set< El::Int > >	induce_subgraph (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges)
std::vector< El::Int >	breadth_first_search (El::Int root, const std::map< El::Int, std::set< El::Int >> &edges)
std::vector< El::Int >	depth_first_search (El::Int root, const std::map< El::Int, std::set< El::Int >> &edges)
std::vector< El::Int >	topological_sort (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges)
void	condensation (const std::set< El::Int > &nodes, const std::map< El::Int, std::set< El::Int >> &edges, std::map< El::Int, std::set< El::Int >> &components, std::set< El::Int > &condensation_nodes, std::map< El::Int, std::set< El::Int >> &condensation_edges)

Function Documentation

breadth_first_search()

std::vector<El::Int> lbann::graph::breadth_first_search	(	El::Int	root,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Perform a breadth-first search starting from a given root node.

The search order is deterministic.

condensation()

void lbann::graph::condensation	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges,
		std::map< El::Int, std::set< El::Int >> &	components,
		std::set< El::Int > &	condensation_nodes,
		std::map< El::Int, std::set< El::Int >> &	condensation_edges
	)

Construct the condensation of a graph.

The condensation of a graph is constructed by determining the strongly connected components, i.e. sets of nodes that are reachable from all nodes in the set, and coalescing them into single nodes. The condensation is a DAG and will be topologically sorted.

depth_first_search()

std::vector<El::Int> lbann::graph::depth_first_search	(	El::Int	root,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Perform a depth-first search starting from a given root node.

A depth-first search post-order is returned. The search order is deterministic.

get_neighbors()

std::set<El::Int> lbann::graph::get_neighbors	(	El::Int	node,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Get nodes adjacent to a given node.

induce_subgraph()

std::map<El::Int, std::set<El::Int> > lbann::graph::induce_subgraph	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Construct an induced subgraph.

Removes edges to nodes outside the set of nodes and returns the new set of edges.

is_closure()

bool lbann::graph::is_closure	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

A closure is a set of nodes with no edges to nodes outside the set.

is_cyclic()

bool lbann::graph::is_cyclic	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Check whether a directed graph is cyclic.

is_topologically_sorted()

bool lbann::graph::is_topologically_sorted	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Check whether a graph is topologically sorted.

A topologically sorted graph has no edges going from a node to an earlier node. The graph must be a directed acyclic graph.

print()

void lbann::graph::print	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges,
		std::ostream &	os
	)

Print the nodes and edges of a graph to an output stream.

topological_sort()

std::vector<El::Int> lbann::graph::topological_sort	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Topologically sort a graph.

A topologically sorted graph has no edges going from a node to an earlier node. The sort is deterministic and does not affect graphs that are already topologically sorted.

transpose()

std::map<El::Int, std::set<El::Int> > lbann::graph::transpose	(	const std::set< El::Int > &	nodes,
		const std::map< El::Int, std::set< El::Int >> &	edges
	)

Construct the transpose of a graph.

Reverses the direction of edges in the graph and returns the new set of edges.