lemon/connectivity.h
changeset 423 ff48c2738fb2
parent 417 6ff53afe98b5
child 425 cace3206223b
equal deleted inserted replaced
0:b2957259973a 1:b0e279495dc5
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #ifndef LEMON_TOPOLOGY_H
    19 #ifndef LEMON_CONNECTIVITY_H
    20 #define LEMON_TOPOLOGY_H
    20 #define LEMON_CONNECTIVITY_H
    21 
    21 
    22 #include <lemon/dfs.h>
    22 #include <lemon/dfs.h>
    23 #include <lemon/bfs.h>
    23 #include <lemon/bfs.h>
    24 #include <lemon/core.h>
    24 #include <lemon/core.h>
    25 #include <lemon/maps.h>
    25 #include <lemon/maps.h>
   152       }
   152       }
   153     }
   153     }
   154     return compNum;
   154     return compNum;
   155   }
   155   }
   156 
   156 
   157   namespace _topology_bits {
   157   namespace _connectivity_bits {
   158 
   158 
   159     template <typename Digraph, typename Iterator >
   159     template <typename Digraph, typename Iterator >
   160     struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
   160     struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
   161     public:
   161     public:
   162       typedef typename Digraph::Node Node;
   162       typedef typename Digraph::Node Node;
   186       Map& _map;
   186       Map& _map;
   187       Value& _value;
   187       Value& _value;
   188     };
   188     };
   189 
   189 
   190     template <typename Digraph, typename ArcMap>
   190     template <typename Digraph, typename ArcMap>
   191     struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
   191     struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
   192     public:
   192     public:
   193       typedef typename Digraph::Node Node;
   193       typedef typename Digraph::Node Node;
   194       typedef typename Digraph::Arc Arc;
   194       typedef typename Digraph::Arc Arc;
   195 
   195 
   196       StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
   196       StronglyConnectedCutArcsVisitor(const Digraph& digraph,
   197                                        ArcMap& cutMap,
   197                                       ArcMap& cutMap,
   198                                        int& cutNum)
   198                                       int& cutNum)
   199         : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
   199         : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
   200           _compMap(digraph), _num(0) {
   200           _compMap(digraph, -1), _num(-1) {
   201       }
   201       }
   202 
   202 
   203       void stop(const Node&) {
   203       void start(const Node&) {
   204         ++_num;
   204         ++_num;
   205       }
   205       }
   206 
   206 
   207       void reach(const Node& node) {
   207       void reach(const Node& node) {
   208         _compMap.set(node, _num);
   208         _compMap.set(node, _num);
   246     typedef typename Digraph::NodeIt NodeIt;
   246     typedef typename Digraph::NodeIt NodeIt;
   247 
   247 
   248     typename Digraph::Node source = NodeIt(digraph);
   248     typename Digraph::Node source = NodeIt(digraph);
   249     if (source == INVALID) return true;
   249     if (source == INVALID) return true;
   250 
   250 
   251     using namespace _topology_bits;
   251     using namespace _connectivity_bits;
   252 
   252 
   253     typedef DfsVisitor<Digraph> Visitor;
   253     typedef DfsVisitor<Digraph> Visitor;
   254     Visitor visitor;
   254     Visitor visitor;
   255 
   255 
   256     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   256     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   263         return false;
   263         return false;
   264       }
   264       }
   265     }
   265     }
   266 
   266 
   267     typedef ReverseDigraph<const Digraph> RDigraph;
   267     typedef ReverseDigraph<const Digraph> RDigraph;
       
   268     typedef typename RDigraph::NodeIt RNodeIt;
   268     RDigraph rdigraph(digraph);
   269     RDigraph rdigraph(digraph);
   269 
   270 
   270     typedef DfsVisitor<Digraph> RVisitor;
   271     typedef DfsVisitor<Digraph> RVisitor;
   271     RVisitor rvisitor;
   272     RVisitor rvisitor;
   272 
   273 
   273     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   274     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   274     rdfs.init();
   275     rdfs.init();
   275     rdfs.addSource(source);
   276     rdfs.addSource(source);
   276     rdfs.start();
   277     rdfs.start();
   277 
   278 
   278     for (NodeIt it(rdigraph); it != INVALID; ++it) {
   279     for (RNodeIt it(rdigraph); it != INVALID; ++it) {
   279       if (!rdfs.reached(it)) {
   280       if (!rdfs.reached(it)) {
   280         return false;
   281         return false;
   281       }
   282       }
   282     }
   283     }
   283 
   284 
   300   /// strongly connected components.
   301   /// strongly connected components.
   301   template <typename Digraph>
   302   template <typename Digraph>
   302   int countStronglyConnectedComponents(const Digraph& digraph) {
   303   int countStronglyConnectedComponents(const Digraph& digraph) {
   303     checkConcept<concepts::Digraph, Digraph>();
   304     checkConcept<concepts::Digraph, Digraph>();
   304 
   305 
   305     using namespace _topology_bits;
   306     using namespace _connectivity_bits;
   306 
   307 
   307     typedef typename Digraph::Node Node;
   308     typedef typename Digraph::Node Node;
   308     typedef typename Digraph::Arc Arc;
   309     typedef typename Digraph::Arc Arc;
   309     typedef typename Digraph::NodeIt NodeIt;
   310     typedef typename Digraph::NodeIt NodeIt;
   310     typedef typename Digraph::ArcIt ArcIt;
   311     typedef typename Digraph::ArcIt ArcIt;
   372     checkConcept<concepts::Digraph, Digraph>();
   373     checkConcept<concepts::Digraph, Digraph>();
   373     typedef typename Digraph::Node Node;
   374     typedef typename Digraph::Node Node;
   374     typedef typename Digraph::NodeIt NodeIt;
   375     typedef typename Digraph::NodeIt NodeIt;
   375     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
   376     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
   376 
   377 
   377     using namespace _topology_bits;
   378     using namespace _connectivity_bits;
   378 
   379 
   379     typedef std::vector<Node> Container;
   380     typedef std::vector<Node> Container;
   380     typedef typename Container::iterator Iterator;
   381     typedef typename Container::iterator Iterator;
   381 
   382 
   382     Container nodes(countNodes(digraph));
   383     Container nodes(countNodes(digraph));
   436     typedef typename Digraph::Node Node;
   437     typedef typename Digraph::Node Node;
   437     typedef typename Digraph::Arc Arc;
   438     typedef typename Digraph::Arc Arc;
   438     typedef typename Digraph::NodeIt NodeIt;
   439     typedef typename Digraph::NodeIt NodeIt;
   439     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
   440     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
   440 
   441 
   441     using namespace _topology_bits;
   442     using namespace _connectivity_bits;
   442 
   443 
   443     typedef std::vector<Node> Container;
   444     typedef std::vector<Node> Container;
   444     typedef typename Container::iterator Iterator;
   445     typedef typename Container::iterator Iterator;
   445 
   446 
   446     Container nodes(countNodes(graph));
   447     Container nodes(countNodes(graph));
   461 
   462 
   462     RDigraph rgraph(graph);
   463     RDigraph rgraph(graph);
   463 
   464 
   464     int cutNum = 0;
   465     int cutNum = 0;
   465 
   466 
   466     typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
   467     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
   467     RVisitor rvisitor(rgraph, cutMap, cutNum);
   468     RVisitor rvisitor(rgraph, cutMap, cutNum);
   468 
   469 
   469     DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
   470     DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
   470 
   471 
   471     rdfs.init();
   472     rdfs.init();
   476       }
   477       }
   477     }
   478     }
   478     return cutNum;
   479     return cutNum;
   479   }
   480   }
   480 
   481 
   481   namespace _topology_bits {
   482   namespace _connectivity_bits {
   482 
   483 
   483     template <typename Digraph>
   484     template <typename Digraph>
   484     class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   485     class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   485     public:
   486     public:
   486       typedef typename Digraph::Node Node;
   487       typedef typename Digraph::Node Node;
   728   template <typename Graph>
   729   template <typename Graph>
   729   int countBiNodeConnectedComponents(const Graph& graph) {
   730   int countBiNodeConnectedComponents(const Graph& graph) {
   730     checkConcept<concepts::Graph, Graph>();
   731     checkConcept<concepts::Graph, Graph>();
   731     typedef typename Graph::NodeIt NodeIt;
   732     typedef typename Graph::NodeIt NodeIt;
   732 
   733 
   733     using namespace _topology_bits;
   734     using namespace _connectivity_bits;
   734 
   735 
   735     typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
   736     typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
   736 
   737 
   737     int compNum = 0;
   738     int compNum = 0;
   738     Visitor visitor(graph, compNum);
   739     Visitor visitor(graph, compNum);
   771     checkConcept<concepts::Graph, Graph>();
   772     checkConcept<concepts::Graph, Graph>();
   772     typedef typename Graph::NodeIt NodeIt;
   773     typedef typename Graph::NodeIt NodeIt;
   773     typedef typename Graph::Edge Edge;
   774     typedef typename Graph::Edge Edge;
   774     checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
   775     checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
   775 
   776 
   776     using namespace _topology_bits;
   777     using namespace _connectivity_bits;
   777 
   778 
   778     typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
   779     typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
   779 
   780 
   780     int compNum = 0;
   781     int compNum = 0;
   781     Visitor visitor(graph, compMap, compNum);
   782     Visitor visitor(graph, compMap, compNum);
   811     checkConcept<concepts::Graph, Graph>();
   812     checkConcept<concepts::Graph, Graph>();
   812     typedef typename Graph::Node Node;
   813     typedef typename Graph::Node Node;
   813     typedef typename Graph::NodeIt NodeIt;
   814     typedef typename Graph::NodeIt NodeIt;
   814     checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
   815     checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
   815 
   816 
   816     using namespace _topology_bits;
   817     using namespace _connectivity_bits;
   817 
   818 
   818     typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
   819     typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
   819 
   820 
   820     int cutNum = 0;
   821     int cutNum = 0;
   821     Visitor visitor(graph, cutMap, cutNum);
   822     Visitor visitor(graph, cutMap, cutNum);
   830       }
   831       }
   831     }
   832     }
   832     return cutNum;
   833     return cutNum;
   833   }
   834   }
   834 
   835 
   835   namespace _topology_bits {
   836   namespace _connectivity_bits {
   836 
   837 
   837     template <typename Digraph>
   838     template <typename Digraph>
   838     class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   839     class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   839     public:
   840     public:
   840       typedef typename Digraph::Node Node;
   841       typedef typename Digraph::Node Node;
  1051   template <typename Graph>
  1052   template <typename Graph>
  1052   int countBiEdgeConnectedComponents(const Graph& graph) {
  1053   int countBiEdgeConnectedComponents(const Graph& graph) {
  1053     checkConcept<concepts::Graph, Graph>();
  1054     checkConcept<concepts::Graph, Graph>();
  1054     typedef typename Graph::NodeIt NodeIt;
  1055     typedef typename Graph::NodeIt NodeIt;
  1055 
  1056 
  1056     using namespace _topology_bits;
  1057     using namespace _connectivity_bits;
  1057 
  1058 
  1058     typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
  1059     typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
  1059 
  1060 
  1060     int compNum = 0;
  1061     int compNum = 0;
  1061     Visitor visitor(graph, compNum);
  1062     Visitor visitor(graph, compNum);
  1093     checkConcept<concepts::Graph, Graph>();
  1094     checkConcept<concepts::Graph, Graph>();
  1094     typedef typename Graph::NodeIt NodeIt;
  1095     typedef typename Graph::NodeIt NodeIt;
  1095     typedef typename Graph::Node Node;
  1096     typedef typename Graph::Node Node;
  1096     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
  1097     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
  1097 
  1098 
  1098     using namespace _topology_bits;
  1099     using namespace _connectivity_bits;
  1099 
  1100 
  1100     typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
  1101     typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
  1101 
  1102 
  1102     int compNum = 0;
  1103     int compNum = 0;
  1103     Visitor visitor(graph, compMap, compNum);
  1104     Visitor visitor(graph, compMap, compNum);
  1134     checkConcept<concepts::Graph, Graph>();
  1135     checkConcept<concepts::Graph, Graph>();
  1135     typedef typename Graph::NodeIt NodeIt;
  1136     typedef typename Graph::NodeIt NodeIt;
  1136     typedef typename Graph::Edge Edge;
  1137     typedef typename Graph::Edge Edge;
  1137     checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
  1138     checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
  1138 
  1139 
  1139     using namespace _topology_bits;
  1140     using namespace _connectivity_bits;
  1140 
  1141 
  1141     typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
  1142     typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
  1142 
  1143 
  1143     int cutNum = 0;
  1144     int cutNum = 0;
  1144     Visitor visitor(graph, cutMap, cutNum);
  1145     Visitor visitor(graph, cutMap, cutNum);
  1154     }
  1155     }
  1155     return cutNum;
  1156     return cutNum;
  1156   }
  1157   }
  1157 
  1158 
  1158 
  1159 
  1159   namespace _topology_bits {
  1160   namespace _connectivity_bits {
  1160 
  1161 
  1161     template <typename Digraph, typename IntNodeMap>
  1162     template <typename Digraph, typename IntNodeMap>
  1162     class TopologicalSortVisitor : public DfsVisitor<Digraph> {
  1163     class TopologicalSortVisitor : public DfsVisitor<Digraph> {
  1163     public:
  1164     public:
  1164       typedef typename Digraph::Node Node;
  1165       typedef typename Digraph::Node Node;
  1191   ///
  1192   ///
  1192   /// \see checkedTopologicalSort
  1193   /// \see checkedTopologicalSort
  1193   /// \see dag
  1194   /// \see dag
  1194   template <typename Digraph, typename NodeMap>
  1195   template <typename Digraph, typename NodeMap>
  1195   void topologicalSort(const Digraph& graph, NodeMap& order) {
  1196   void topologicalSort(const Digraph& graph, NodeMap& order) {
  1196     using namespace _topology_bits;
  1197     using namespace _connectivity_bits;
  1197 
  1198 
  1198     checkConcept<concepts::Digraph, Digraph>();
  1199     checkConcept<concepts::Digraph, Digraph>();
  1199     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
  1200     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
  1200 
  1201 
  1201     typedef typename Digraph::Node Node;
  1202     typedef typename Digraph::Node Node;
  1232   /// \return %False when the graph is not DAG.
  1233   /// \return %False when the graph is not DAG.
  1233   ///
  1234   ///
  1234   /// \see topologicalSort
  1235   /// \see topologicalSort
  1235   /// \see dag
  1236   /// \see dag
  1236   template <typename Digraph, typename NodeMap>
  1237   template <typename Digraph, typename NodeMap>
  1237   bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
  1238   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
  1238     using namespace _topology_bits;
  1239     using namespace _connectivity_bits;
  1239 
  1240 
  1240     checkConcept<concepts::Digraph, Digraph>();
  1241     checkConcept<concepts::Digraph, Digraph>();
  1241     checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
  1242     checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
  1242       NodeMap>();
  1243       NodeMap>();
  1243 
  1244 
  1244     typedef typename Digraph::Node Node;
  1245     typedef typename Digraph::Node Node;
  1245     typedef typename Digraph::NodeIt NodeIt;
  1246     typedef typename Digraph::NodeIt NodeIt;
  1246     typedef typename Digraph::Arc Arc;
  1247     typedef typename Digraph::Arc Arc;
  1247 
  1248 
  1248     order = constMap<Node, int, -1>();
  1249     for (NodeIt it(digraph); it != INVALID; ++it) {
       
  1250       order.set(it, -1);
       
  1251     }
  1249 
  1252 
  1250     TopologicalSortVisitor<Digraph, NodeMap>
  1253     TopologicalSortVisitor<Digraph, NodeMap>
  1251       visitor(order, countNodes(graph));
  1254       visitor(order, countNodes(digraph));
  1252 
  1255 
  1253     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1256     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1254       dfs(graph, visitor);
  1257       dfs(digraph, visitor);
  1255 
  1258 
  1256     dfs.init();
  1259     dfs.init();
  1257     for (NodeIt it(graph); it != INVALID; ++it) {
  1260     for (NodeIt it(digraph); it != INVALID; ++it) {
  1258       if (!dfs.reached(it)) {
  1261       if (!dfs.reached(it)) {
  1259         dfs.addSource(it);
  1262         dfs.addSource(it);
  1260         while (!dfs.emptyQueue()) {
  1263         while (!dfs.emptyQueue()) {
  1261            Arc edge = dfs.nextArc();
  1264            Arc arc = dfs.nextArc();
  1262            Node target = graph.target(edge);
  1265            Node target = digraph.target(arc);
  1263            if (dfs.reached(target) && order[target] == -1) {
  1266            if (dfs.reached(target) && order[target] == -1) {
  1264              return false;
  1267              return false;
  1265            }
  1268            }
  1266            dfs.processNextArc();
  1269            dfs.processNextArc();
  1267          }
  1270          }
  1277   /// Check that the given directed graph is a DAG. The DAG is
  1280   /// Check that the given directed graph is a DAG. The DAG is
  1278   /// an Directed Acyclic Digraph.
  1281   /// an Directed Acyclic Digraph.
  1279   /// \return %False when the graph is not DAG.
  1282   /// \return %False when the graph is not DAG.
  1280   /// \see acyclic
  1283   /// \see acyclic
  1281   template <typename Digraph>
  1284   template <typename Digraph>
  1282   bool dag(const Digraph& graph) {
  1285   bool dag(const Digraph& digraph) {
  1283 
  1286 
  1284     checkConcept<concepts::Digraph, Digraph>();
  1287     checkConcept<concepts::Digraph, Digraph>();
  1285 
  1288 
  1286     typedef typename Digraph::Node Node;
  1289     typedef typename Digraph::Node Node;
  1287     typedef typename Digraph::NodeIt NodeIt;
  1290     typedef typename Digraph::NodeIt NodeIt;
  1288     typedef typename Digraph::Arc Arc;
  1291     typedef typename Digraph::Arc Arc;
  1289 
  1292 
  1290     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
  1293     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
  1291 
  1294 
  1292     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
  1295     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
  1293       Create dfs(graph);
  1296       Create dfs(digraph);
  1294 
  1297 
  1295     ProcessedMap processed(graph);
  1298     ProcessedMap processed(digraph);
  1296     dfs.processedMap(processed);
  1299     dfs.processedMap(processed);
  1297 
  1300 
  1298     dfs.init();
  1301     dfs.init();
  1299     for (NodeIt it(graph); it != INVALID; ++it) {
  1302     for (NodeIt it(digraph); it != INVALID; ++it) {
  1300       if (!dfs.reached(it)) {
  1303       if (!dfs.reached(it)) {
  1301         dfs.addSource(it);
  1304         dfs.addSource(it);
  1302         while (!dfs.emptyQueue()) {
  1305         while (!dfs.emptyQueue()) {
  1303           Arc edge = dfs.nextArc();
  1306           Arc edge = dfs.nextArc();
  1304           Node target = graph.target(edge);
  1307           Node target = digraph.target(edge);
  1305           if (dfs.reached(target) && !processed[target]) {
  1308           if (dfs.reached(target) && !processed[target]) {
  1306             return false;
  1309             return false;
  1307           }
  1310           }
  1308           dfs.processNextArc();
  1311           dfs.processNextArc();
  1309         }
  1312         }
  1378       }
  1381       }
  1379     }
  1382     }
  1380     return true;
  1383     return true;
  1381   }
  1384   }
  1382 
  1385 
  1383   namespace _topology_bits {
  1386   namespace _connectivity_bits {
  1384 
  1387 
  1385     template <typename Digraph>
  1388     template <typename Digraph>
  1386     class BipartiteVisitor : public BfsVisitor<Digraph> {
  1389     class BipartiteVisitor : public BfsVisitor<Digraph> {
  1387     public:
  1390     public:
  1388       typedef typename Digraph::Arc Arc;
  1391       typedef typename Digraph::Arc Arc;
  1447   /// \param graph The undirected graph.
  1450   /// \param graph The undirected graph.
  1448   /// \return %True if \c graph is bipartite, %false otherwise.
  1451   /// \return %True if \c graph is bipartite, %false otherwise.
  1449   /// \sa bipartitePartitions
  1452   /// \sa bipartitePartitions
  1450   template<typename Graph>
  1453   template<typename Graph>
  1451   inline bool bipartite(const Graph &graph){
  1454   inline bool bipartite(const Graph &graph){
  1452     using namespace _topology_bits;
  1455     using namespace _connectivity_bits;
  1453 
  1456 
  1454     checkConcept<concepts::Graph, Graph>();
  1457     checkConcept<concepts::Graph, Graph>();
  1455 
  1458 
  1456     typedef typename Graph::NodeIt NodeIt;
  1459     typedef typename Graph::NodeIt NodeIt;
  1457     typedef typename Graph::ArcIt ArcIt;
  1460     typedef typename Graph::ArcIt ArcIt;
  1487   /// \retval partMap A writable bool map of nodes. It will be set as the
  1490   /// \retval partMap A writable bool map of nodes. It will be set as the
  1488   /// two partitions of the graph.
  1491   /// two partitions of the graph.
  1489   /// \return %True if \c graph is bipartite, %false otherwise.
  1492   /// \return %True if \c graph is bipartite, %false otherwise.
  1490   template<typename Graph, typename NodeMap>
  1493   template<typename Graph, typename NodeMap>
  1491   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1494   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1492     using namespace _topology_bits;
  1495     using namespace _connectivity_bits;
  1493 
  1496 
  1494     checkConcept<concepts::Graph, Graph>();
  1497     checkConcept<concepts::Graph, Graph>();
  1495 
  1498 
  1496     typedef typename Graph::Node Node;
  1499     typedef typename Graph::Node Node;
  1497     typedef typename Graph::NodeIt NodeIt;
  1500     typedef typename Graph::NodeIt NodeIt;
  1518 
  1521 
  1519   /// \brief Returns true when there are not loop edges in the graph.
  1522   /// \brief Returns true when there are not loop edges in the graph.
  1520   ///
  1523   ///
  1521   /// Returns true when there are not loop edges in the graph.
  1524   /// Returns true when there are not loop edges in the graph.
  1522   template <typename Digraph>
  1525   template <typename Digraph>
  1523   bool loopFree(const Digraph& graph) {
  1526   bool loopFree(const Digraph& digraph) {
  1524     for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
  1527     for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
  1525       if (graph.source(it) == graph.target(it)) return false;
  1528       if (digraph.source(it) == digraph.target(it)) return false;
  1526     }
  1529     }
  1527     return true;
  1530     return true;
  1528   }
  1531   }
  1529 
  1532 
  1530   /// \brief Returns true when there are not parallel edges in the graph.
  1533   /// \brief Returns true when there are not parallel edges in the graph.
  1531   ///
  1534   ///
  1532   /// Returns true when there are not parallel edges in the graph.
  1535   /// Returns true when there are not parallel edges in the graph.
  1533   template <typename Digraph>
  1536   template <typename Digraph>
  1534   bool parallelFree(const Digraph& graph) {
  1537   bool parallelFree(const Digraph& digraph) {
  1535     typename Digraph::template NodeMap<bool> reached(graph, false);
  1538     typename Digraph::template NodeMap<bool> reached(digraph, false);
  1536     for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
  1539     for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
  1537       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1540       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
  1538         if (reached[graph.target(e)]) return false;
  1541         if (reached[digraph.target(a)]) return false;
  1539         reached.set(graph.target(e), true);
  1542         reached.set(digraph.target(a), true);
  1540       }
  1543       }
  1541       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1544       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
  1542         reached.set(graph.target(e), false);
  1545         reached.set(digraph.target(a), false);
  1543       }
  1546       }
  1544     }
  1547     }
  1545     return true;
  1548     return true;
  1546   }
  1549   }
  1547 
  1550 
  1549   /// edges in the graph.
  1552   /// edges in the graph.
  1550   ///
  1553   ///
  1551   /// Returns true when there are not loop edges and parallel edges in
  1554   /// Returns true when there are not loop edges and parallel edges in
  1552   /// the graph.
  1555   /// the graph.
  1553   template <typename Digraph>
  1556   template <typename Digraph>
  1554   bool simpleDigraph(const Digraph& graph) {
  1557   bool simpleDigraph(const Digraph& digraph) {
  1555     typename Digraph::template NodeMap<bool> reached(graph, false);
  1558     typename Digraph::template NodeMap<bool> reached(digraph, false);
  1556     for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
  1559     for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
  1557       reached.set(n, true);
  1560       reached.set(n, true);
  1558       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1561       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
  1559         if (reached[graph.target(e)]) return false;
  1562         if (reached[digraph.target(a)]) return false;
  1560         reached.set(graph.target(e), true);
  1563         reached.set(digraph.target(a), true);
  1561       }
  1564       }
  1562       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1565       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
  1563         reached.set(graph.target(e), false);
  1566         reached.set(digraph.target(a), false);
  1564       }
  1567       }
  1565       reached.set(n, false);
  1568       reached.set(n, false);
  1566     }
  1569     }
  1567     return true;
  1570     return true;
  1568   }
  1571   }
  1569 
  1572 
  1570 } //namespace lemon
  1573 } //namespace lemon
  1571 
  1574 
  1572 #endif //LEMON_TOPOLOGY_H
  1575 #endif //LEMON_CONNECTIVITY_H