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/concept/graph.h>
#include <lemon/concept/ugraph.h>
#include <lemon/concept_check.h>
#include <lemon/bin_heap.h>
#include <lemon/linear_heap.h>
#include <stack>
#include <functional>

Go to the source code of this file.

Namespaces

namespace  lemon
namespace  lemon::_topology_bits

Functions

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


Generated on Fri Feb 3 18:39:55 2006 for LEMON by  doxygen 1.4.6