topology.h File Reference


Detailed Description

Topology related algorithms

#include <lemon/dfs.h>
#include <lemon/bfs.h>
#include <lemon/graph_utils.h>
#include <lemon/graph_adaptor.h>
#include <lemon/maps.h>
#include <lemon/concepts/graph.h>
#include <lemon/concepts/ugraph.h>
#include <lemon/concept_check.h>
#include <lemon/bin_heap.h>
#include <lemon/bucket_heap.h>
#include <stack>
#include <functional>

Namespaces

namespace  lemon
namespace  lemon::_topology_bits

Functions

template<typename UGraph>
bool connected (const UGraph &graph)
 Check that the given undirected graph is connected.
template<typename UGraph>
int countConnectedComponents (const UGraph &graph)
 Count the number of connected components of an undirected graph.
template<class UGraph, class NodeMap>
int connectedComponents (const UGraph &graph, NodeMap &compMap)
 Find the connected components of an undirected graph.
template<typename Graph>
bool stronglyConnected (const Graph &graph)
 Check that the given directed graph is strongly connected.
template<typename Graph>
int countStronglyConnectedComponents (const Graph &graph)
 Count the strongly connected components of a directed graph.
template<typename Graph, typename NodeMap>
int stronglyConnectedComponents (const Graph &graph, NodeMap &compMap)
 Find the strongly connected components of a directed graph.
template<typename Graph, typename EdgeMap>
int stronglyConnectedCutEdges (const Graph &graph, EdgeMap &cutMap)
 Find the cut edges of the strongly connected components.
template<typename UGraph>
int countBiNodeConnectedComponents (const UGraph &graph)
 Count the biconnected components.
template<typename UGraph>
bool biNodeConnected (const UGraph &graph)
 Checks the graph is bi-node-connected.
template<typename UGraph, typename UEdgeMap>
int biNodeConnectedComponents (const UGraph &graph, UEdgeMap &compMap)
 Find the bi-node-connected components.
template<typename UGraph, typename NodeMap>
int biNodeConnectedCutNodes (const UGraph &graph, NodeMap &cutMap)
 Find the bi-node-connected cut nodes.
template<typename UGraph>
bool biEdgeConnected (const UGraph &graph)
 Checks that the graph is bi-edge-connected.
template<typename UGraph>
int countBiEdgeConnectedComponents (const UGraph &graph)
 Count the bi-edge-connected components.
template<typename UGraph, typename NodeMap>
int biEdgeConnectedComponents (const UGraph &graph, NodeMap &compMap)
 Find the bi-edge-connected components.
template<typename UGraph, typename UEdgeMap>
int biEdgeConnectedCutEdges (const UGraph &graph, UEdgeMap &cutMap)
 Find the bi-edge-connected cut edges.
template<typename Graph, typename NodeMap>
void topologicalSort (const Graph &graph, NodeMap &order)
 Sort the nodes of a DAG into topolgical order.
template<typename Graph, typename NodeMap>
bool checkedTopologicalSort (const Graph &graph, NodeMap &order)
 Sort the nodes of a DAG into topolgical order.
template<typename Graph>
bool dag (const Graph &graph)
 Check that the given directed graph is a DAG.
template<typename UGraph>
bool acyclic (const UGraph &graph)
 Check that the given undirected graph is acyclic.
template<typename UGraph>
bool tree (const UGraph &graph)
 Check that the given undirected graph is tree.
template<typename UGraph>
bool bipartite (const UGraph &graph)
 Check if the given undirected graph is bipartite or not.
template<typename UGraph, typename NodeMap>
bool bipartitePartitions (const UGraph &graph, NodeMap &partMap)
 Check if the given undirected graph is bipartite or not.


Generated on Tue Oct 31 09:49:37 2006 for LEMON by  doxygen 1.5.1