connectivity.h File Reference

Detailed Description

Connectivity algorithms

#include <lemon/dfs.h>
#include <lemon/bfs.h>
#include <lemon/core.h>
#include <lemon/maps.h>
#include <lemon/adaptors.h>
#include <lemon/concepts/digraph.h>
#include <lemon/concepts/graph.h>
#include <lemon/concept_check.h>
#include <stack>
#include <functional>

Namespaces
namespace	lemon
	The namespace of LEMON.

Functions
template<typename Graph>
bool	connected (const Graph &graph)
	Check whether an undirected graph is connected.
template<typename Graph>
int	countConnectedComponents (const Graph &graph)
	Count the number of connected components of an undirected graph.
template<class Graph, class NodeMap>
int	connectedComponents (const Graph &graph, NodeMap &compMap)
	Find the connected components of an undirected graph.
template<typename Digraph>
bool	stronglyConnected (const Digraph &digraph)
	Check whether a directed graph is strongly connected.
template<typename Digraph>
int	countStronglyConnectedComponents (const Digraph &digraph)
	Count the number of strongly connected components of a directed graph.
template<typename Digraph, typename NodeMap>
int	stronglyConnectedComponents (const Digraph &digraph, NodeMap &compMap)
	Find the strongly connected components of a directed graph.
template<typename Digraph, typename ArcMap>
int	stronglyConnectedCutArcs (const Digraph &digraph, ArcMap &cutMap)
	Find the cut arcs of the strongly connected components.
template<typename Graph>
int	countBiNodeConnectedComponents (const Graph &graph)
	Count the number of bi-node-connected components of an undirected graph.
template<typename Graph>
bool	biNodeConnected (const Graph &graph)
	Check whether an undirected graph is bi-node-connected.
template<typename Graph, typename EdgeMap>
int	biNodeConnectedComponents (const Graph &graph, EdgeMap &compMap)
	Find the bi-node-connected components of an undirected graph.
template<typename Graph, typename NodeMap>
int	biNodeConnectedCutNodes (const Graph &graph, NodeMap &cutMap)
	Find the bi-node-connected cut nodes in an undirected graph.
template<typename Graph>
int	countBiEdgeConnectedComponents (const Graph &graph)
	Count the number of bi-edge-connected components of an undirected graph.
template<typename Graph>
bool	biEdgeConnected (const Graph &graph)
	Check whether an undirected graph is bi-edge-connected.
template<typename Graph, typename NodeMap>
int	biEdgeConnectedComponents (const Graph &graph, NodeMap &compMap)
	Find the bi-edge-connected components of an undirected graph.
template<typename Graph, typename EdgeMap>
int	biEdgeConnectedCutEdges (const Graph &graph, EdgeMap &cutMap)
	Find the bi-edge-connected cut edges in an undirected graph.
template<typename Digraph>
bool	dag (const Digraph &digraph)
	Check whether a digraph is DAG.
template<typename Digraph, typename NodeMap>
void	topologicalSort (const Digraph &digraph, NodeMap &order)
	Sort the nodes of a DAG into topolgical order.
template<typename Digraph, typename NodeMap>
bool	checkedTopologicalSort (const Digraph &digraph, NodeMap &order)
	Sort the nodes of a DAG into topolgical order.
template<typename Graph>
bool	acyclic (const Graph &graph)
	Check whether an undirected graph is acyclic.
template<typename Graph>
bool	tree (const Graph &graph)
	Check whether an undirected graph is tree.
template<typename Graph>
bool	bipartite (const Graph &graph)
	Check whether an undirected graph is bipartite.
template<typename Graph, typename NodeMap>
bool	bipartitePartitions (const Graph &graph, NodeMap &partMap)
	Find the bipartite partitions of an undirected graph.
template<typename Graph>
bool	loopFree (const Graph &graph)
	Check whether the given graph contains no loop arcs/edges.
template<typename Graph>
bool	parallelFree (const Graph &graph)
	Check whether the given graph contains no parallel arcs/edges.
template<typename Graph>
bool	simpleGraph (const Graph &graph)
	Check whether the given graph is simple.