Mercuriallemon-main / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/connectivity.h
changeset 613 b1811c363299
parent 559 c5fd2d996909
child 647 dcba640438c7
equal deleted inserted replaced
4:11f76843d458 5:f94ea23f5613 
    30 #include <lemon/concept_check.h>
 
    30 #include <lemon/concept_check.h>
 
    31 
    31 
    32 #include <stack>
 
    32 #include <stack>
 
    33 #include <functional>
 
    33 #include <functional>
 
    34 
    34 
    35 /// \ingroup connectivity
 
    35 /// \ingroup graph_properties
 
    36 /// \file
 
    36 /// \file
 
    37 /// \brief Connectivity algorithms
 
    37 /// \brief Connectivity algorithms
 
    38 ///
 
    38 ///
 
    39 /// Connectivity algorithms
 
    39 /// Connectivity algorithms
 
    40 
    40 
    41 namespace lemon {
 
    41 namespace lemon {
 
    42 
    42 
    43   /// \ingroup connectivity
 
    43   /// \ingroup graph_properties
 
    44   ///
 
    44   ///
 
    45   /// \brief Check whether the given undirected graph is connected.
 
    45   /// \brief Check whether the given undirected graph is connected.
 
    46   ///
 
    46   ///
 
    47   /// Check whether the given undirected graph is connected.
 
    47   /// Check whether the given undirected graph is connected.
 
    48   /// \param graph The undirected graph.
 
    48   /// \param graph The undirected graph.
 
    61       }
 
    61       }
 
    62     }
 
    62     }
 
    63     return true;
 
    63     return true;
 
    64   }
 
    64   }
 
    65 
    65 
    66   /// \ingroup connectivity
 
    66   /// \ingroup graph_properties
 
    67   ///
 
    67   ///
 
    68   /// \brief Count the number of connected components of an undirected graph
 
    68   /// \brief Count the number of connected components of an undirected graph
 
    69   ///
 
    69   ///
 
    70   /// Count the number of connected components of an undirected graph
 
    70   /// Count the number of connected components of an undirected graph
 
    71   ///
 
    71   ///
 
   103       }
 
   103       }
 
   104     }
 
   104     }
 
   105     return compNum;
 
   105     return compNum;
 
   106   }
 
   106   }
 
   107 
   107 
   108   /// \ingroup connectivity
 
   108   /// \ingroup graph_properties
 
   109   ///
 
   109   ///
 
   110   /// \brief Find the connected components of an undirected graph
 
   110   /// \brief Find the connected components of an undirected graph
 
   111   ///
 
   111   ///
 
   112   /// Find the connected components of an undirected graph.
 
   112   /// Find the connected components of an undirected graph.
 
       
   113   ///
 
       
   114   /// \image html connected_components.png
 
       
   115   /// \image latex connected_components.eps "Connected components" width=\textwidth
 
   113   ///
 
   116   ///
 
   114   /// \param graph The graph. It must be undirected.
 
   117   /// \param graph The graph. It must be undirected.
 
   115   /// \retval compMap A writable node map. The values will be set from 0 to
 
   118   /// \retval compMap A writable node map. The values will be set from 0 to
 
   116   /// the number of the connected components minus one. Each values of the map
 
   119   /// the number of the connected components minus one. Each values of the map
 
   117   /// will be set exactly once, the values of a certain component will be
 
   120   /// will be set exactly once, the values of a certain component will be
 
   118   /// set continuously.
 
   121   /// set continuously.
 
   119   /// \return The number of components
 
   122   /// \return The number of components
 
   120   ///
 
       
   121   template <class Graph, class NodeMap>
 
   123   template <class Graph, class NodeMap>
 
   122   int connectedComponents(const Graph &graph, NodeMap &compMap) {
 
   124   int connectedComponents(const Graph &graph, NodeMap &compMap) {
 
   123     checkConcept<concepts::Graph, Graph>();
 
   125     checkConcept<concepts::Graph, Graph>();
 
   124     typedef typename Graph::Node Node;
 
   126     typedef typename Graph::Node Node;
 
   125     typedef typename Graph::Arc Arc;
 
   127     typedef typename Graph::Arc Arc;
 
   225     };
 
   227     };
 
   226 
   228 
   227   }
 
   229   }
 
   228 
   230 
   229 
   231 
   230   /// \ingroup connectivity
 
   232   /// \ingroup graph_properties
 
   231   ///
 
   233   ///
 
   232   /// \brief Check whether the given directed graph is strongly connected.
 
   234   /// \brief Check whether the given directed graph is strongly connected.
 
   233   ///
 
   235   ///
 
   234   /// Check whether the given directed graph is strongly connected. The
 
   236   /// Check whether the given directed graph is strongly connected. The
 
   235   /// graph is strongly connected when any two nodes of the graph are
 
   237   /// graph is strongly connected when any two nodes of the graph are
 
   283     }
 
   285     }
 
   284 
   286 
   285     return true;
 
   287     return true;
 
   286   }
 
   288   }
 
   287 
   289 
   288   /// \ingroup connectivity
 
   290   /// \ingroup graph_properties
 
   289   ///
 
   291   ///
 
   290   /// \brief Count the strongly connected components of a directed graph
 
   292   /// \brief Count the strongly connected components of a directed graph
 
   291   ///
 
   293   ///
 
   292   /// Count the strongly connected components of a directed graph.
 
   294   /// Count the strongly connected components of a directed graph.
 
   293   /// The strongly connected components are the classes of an
 
   295   /// The strongly connected components are the classes of an
 
   347       }
 
   349       }
 
   348     }
 
   350     }
 
   349     return compNum;
 
   351     return compNum;
 
   350   }
 
   352   }
 
   351 
   353 
   352   /// \ingroup connectivity
 
   354   /// \ingroup graph_properties
 
   353   ///
 
   355   ///
 
   354   /// \brief Find the strongly connected components of a directed graph
 
   356   /// \brief Find the strongly connected components of a directed graph
 
   355   ///
 
   357   ///
 
   356   /// Find the strongly connected components of a directed graph.  The
 
   358   /// Find the strongly connected components of a directed graph.  The
 
   357   /// strongly connected components are the classes of an equivalence
 
   359   /// strongly connected components are the classes of an equivalence
 
   359   /// relationship when there are directed paths between them in both
 
   361   /// relationship when there are directed paths between them in both
 
   360   /// direction. In addition, the numbering of components will satisfy
 
   362   /// direction. In addition, the numbering of components will satisfy
 
   361   /// that there is no arc going from a higher numbered component to
 
   363   /// that there is no arc going from a higher numbered component to
 
   362   /// a lower.
 
   364   /// a lower.
 
   363   ///
 
   365   ///
 
       
   366   /// \image html strongly_connected_components.png
 
       
   367   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
 
       
   368   ///
 
   364   /// \param digraph The digraph.
 
   369   /// \param digraph The digraph.
 
   365   /// \retval compMap A writable node map. The values will be set from 0 to
 
   370   /// \retval compMap A writable node map. The values will be set from 0 to
 
   366   /// the number of the strongly connected components minus one. Each value
 
   371   /// the number of the strongly connected components minus one. Each value
 
   367   /// of the map will be set exactly once, the values of a certain component
 
   372   /// of the map will be set exactly once, the values of a certain component
 
   368   /// will be set continuously.
 
   373   /// will be set continuously.
 
   369   /// \return The number of components
 
   374   /// \return The number of components
 
   370   ///
 
       
   371   template <typename Digraph, typename NodeMap>
 
   375   template <typename Digraph, typename NodeMap>
 
   372   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
 
   376   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
 
   373     checkConcept<concepts::Digraph, Digraph>();
 
   377     checkConcept<concepts::Digraph, Digraph>();
 
   374     typedef typename Digraph::Node Node;
 
   378     typedef typename Digraph::Node Node;
 
   375     typedef typename Digraph::NodeIt NodeIt;
 
   379     typedef typename Digraph::NodeIt NodeIt;
 
   414       }
 
   418       }
 
   415     }
 
   419     }
 
   416     return compNum;
 
   420     return compNum;
 
   417   }
 
   421   }
 
   418 
   422 
   419   /// \ingroup connectivity
 
   423   /// \ingroup graph_properties
 
   420   ///
 
   424   ///
 
   421   /// \brief Find the cut arcs of the strongly connected components.
 
   425   /// \brief Find the cut arcs of the strongly connected components.
 
   422   ///
 
   426   ///
 
   423   /// Find the cut arcs of the strongly connected components.
 
   427   /// Find the cut arcs of the strongly connected components.
 
   424   /// The strongly connected components are the classes of an equivalence
 
   428   /// The strongly connected components are the classes of an equivalence
 
   698   }
 
   702   }
 
   699 
   703 
   700   template <typename Graph>
 
   704   template <typename Graph>
 
   701   int countBiNodeConnectedComponents(const Graph& graph);
 
   705   int countBiNodeConnectedComponents(const Graph& graph);
 
   702 
   706 
   703   /// \ingroup connectivity
 
   707   /// \ingroup graph_properties
 
   704   ///
 
   708   ///
 
   705   /// \brief Checks the graph is bi-node-connected.
 
   709   /// \brief Checks the graph is bi-node-connected.
 
   706   ///
 
   710   ///
 
   707   /// This function checks that the undirected graph is bi-node-connected
 
   711   /// This function checks that the undirected graph is bi-node-connected
 
   708   /// graph. The graph is bi-node-connected if any two undirected edge is
 
   712   /// graph. The graph is bi-node-connected if any two undirected edge is
 
   713   template <typename Graph>
 
   717   template <typename Graph>
 
   714   bool biNodeConnected(const Graph& graph) {
 
   718   bool biNodeConnected(const Graph& graph) {
 
   715     return countBiNodeConnectedComponents(graph) <= 1;
 
   719     return countBiNodeConnectedComponents(graph) <= 1;
 
   716   }
 
   720   }
 
   717 
   721 
   718   /// \ingroup connectivity
 
   722   /// \ingroup graph_properties
 
   719   ///
 
   723   ///
 
   720   /// \brief Count the biconnected components.
 
   724   /// \brief Count the biconnected components.
 
   721   ///
 
   725   ///
 
   722   /// This function finds the bi-node-connected components in an undirected
 
   726   /// This function finds the bi-node-connected components in an undirected
 
   723   /// graph. The biconnected components are the classes of an equivalence
 
   727   /// graph. The biconnected components are the classes of an equivalence
 
   748       }
 
   752       }
 
   749     }
 
   753     }
 
   750     return compNum;
 
   754     return compNum;
 
   751   }
 
   755   }
 
   752 
   756 
   753   /// \ingroup connectivity
 
   757   /// \ingroup graph_properties
 
   754   ///
 
   758   ///
 
   755   /// \brief Find the bi-node-connected components.
 
   759   /// \brief Find the bi-node-connected components.
 
   756   ///
 
   760   ///
 
   757   /// This function finds the bi-node-connected components in an undirected
 
   761   /// This function finds the bi-node-connected components in an undirected
 
   758   /// graph. The bi-node-connected components are the classes of an equivalence
 
   762   /// graph. The bi-node-connected components are the classes of an equivalence
 
   759   /// relation on the undirected edges. Two undirected edge are in relationship
 
   763   /// relation on the undirected edges. Two undirected edge are in relationship
 
   760   /// when they are on same circle.
 
   764   /// when they are on same circle.
 
       
   765   ///
 
       
   766   /// \image html node_biconnected_components.png
 
       
   767   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
 
   761   ///
 
   768   ///
 
   762   /// \param graph The graph.
 
   769   /// \param graph The graph.
 
   763   /// \retval compMap A writable uedge map. The values will be set from 0
 
   770   /// \retval compMap A writable uedge map. The values will be set from 0
 
   764   /// to the number of the biconnected components minus one. Each values
 
   771   /// to the number of the biconnected components minus one. Each values
 
   765   /// of the map will be set exactly once, the values of a certain component
 
   772   /// of the map will be set exactly once, the values of a certain component
 
   766   /// will be set continuously.
 
   773   /// will be set continuously.
 
   767   /// \return The number of components.
 
   774   /// \return The number of components.
 
   768   ///
 
       
   769   template <typename Graph, typename EdgeMap>
 
   775   template <typename Graph, typename EdgeMap>
 
   770   int biNodeConnectedComponents(const Graph& graph,
 
   776   int biNodeConnectedComponents(const Graph& graph,
 
   771                                 EdgeMap& compMap) {
 
   777                                 EdgeMap& compMap) {
 
   772     checkConcept<concepts::Graph, Graph>();
 
   778     checkConcept<concepts::Graph, Graph>();
 
   773     typedef typename Graph::NodeIt NodeIt;
 
   779     typedef typename Graph::NodeIt NodeIt;
 
   791       }
 
   797       }
 
   792     }
 
   798     }
 
   793     return compNum;
 
   799     return compNum;
 
   794   }
 
   800   }
 
   795 
   801 
   796   /// \ingroup connectivity
 
   802   /// \ingroup graph_properties
 
   797   ///
 
   803   ///
 
   798   /// \brief Find the bi-node-connected cut nodes.
 
   804   /// \brief Find the bi-node-connected cut nodes.
 
   799   ///
 
   805   ///
 
   800   /// This function finds the bi-node-connected cut nodes in an undirected
 
   806   /// This function finds the bi-node-connected cut nodes in an undirected
 
   801   /// graph. The bi-node-connected components are the classes of an equivalence
 
   807   /// graph. The bi-node-connected components are the classes of an equivalence
 
  1021   }
 
  1027   }
 
  1022 
  1028 
  1023   template <typename Graph>
 
  1029   template <typename Graph>
 
  1024   int countBiEdgeConnectedComponents(const Graph& graph);
 
  1030   int countBiEdgeConnectedComponents(const Graph& graph);
 
  1025 
  1031 
  1026   /// \ingroup connectivity
 
  1032   /// \ingroup graph_properties
 
  1027   ///
 
  1033   ///
 
  1028   /// \brief Checks that the graph is bi-edge-connected.
 
  1034   /// \brief Checks that the graph is bi-edge-connected.
 
  1029   ///
 
  1035   ///
 
  1030   /// This function checks that the graph is bi-edge-connected. The undirected
 
  1036   /// This function checks that the graph is bi-edge-connected. The undirected
 
  1031   /// graph is bi-edge-connected when any two nodes are connected with two
 
  1037   /// graph is bi-edge-connected when any two nodes are connected with two
 
  1036   template <typename Graph>
 
  1042   template <typename Graph>
 
  1037   bool biEdgeConnected(const Graph& graph) {
 
  1043   bool biEdgeConnected(const Graph& graph) {
 
  1038     return countBiEdgeConnectedComponents(graph) <= 1;
 
  1044     return countBiEdgeConnectedComponents(graph) <= 1;
 
  1039   }
 
  1045   }
 
  1040 
  1046 
  1041   /// \ingroup connectivity
 
  1047   /// \ingroup graph_properties
 
  1042   ///
 
  1048   ///
 
  1043   /// \brief Count the bi-edge-connected components.
 
  1049   /// \brief Count the bi-edge-connected components.
 
  1044   ///
 
  1050   ///
 
  1045   /// This function count the bi-edge-connected components in an undirected
 
  1051   /// This function count the bi-edge-connected components in an undirected
 
  1046   /// graph. The bi-edge-connected components are the classes of an equivalence
 
  1052   /// graph. The bi-edge-connected components are the classes of an equivalence
 
  1071       }
 
  1077       }
 
  1072     }
 
  1078     }
 
  1073     return compNum;
 
  1079     return compNum;
 
  1074   }
 
  1080   }
 
  1075 
  1081 
  1076   /// \ingroup connectivity
 
  1082   /// \ingroup graph_properties
 
  1077   ///
 
  1083   ///
 
  1078   /// \brief Find the bi-edge-connected components.
 
  1084   /// \brief Find the bi-edge-connected components.
 
  1079   ///
 
  1085   ///
 
  1080   /// This function finds the bi-edge-connected components in an undirected
 
  1086   /// This function finds the bi-edge-connected components in an undirected
 
  1081   /// graph. The bi-edge-connected components are the classes of an equivalence
 
  1087   /// graph. The bi-edge-connected components are the classes of an equivalence
 
  1082   /// relation on the nodes. Two nodes are in relationship when they are
 
  1088   /// relation on the nodes. Two nodes are in relationship when they are
 
  1083   /// connected at least two edge-disjoint paths.
 
  1089   /// connected at least two edge-disjoint paths.
 
       
  1090   ///
 
       
  1091   /// \image html edge_biconnected_components.png
 
       
  1092   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 
  1084   ///
 
  1093   ///
 
  1085   /// \param graph The graph.
 
  1094   /// \param graph The graph.
 
  1086   /// \retval compMap A writable node map. The values will be set from 0 to
 
  1095   /// \retval compMap A writable node map. The values will be set from 0 to
 
  1087   /// the number of the biconnected components minus one. Each values
 
  1096   /// the number of the biconnected components minus one. Each values
 
  1088   /// of the map will be set exactly once, the values of a certain component
 
  1097   /// of the map will be set exactly once, the values of a certain component
 
  1089   /// will be set continuously.
 
  1098   /// will be set continuously.
 
  1090   /// \return The number of components.
 
  1099   /// \return The number of components.
 
  1091   ///
 
       
  1092   template <typename Graph, typename NodeMap>
 
  1100   template <typename Graph, typename NodeMap>
 
  1093   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
 
  1101   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
 
  1094     checkConcept<concepts::Graph, Graph>();
 
  1102     checkConcept<concepts::Graph, Graph>();
 
  1095     typedef typename Graph::NodeIt NodeIt;
 
  1103     typedef typename Graph::NodeIt NodeIt;
 
  1096     typedef typename Graph::Node Node;
 
  1104     typedef typename Graph::Node Node;
 
  1113       }
 
  1121       }
 
  1114     }
 
  1122     }
 
  1115     return compNum;
 
  1123     return compNum;
 
  1116   }
 
  1124   }
 
  1117 
  1125 
  1118   /// \ingroup connectivity
 
  1126   /// \ingroup graph_properties
 
  1119   ///
 
  1127   ///
 
  1120   /// \brief Find the bi-edge-connected cut edges.
 
  1128   /// \brief Find the bi-edge-connected cut edges.
 
  1121   ///
 
  1129   ///
 
  1122   /// This function finds the bi-edge-connected components in an undirected
 
  1130   /// This function finds the bi-edge-connected components in an undirected
 
  1123   /// graph. The bi-edge-connected components are the classes of an equivalence
 
  1131   /// graph. The bi-edge-connected components are the classes of an equivalence
 
  1177       int _num;
 
  1185       int _num;
 
  1178     };
 
  1186     };
 
  1179 
  1187 
  1180   }
 
  1188   }
 
  1181 
  1189 
  1182   /// \ingroup connectivity
 
  1190   /// \ingroup graph_properties
 
  1183   ///
 
  1191   ///
 
  1184   /// \brief Sort the nodes of a DAG into topolgical order.
 
  1192   /// \brief Sort the nodes of a DAG into topolgical order.
 
  1185   ///
 
  1193   ///
 
  1186   /// Sort the nodes of a DAG into topolgical order.
 
  1194   /// Sort the nodes of a DAG into topolgical order.
 
  1187   ///
 
  1195   ///
 
  1216         dfs.start();
 
  1224         dfs.start();
 
  1217       }
 
  1225       }
 
  1218     }
 
  1226     }
 
  1219   }
 
  1227   }
 
  1220 
  1228 
  1221   /// \ingroup connectivity
 
  1229   /// \ingroup graph_properties
 
  1222   ///
 
  1230   ///
 
  1223   /// \brief Sort the nodes of a DAG into topolgical order.
 
  1231   /// \brief Sort the nodes of a DAG into topolgical order.
 
  1224   ///
 
  1232   ///
 
  1225   /// Sort the nodes of a DAG into topolgical order. It also checks
 
  1233   /// Sort the nodes of a DAG into topolgical order. It also checks
 
  1226   /// that the given graph is DAG.
 
  1234   /// that the given graph is DAG.
 
  1271       }
 
  1279       }
 
  1272     }
 
  1280     }
 
  1273     return true;
 
  1281     return true;
 
  1274   }
 
  1282   }
 
  1275 
  1283 
  1276   /// \ingroup connectivity
 
  1284   /// \ingroup graph_properties
 
  1277   ///
 
  1285   ///
 
  1278   /// \brief Check that the given directed graph is a DAG.
 
  1286   /// \brief Check that the given directed graph is a DAG.
 
  1279   ///
 
  1287   ///
 
  1280   /// Check that the given directed graph is a DAG. The DAG is
 
  1288   /// Check that the given directed graph is a DAG. The DAG is
 
  1281   /// an Directed Acyclic Digraph.
 
  1289   /// an Directed Acyclic Digraph.
 
  1313       }
 
  1321       }
 
  1314     }
 
  1322     }
 
  1315     return true;
 
  1323     return true;
 
  1316   }
 
  1324   }
 
  1317 
  1325 
  1318   /// \ingroup connectivity
 
  1326   /// \ingroup graph_properties
 
  1319   ///
 
  1327   ///
 
  1320   /// \brief Check that the given undirected graph is acyclic.
 
  1328   /// \brief Check that the given undirected graph is acyclic.
 
  1321   ///
 
  1329   ///
 
  1322   /// Check that the given undirected graph acyclic.
 
  1330   /// Check that the given undirected graph acyclic.
 
  1323   /// \param graph The undirected graph.
 
  1331   /// \param graph The undirected graph.
 
  1347       }
 
  1355       }
 
  1348     }
 
  1356     }
 
  1349     return true;
 
  1357     return true;
 
  1350   }
 
  1358   }
 
  1351 
  1359 
  1352   /// \ingroup connectivity
 
  1360   /// \ingroup graph_properties
 
  1353   ///
 
  1361   ///
 
  1354   /// \brief Check that the given undirected graph is tree.
 
  1362   /// \brief Check that the given undirected graph is tree.
 
  1355   ///
 
  1363   ///
 
  1356   /// Check that the given undirected graph is tree.
 
  1364   /// Check that the given undirected graph is tree.
 
  1357   /// \param graph The undirected graph.
 
  1365   /// \param graph The undirected graph.
 
  1439       PartMap& _part;
 
  1447       PartMap& _part;
 
  1440       bool& _bipartite;
 
  1448       bool& _bipartite;
 
  1441     };
 
  1449     };
 
  1442   }
 
  1450   }
 
  1443 
  1451 
  1444   /// \ingroup connectivity
 
  1452   /// \ingroup graph_properties
 
  1445   ///
 
  1453   ///
 
  1446   /// \brief Check if the given undirected graph is bipartite or not
 
  1454   /// \brief Check if the given undirected graph is bipartite or not
 
  1447   ///
 
  1455   ///
 
  1448   /// The function checks if the given undirected \c graph graph is bipartite
 
  1456   /// The function checks if the given undirected \c graph graph is bipartite
 
  1449   /// or not. The \ref Bfs algorithm is used to calculate the result.
 
  1457   /// or not. The \ref Bfs algorithm is used to calculate the result.
 
  1476       }
 
  1484       }
 
  1477     }
 
  1485     }
 
  1478     return true;
 
  1486     return true;
 
  1479   }
 
  1487   }
 
  1480 
  1488 
  1481   /// \ingroup connectivity
 
  1489   /// \ingroup graph_properties
 
  1482   ///
 
  1490   ///
 
  1483   /// \brief Check if the given undirected graph is bipartite or not
 
  1491   /// \brief Check if the given undirected graph is bipartite or not
 
  1484   ///
 
  1492   ///
 
  1485   /// The function checks if the given undirected graph is bipartite
 
  1493   /// The function checks if the given undirected graph is bipartite
 
  1486   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
 
  1494   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
 
  1487   /// During the execution, the \c partMap will be set as the two
 
  1495   /// During the execution, the \c partMap will be set as the two
 
  1488   /// partitions of the graph.
 
  1496   /// partitions of the graph.
 
       
  1497   ///
 
       
  1498   /// \image html bipartite_partitions.png
 
       
  1499   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
 
       
  1500   ///
 
  1489   /// \param graph The undirected graph.
 
  1501   /// \param graph The undirected graph.
 
  1490   /// \retval partMap A writable bool map of nodes. It will be set as the
 
  1502   /// \retval partMap A writable bool map of nodes. It will be set as the
 
  1491   /// two partitions of the graph.
 
  1503   /// two partitions of the graph.
 
  1492   /// \return \c true if \c graph is bipartite, \c false otherwise.
 
  1504   /// \return \c true if \c graph is bipartite, \c false otherwise.
 
  1493   template<typename Graph, typename NodeMap>
 
  1505   template<typename Graph, typename NodeMap>
lemon-main