lemon/connectivity.h
changeset 878 d6052a9c4e8d
parent 647 dcba640438c7
child 877 141f9c0db4a3
child 1089 552e3d1242c6
equal deleted inserted replaced
6:b2e4d2477e0d 7:ae39c487374b
    40 
    40 
    41 namespace lemon {
    41 namespace lemon {
    42 
    42 
    43   /// \ingroup graph_properties
    43   /// \ingroup graph_properties
    44   ///
    44   ///
    45   /// \brief Check whether the given undirected graph is connected.
    45   /// \brief Check whether an undirected graph is connected.
    46   ///
    46   ///
    47   /// Check whether the given undirected graph is connected.
    47   /// This function checks whether the given undirected graph is connected,
    48   /// \param graph The undirected graph.
    48   /// i.e. there is a path between any two nodes in the graph.
    49   /// \return \c true when there is path between any two nodes in the graph.
    49   ///
       
    50   /// \return \c true if the graph is connected.
    50   /// \note By definition, the empty graph is connected.
    51   /// \note By definition, the empty graph is connected.
       
    52   ///
       
    53   /// \see countConnectedComponents(), connectedComponents()
       
    54   /// \see stronglyConnected()
    51   template <typename Graph>
    55   template <typename Graph>
    52   bool connected(const Graph& graph) {
    56   bool connected(const Graph& graph) {
    53     checkConcept<concepts::Graph, Graph>();
    57     checkConcept<concepts::Graph, Graph>();
    54     typedef typename Graph::NodeIt NodeIt;
    58     typedef typename Graph::NodeIt NodeIt;
    55     if (NodeIt(graph) == INVALID) return true;
    59     if (NodeIt(graph) == INVALID) return true;
    65 
    69 
    66   /// \ingroup graph_properties
    70   /// \ingroup graph_properties
    67   ///
    71   ///
    68   /// \brief Count the number of connected components of an undirected graph
    72   /// \brief Count the number of connected components of an undirected graph
    69   ///
    73   ///
    70   /// Count the number of connected components of an undirected graph
    74   /// This function counts the number of connected components of the given
    71   ///
    75   /// undirected graph.
    72   /// \param graph The graph. It must be undirected.
    76   ///
    73   /// \return The number of components
    77   /// The connected components are the classes of an equivalence relation
       
    78   /// on the nodes of an undirected graph. Two nodes are in the same class
       
    79   /// if they are connected with a path.
       
    80   ///
       
    81   /// \return The number of connected components.
    74   /// \note By definition, the empty graph consists
    82   /// \note By definition, the empty graph consists
    75   /// of zero connected components.
    83   /// of zero connected components.
       
    84   ///
       
    85   /// \see connected(), connectedComponents()
    76   template <typename Graph>
    86   template <typename Graph>
    77   int countConnectedComponents(const Graph &graph) {
    87   int countConnectedComponents(const Graph &graph) {
    78     checkConcept<concepts::Graph, Graph>();
    88     checkConcept<concepts::Graph, Graph>();
    79     typedef typename Graph::Node Node;
    89     typedef typename Graph::Node Node;
    80     typedef typename Graph::Arc Arc;
    90     typedef typename Graph::Arc Arc;
   107 
   117 
   108   /// \ingroup graph_properties
   118   /// \ingroup graph_properties
   109   ///
   119   ///
   110   /// \brief Find the connected components of an undirected graph
   120   /// \brief Find the connected components of an undirected graph
   111   ///
   121   ///
   112   /// Find the connected components of an undirected graph.
   122   /// This function finds the connected components of the given undirected
       
   123   /// graph.
       
   124   ///
       
   125   /// The connected components are the classes of an equivalence relation
       
   126   /// on the nodes of an undirected graph. Two nodes are in the same class
       
   127   /// if they are connected with a path.
   113   ///
   128   ///
   114   /// \image html connected_components.png
   129   /// \image html connected_components.png
   115   /// \image latex connected_components.eps "Connected components" width=\textwidth
   130   /// \image latex connected_components.eps "Connected components" width=\textwidth
   116   ///
   131   ///
   117   /// \param graph The graph. It must be undirected.
   132   /// \param graph The undirected graph.
   118   /// \retval compMap A writable node map. The values will be set from 0 to
   133   /// \retval compMap A writable node map. The values will be set from 0 to
   119   /// the number of the connected components minus one. Each values of the map
   134   /// the number of the connected components minus one. Each value of the map
   120   /// will be set exactly once, the values of a certain component will be
   135   /// will be set exactly once, and the values of a certain component will be
   121   /// set continuously.
   136   /// set continuously.
   122   /// \return The number of components
   137   /// \return The number of connected components.
       
   138   /// \note By definition, the empty graph consists
       
   139   /// of zero connected components.
       
   140   ///
       
   141   /// \see connected(), countConnectedComponents()
   123   template <class Graph, class NodeMap>
   142   template <class Graph, class NodeMap>
   124   int connectedComponents(const Graph &graph, NodeMap &compMap) {
   143   int connectedComponents(const Graph &graph, NodeMap &compMap) {
   125     checkConcept<concepts::Graph, Graph>();
   144     checkConcept<concepts::Graph, Graph>();
   126     typedef typename Graph::Node Node;
   145     typedef typename Graph::Node Node;
   127     typedef typename Graph::Arc Arc;
   146     typedef typename Graph::Arc Arc;
   229   }
   248   }
   230 
   249 
   231 
   250 
   232   /// \ingroup graph_properties
   251   /// \ingroup graph_properties
   233   ///
   252   ///
   234   /// \brief Check whether the given directed graph is strongly connected.
   253   /// \brief Check whether a directed graph is strongly connected.
   235   ///
   254   ///
   236   /// Check whether the given directed graph is strongly connected. The
   255   /// This function checks whether the given directed graph is strongly
   237   /// graph is strongly connected when any two nodes of the graph are
   256   /// connected, i.e. any two nodes of the digraph are
   238   /// connected with directed paths in both direction.
   257   /// connected with directed paths in both direction.
   239   /// \return \c false when the graph is not strongly connected.
   258   ///
   240   /// \see connected
   259   /// \return \c true if the digraph is strongly connected.
   241   ///
   260   /// \note By definition, the empty digraph is strongly connected.
   242   /// \note By definition, the empty graph is strongly connected.
   261   /// 
       
   262   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
       
   263   /// \see connected()
   243   template <typename Digraph>
   264   template <typename Digraph>
   244   bool stronglyConnected(const Digraph& digraph) {
   265   bool stronglyConnected(const Digraph& digraph) {
   245     checkConcept<concepts::Digraph, Digraph>();
   266     checkConcept<concepts::Digraph, Digraph>();
   246 
   267 
   247     typedef typename Digraph::Node Node;
   268     typedef typename Digraph::Node Node;
   268 
   289 
   269     typedef ReverseDigraph<const Digraph> RDigraph;
   290     typedef ReverseDigraph<const Digraph> RDigraph;
   270     typedef typename RDigraph::NodeIt RNodeIt;
   291     typedef typename RDigraph::NodeIt RNodeIt;
   271     RDigraph rdigraph(digraph);
   292     RDigraph rdigraph(digraph);
   272 
   293 
   273     typedef DfsVisitor<Digraph> RVisitor;
   294     typedef DfsVisitor<RDigraph> RVisitor;
   274     RVisitor rvisitor;
   295     RVisitor rvisitor;
   275 
   296 
   276     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   297     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   277     rdfs.init();
   298     rdfs.init();
   278     rdfs.addSource(source);
   299     rdfs.addSource(source);
   287     return true;
   308     return true;
   288   }
   309   }
   289 
   310 
   290   /// \ingroup graph_properties
   311   /// \ingroup graph_properties
   291   ///
   312   ///
   292   /// \brief Count the strongly connected components of a directed graph
   313   /// \brief Count the number of strongly connected components of a 
   293   ///
   314   /// directed graph
   294   /// Count the strongly connected components of a directed graph.
   315   ///
       
   316   /// This function counts the number of strongly connected components of
       
   317   /// the given directed graph.
       
   318   ///
   295   /// The strongly connected components are the classes of an
   319   /// The strongly connected components are the classes of an
   296   /// equivalence relation on the nodes of the graph. Two nodes are in
   320   /// equivalence relation on the nodes of a digraph. Two nodes are in
   297   /// the same class if they are connected with directed paths in both
   321   /// the same class if they are connected with directed paths in both
   298   /// direction.
   322   /// direction.
   299   ///
   323   ///
   300   /// \param digraph The graph.
   324   /// \return The number of strongly connected components.
   301   /// \return The number of components
   325   /// \note By definition, the empty digraph has zero
   302   /// \note By definition, the empty graph has zero
       
   303   /// strongly connected components.
   326   /// strongly connected components.
       
   327   ///
       
   328   /// \see stronglyConnected(), stronglyConnectedComponents()
   304   template <typename Digraph>
   329   template <typename Digraph>
   305   int countStronglyConnectedComponents(const Digraph& digraph) {
   330   int countStronglyConnectedComponents(const Digraph& digraph) {
   306     checkConcept<concepts::Digraph, Digraph>();
   331     checkConcept<concepts::Digraph, Digraph>();
   307 
   332 
   308     using namespace _connectivity_bits;
   333     using namespace _connectivity_bits;
   353 
   378 
   354   /// \ingroup graph_properties
   379   /// \ingroup graph_properties
   355   ///
   380   ///
   356   /// \brief Find the strongly connected components of a directed graph
   381   /// \brief Find the strongly connected components of a directed graph
   357   ///
   382   ///
   358   /// Find the strongly connected components of a directed graph.  The
   383   /// This function finds the strongly connected components of the given
   359   /// strongly connected components are the classes of an equivalence
   384   /// directed graph. In addition, the numbering of the components will
   360   /// relation on the nodes of the graph. Two nodes are in
   385   /// satisfy that there is no arc going from a higher numbered component
   361   /// relationship when there are directed paths between them in both
   386   /// to a lower one (i.e. it provides a topological order of the components).
   362   /// direction. In addition, the numbering of components will satisfy
   387   ///
   363   /// that there is no arc going from a higher numbered component to
   388   /// The strongly connected components are the classes of an
   364   /// a lower.
   389   /// equivalence relation on the nodes of a digraph. Two nodes are in
       
   390   /// the same class if they are connected with directed paths in both
       
   391   /// direction.
   365   ///
   392   ///
   366   /// \image html strongly_connected_components.png
   393   /// \image html strongly_connected_components.png
   367   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
   394   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
   368   ///
   395   ///
   369   /// \param digraph The digraph.
   396   /// \param digraph The digraph.
   370   /// \retval compMap A writable node map. The values will be set from 0 to
   397   /// \retval compMap A writable node map. The values will be set from 0 to
   371   /// the number of the strongly connected components minus one. Each value
   398   /// the number of the strongly connected components minus one. Each value
   372   /// of the map will be set exactly once, the values of a certain component
   399   /// of the map will be set exactly once, and the values of a certain
   373   /// will be set continuously.
   400   /// component will be set continuously.
   374   /// \return The number of components
   401   /// \return The number of strongly connected components.
       
   402   /// \note By definition, the empty digraph has zero
       
   403   /// strongly connected components.
       
   404   ///
       
   405   /// \see stronglyConnected(), countStronglyConnectedComponents()
   375   template <typename Digraph, typename NodeMap>
   406   template <typename Digraph, typename NodeMap>
   376   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
   407   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
   377     checkConcept<concepts::Digraph, Digraph>();
   408     checkConcept<concepts::Digraph, Digraph>();
   378     typedef typename Digraph::Node Node;
   409     typedef typename Digraph::Node Node;
   379     typedef typename Digraph::NodeIt NodeIt;
   410     typedef typename Digraph::NodeIt NodeIt;
   422 
   453 
   423   /// \ingroup graph_properties
   454   /// \ingroup graph_properties
   424   ///
   455   ///
   425   /// \brief Find the cut arcs of the strongly connected components.
   456   /// \brief Find the cut arcs of the strongly connected components.
   426   ///
   457   ///
   427   /// Find the cut arcs of the strongly connected components.
   458   /// This function finds the cut arcs of the strongly connected components
   428   /// The strongly connected components are the classes of an equivalence
   459   /// of the given digraph.
   429   /// relation on the nodes of the graph. Two nodes are in relationship
   460   ///
   430   /// when there are directed paths between them in both direction.
   461   /// The strongly connected components are the classes of an
       
   462   /// equivalence relation on the nodes of a digraph. Two nodes are in
       
   463   /// the same class if they are connected with directed paths in both
       
   464   /// direction.
   431   /// The strongly connected components are separated by the cut arcs.
   465   /// The strongly connected components are separated by the cut arcs.
   432   ///
   466   ///
   433   /// \param graph The graph.
   467   /// \param digraph The digraph.
   434   /// \retval cutMap A writable node map. The values will be set true when the
   468   /// \retval cutMap A writable arc map. The values will be set to \c true
   435   /// arc is a cut arc.
   469   /// for the cut arcs (exactly once for each cut arc), and will not be
   436   ///
   470   /// changed for other arcs.
   437   /// \return The number of cut arcs
   471   /// \return The number of cut arcs.
       
   472   ///
       
   473   /// \see stronglyConnected(), stronglyConnectedComponents()
   438   template <typename Digraph, typename ArcMap>
   474   template <typename Digraph, typename ArcMap>
   439   int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
   475   int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
   440     checkConcept<concepts::Digraph, Digraph>();
   476     checkConcept<concepts::Digraph, Digraph>();
   441     typedef typename Digraph::Node Node;
   477     typedef typename Digraph::Node Node;
   442     typedef typename Digraph::Arc Arc;
   478     typedef typename Digraph::Arc Arc;
   443     typedef typename Digraph::NodeIt NodeIt;
   479     typedef typename Digraph::NodeIt NodeIt;
   444     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
   480     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
   446     using namespace _connectivity_bits;
   482     using namespace _connectivity_bits;
   447 
   483 
   448     typedef std::vector<Node> Container;
   484     typedef std::vector<Node> Container;
   449     typedef typename Container::iterator Iterator;
   485     typedef typename Container::iterator Iterator;
   450 
   486 
   451     Container nodes(countNodes(graph));
   487     Container nodes(countNodes(digraph));
   452     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   488     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   453     Visitor visitor(nodes.begin());
   489     Visitor visitor(nodes.begin());
   454 
   490 
   455     DfsVisit<Digraph, Visitor> dfs(graph, visitor);
   491     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   456     dfs.init();
   492     dfs.init();
   457     for (NodeIt it(graph); it != INVALID; ++it) {
   493     for (NodeIt it(digraph); it != INVALID; ++it) {
   458       if (!dfs.reached(it)) {
   494       if (!dfs.reached(it)) {
   459         dfs.addSource(it);
   495         dfs.addSource(it);
   460         dfs.start();
   496         dfs.start();
   461       }
   497       }
   462     }
   498     }
   463 
   499 
   464     typedef typename Container::reverse_iterator RIterator;
   500     typedef typename Container::reverse_iterator RIterator;
   465     typedef ReverseDigraph<const Digraph> RDigraph;
   501     typedef ReverseDigraph<const Digraph> RDigraph;
   466 
   502 
   467     RDigraph rgraph(graph);
   503     RDigraph rdigraph(digraph);
   468 
   504 
   469     int cutNum = 0;
   505     int cutNum = 0;
   470 
   506 
   471     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
   507     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
   472     RVisitor rvisitor(rgraph, cutMap, cutNum);
   508     RVisitor rvisitor(rdigraph, cutMap, cutNum);
   473 
   509 
   474     DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
   510     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   475 
   511 
   476     rdfs.init();
   512     rdfs.init();
   477     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   513     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   478       if (!rdfs.reached(*it)) {
   514       if (!rdfs.reached(*it)) {
   479         rdfs.addSource(*it);
   515         rdfs.addSource(*it);
   704   template <typename Graph>
   740   template <typename Graph>
   705   int countBiNodeConnectedComponents(const Graph& graph);
   741   int countBiNodeConnectedComponents(const Graph& graph);
   706 
   742 
   707   /// \ingroup graph_properties
   743   /// \ingroup graph_properties
   708   ///
   744   ///
   709   /// \brief Checks the graph is bi-node-connected.
   745   /// \brief Check whether an undirected graph is bi-node-connected.
   710   ///
   746   ///
   711   /// This function checks that the undirected graph is bi-node-connected
   747   /// This function checks whether the given undirected graph is 
   712   /// graph. The graph is bi-node-connected if any two undirected edge is
   748   /// bi-node-connected, i.e. any two edges are on same circle.
   713   /// on same circle.
   749   ///
   714   ///
   750   /// \return \c true if the graph bi-node-connected.
   715   /// \param graph The graph.
   751   /// \note By definition, the empty graph is bi-node-connected.
   716   /// \return \c true when the graph bi-node-connected.
   752   ///
       
   753   /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
   717   template <typename Graph>
   754   template <typename Graph>
   718   bool biNodeConnected(const Graph& graph) {
   755   bool biNodeConnected(const Graph& graph) {
   719     return countBiNodeConnectedComponents(graph) <= 1;
   756     return countBiNodeConnectedComponents(graph) <= 1;
   720   }
   757   }
   721 
   758 
   722   /// \ingroup graph_properties
   759   /// \ingroup graph_properties
   723   ///
   760   ///
   724   /// \brief Count the biconnected components.
   761   /// \brief Count the number of bi-node-connected components of an 
   725   ///
   762   /// undirected graph.
   726   /// This function finds the bi-node-connected components in an undirected
   763   ///
   727   /// graph. The biconnected components are the classes of an equivalence
   764   /// This function counts the number of bi-node-connected components of
   728   /// relation on the undirected edges. Two undirected edge is in relationship
   765   /// the given undirected graph.
   729   /// when they are on same circle.
   766   ///
   730   ///
   767   /// The bi-node-connected components are the classes of an equivalence
   731   /// \param graph The graph.
   768   /// relation on the edges of a undirected graph. Two edges are in the
   732   /// \return The number of components.
   769   /// same class if they are on same circle.
       
   770   ///
       
   771   /// \return The number of bi-node-connected components.
       
   772   ///
       
   773   /// \see biNodeConnected(), biNodeConnectedComponents()
   733   template <typename Graph>
   774   template <typename Graph>
   734   int countBiNodeConnectedComponents(const Graph& graph) {
   775   int countBiNodeConnectedComponents(const Graph& graph) {
   735     checkConcept<concepts::Graph, Graph>();
   776     checkConcept<concepts::Graph, Graph>();
   736     typedef typename Graph::NodeIt NodeIt;
   777     typedef typename Graph::NodeIt NodeIt;
   737 
   778 
   754     return compNum;
   795     return compNum;
   755   }
   796   }
   756 
   797 
   757   /// \ingroup graph_properties
   798   /// \ingroup graph_properties
   758   ///
   799   ///
   759   /// \brief Find the bi-node-connected components.
   800   /// \brief Find the bi-node-connected components of an undirected graph.
   760   ///
   801   ///
   761   /// This function finds the bi-node-connected components in an undirected
   802   /// This function finds the bi-node-connected components of the given
   762   /// graph. The bi-node-connected components are the classes of an equivalence
   803   /// undirected graph.
   763   /// relation on the undirected edges. Two undirected edge are in relationship
   804   ///
   764   /// when they are on same circle.
   805   /// The bi-node-connected components are the classes of an equivalence
       
   806   /// relation on the edges of a undirected graph. Two edges are in the
       
   807   /// same class if they are on same circle.
   765   ///
   808   ///
   766   /// \image html node_biconnected_components.png
   809   /// \image html node_biconnected_components.png
   767   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   810   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   768   ///
   811   ///
   769   /// \param graph The graph.
   812   /// \param graph The undirected graph.
   770   /// \retval compMap A writable uedge map. The values will be set from 0
   813   /// \retval compMap A writable edge map. The values will be set from 0
   771   /// to the number of the biconnected components minus one. Each values
   814   /// to the number of the bi-node-connected components minus one. Each
   772   /// of the map will be set exactly once, the values of a certain component
   815   /// value of the map will be set exactly once, and the values of a 
   773   /// will be set continuously.
   816   /// certain component will be set continuously.
   774   /// \return The number of components.
   817   /// \return The number of bi-node-connected components.
       
   818   ///
       
   819   /// \see biNodeConnected(), countBiNodeConnectedComponents()
   775   template <typename Graph, typename EdgeMap>
   820   template <typename Graph, typename EdgeMap>
   776   int biNodeConnectedComponents(const Graph& graph,
   821   int biNodeConnectedComponents(const Graph& graph,
   777                                 EdgeMap& compMap) {
   822                                 EdgeMap& compMap) {
   778     checkConcept<concepts::Graph, Graph>();
   823     checkConcept<concepts::Graph, Graph>();
   779     typedef typename Graph::NodeIt NodeIt;
   824     typedef typename Graph::NodeIt NodeIt;
   799     return compNum;
   844     return compNum;
   800   }
   845   }
   801 
   846 
   802   /// \ingroup graph_properties
   847   /// \ingroup graph_properties
   803   ///
   848   ///
   804   /// \brief Find the bi-node-connected cut nodes.
   849   /// \brief Find the bi-node-connected cut nodes in an undirected graph.
   805   ///
   850   ///
   806   /// This function finds the bi-node-connected cut nodes in an undirected
   851   /// This function finds the bi-node-connected cut nodes in the given
   807   /// graph. The bi-node-connected components are the classes of an equivalence
   852   /// undirected graph.
   808   /// relation on the undirected edges. Two undirected edges are in
   853   ///
   809   /// relationship when they are on same circle. The biconnected components
   854   /// The bi-node-connected components are the classes of an equivalence
   810   /// are separted by nodes which are the cut nodes of the components.
   855   /// relation on the edges of a undirected graph. Two edges are in the
   811   ///
   856   /// same class if they are on same circle.
   812   /// \param graph The graph.
   857   /// The bi-node-connected components are separted by the cut nodes of
   813   /// \retval cutMap A writable edge map. The values will be set true when
   858   /// the components.
   814   /// the node separate two or more components.
   859   ///
       
   860   /// \param graph The undirected graph.
       
   861   /// \retval cutMap A writable node map. The values will be set to 
       
   862   /// \c true for the nodes that separate two or more components
       
   863   /// (exactly once for each cut node), and will not be changed for
       
   864   /// other nodes.
   815   /// \return The number of the cut nodes.
   865   /// \return The number of the cut nodes.
       
   866   ///
       
   867   /// \see biNodeConnected(), biNodeConnectedComponents()
   816   template <typename Graph, typename NodeMap>
   868   template <typename Graph, typename NodeMap>
   817   int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
   869   int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
   818     checkConcept<concepts::Graph, Graph>();
   870     checkConcept<concepts::Graph, Graph>();
   819     typedef typename Graph::Node Node;
   871     typedef typename Graph::Node Node;
   820     typedef typename Graph::NodeIt NodeIt;
   872     typedef typename Graph::NodeIt NodeIt;
  1029   template <typename Graph>
  1081   template <typename Graph>
  1030   int countBiEdgeConnectedComponents(const Graph& graph);
  1082   int countBiEdgeConnectedComponents(const Graph& graph);
  1031 
  1083 
  1032   /// \ingroup graph_properties
  1084   /// \ingroup graph_properties
  1033   ///
  1085   ///
  1034   /// \brief Checks that the graph is bi-edge-connected.
  1086   /// \brief Check whether an undirected graph is bi-edge-connected.
  1035   ///
  1087   ///
  1036   /// This function checks that the graph is bi-edge-connected. The undirected
  1088   /// This function checks whether the given undirected graph is 
  1037   /// graph is bi-edge-connected when any two nodes are connected with two
  1089   /// bi-edge-connected, i.e. any two nodes are connected with at least
  1038   /// edge-disjoint paths.
  1090   /// two edge-disjoint paths.
  1039   ///
  1091   ///
  1040   /// \param graph The undirected graph.
  1092   /// \return \c true if the graph is bi-edge-connected.
  1041   /// \return The number of components.
  1093   /// \note By definition, the empty graph is bi-edge-connected.
       
  1094   ///
       
  1095   /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
  1042   template <typename Graph>
  1096   template <typename Graph>
  1043   bool biEdgeConnected(const Graph& graph) {
  1097   bool biEdgeConnected(const Graph& graph) {
  1044     return countBiEdgeConnectedComponents(graph) <= 1;
  1098     return countBiEdgeConnectedComponents(graph) <= 1;
  1045   }
  1099   }
  1046 
  1100 
  1047   /// \ingroup graph_properties
  1101   /// \ingroup graph_properties
  1048   ///
  1102   ///
  1049   /// \brief Count the bi-edge-connected components.
  1103   /// \brief Count the number of bi-edge-connected components of an
  1050   ///
  1104   /// undirected graph.
  1051   /// This function count the bi-edge-connected components in an undirected
  1105   ///
  1052   /// graph. The bi-edge-connected components are the classes of an equivalence
  1106   /// This function counts the number of bi-edge-connected components of
  1053   /// relation on the nodes. Two nodes are in relationship when they are
  1107   /// the given undirected graph.
  1054   /// connected with at least two edge-disjoint paths.
  1108   ///
  1055   ///
  1109   /// The bi-edge-connected components are the classes of an equivalence
  1056   /// \param graph The undirected graph.
  1110   /// relation on the nodes of an undirected graph. Two nodes are in the
  1057   /// \return The number of components.
  1111   /// same class if they are connected with at least two edge-disjoint
       
  1112   /// paths.
       
  1113   ///
       
  1114   /// \return The number of bi-edge-connected components.
       
  1115   ///
       
  1116   /// \see biEdgeConnected(), biEdgeConnectedComponents()
  1058   template <typename Graph>
  1117   template <typename Graph>
  1059   int countBiEdgeConnectedComponents(const Graph& graph) {
  1118   int countBiEdgeConnectedComponents(const Graph& graph) {
  1060     checkConcept<concepts::Graph, Graph>();
  1119     checkConcept<concepts::Graph, Graph>();
  1061     typedef typename Graph::NodeIt NodeIt;
  1120     typedef typename Graph::NodeIt NodeIt;
  1062 
  1121 
  1079     return compNum;
  1138     return compNum;
  1080   }
  1139   }
  1081 
  1140 
  1082   /// \ingroup graph_properties
  1141   /// \ingroup graph_properties
  1083   ///
  1142   ///
  1084   /// \brief Find the bi-edge-connected components.
  1143   /// \brief Find the bi-edge-connected components of an undirected graph.
  1085   ///
  1144   ///
  1086   /// This function finds the bi-edge-connected components in an undirected
  1145   /// This function finds the bi-edge-connected components of the given
  1087   /// graph. The bi-edge-connected components are the classes of an equivalence
  1146   /// undirected graph.
  1088   /// relation on the nodes. Two nodes are in relationship when they are
  1147   ///
  1089   /// connected at least two edge-disjoint paths.
  1148   /// The bi-edge-connected components are the classes of an equivalence
       
  1149   /// relation on the nodes of an undirected graph. Two nodes are in the
       
  1150   /// same class if they are connected with at least two edge-disjoint
       
  1151   /// paths.
  1090   ///
  1152   ///
  1091   /// \image html edge_biconnected_components.png
  1153   /// \image html edge_biconnected_components.png
  1092   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
  1154   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
  1093   ///
  1155   ///
  1094   /// \param graph The graph.
  1156   /// \param graph The undirected graph.
  1095   /// \retval compMap A writable node map. The values will be set from 0 to
  1157   /// \retval compMap A writable node map. The values will be set from 0 to
  1096   /// the number of the biconnected components minus one. Each values
  1158   /// the number of the bi-edge-connected components minus one. Each value
  1097   /// of the map will be set exactly once, the values of a certain component
  1159   /// of the map will be set exactly once, and the values of a certain
  1098   /// will be set continuously.
  1160   /// component will be set continuously.
  1099   /// \return The number of components.
  1161   /// \return The number of bi-edge-connected components.
       
  1162   ///
       
  1163   /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
  1100   template <typename Graph, typename NodeMap>
  1164   template <typename Graph, typename NodeMap>
  1101   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
  1165   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
  1102     checkConcept<concepts::Graph, Graph>();
  1166     checkConcept<concepts::Graph, Graph>();
  1103     typedef typename Graph::NodeIt NodeIt;
  1167     typedef typename Graph::NodeIt NodeIt;
  1104     typedef typename Graph::Node Node;
  1168     typedef typename Graph::Node Node;
  1123     return compNum;
  1187     return compNum;
  1124   }
  1188   }
  1125 
  1189 
  1126   /// \ingroup graph_properties
  1190   /// \ingroup graph_properties
  1127   ///
  1191   ///
  1128   /// \brief Find the bi-edge-connected cut edges.
  1192   /// \brief Find the bi-edge-connected cut edges in an undirected graph.
  1129   ///
  1193   ///
  1130   /// This function finds the bi-edge-connected components in an undirected
  1194   /// This function finds the bi-edge-connected cut edges in the given
  1131   /// graph. The bi-edge-connected components are the classes of an equivalence
  1195   /// undirected graph. 
  1132   /// relation on the nodes. Two nodes are in relationship when they are
  1196   ///
  1133   /// connected with at least two edge-disjoint paths. The bi-edge-connected
  1197   /// The bi-edge-connected components are the classes of an equivalence
  1134   /// components are separted by edges which are the cut edges of the
  1198   /// relation on the nodes of an undirected graph. Two nodes are in the
  1135   /// components.
  1199   /// same class if they are connected with at least two edge-disjoint
  1136   ///
  1200   /// paths.
  1137   /// \param graph The graph.
  1201   /// The bi-edge-connected components are separted by the cut edges of
  1138   /// \retval cutMap A writable node map. The values will be set true when the
  1202   /// the components.
  1139   /// edge is a cut edge.
  1203   ///
       
  1204   /// \param graph The undirected graph.
       
  1205   /// \retval cutMap A writable edge map. The values will be set to \c true
       
  1206   /// for the cut edges (exactly once for each cut edge), and will not be
       
  1207   /// changed for other edges.
  1140   /// \return The number of cut edges.
  1208   /// \return The number of cut edges.
       
  1209   ///
       
  1210   /// \see biEdgeConnected(), biEdgeConnectedComponents()
  1141   template <typename Graph, typename EdgeMap>
  1211   template <typename Graph, typename EdgeMap>
  1142   int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
  1212   int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
  1143     checkConcept<concepts::Graph, Graph>();
  1213     checkConcept<concepts::Graph, Graph>();
  1144     typedef typename Graph::NodeIt NodeIt;
  1214     typedef typename Graph::NodeIt NodeIt;
  1145     typedef typename Graph::Edge Edge;
  1215     typedef typename Graph::Edge Edge;
  1187 
  1257 
  1188   }
  1258   }
  1189 
  1259 
  1190   /// \ingroup graph_properties
  1260   /// \ingroup graph_properties
  1191   ///
  1261   ///
  1192   /// \brief Sort the nodes of a DAG into topolgical order.
  1262   /// \brief Check whether a digraph is DAG.
  1193   ///
  1263   ///
  1194   /// Sort the nodes of a DAG into topolgical order.
  1264   /// This function checks whether the given digraph is DAG, i.e.
  1195   ///
  1265   /// \e Directed \e Acyclic \e Graph.
  1196   /// \param graph The graph. It must be directed and acyclic.
  1266   /// \return \c true if there is no directed cycle in the digraph.
  1197   /// \retval order A writable node map. The values will be set from 0 to
  1267   /// \see acyclic()
  1198   /// the number of the nodes in the graph minus one. Each values of the map
  1268   template <typename Digraph>
  1199   /// will be set exactly once, the values  will be set descending order.
  1269   bool dag(const Digraph& digraph) {
  1200   ///
       
  1201   /// \see checkedTopologicalSort
       
  1202   /// \see dag
       
  1203   template <typename Digraph, typename NodeMap>
       
  1204   void topologicalSort(const Digraph& graph, NodeMap& order) {
       
  1205     using namespace _connectivity_bits;
       
  1206 
  1270 
  1207     checkConcept<concepts::Digraph, Digraph>();
  1271     checkConcept<concepts::Digraph, Digraph>();
  1208     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
       
  1209 
  1272 
  1210     typedef typename Digraph::Node Node;
  1273     typedef typename Digraph::Node Node;
  1211     typedef typename Digraph::NodeIt NodeIt;
  1274     typedef typename Digraph::NodeIt NodeIt;
  1212     typedef typename Digraph::Arc Arc;
  1275     typedef typename Digraph::Arc Arc;
  1213 
  1276 
       
  1277     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       
  1278 
       
  1279     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
       
  1280       Create dfs(digraph);
       
  1281 
       
  1282     ProcessedMap processed(digraph);
       
  1283     dfs.processedMap(processed);
       
  1284 
       
  1285     dfs.init();
       
  1286     for (NodeIt it(digraph); it != INVALID; ++it) {
       
  1287       if (!dfs.reached(it)) {
       
  1288         dfs.addSource(it);
       
  1289         while (!dfs.emptyQueue()) {
       
  1290           Arc arc = dfs.nextArc();
       
  1291           Node target = digraph.target(arc);
       
  1292           if (dfs.reached(target) && !processed[target]) {
       
  1293             return false;
       
  1294           }
       
  1295           dfs.processNextArc();
       
  1296         }
       
  1297       }
       
  1298     }
       
  1299     return true;
       
  1300   }
       
  1301 
       
  1302   /// \ingroup graph_properties
       
  1303   ///
       
  1304   /// \brief Sort the nodes of a DAG into topolgical order.
       
  1305   ///
       
  1306   /// This function sorts the nodes of the given acyclic digraph (DAG)
       
  1307   /// into topolgical order.
       
  1308   ///
       
  1309   /// \param digraph The digraph, which must be DAG.
       
  1310   /// \retval order A writable node map. The values will be set from 0 to
       
  1311   /// the number of the nodes in the digraph minus one. Each value of the
       
  1312   /// map will be set exactly once, and the values will be set descending
       
  1313   /// order.
       
  1314   ///
       
  1315   /// \see dag(), checkedTopologicalSort()
       
  1316   template <typename Digraph, typename NodeMap>
       
  1317   void topologicalSort(const Digraph& digraph, NodeMap& order) {
       
  1318     using namespace _connectivity_bits;
       
  1319 
       
  1320     checkConcept<concepts::Digraph, Digraph>();
       
  1321     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
       
  1322 
       
  1323     typedef typename Digraph::Node Node;
       
  1324     typedef typename Digraph::NodeIt NodeIt;
       
  1325     typedef typename Digraph::Arc Arc;
       
  1326 
  1214     TopologicalSortVisitor<Digraph, NodeMap>
  1327     TopologicalSortVisitor<Digraph, NodeMap>
  1215       visitor(order, countNodes(graph));
  1328       visitor(order, countNodes(digraph));
  1216 
  1329 
  1217     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1330     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1218       dfs(graph, visitor);
  1331       dfs(digraph, visitor);
  1219 
  1332 
  1220     dfs.init();
  1333     dfs.init();
  1221     for (NodeIt it(graph); it != INVALID; ++it) {
  1334     for (NodeIt it(digraph); it != INVALID; ++it) {
  1222       if (!dfs.reached(it)) {
  1335       if (!dfs.reached(it)) {
  1223         dfs.addSource(it);
  1336         dfs.addSource(it);
  1224         dfs.start();
  1337         dfs.start();
  1225       }
  1338       }
  1226     }
  1339     }
  1228 
  1341 
  1229   /// \ingroup graph_properties
  1342   /// \ingroup graph_properties
  1230   ///
  1343   ///
  1231   /// \brief Sort the nodes of a DAG into topolgical order.
  1344   /// \brief Sort the nodes of a DAG into topolgical order.
  1232   ///
  1345   ///
  1233   /// Sort the nodes of a DAG into topolgical order. It also checks
  1346   /// This function sorts the nodes of the given acyclic digraph (DAG)
  1234   /// that the given graph is DAG.
  1347   /// into topolgical order and also checks whether the given digraph
  1235   ///
  1348   /// is DAG.
  1236   /// \param digraph The graph. It must be directed and acyclic.
  1349   ///
  1237   /// \retval order A readable - writable node map. The values will be set
  1350   /// \param digraph The digraph.
  1238   /// from 0 to the number of the nodes in the graph minus one. Each values
  1351   /// \retval order A readable and writable node map. The values will be
  1239   /// of the map will be set exactly once, the values will be set descending
  1352   /// set from 0 to the number of the nodes in the digraph minus one. 
  1240   /// order.
  1353   /// Each value of the map will be set exactly once, and the values will
  1241   /// \return \c false when the graph is not DAG.
  1354   /// be set descending order.
  1242   ///
  1355   /// \return \c false if the digraph is not DAG.
  1243   /// \see topologicalSort
  1356   ///
  1244   /// \see dag
  1357   /// \see dag(), topologicalSort()
  1245   template <typename Digraph, typename NodeMap>
  1358   template <typename Digraph, typename NodeMap>
  1246   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
  1359   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
  1247     using namespace _connectivity_bits;
  1360     using namespace _connectivity_bits;
  1248 
  1361 
  1249     checkConcept<concepts::Digraph, Digraph>();
  1362     checkConcept<concepts::Digraph, Digraph>();
  1281     return true;
  1394     return true;
  1282   }
  1395   }
  1283 
  1396 
  1284   /// \ingroup graph_properties
  1397   /// \ingroup graph_properties
  1285   ///
  1398   ///
  1286   /// \brief Check that the given directed graph is a DAG.
  1399   /// \brief Check whether an undirected graph is acyclic.
  1287   ///
  1400   ///
  1288   /// Check that the given directed graph is a DAG. The DAG is
  1401   /// This function checks whether the given undirected graph is acyclic.
  1289   /// an Directed Acyclic Digraph.
  1402   /// \return \c true if there is no cycle in the graph.
  1290   /// \return \c false when the graph is not DAG.
  1403   /// \see dag()
  1291   /// \see acyclic
       
  1292   template <typename Digraph>
       
  1293   bool dag(const Digraph& digraph) {
       
  1294 
       
  1295     checkConcept<concepts::Digraph, Digraph>();
       
  1296 
       
  1297     typedef typename Digraph::Node Node;
       
  1298     typedef typename Digraph::NodeIt NodeIt;
       
  1299     typedef typename Digraph::Arc Arc;
       
  1300 
       
  1301     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       
  1302 
       
  1303     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
       
  1304       Create dfs(digraph);
       
  1305 
       
  1306     ProcessedMap processed(digraph);
       
  1307     dfs.processedMap(processed);
       
  1308 
       
  1309     dfs.init();
       
  1310     for (NodeIt it(digraph); it != INVALID; ++it) {
       
  1311       if (!dfs.reached(it)) {
       
  1312         dfs.addSource(it);
       
  1313         while (!dfs.emptyQueue()) {
       
  1314           Arc edge = dfs.nextArc();
       
  1315           Node target = digraph.target(edge);
       
  1316           if (dfs.reached(target) && !processed[target]) {
       
  1317             return false;
       
  1318           }
       
  1319           dfs.processNextArc();
       
  1320         }
       
  1321       }
       
  1322     }
       
  1323     return true;
       
  1324   }
       
  1325 
       
  1326   /// \ingroup graph_properties
       
  1327   ///
       
  1328   /// \brief Check that the given undirected graph is acyclic.
       
  1329   ///
       
  1330   /// Check that the given undirected graph acyclic.
       
  1331   /// \param graph The undirected graph.
       
  1332   /// \return \c true when there is no circle in the graph.
       
  1333   /// \see dag
       
  1334   template <typename Graph>
  1404   template <typename Graph>
  1335   bool acyclic(const Graph& graph) {
  1405   bool acyclic(const Graph& graph) {
  1336     checkConcept<concepts::Graph, Graph>();
  1406     checkConcept<concepts::Graph, Graph>();
  1337     typedef typename Graph::Node Node;
  1407     typedef typename Graph::Node Node;
  1338     typedef typename Graph::NodeIt NodeIt;
  1408     typedef typename Graph::NodeIt NodeIt;
  1341     dfs.init();
  1411     dfs.init();
  1342     for (NodeIt it(graph); it != INVALID; ++it) {
  1412     for (NodeIt it(graph); it != INVALID; ++it) {
  1343       if (!dfs.reached(it)) {
  1413       if (!dfs.reached(it)) {
  1344         dfs.addSource(it);
  1414         dfs.addSource(it);
  1345         while (!dfs.emptyQueue()) {
  1415         while (!dfs.emptyQueue()) {
  1346           Arc edge = dfs.nextArc();
  1416           Arc arc = dfs.nextArc();
  1347           Node source = graph.source(edge);
  1417           Node source = graph.source(arc);
  1348           Node target = graph.target(edge);
  1418           Node target = graph.target(arc);
  1349           if (dfs.reached(target) &&
  1419           if (dfs.reached(target) &&
  1350               dfs.predArc(source) != graph.oppositeArc(edge)) {
  1420               dfs.predArc(source) != graph.oppositeArc(arc)) {
  1351             return false;
  1421             return false;
  1352           }
  1422           }
  1353           dfs.processNextArc();
  1423           dfs.processNextArc();
  1354         }
  1424         }
  1355       }
  1425       }
  1357     return true;
  1427     return true;
  1358   }
  1428   }
  1359 
  1429 
  1360   /// \ingroup graph_properties
  1430   /// \ingroup graph_properties
  1361   ///
  1431   ///
  1362   /// \brief Check that the given undirected graph is tree.
  1432   /// \brief Check whether an undirected graph is tree.
  1363   ///
  1433   ///
  1364   /// Check that the given undirected graph is tree.
  1434   /// This function checks whether the given undirected graph is tree.
  1365   /// \param graph The undirected graph.
  1435   /// \return \c true if the graph is acyclic and connected.
  1366   /// \return \c true when the graph is acyclic and connected.
  1436   /// \see acyclic(), connected()
  1367   template <typename Graph>
  1437   template <typename Graph>
  1368   bool tree(const Graph& graph) {
  1438   bool tree(const Graph& graph) {
  1369     checkConcept<concepts::Graph, Graph>();
  1439     checkConcept<concepts::Graph, Graph>();
  1370     typedef typename Graph::Node Node;
  1440     typedef typename Graph::Node Node;
  1371     typedef typename Graph::NodeIt NodeIt;
  1441     typedef typename Graph::NodeIt NodeIt;
  1373     if (NodeIt(graph) == INVALID) return true;
  1443     if (NodeIt(graph) == INVALID) return true;
  1374     Dfs<Graph> dfs(graph);
  1444     Dfs<Graph> dfs(graph);
  1375     dfs.init();
  1445     dfs.init();
  1376     dfs.addSource(NodeIt(graph));
  1446     dfs.addSource(NodeIt(graph));
  1377     while (!dfs.emptyQueue()) {
  1447     while (!dfs.emptyQueue()) {
  1378       Arc edge = dfs.nextArc();
  1448       Arc arc = dfs.nextArc();
  1379       Node source = graph.source(edge);
  1449       Node source = graph.source(arc);
  1380       Node target = graph.target(edge);
  1450       Node target = graph.target(arc);
  1381       if (dfs.reached(target) &&
  1451       if (dfs.reached(target) &&
  1382           dfs.predArc(source) != graph.oppositeArc(edge)) {
  1452           dfs.predArc(source) != graph.oppositeArc(arc)) {
  1383         return false;
  1453         return false;
  1384       }
  1454       }
  1385       dfs.processNextArc();
  1455       dfs.processNextArc();
  1386     }
  1456     }
  1387     for (NodeIt it(graph); it != INVALID; ++it) {
  1457     for (NodeIt it(graph); it != INVALID; ++it) {
  1450     };
  1520     };
  1451   }
  1521   }
  1452 
  1522 
  1453   /// \ingroup graph_properties
  1523   /// \ingroup graph_properties
  1454   ///
  1524   ///
  1455   /// \brief Check if the given undirected graph is bipartite or not
  1525   /// \brief Check whether an undirected graph is bipartite.
  1456   ///
  1526   ///
  1457   /// The function checks if the given undirected \c graph graph is bipartite
  1527   /// The function checks whether the given undirected graph is bipartite.
  1458   /// or not. The \ref Bfs algorithm is used to calculate the result.
  1528   /// \return \c true if the graph is bipartite.
  1459   /// \param graph The undirected graph.
  1529   ///
  1460   /// \return \c true if \c graph is bipartite, \c false otherwise.
  1530   /// \see bipartitePartitions()
  1461   /// \sa bipartitePartitions
       
  1462   template<typename Graph>
  1531   template<typename Graph>
  1463   inline bool bipartite(const Graph &graph){
  1532   bool bipartite(const Graph &graph){
  1464     using namespace _connectivity_bits;
  1533     using namespace _connectivity_bits;
  1465 
  1534 
  1466     checkConcept<concepts::Graph, Graph>();
  1535     checkConcept<concepts::Graph, Graph>();
  1467 
  1536 
  1468     typedef typename Graph::NodeIt NodeIt;
  1537     typedef typename Graph::NodeIt NodeIt;
  1487     return true;
  1556     return true;
  1488   }
  1557   }
  1489 
  1558 
  1490   /// \ingroup graph_properties
  1559   /// \ingroup graph_properties
  1491   ///
  1560   ///
  1492   /// \brief Check if the given undirected graph is bipartite or not
  1561   /// \brief Find the bipartite partitions of an undirected graph.
  1493   ///
  1562   ///
  1494   /// The function checks if the given undirected graph is bipartite
  1563   /// This function checks whether the given undirected graph is bipartite
  1495   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
  1564   /// and gives back the bipartite partitions.
  1496   /// During the execution, the \c partMap will be set as the two
       
  1497   /// partitions of the graph.
       
  1498   ///
  1565   ///
  1499   /// \image html bipartite_partitions.png
  1566   /// \image html bipartite_partitions.png
  1500   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
  1567   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
  1501   ///
  1568   ///
  1502   /// \param graph The undirected graph.
  1569   /// \param graph The undirected graph.
  1503   /// \retval partMap A writable bool map of nodes. It will be set as the
  1570   /// \retval partMap A writable node map of \c bool (or convertible) value
  1504   /// two partitions of the graph.
  1571   /// type. The values will be set to \c true for one component and
  1505   /// \return \c true if \c graph is bipartite, \c false otherwise.
  1572   /// \c false for the other one.
       
  1573   /// \return \c true if the graph is bipartite, \c false otherwise.
       
  1574   ///
       
  1575   /// \see bipartite()
  1506   template<typename Graph, typename NodeMap>
  1576   template<typename Graph, typename NodeMap>
  1507   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1577   bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1508     using namespace _connectivity_bits;
  1578     using namespace _connectivity_bits;
  1509 
  1579 
  1510     checkConcept<concepts::Graph, Graph>();
  1580     checkConcept<concepts::Graph, Graph>();
       
  1581     checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
  1511 
  1582 
  1512     typedef typename Graph::Node Node;
  1583     typedef typename Graph::Node Node;
  1513     typedef typename Graph::NodeIt NodeIt;
  1584     typedef typename Graph::NodeIt NodeIt;
  1514     typedef typename Graph::ArcIt ArcIt;
  1585     typedef typename Graph::ArcIt ArcIt;
  1515 
  1586 
  1530       }
  1601       }
  1531     }
  1602     }
  1532     return true;
  1603     return true;
  1533   }
  1604   }
  1534 
  1605 
  1535   /// \brief Returns true when there are not loop edges in the graph.
  1606   /// \ingroup graph_properties
  1536   ///
  1607   ///
  1537   /// Returns true when there are not loop edges in the graph.
  1608   /// \brief Check whether the given graph contains no loop arcs/edges.
  1538   template <typename Digraph>
  1609   ///
  1539   bool loopFree(const Digraph& digraph) {
  1610   /// This function returns \c true if there are no loop arcs/edges in
  1540     for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
  1611   /// the given graph. It works for both directed and undirected graphs.
  1541       if (digraph.source(it) == digraph.target(it)) return false;
  1612   template <typename Graph>
       
  1613   bool loopFree(const Graph& graph) {
       
  1614     for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
       
  1615       if (graph.source(it) == graph.target(it)) return false;
  1542     }
  1616     }
  1543     return true;
  1617     return true;
  1544   }
  1618   }
  1545 
  1619 
  1546   /// \brief Returns true when there are not parallel edges in the graph.
  1620   /// \ingroup graph_properties
  1547   ///
  1621   ///
  1548   /// Returns true when there are not parallel edges in the graph.
  1622   /// \brief Check whether the given graph contains no parallel arcs/edges.
       
  1623   ///
       
  1624   /// This function returns \c true if there are no parallel arcs/edges in
       
  1625   /// the given graph. It works for both directed and undirected graphs.
  1549   template <typename Graph>
  1626   template <typename Graph>
  1550   bool parallelFree(const Graph& graph) {
  1627   bool parallelFree(const Graph& graph) {
  1551     typename Graph::template NodeMap<int> reached(graph, 0);
  1628     typename Graph::template NodeMap<int> reached(graph, 0);
  1552     int cnt = 1;
  1629     int cnt = 1;
  1553     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
  1630     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
  1558       ++cnt;
  1635       ++cnt;
  1559     }
  1636     }
  1560     return true;
  1637     return true;
  1561   }
  1638   }
  1562 
  1639 
  1563   /// \brief Returns true when there are not loop edges and parallel
  1640   /// \ingroup graph_properties
  1564   /// edges in the graph.
  1641   ///
  1565   ///
  1642   /// \brief Check whether the given graph is simple.
  1566   /// Returns true when there are not loop edges and parallel edges in
  1643   ///
  1567   /// the graph.
  1644   /// This function returns \c true if the given graph is simple, i.e.
       
  1645   /// it contains no loop arcs/edges and no parallel arcs/edges.
       
  1646   /// The function works for both directed and undirected graphs.
       
  1647   /// \see loopFree(), parallelFree()
  1568   template <typename Graph>
  1648   template <typename Graph>
  1569   bool simpleGraph(const Graph& graph) {
  1649   bool simpleGraph(const Graph& graph) {
  1570     typename Graph::template NodeMap<int> reached(graph, 0);
  1650     typename Graph::template NodeMap<int> reached(graph, 0);
  1571     int cnt = 1;
  1651     int cnt = 1;
  1572     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
  1652     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {