deba@417: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@417:  *
deba@417:  * This file is a part of LEMON, a generic C++ optimization library.
deba@417:  *
alpar@1092:  * Copyright (C) 2003-2013
deba@417:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@417:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@417:  *
deba@417:  * Permission to use, modify and distribute this software is granted
deba@417:  * provided that this copyright notice appears in all copies. For
deba@417:  * precise terms see the accompanying LICENSE file.
deba@417:  *
deba@417:  * This software is provided "AS IS" with no warranty of any kind,
deba@417:  * express or implied, and with no claim as to its suitability for any
deba@417:  * purpose.
deba@417:  *
deba@417:  */
deba@417: 
deba@419: #ifndef LEMON_CONNECTIVITY_H
deba@419: #define LEMON_CONNECTIVITY_H
deba@417: 
deba@417: #include <lemon/dfs.h>
deba@417: #include <lemon/bfs.h>
deba@417: #include <lemon/core.h>
deba@417: #include <lemon/maps.h>
deba@417: #include <lemon/adaptors.h>
deba@417: 
deba@417: #include <lemon/concepts/digraph.h>
deba@417: #include <lemon/concepts/graph.h>
deba@417: #include <lemon/concept_check.h>
deba@417: 
deba@417: #include <stack>
deba@417: #include <functional>
deba@417: 
kpeter@586: /// \ingroup graph_properties
deba@417: /// \file
deba@417: /// \brief Connectivity algorithms
deba@417: ///
deba@417: /// Connectivity algorithms
deba@417: 
deba@417: namespace lemon {
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether an undirected graph is connected.
deba@417:   ///
kpeter@648:   /// This function checks whether the given undirected graph is connected,
kpeter@648:   /// i.e. there is a path between any two nodes in the graph.
kpeter@648:   ///
kpeter@648:   /// \return \c true if the graph is connected.
deba@417:   /// \note By definition, the empty graph is connected.
kpeter@648:   ///
kpeter@648:   /// \see countConnectedComponents(), connectedComponents()
kpeter@648:   /// \see stronglyConnected()
deba@417:   template <typename Graph>
deba@417:   bool connected(const Graph& graph) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     if (NodeIt(graph) == INVALID) return true;
deba@417:     Dfs<Graph> dfs(graph);
deba@417:     dfs.run(NodeIt(graph));
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         return false;
deba@417:       }
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
deba@417:   /// \brief Count the number of connected components of an undirected graph
deba@417:   ///
kpeter@648:   /// This function counts the number of connected components of the given
kpeter@648:   /// undirected graph.
deba@417:   ///
kpeter@648:   /// The connected components are the classes of an equivalence relation
kpeter@648:   /// on the nodes of an undirected graph. Two nodes are in the same class
kpeter@648:   /// if they are connected with a path.
kpeter@648:   ///
kpeter@648:   /// \return The number of connected components.
deba@417:   /// \note By definition, the empty graph consists
deba@417:   /// of zero connected components.
kpeter@648:   ///
kpeter@648:   /// \see connected(), connectedComponents()
deba@417:   template <typename Graph>
deba@417:   int countConnectedComponents(const Graph &graph) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::Node Node;
deba@417:     typedef typename Graph::Arc Arc;
deba@417: 
deba@417:     typedef NullMap<Node, Arc> PredMap;
deba@417:     typedef NullMap<Node, int> DistMap;
deba@417: 
deba@417:     int compNum = 0;
deba@417:     typename Bfs<Graph>::
deba@417:       template SetPredMap<PredMap>::
deba@417:       template SetDistMap<DistMap>::
deba@417:       Create bfs(graph);
deba@417: 
deba@417:     PredMap predMap;
deba@417:     bfs.predMap(predMap);
deba@417: 
deba@417:     DistMap distMap;
deba@417:     bfs.distMap(distMap);
deba@417: 
deba@417:     bfs.init();
deba@417:     for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@417:       if (!bfs.reached(n)) {
deba@417:         bfs.addSource(n);
deba@417:         bfs.start();
deba@417:         ++compNum;
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
deba@417:   /// \brief Find the connected components of an undirected graph
deba@417:   ///
kpeter@648:   /// This function finds the connected components of the given undirected
kpeter@648:   /// graph.
kpeter@648:   ///
kpeter@648:   /// The connected components are the classes of an equivalence relation
kpeter@648:   /// on the nodes of an undirected graph. Two nodes are in the same class
kpeter@648:   /// if they are connected with a path.
deba@417:   ///
kpeter@586:   /// \image html connected_components.png
kpeter@586:   /// \image latex connected_components.eps "Connected components" width=\textwidth
kpeter@586:   ///
kpeter@648:   /// \param graph The undirected graph.
deba@417:   /// \retval compMap A writable node map. The values will be set from 0 to
kpeter@648:   /// the number of the connected components minus one. Each value of the map
kpeter@648:   /// will be set exactly once, and the values of a certain component will be
deba@417:   /// set continuously.
kpeter@648:   /// \return The number of connected components.
kpeter@648:   /// \note By definition, the empty graph consists
kpeter@648:   /// of zero connected components.
kpeter@648:   ///
kpeter@648:   /// \see connected(), countConnectedComponents()
deba@417:   template <class Graph, class NodeMap>
deba@417:   int connectedComponents(const Graph &graph, NodeMap &compMap) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::Node Node;
deba@417:     typedef typename Graph::Arc Arc;
deba@417:     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
deba@417: 
deba@417:     typedef NullMap<Node, Arc> PredMap;
deba@417:     typedef NullMap<Node, int> DistMap;
deba@417: 
deba@417:     int compNum = 0;
deba@417:     typename Bfs<Graph>::
deba@417:       template SetPredMap<PredMap>::
deba@417:       template SetDistMap<DistMap>::
deba@417:       Create bfs(graph);
deba@417: 
deba@417:     PredMap predMap;
deba@417:     bfs.predMap(predMap);
deba@417: 
deba@417:     DistMap distMap;
deba@417:     bfs.distMap(distMap);
deba@417: 
deba@417:     bfs.init();
deba@417:     for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@417:       if(!bfs.reached(n)) {
deba@417:         bfs.addSource(n);
deba@417:         while (!bfs.emptyQueue()) {
deba@417:           compMap.set(bfs.nextNode(), compNum);
deba@417:           bfs.processNextNode();
deba@417:         }
deba@417:         ++compNum;
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
deba@419:   namespace _connectivity_bits {
deba@417: 
deba@417:     template <typename Digraph, typename Iterator >
deba@417:     struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       LeaveOrderVisitor(Iterator it) : _it(it) {}
deba@417: 
deba@417:       void leave(const Node& node) {
deba@417:         *(_it++) = node;
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       Iterator _it;
deba@417:     };
deba@417: 
deba@417:     template <typename Digraph, typename Map>
deba@417:     struct FillMapVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Map::Value Value;
deba@417: 
deba@417:       FillMapVisitor(Map& map, Value& value)
deba@417:         : _map(map), _value(value) {}
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _map.set(node, _value);
deba@417:       }
deba@417:     private:
deba@417:       Map& _map;
deba@417:       Value& _value;
deba@417:     };
deba@417: 
deba@417:     template <typename Digraph, typename ArcMap>
deba@419:     struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417: 
deba@419:       StronglyConnectedCutArcsVisitor(const Digraph& digraph,
deba@419:                                       ArcMap& cutMap,
deba@419:                                       int& cutNum)
deba@417:         : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
deba@419:           _compMap(digraph, -1), _num(-1) {
deba@417:       }
deba@417: 
deba@419:       void start(const Node&) {
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _compMap.set(node, _num);
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& arc) {
deba@417:          if (_compMap[_digraph.source(arc)] !=
deba@417:              _compMap[_digraph.target(arc)]) {
deba@417:            _cutMap.set(arc, true);
deba@417:            ++_cutNum;
deba@417:          }
deba@417:       }
deba@417:     private:
deba@417:       const Digraph& _digraph;
deba@417:       ArcMap& _cutMap;
deba@417:       int& _cutNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _compMap;
deba@417:       int _num;
deba@417:     };
deba@417: 
deba@417:   }
deba@417: 
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether a directed graph is strongly connected.
deba@417:   ///
kpeter@648:   /// This function checks whether the given directed graph is strongly
kpeter@648:   /// connected, i.e. any two nodes of the digraph are
deba@417:   /// connected with directed paths in both direction.
deba@417:   ///
kpeter@648:   /// \return \c true if the digraph is strongly connected.
kpeter@648:   /// \note By definition, the empty digraph is strongly connected.
alpar@877:   ///
kpeter@648:   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
kpeter@648:   /// \see connected()
deba@417:   template <typename Digraph>
deba@417:   bool stronglyConnected(const Digraph& digraph) {
deba@417:     checkConcept<concepts::Digraph, Digraph>();
deba@417: 
deba@417:     typedef typename Digraph::Node Node;
deba@417:     typedef typename Digraph::NodeIt NodeIt;
deba@417: 
deba@417:     typename Digraph::Node source = NodeIt(digraph);
deba@417:     if (source == INVALID) return true;
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef DfsVisitor<Digraph> Visitor;
deba@417:     Visitor visitor;
deba@417: 
deba@417:     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417:     dfs.init();
deba@417:     dfs.addSource(source);
deba@417:     dfs.start();
deba@417: 
deba@417:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         return false;
deba@417:       }
deba@417:     }
deba@417: 
deba@417:     typedef ReverseDigraph<const Digraph> RDigraph;
deba@419:     typedef typename RDigraph::NodeIt RNodeIt;
deba@417:     RDigraph rdigraph(digraph);
deba@417: 
kpeter@648:     typedef DfsVisitor<RDigraph> RVisitor;
deba@417:     RVisitor rvisitor;
deba@417: 
deba@417:     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417:     rdfs.init();
deba@417:     rdfs.addSource(source);
deba@417:     rdfs.start();
deba@417: 
deba@419:     for (RNodeIt it(rdigraph); it != INVALID; ++it) {
deba@417:       if (!rdfs.reached(it)) {
deba@417:         return false;
deba@417:       }
deba@417:     }
deba@417: 
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
alpar@877:   /// \brief Count the number of strongly connected components of a
kpeter@648:   /// directed graph
deba@417:   ///
kpeter@648:   /// This function counts the number of strongly connected components of
kpeter@648:   /// the given directed graph.
kpeter@648:   ///
deba@417:   /// The strongly connected components are the classes of an
kpeter@648:   /// equivalence relation on the nodes of a digraph. Two nodes are in
deba@417:   /// the same class if they are connected with directed paths in both
deba@417:   /// direction.
deba@417:   ///
kpeter@648:   /// \return The number of strongly connected components.
kpeter@648:   /// \note By definition, the empty digraph has zero
deba@417:   /// strongly connected components.
kpeter@648:   ///
kpeter@648:   /// \see stronglyConnected(), stronglyConnectedComponents()
deba@417:   template <typename Digraph>
deba@417:   int countStronglyConnectedComponents(const Digraph& digraph) {
deba@417:     checkConcept<concepts::Digraph, Digraph>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef typename Digraph::Node Node;
deba@417:     typedef typename Digraph::Arc Arc;
deba@417:     typedef typename Digraph::NodeIt NodeIt;
deba@417:     typedef typename Digraph::ArcIt ArcIt;
deba@417: 
deba@417:     typedef std::vector<Node> Container;
deba@417:     typedef typename Container::iterator Iterator;
deba@417: 
deba@417:     Container nodes(countNodes(digraph));
deba@417:     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
deba@417:     Visitor visitor(nodes.begin());
deba@417: 
deba@417:     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417:     dfs.init();
deba@417:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417: 
deba@417:     typedef typename Container::reverse_iterator RIterator;
deba@417:     typedef ReverseDigraph<const Digraph> RDigraph;
deba@417: 
deba@417:     RDigraph rdigraph(digraph);
deba@417: 
deba@417:     typedef DfsVisitor<Digraph> RVisitor;
deba@417:     RVisitor rvisitor;
deba@417: 
deba@417:     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417: 
deba@417:     int compNum = 0;
deba@417: 
deba@417:     rdfs.init();
deba@417:     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@417:       if (!rdfs.reached(*it)) {
deba@417:         rdfs.addSource(*it);
deba@417:         rdfs.start();
deba@417:         ++compNum;
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
deba@417:   /// \brief Find the strongly connected components of a directed graph
deba@417:   ///
kpeter@648:   /// This function finds the strongly connected components of the given
kpeter@648:   /// directed graph. In addition, the numbering of the components will
kpeter@648:   /// satisfy that there is no arc going from a higher numbered component
kpeter@648:   /// to a lower one (i.e. it provides a topological order of the components).
kpeter@648:   ///
kpeter@648:   /// The strongly connected components are the classes of an
kpeter@648:   /// equivalence relation on the nodes of a digraph. Two nodes are in
kpeter@648:   /// the same class if they are connected with directed paths in both
kpeter@648:   /// direction.
deba@417:   ///
kpeter@586:   /// \image html strongly_connected_components.png
kpeter@586:   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
kpeter@586:   ///
deba@417:   /// \param digraph The digraph.
deba@417:   /// \retval compMap A writable node map. The values will be set from 0 to
deba@417:   /// the number of the strongly connected components minus one. Each value
kpeter@648:   /// of the map will be set exactly once, and the values of a certain
kpeter@648:   /// component will be set continuously.
kpeter@648:   /// \return The number of strongly connected components.
kpeter@648:   /// \note By definition, the empty digraph has zero
kpeter@648:   /// strongly connected components.
kpeter@648:   ///
kpeter@648:   /// \see stronglyConnected(), countStronglyConnectedComponents()
deba@417:   template <typename Digraph, typename NodeMap>
deba@417:   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
deba@417:     checkConcept<concepts::Digraph, Digraph>();
deba@417:     typedef typename Digraph::Node Node;
deba@417:     typedef typename Digraph::NodeIt NodeIt;
deba@417:     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef std::vector<Node> Container;
deba@417:     typedef typename Container::iterator Iterator;
deba@417: 
deba@417:     Container nodes(countNodes(digraph));
deba@417:     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
deba@417:     Visitor visitor(nodes.begin());
deba@417: 
deba@417:     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417:     dfs.init();
deba@417:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417: 
deba@417:     typedef typename Container::reverse_iterator RIterator;
deba@417:     typedef ReverseDigraph<const Digraph> RDigraph;
deba@417: 
deba@417:     RDigraph rdigraph(digraph);
deba@417: 
deba@417:     int compNum = 0;
deba@417: 
deba@417:     typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
deba@417:     RVisitor rvisitor(compMap, compNum);
deba@417: 
deba@417:     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417: 
deba@417:     rdfs.init();
deba@417:     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@417:       if (!rdfs.reached(*it)) {
deba@417:         rdfs.addSource(*it);
deba@417:         rdfs.start();
deba@417:         ++compNum;
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
deba@417:   /// \brief Find the cut arcs of the strongly connected components.
deba@417:   ///
kpeter@648:   /// This function finds the cut arcs of the strongly connected components
kpeter@648:   /// of the given digraph.
kpeter@648:   ///
kpeter@648:   /// The strongly connected components are the classes of an
kpeter@648:   /// equivalence relation on the nodes of a digraph. Two nodes are in
kpeter@648:   /// the same class if they are connected with directed paths in both
kpeter@648:   /// direction.
deba@417:   /// The strongly connected components are separated by the cut arcs.
deba@417:   ///
kpeter@648:   /// \param digraph The digraph.
kpeter@648:   /// \retval cutMap A writable arc map. The values will be set to \c true
kpeter@648:   /// for the cut arcs (exactly once for each cut arc), and will not be
kpeter@648:   /// changed for other arcs.
kpeter@648:   /// \return The number of cut arcs.
deba@417:   ///
kpeter@648:   /// \see stronglyConnected(), stronglyConnectedComponents()
deba@417:   template <typename Digraph, typename ArcMap>
kpeter@648:   int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
deba@417:     checkConcept<concepts::Digraph, Digraph>();
deba@417:     typedef typename Digraph::Node Node;
deba@417:     typedef typename Digraph::Arc Arc;
deba@417:     typedef typename Digraph::NodeIt NodeIt;
deba@417:     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef std::vector<Node> Container;
deba@417:     typedef typename Container::iterator Iterator;
deba@417: 
kpeter@648:     Container nodes(countNodes(digraph));
deba@417:     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
deba@417:     Visitor visitor(nodes.begin());
deba@417: 
kpeter@648:     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417:     dfs.init();
kpeter@648:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417: 
deba@417:     typedef typename Container::reverse_iterator RIterator;
deba@417:     typedef ReverseDigraph<const Digraph> RDigraph;
deba@417: 
kpeter@648:     RDigraph rdigraph(digraph);
deba@417: 
deba@417:     int cutNum = 0;
deba@417: 
deba@419:     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
kpeter@648:     RVisitor rvisitor(rdigraph, cutMap, cutNum);
deba@417: 
kpeter@648:     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417: 
deba@417:     rdfs.init();
deba@417:     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@417:       if (!rdfs.reached(*it)) {
deba@417:         rdfs.addSource(*it);
deba@417:         rdfs.start();
deba@417:       }
deba@417:     }
deba@417:     return cutNum;
deba@417:   }
deba@417: 
deba@419:   namespace _connectivity_bits {
deba@417: 
deba@417:     template <typename Digraph>
deba@417:     class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Edge Edge;
deba@417: 
deba@417:       CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
deba@417:         : _graph(graph), _compNum(compNum),
deba@417:           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _predMap.set(node, INVALID);
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _numMap.set(node, _num);
deba@417:         _retMap.set(node, _num);
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void discover(const Arc& edge) {
deba@417:         _predMap.set(_graph.target(edge), _graph.source(edge));
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& edge) {
deba@417:         if (_graph.source(edge) == _graph.target(edge) &&
deba@417:             _graph.direction(edge)) {
deba@417:           ++_compNum;
deba@417:           return;
deba@417:         }
deba@417:         if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
deba@417:           return;
deba@417:         }
deba@417:         if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void backtrack(const Arc& edge) {
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:         if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@417:           ++_compNum;
deba@417:         }
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       const Digraph& _graph;
deba@417:       int& _compNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _numMap;
deba@417:       typename Digraph::template NodeMap<int> _retMap;
deba@417:       typename Digraph::template NodeMap<Node> _predMap;
deba@417:       int _num;
deba@417:     };
deba@417: 
deba@417:     template <typename Digraph, typename ArcMap>
deba@417:     class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Edge Edge;
deba@417: 
deba@417:       BiNodeConnectedComponentsVisitor(const Digraph& graph,
deba@417:                                        ArcMap& compMap, int &compNum)
deba@417:         : _graph(graph), _compMap(compMap), _compNum(compNum),
deba@417:           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _predMap.set(node, INVALID);
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _numMap.set(node, _num);
deba@417:         _retMap.set(node, _num);
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void discover(const Arc& edge) {
deba@417:         Node target = _graph.target(edge);
deba@417:         _predMap.set(target, edge);
deba@417:         _edgeStack.push(edge);
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& edge) {
deba@417:         Node source = _graph.source(edge);
deba@417:         Node target = _graph.target(edge);
deba@417:         if (source == target && _graph.direction(edge)) {
deba@417:           _compMap.set(edge, _compNum);
deba@417:           ++_compNum;
deba@417:           return;
deba@417:         }
deba@417:         if (_numMap[target] < _numMap[source]) {
deba@417:           if (_predMap[source] != _graph.oppositeArc(edge)) {
deba@417:             _edgeStack.push(edge);
deba@417:           }
deba@417:         }
deba@417:         if (_predMap[source] != INVALID &&
deba@417:             target == _graph.source(_predMap[source])) {
deba@417:           return;
deba@417:         }
deba@417:         if (_retMap[source] > _numMap[target]) {
deba@417:           _retMap.set(source, _numMap[target]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void backtrack(const Arc& edge) {
deba@417:         Node source = _graph.source(edge);
deba@417:         Node target = _graph.target(edge);
deba@417:         if (_retMap[source] > _retMap[target]) {
deba@417:           _retMap.set(source, _retMap[target]);
deba@417:         }
deba@417:         if (_numMap[source] <= _retMap[target]) {
deba@417:           while (_edgeStack.top() != edge) {
deba@417:             _compMap.set(_edgeStack.top(), _compNum);
deba@417:             _edgeStack.pop();
deba@417:           }
deba@417:           _compMap.set(edge, _compNum);
deba@417:           _edgeStack.pop();
deba@417:           ++_compNum;
deba@417:         }
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       const Digraph& _graph;
deba@417:       ArcMap& _compMap;
deba@417:       int& _compNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _numMap;
deba@417:       typename Digraph::template NodeMap<int> _retMap;
deba@417:       typename Digraph::template NodeMap<Arc> _predMap;
deba@417:       std::stack<Edge> _edgeStack;
deba@417:       int _num;
deba@417:     };
deba@417: 
deba@417: 
deba@417:     template <typename Digraph, typename NodeMap>
deba@417:     class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Edge Edge;
deba@417: 
deba@417:       BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
deba@417:                                      int& cutNum)
deba@417:         : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
deba@417:           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _predMap.set(node, INVALID);
deba@417:         rootCut = false;
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _numMap.set(node, _num);
deba@417:         _retMap.set(node, _num);
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void discover(const Arc& edge) {
deba@417:         _predMap.set(_graph.target(edge), _graph.source(edge));
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& edge) {
deba@417:         if (_graph.source(edge) == _graph.target(edge) &&
deba@417:             _graph.direction(edge)) {
deba@417:           if (!_cutMap[_graph.source(edge)]) {
deba@417:             _cutMap.set(_graph.source(edge), true);
deba@417:             ++_cutNum;
deba@417:           }
deba@417:           return;
deba@417:         }
deba@417:         if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
deba@417:         if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void backtrack(const Arc& edge) {
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:         if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@417:           if (_predMap[_graph.source(edge)] != INVALID) {
deba@417:             if (!_cutMap[_graph.source(edge)]) {
deba@417:               _cutMap.set(_graph.source(edge), true);
deba@417:               ++_cutNum;
deba@417:             }
deba@417:           } else if (rootCut) {
deba@417:             if (!_cutMap[_graph.source(edge)]) {
deba@417:               _cutMap.set(_graph.source(edge), true);
deba@417:               ++_cutNum;
deba@417:             }
deba@417:           } else {
deba@417:             rootCut = true;
deba@417:           }
deba@417:         }
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       const Digraph& _graph;
deba@417:       NodeMap& _cutMap;
deba@417:       int& _cutNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _numMap;
deba@417:       typename Digraph::template NodeMap<int> _retMap;
deba@417:       typename Digraph::template NodeMap<Node> _predMap;
deba@417:       std::stack<Edge> _edgeStack;
deba@417:       int _num;
deba@417:       bool rootCut;
deba@417:     };
deba@417: 
deba@417:   }
deba@417: 
deba@417:   template <typename Graph>
deba@417:   int countBiNodeConnectedComponents(const Graph& graph);
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether an undirected graph is bi-node-connected.
deba@417:   ///
deba@1089:   /// This function checks whether the given undirected graph is
deba@1089:   /// bi-node-connected, i.e. a connected graph without articulation
deba@1089:   /// node.
deba@417:   ///
kpeter@648:   /// \return \c true if the graph bi-node-connected.
alpar@1090:   ///
alpar@1090:   /// \note By definition,
alpar@1090:   /// \li a graph consisting of zero or one node is bi-node-connected,
alpar@1090:   /// \li a graph consisting of two isolated nodes
alpar@1090:   /// is \e not bi-node-connected and
alpar@1090:   /// \li a graph consisting of two nodes connected by an edge
alpar@1090:   /// is bi-node-connected.
kpeter@648:   ///
kpeter@648:   /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
deba@417:   template <typename Graph>
deba@417:   bool biNodeConnected(const Graph& graph) {
deba@1089:     bool hasNonIsolated = false, hasIsolated = false;
deba@1089:     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@1089:       if (typename Graph::OutArcIt(graph, n) == INVALID) {
deba@1089:         if (hasIsolated || hasNonIsolated) {
deba@1089:           return false;
deba@1089:         } else {
deba@1089:           hasIsolated = true;
deba@1089:         }
deba@1089:       } else {
deba@1089:         if (hasIsolated) {
deba@1089:           return false;
deba@1089:         } else {
deba@1089:           hasNonIsolated = true;
deba@1089:         }
deba@1089:       }
deba@1089:     }
deba@417:     return countBiNodeConnectedComponents(graph) <= 1;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
alpar@877:   /// \brief Count the number of bi-node-connected components of an
kpeter@648:   /// undirected graph.
deba@417:   ///
kpeter@648:   /// This function counts the number of bi-node-connected components of
kpeter@648:   /// the given undirected graph.
deba@417:   ///
kpeter@648:   /// The bi-node-connected components are the classes of an equivalence
kpeter@648:   /// relation on the edges of a undirected graph. Two edges are in the
kpeter@648:   /// same class if they are on same circle.
kpeter@648:   ///
kpeter@648:   /// \return The number of bi-node-connected components.
kpeter@648:   ///
kpeter@648:   /// \see biNodeConnected(), biNodeConnectedComponents()
deba@417:   template <typename Graph>
deba@417:   int countBiNodeConnectedComponents(const Graph& graph) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
deba@417: 
deba@417:     int compNum = 0;
deba@417:     Visitor visitor(graph, compNum);
deba@417: 
deba@417:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417:     dfs.init();
deba@417: 
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Find the bi-node-connected components of an undirected graph.
deba@417:   ///
kpeter@648:   /// This function finds the bi-node-connected components of the given
kpeter@648:   /// undirected graph.
kpeter@648:   ///
kpeter@648:   /// The bi-node-connected components are the classes of an equivalence
kpeter@648:   /// relation on the edges of a undirected graph. Two edges are in the
kpeter@648:   /// same class if they are on same circle.
deba@417:   ///
kpeter@586:   /// \image html node_biconnected_components.png
kpeter@586:   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
kpeter@586:   ///
kpeter@648:   /// \param graph The undirected graph.
kpeter@648:   /// \retval compMap A writable edge map. The values will be set from 0
kpeter@648:   /// to the number of the bi-node-connected components minus one. Each
alpar@877:   /// value of the map will be set exactly once, and the values of a
kpeter@648:   /// certain component will be set continuously.
kpeter@648:   /// \return The number of bi-node-connected components.
kpeter@648:   ///
kpeter@648:   /// \see biNodeConnected(), countBiNodeConnectedComponents()
deba@417:   template <typename Graph, typename EdgeMap>
deba@417:   int biNodeConnectedComponents(const Graph& graph,
deba@417:                                 EdgeMap& compMap) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::Edge Edge;
deba@417:     checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
deba@417: 
deba@417:     int compNum = 0;
deba@417:     Visitor visitor(graph, compMap, compNum);
deba@417: 
deba@417:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417:     dfs.init();
deba@417: 
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Find the bi-node-connected cut nodes in an undirected graph.
deba@417:   ///
kpeter@648:   /// This function finds the bi-node-connected cut nodes in the given
kpeter@648:   /// undirected graph.
deba@417:   ///
kpeter@648:   /// The bi-node-connected components are the classes of an equivalence
kpeter@648:   /// relation on the edges of a undirected graph. Two edges are in the
kpeter@648:   /// same class if they are on same circle.
kpeter@648:   /// The bi-node-connected components are separted by the cut nodes of
kpeter@648:   /// the components.
kpeter@648:   ///
kpeter@648:   /// \param graph The undirected graph.
alpar@877:   /// \retval cutMap A writable node map. The values will be set to
kpeter@648:   /// \c true for the nodes that separate two or more components
kpeter@648:   /// (exactly once for each cut node), and will not be changed for
kpeter@648:   /// other nodes.
deba@417:   /// \return The number of the cut nodes.
kpeter@648:   ///
kpeter@648:   /// \see biNodeConnected(), biNodeConnectedComponents()
deba@417:   template <typename Graph, typename NodeMap>
deba@417:   int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::Node Node;
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
deba@417: 
deba@417:     int cutNum = 0;
deba@417:     Visitor visitor(graph, cutMap, cutNum);
deba@417: 
deba@417:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417:     dfs.init();
deba@417: 
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:     return cutNum;
deba@417:   }
deba@417: 
deba@419:   namespace _connectivity_bits {
deba@417: 
deba@417:     template <typename Digraph>
deba@417:     class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Edge Edge;
deba@417: 
deba@417:       CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
deba@417:         : _graph(graph), _compNum(compNum),
deba@417:           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _predMap.set(node, INVALID);
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _numMap.set(node, _num);
deba@417:         _retMap.set(node, _num);
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void leave(const Node& node) {
deba@417:         if (_numMap[node] <= _retMap[node]) {
deba@417:           ++_compNum;
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void discover(const Arc& edge) {
deba@417:         _predMap.set(_graph.target(edge), edge);
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& edge) {
deba@417:         if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
deba@417:           return;
deba@417:         }
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void backtrack(const Arc& edge) {
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       const Digraph& _graph;
deba@417:       int& _compNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _numMap;
deba@417:       typename Digraph::template NodeMap<int> _retMap;
deba@417:       typename Digraph::template NodeMap<Arc> _predMap;
deba@417:       int _num;
deba@417:     };
deba@417: 
deba@417:     template <typename Digraph, typename NodeMap>
deba@417:     class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Edge Edge;
deba@417: 
deba@417:       BiEdgeConnectedComponentsVisitor(const Digraph& graph,
deba@417:                                        NodeMap& compMap, int &compNum)
deba@417:         : _graph(graph), _compMap(compMap), _compNum(compNum),
deba@417:           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _predMap.set(node, INVALID);
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _numMap.set(node, _num);
deba@417:         _retMap.set(node, _num);
deba@417:         _nodeStack.push(node);
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void leave(const Node& node) {
deba@417:         if (_numMap[node] <= _retMap[node]) {
deba@417:           while (_nodeStack.top() != node) {
deba@417:             _compMap.set(_nodeStack.top(), _compNum);
deba@417:             _nodeStack.pop();
deba@417:           }
deba@417:           _compMap.set(node, _compNum);
deba@417:           _nodeStack.pop();
deba@417:           ++_compNum;
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void discover(const Arc& edge) {
deba@417:         _predMap.set(_graph.target(edge), edge);
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& edge) {
deba@417:         if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
deba@417:           return;
deba@417:         }
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void backtrack(const Arc& edge) {
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       const Digraph& _graph;
deba@417:       NodeMap& _compMap;
deba@417:       int& _compNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _numMap;
deba@417:       typename Digraph::template NodeMap<int> _retMap;
deba@417:       typename Digraph::template NodeMap<Arc> _predMap;
deba@417:       std::stack<Node> _nodeStack;
deba@417:       int _num;
deba@417:     };
deba@417: 
deba@417: 
deba@417:     template <typename Digraph, typename ArcMap>
deba@417:     class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Edge Edge;
deba@417: 
deba@417:       BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
deba@417:                                      ArcMap& cutMap, int &cutNum)
deba@417:         : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
deba@417:           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _predMap[node] = INVALID;
deba@417:       }
deba@417: 
deba@417:       void reach(const Node& node) {
deba@417:         _numMap.set(node, _num);
deba@417:         _retMap.set(node, _num);
deba@417:         ++_num;
deba@417:       }
deba@417: 
deba@417:       void leave(const Node& node) {
deba@417:         if (_numMap[node] <= _retMap[node]) {
deba@417:           if (_predMap[node] != INVALID) {
deba@417:             _cutMap.set(_predMap[node], true);
deba@417:             ++_cutNum;
deba@417:           }
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void discover(const Arc& edge) {
deba@417:         _predMap.set(_graph.target(edge), edge);
deba@417:       }
deba@417: 
deba@417:       void examine(const Arc& edge) {
deba@417:         if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
deba@417:           return;
deba@417:         }
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:       void backtrack(const Arc& edge) {
deba@417:         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417:           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417:         }
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       const Digraph& _graph;
deba@417:       ArcMap& _cutMap;
deba@417:       int& _cutNum;
deba@417: 
deba@417:       typename Digraph::template NodeMap<int> _numMap;
deba@417:       typename Digraph::template NodeMap<int> _retMap;
deba@417:       typename Digraph::template NodeMap<Arc> _predMap;
deba@417:       int _num;
deba@417:     };
deba@417:   }
deba@417: 
deba@417:   template <typename Graph>
deba@417:   int countBiEdgeConnectedComponents(const Graph& graph);
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether an undirected graph is bi-edge-connected.
deba@417:   ///
alpar@877:   /// This function checks whether the given undirected graph is
kpeter@648:   /// bi-edge-connected, i.e. any two nodes are connected with at least
kpeter@648:   /// two edge-disjoint paths.
deba@417:   ///
kpeter@648:   /// \return \c true if the graph is bi-edge-connected.
kpeter@648:   /// \note By definition, the empty graph is bi-edge-connected.
kpeter@648:   ///
kpeter@648:   /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
deba@417:   template <typename Graph>
deba@417:   bool biEdgeConnected(const Graph& graph) {
deba@417:     return countBiEdgeConnectedComponents(graph) <= 1;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Count the number of bi-edge-connected components of an
kpeter@648:   /// undirected graph.
deba@417:   ///
kpeter@648:   /// This function counts the number of bi-edge-connected components of
kpeter@648:   /// the given undirected graph.
deba@417:   ///
kpeter@648:   /// The bi-edge-connected components are the classes of an equivalence
kpeter@648:   /// relation on the nodes of an undirected graph. Two nodes are in the
kpeter@648:   /// same class if they are connected with at least two edge-disjoint
kpeter@648:   /// paths.
kpeter@648:   ///
kpeter@648:   /// \return The number of bi-edge-connected components.
kpeter@648:   ///
kpeter@648:   /// \see biEdgeConnected(), biEdgeConnectedComponents()
deba@417:   template <typename Graph>
deba@417:   int countBiEdgeConnectedComponents(const Graph& graph) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
deba@417: 
deba@417:     int compNum = 0;
deba@417:     Visitor visitor(graph, compNum);
deba@417: 
deba@417:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417:     dfs.init();
deba@417: 
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Find the bi-edge-connected components of an undirected graph.
deba@417:   ///
kpeter@648:   /// This function finds the bi-edge-connected components of the given
kpeter@648:   /// undirected graph.
kpeter@648:   ///
kpeter@648:   /// The bi-edge-connected components are the classes of an equivalence
kpeter@648:   /// relation on the nodes of an undirected graph. Two nodes are in the
kpeter@648:   /// same class if they are connected with at least two edge-disjoint
kpeter@648:   /// paths.
deba@417:   ///
kpeter@586:   /// \image html edge_biconnected_components.png
kpeter@586:   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
kpeter@586:   ///
kpeter@648:   /// \param graph The undirected graph.
deba@417:   /// \retval compMap A writable node map. The values will be set from 0 to
kpeter@648:   /// the number of the bi-edge-connected components minus one. Each value
kpeter@648:   /// of the map will be set exactly once, and the values of a certain
kpeter@648:   /// component will be set continuously.
kpeter@648:   /// \return The number of bi-edge-connected components.
kpeter@648:   ///
kpeter@648:   /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
deba@417:   template <typename Graph, typename NodeMap>
deba@417:   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::Node Node;
deba@417:     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
deba@417: 
deba@417:     int compNum = 0;
deba@417:     Visitor visitor(graph, compMap, compNum);
deba@417: 
deba@417:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417:     dfs.init();
deba@417: 
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:     return compNum;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Find the bi-edge-connected cut edges in an undirected graph.
deba@417:   ///
kpeter@648:   /// This function finds the bi-edge-connected cut edges in the given
alpar@877:   /// undirected graph.
deba@417:   ///
kpeter@648:   /// The bi-edge-connected components are the classes of an equivalence
kpeter@648:   /// relation on the nodes of an undirected graph. Two nodes are in the
kpeter@648:   /// same class if they are connected with at least two edge-disjoint
kpeter@648:   /// paths.
kpeter@648:   /// The bi-edge-connected components are separted by the cut edges of
kpeter@648:   /// the components.
kpeter@648:   ///
kpeter@648:   /// \param graph The undirected graph.
kpeter@648:   /// \retval cutMap A writable edge map. The values will be set to \c true
kpeter@648:   /// for the cut edges (exactly once for each cut edge), and will not be
kpeter@648:   /// changed for other edges.
deba@417:   /// \return The number of cut edges.
kpeter@648:   ///
kpeter@648:   /// \see biEdgeConnected(), biEdgeConnectedComponents()
deba@417:   template <typename Graph, typename EdgeMap>
deba@417:   int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::Edge Edge;
deba@417:     checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
deba@417: 
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
deba@417: 
deba@417:     int cutNum = 0;
deba@417:     Visitor visitor(graph, cutMap, cutNum);
deba@417: 
deba@417:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417:     dfs.init();
deba@417: 
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:     return cutNum;
deba@417:   }
deba@417: 
deba@417: 
deba@419:   namespace _connectivity_bits {
deba@417: 
deba@417:     template <typename Digraph, typename IntNodeMap>
deba@417:     class TopologicalSortVisitor : public DfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Node Node;
deba@417:       typedef typename Digraph::Arc edge;
deba@417: 
deba@417:       TopologicalSortVisitor(IntNodeMap& order, int num)
deba@417:         : _order(order), _num(num) {}
deba@417: 
deba@417:       void leave(const Node& node) {
deba@417:         _order.set(node, --_num);
deba@417:       }
deba@417: 
deba@417:     private:
deba@417:       IntNodeMap& _order;
deba@417:       int _num;
deba@417:     };
deba@417: 
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether a digraph is DAG.
kpeter@648:   ///
kpeter@648:   /// This function checks whether the given digraph is DAG, i.e.
kpeter@648:   /// \e Directed \e Acyclic \e Graph.
kpeter@648:   /// \return \c true if there is no directed cycle in the digraph.
kpeter@648:   /// \see acyclic()
kpeter@648:   template <typename Digraph>
kpeter@648:   bool dag(const Digraph& digraph) {
kpeter@648: 
kpeter@648:     checkConcept<concepts::Digraph, Digraph>();
kpeter@648: 
kpeter@648:     typedef typename Digraph::Node Node;
kpeter@648:     typedef typename Digraph::NodeIt NodeIt;
kpeter@648:     typedef typename Digraph::Arc Arc;
kpeter@648: 
kpeter@648:     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
kpeter@648: 
kpeter@648:     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
kpeter@648:       Create dfs(digraph);
kpeter@648: 
kpeter@648:     ProcessedMap processed(digraph);
kpeter@648:     dfs.processedMap(processed);
kpeter@648: 
kpeter@648:     dfs.init();
kpeter@648:     for (NodeIt it(digraph); it != INVALID; ++it) {
kpeter@648:       if (!dfs.reached(it)) {
kpeter@648:         dfs.addSource(it);
kpeter@648:         while (!dfs.emptyQueue()) {
kpeter@648:           Arc arc = dfs.nextArc();
kpeter@648:           Node target = digraph.target(arc);
kpeter@648:           if (dfs.reached(target) && !processed[target]) {
kpeter@648:             return false;
kpeter@648:           }
kpeter@648:           dfs.processNextArc();
kpeter@648:         }
kpeter@648:       }
kpeter@648:     }
kpeter@648:     return true;
kpeter@648:   }
kpeter@648: 
kpeter@648:   /// \ingroup graph_properties
kpeter@648:   ///
deba@417:   /// \brief Sort the nodes of a DAG into topolgical order.
deba@417:   ///
kpeter@648:   /// This function sorts the nodes of the given acyclic digraph (DAG)
kpeter@648:   /// into topolgical order.
deba@417:   ///
kpeter@648:   /// \param digraph The digraph, which must be DAG.
deba@417:   /// \retval order A writable node map. The values will be set from 0 to
kpeter@648:   /// the number of the nodes in the digraph minus one. Each value of the
kpeter@648:   /// map will be set exactly once, and the values will be set descending
kpeter@648:   /// order.
deba@417:   ///
kpeter@648:   /// \see dag(), checkedTopologicalSort()
deba@417:   template <typename Digraph, typename NodeMap>
kpeter@648:   void topologicalSort(const Digraph& digraph, NodeMap& order) {
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     checkConcept<concepts::Digraph, Digraph>();
deba@417:     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
deba@417: 
deba@417:     typedef typename Digraph::Node Node;
deba@417:     typedef typename Digraph::NodeIt NodeIt;
deba@417:     typedef typename Digraph::Arc Arc;
deba@417: 
deba@417:     TopologicalSortVisitor<Digraph, NodeMap>
kpeter@648:       visitor(order, countNodes(digraph));
deba@417: 
deba@417:     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
kpeter@648:       dfs(digraph, visitor);
deba@417: 
deba@417:     dfs.init();
kpeter@648:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         dfs.start();
deba@417:       }
deba@417:     }
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
deba@417:   /// \brief Sort the nodes of a DAG into topolgical order.
deba@417:   ///
kpeter@648:   /// This function sorts the nodes of the given acyclic digraph (DAG)
kpeter@648:   /// into topolgical order and also checks whether the given digraph
kpeter@648:   /// is DAG.
deba@417:   ///
kpeter@648:   /// \param digraph The digraph.
kpeter@648:   /// \retval order A readable and writable node map. The values will be
alpar@877:   /// set from 0 to the number of the nodes in the digraph minus one.
kpeter@648:   /// Each value of the map will be set exactly once, and the values will
kpeter@648:   /// be set descending order.
kpeter@648:   /// \return \c false if the digraph is not DAG.
deba@417:   ///
kpeter@648:   /// \see dag(), topologicalSort()
deba@417:   template <typename Digraph, typename NodeMap>
deba@419:   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     checkConcept<concepts::Digraph, Digraph>();
deba@417:     checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
deba@417:       NodeMap>();
deba@417: 
deba@417:     typedef typename Digraph::Node Node;
deba@417:     typedef typename Digraph::NodeIt NodeIt;
deba@417:     typedef typename Digraph::Arc Arc;
deba@417: 
deba@419:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@419:       order.set(it, -1);
deba@419:     }
deba@417: 
deba@417:     TopologicalSortVisitor<Digraph, NodeMap>
deba@419:       visitor(order, countNodes(digraph));
deba@417: 
deba@417:     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
deba@419:       dfs(digraph, visitor);
deba@417: 
deba@417:     dfs.init();
deba@419:     for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         while (!dfs.emptyQueue()) {
deba@419:            Arc arc = dfs.nextArc();
deba@419:            Node target = digraph.target(arc);
deba@417:            if (dfs.reached(target) && order[target] == -1) {
deba@417:              return false;
deba@417:            }
deba@417:            dfs.processNextArc();
deba@417:          }
deba@417:       }
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether an undirected graph is acyclic.
deba@417:   ///
kpeter@648:   /// This function checks whether the given undirected graph is acyclic.
kpeter@648:   /// \return \c true if there is no cycle in the graph.
kpeter@648:   /// \see dag()
deba@417:   template <typename Graph>
deba@417:   bool acyclic(const Graph& graph) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::Node Node;
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::Arc Arc;
deba@417:     Dfs<Graph> dfs(graph);
deba@417:     dfs.init();
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         dfs.addSource(it);
deba@417:         while (!dfs.emptyQueue()) {
kpeter@648:           Arc arc = dfs.nextArc();
kpeter@648:           Node source = graph.source(arc);
kpeter@648:           Node target = graph.target(arc);
deba@417:           if (dfs.reached(target) &&
kpeter@648:               dfs.predArc(source) != graph.oppositeArc(arc)) {
deba@417:             return false;
deba@417:           }
deba@417:           dfs.processNextArc();
deba@417:         }
deba@417:       }
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether an undirected graph is tree.
deba@417:   ///
kpeter@648:   /// This function checks whether the given undirected graph is tree.
kpeter@648:   /// \return \c true if the graph is acyclic and connected.
kpeter@648:   /// \see acyclic(), connected()
deba@417:   template <typename Graph>
deba@417:   bool tree(const Graph& graph) {
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417:     typedef typename Graph::Node Node;
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::Arc Arc;
kpeter@647:     if (NodeIt(graph) == INVALID) return true;
deba@417:     Dfs<Graph> dfs(graph);
deba@417:     dfs.init();
deba@417:     dfs.addSource(NodeIt(graph));
deba@417:     while (!dfs.emptyQueue()) {
kpeter@648:       Arc arc = dfs.nextArc();
kpeter@648:       Node source = graph.source(arc);
kpeter@648:       Node target = graph.target(arc);
deba@417:       if (dfs.reached(target) &&
kpeter@648:           dfs.predArc(source) != graph.oppositeArc(arc)) {
deba@417:         return false;
deba@417:       }
deba@417:       dfs.processNextArc();
deba@417:     }
deba@417:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if (!dfs.reached(it)) {
deba@417:         return false;
deba@417:       }
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
deba@419:   namespace _connectivity_bits {
deba@417: 
deba@417:     template <typename Digraph>
deba@417:     class BipartiteVisitor : public BfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Node Node;
deba@417: 
deba@417:       BipartiteVisitor(const Digraph& graph, bool& bipartite)
deba@417:         : _graph(graph), _part(graph), _bipartite(bipartite) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _part[node] = true;
deba@417:       }
deba@417:       void discover(const Arc& edge) {
deba@417:         _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
deba@417:       }
deba@417:       void examine(const Arc& edge) {
deba@417:         _bipartite = _bipartite &&
deba@417:           _part[_graph.target(edge)] != _part[_graph.source(edge)];
deba@417:       }
deba@417: 
deba@417:     private:
deba@417: 
deba@417:       const Digraph& _graph;
deba@417:       typename Digraph::template NodeMap<bool> _part;
deba@417:       bool& _bipartite;
deba@417:     };
deba@417: 
deba@417:     template <typename Digraph, typename PartMap>
deba@417:     class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
deba@417:     public:
deba@417:       typedef typename Digraph::Arc Arc;
deba@417:       typedef typename Digraph::Node Node;
deba@417: 
deba@417:       BipartitePartitionsVisitor(const Digraph& graph,
deba@417:                                  PartMap& part, bool& bipartite)
deba@417:         : _graph(graph), _part(part), _bipartite(bipartite) {}
deba@417: 
deba@417:       void start(const Node& node) {
deba@417:         _part.set(node, true);
deba@417:       }
deba@417:       void discover(const Arc& edge) {
deba@417:         _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
deba@417:       }
deba@417:       void examine(const Arc& edge) {
deba@417:         _bipartite = _bipartite &&
deba@417:           _part[_graph.target(edge)] != _part[_graph.source(edge)];
deba@417:       }
deba@417: 
deba@417:     private:
deba@417: 
deba@417:       const Digraph& _graph;
deba@417:       PartMap& _part;
deba@417:       bool& _bipartite;
deba@417:     };
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether an undirected graph is bipartite.
deba@417:   ///
kpeter@648:   /// The function checks whether the given undirected graph is bipartite.
kpeter@648:   /// \return \c true if the graph is bipartite.
kpeter@648:   ///
kpeter@648:   /// \see bipartitePartitions()
deba@417:   template<typename Graph>
kpeter@648:   bool bipartite(const Graph &graph){
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     checkConcept<concepts::Graph, Graph>();
deba@417: 
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::ArcIt ArcIt;
deba@417: 
deba@417:     bool bipartite = true;
deba@417: 
deba@417:     BipartiteVisitor<Graph>
deba@417:       visitor(graph, bipartite);
deba@417:     BfsVisit<Graph, BipartiteVisitor<Graph> >
deba@417:       bfs(graph, visitor);
deba@417:     bfs.init();
deba@417:     for(NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if(!bfs.reached(it)){
deba@417:         bfs.addSource(it);
deba@417:         while (!bfs.emptyQueue()) {
deba@417:           bfs.processNextNode();
deba@417:           if (!bipartite) return false;
deba@417:         }
deba@417:       }
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@586:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Find the bipartite partitions of an undirected graph.
deba@417:   ///
kpeter@648:   /// This function checks whether the given undirected graph is bipartite
kpeter@648:   /// and gives back the bipartite partitions.
kpeter@586:   ///
kpeter@586:   /// \image html bipartite_partitions.png
kpeter@586:   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
kpeter@586:   ///
deba@417:   /// \param graph The undirected graph.
kpeter@648:   /// \retval partMap A writable node map of \c bool (or convertible) value
kpeter@648:   /// type. The values will be set to \c true for one component and
kpeter@648:   /// \c false for the other one.
kpeter@648:   /// \return \c true if the graph is bipartite, \c false otherwise.
kpeter@648:   ///
kpeter@648:   /// \see bipartite()
deba@417:   template<typename Graph, typename NodeMap>
kpeter@648:   bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
deba@419:     using namespace _connectivity_bits;
deba@417: 
deba@417:     checkConcept<concepts::Graph, Graph>();
kpeter@648:     checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
deba@417: 
deba@417:     typedef typename Graph::Node Node;
deba@417:     typedef typename Graph::NodeIt NodeIt;
deba@417:     typedef typename Graph::ArcIt ArcIt;
deba@417: 
deba@417:     bool bipartite = true;
deba@417: 
deba@417:     BipartitePartitionsVisitor<Graph, NodeMap>
deba@417:       visitor(graph, partMap, bipartite);
deba@417:     BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
deba@417:       bfs(graph, visitor);
deba@417:     bfs.init();
deba@417:     for(NodeIt it(graph); it != INVALID; ++it) {
deba@417:       if(!bfs.reached(it)){
deba@417:         bfs.addSource(it);
deba@417:         while (!bfs.emptyQueue()) {
deba@417:           bfs.processNextNode();
deba@417:           if (!bipartite) return false;
deba@417:         }
deba@417:       }
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@648:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether the given graph contains no loop arcs/edges.
kpeter@648:   ///
kpeter@648:   /// This function returns \c true if there are no loop arcs/edges in
kpeter@648:   /// the given graph. It works for both directed and undirected graphs.
kpeter@648:   template <typename Graph>
kpeter@648:   bool loopFree(const Graph& graph) {
kpeter@648:     for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
kpeter@648:       if (graph.source(it) == graph.target(it)) return false;
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@648:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether the given graph contains no parallel arcs/edges.
kpeter@648:   ///
kpeter@648:   /// This function returns \c true if there are no parallel arcs/edges in
kpeter@648:   /// the given graph. It works for both directed and undirected graphs.
kpeter@647:   template <typename Graph>
kpeter@647:   bool parallelFree(const Graph& graph) {
kpeter@647:     typename Graph::template NodeMap<int> reached(graph, 0);
kpeter@647:     int cnt = 1;
kpeter@647:     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
kpeter@647:       for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
kpeter@647:         if (reached[graph.target(a)] == cnt) return false;
kpeter@647:         reached[graph.target(a)] = cnt;
deba@417:       }
kpeter@647:       ++cnt;
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
kpeter@648:   /// \ingroup graph_properties
deba@417:   ///
kpeter@648:   /// \brief Check whether the given graph is simple.
kpeter@648:   ///
kpeter@648:   /// This function returns \c true if the given graph is simple, i.e.
kpeter@648:   /// it contains no loop arcs/edges and no parallel arcs/edges.
kpeter@648:   /// The function works for both directed and undirected graphs.
kpeter@648:   /// \see loopFree(), parallelFree()
kpeter@647:   template <typename Graph>
kpeter@647:   bool simpleGraph(const Graph& graph) {
kpeter@647:     typename Graph::template NodeMap<int> reached(graph, 0);
kpeter@647:     int cnt = 1;
kpeter@647:     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
kpeter@647:       reached[n] = cnt;
kpeter@647:       for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
kpeter@647:         if (reached[graph.target(a)] == cnt) return false;
kpeter@647:         reached[graph.target(a)] = cnt;
deba@417:       }
kpeter@647:       ++cnt;
deba@417:     }
deba@417:     return true;
deba@417:   }
deba@417: 
deba@417: } //namespace lemon
deba@417: 
deba@419: #endif //LEMON_CONNECTIVITY_H