All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Namespaces | Functions
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.