478 } |
478 } |
479 |
479 |
480 namespace _topology_bits { |
480 namespace _topology_bits { |
481 |
481 |
482 template <typename Graph> |
482 template <typename Graph> |
483 class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { |
483 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
484 public: |
484 public: |
485 typedef typename Graph::Node Node; |
485 typedef typename Graph::Node Node; |
486 typedef typename Graph::Edge Edge; |
486 typedef typename Graph::Edge Edge; |
487 typedef typename Graph::UndirEdge UndirEdge; |
487 typedef typename Graph::UndirEdge UndirEdge; |
488 |
488 |
489 CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) |
489 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) |
490 : _graph(graph), _compNum(compNum), |
490 : _graph(graph), _compNum(compNum), |
491 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
491 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
492 |
492 |
493 void start(const Node& node) { |
493 void start(const Node& node) { |
494 _predMap.set(node, INVALID); |
494 _predMap.set(node, INVALID); |
536 typename Graph::template NodeMap<Node> _predMap; |
536 typename Graph::template NodeMap<Node> _predMap; |
537 int _num; |
537 int _num; |
538 }; |
538 }; |
539 |
539 |
540 template <typename Graph, typename EdgeMap> |
540 template <typename Graph, typename EdgeMap> |
541 class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { |
541 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
542 public: |
542 public: |
543 typedef typename Graph::Node Node; |
543 typedef typename Graph::Node Node; |
544 typedef typename Graph::Edge Edge; |
544 typedef typename Graph::Edge Edge; |
545 typedef typename Graph::UndirEdge UndirEdge; |
545 typedef typename Graph::UndirEdge UndirEdge; |
546 |
546 |
547 NodeBiconnectedComponentsVisitor(const Graph& graph, |
547 BiNodeConnectedComponentsVisitor(const Graph& graph, |
548 EdgeMap& compMap, int &compNum) |
548 EdgeMap& compMap, int &compNum) |
549 : _graph(graph), _compMap(compMap), _compNum(compNum), |
549 : _graph(graph), _compMap(compMap), _compNum(compNum), |
550 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
550 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
551 |
551 |
552 void start(const Node& node) { |
552 void start(const Node& node) { |
616 int _num; |
616 int _num; |
617 }; |
617 }; |
618 |
618 |
619 |
619 |
620 template <typename Graph, typename NodeMap> |
620 template <typename Graph, typename NodeMap> |
621 class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> { |
621 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> { |
622 public: |
622 public: |
623 typedef typename Graph::Node Node; |
623 typedef typename Graph::Node Node; |
624 typedef typename Graph::Edge Edge; |
624 typedef typename Graph::Edge Edge; |
625 typedef typename Graph::UndirEdge UndirEdge; |
625 typedef typename Graph::UndirEdge UndirEdge; |
626 |
626 |
627 NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, |
627 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, |
628 int& cutNum) |
628 int& cutNum) |
629 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
629 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
630 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
630 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
631 |
631 |
632 void start(const Node& node) { |
632 void start(const Node& node) { |
709 /// \param graph The graph. |
709 /// \param graph The graph. |
710 /// \return %True when the graph bi-node-connected. |
710 /// \return %True when the graph bi-node-connected. |
711 /// \todo Make it faster. |
711 /// \todo Make it faster. |
712 template <typename UndirGraph> |
712 template <typename UndirGraph> |
713 bool biNodeConnected(const UndirGraph& graph) { |
713 bool biNodeConnected(const UndirGraph& graph) { |
714 return countNodeBiconnectedComponents(graph) == 1; |
714 return countBiNodeConnectedComponents(graph) == 1; |
715 } |
715 } |
716 |
716 |
717 /// \ingroup topology |
717 /// \ingroup topology |
718 /// |
718 /// |
719 /// \brief Count the biconnected components. |
719 /// \brief Count the biconnected components. |
724 /// when they are on same circle. |
724 /// when they are on same circle. |
725 /// |
725 /// |
726 /// \param graph The graph. |
726 /// \param graph The graph. |
727 /// \return The number of components. |
727 /// \return The number of components. |
728 template <typename UndirGraph> |
728 template <typename UndirGraph> |
729 int countNodeBiconnectedComponents(const UndirGraph& graph) { |
729 int countBiNodeConnectedComponents(const UndirGraph& graph) { |
730 checkConcept<concept::UndirGraph, UndirGraph>(); |
730 checkConcept<concept::UndirGraph, UndirGraph>(); |
731 typedef typename UndirGraph::NodeIt NodeIt; |
731 typedef typename UndirGraph::NodeIt NodeIt; |
732 |
732 |
733 using namespace _topology_bits; |
733 using namespace _topology_bits; |
734 |
734 |
735 typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor; |
735 typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor; |
736 |
736 |
737 int compNum = 0; |
737 int compNum = 0; |
738 Visitor visitor(graph, compNum); |
738 Visitor visitor(graph, compNum); |
739 |
739 |
740 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
740 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
776 typedef typename UndirGraph::UndirEdge UndirEdge; |
776 typedef typename UndirGraph::UndirEdge UndirEdge; |
777 checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>(); |
777 checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>(); |
778 |
778 |
779 using namespace _topology_bits; |
779 using namespace _topology_bits; |
780 |
780 |
781 typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor; |
781 typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor; |
782 |
782 |
783 int compNum = 0; |
783 int compNum = 0; |
784 Visitor visitor(graph, compMap, compNum); |
784 Visitor visitor(graph, compMap, compNum); |
785 |
785 |
786 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
786 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
816 typedef typename UndirGraph::NodeIt NodeIt; |
816 typedef typename UndirGraph::NodeIt NodeIt; |
817 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); |
817 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); |
818 |
818 |
819 using namespace _topology_bits; |
819 using namespace _topology_bits; |
820 |
820 |
821 typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor; |
821 typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor; |
822 |
822 |
823 int cutNum = 0; |
823 int cutNum = 0; |
824 Visitor visitor(graph, cutMap, cutNum); |
824 Visitor visitor(graph, cutMap, cutNum); |
825 |
825 |
826 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
826 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
836 } |
836 } |
837 |
837 |
838 namespace _topology_bits { |
838 namespace _topology_bits { |
839 |
839 |
840 template <typename Graph> |
840 template <typename Graph> |
841 class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { |
841 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
842 public: |
842 public: |
843 typedef typename Graph::Node Node; |
843 typedef typename Graph::Node Node; |
844 typedef typename Graph::Edge Edge; |
844 typedef typename Graph::Edge Edge; |
845 typedef typename Graph::UndirEdge UndirEdge; |
845 typedef typename Graph::UndirEdge UndirEdge; |
846 |
846 |
847 CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) |
847 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) |
848 : _graph(graph), _compNum(compNum), |
848 : _graph(graph), _compNum(compNum), |
849 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
849 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
850 |
850 |
851 void start(const Node& node) { |
851 void start(const Node& node) { |
852 _predMap.set(node, INVALID); |
852 _predMap.set(node, INVALID); |
892 typename Graph::template NodeMap<Edge> _predMap; |
892 typename Graph::template NodeMap<Edge> _predMap; |
893 int _num; |
893 int _num; |
894 }; |
894 }; |
895 |
895 |
896 template <typename Graph, typename NodeMap> |
896 template <typename Graph, typename NodeMap> |
897 class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { |
897 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
898 public: |
898 public: |
899 typedef typename Graph::Node Node; |
899 typedef typename Graph::Node Node; |
900 typedef typename Graph::Edge Edge; |
900 typedef typename Graph::Edge Edge; |
901 typedef typename Graph::UndirEdge UndirEdge; |
901 typedef typename Graph::UndirEdge UndirEdge; |
902 |
902 |
903 EdgeBiconnectedComponentsVisitor(const Graph& graph, |
903 BiEdgeConnectedComponentsVisitor(const Graph& graph, |
904 NodeMap& compMap, int &compNum) |
904 NodeMap& compMap, int &compNum) |
905 : _graph(graph), _compMap(compMap), _compNum(compNum), |
905 : _graph(graph), _compMap(compMap), _compNum(compNum), |
906 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
906 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
907 |
907 |
908 void start(const Node& node) { |
908 void start(const Node& node) { |
959 int _num; |
959 int _num; |
960 }; |
960 }; |
961 |
961 |
962 |
962 |
963 template <typename Graph, typename EdgeMap> |
963 template <typename Graph, typename EdgeMap> |
964 class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> { |
964 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> { |
965 public: |
965 public: |
966 typedef typename Graph::Node Node; |
966 typedef typename Graph::Node Node; |
967 typedef typename Graph::Edge Edge; |
967 typedef typename Graph::Edge Edge; |
968 typedef typename Graph::UndirEdge UndirEdge; |
968 typedef typename Graph::UndirEdge UndirEdge; |
969 |
969 |
970 EdgeBiconnectedCutEdgesVisitor(const Graph& graph, |
970 BiEdgeConnectedCutEdgesVisitor(const Graph& graph, |
971 EdgeMap& cutMap, int &cutNum) |
971 EdgeMap& cutMap, int &cutNum) |
972 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
972 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
973 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
973 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
974 |
974 |
975 void start(const Node& node) { |
975 void start(const Node& node) { |
1036 /// \param graph The undirected graph. |
1036 /// \param graph The undirected graph. |
1037 /// \return The number of components. |
1037 /// \return The number of components. |
1038 /// \todo Make it faster. |
1038 /// \todo Make it faster. |
1039 template <typename UndirGraph> |
1039 template <typename UndirGraph> |
1040 bool biEdgeConnected(const UndirGraph& graph) { |
1040 bool biEdgeConnected(const UndirGraph& graph) { |
1041 return countEdgeBiconnectedComponents(graph) == 1; |
1041 return countBiEdgeConnectedComponents(graph) == 1; |
1042 } |
1042 } |
1043 |
1043 |
1044 /// \ingroup topology |
1044 /// \ingroup topology |
1045 /// |
1045 /// |
1046 /// \brief Count the bi-edge-connected components. |
1046 /// \brief Count the bi-edge-connected components. |
1051 /// connected with at least two edge-disjoint paths. |
1051 /// connected with at least two edge-disjoint paths. |
1052 /// |
1052 /// |
1053 /// \param graph The undirected graph. |
1053 /// \param graph The undirected graph. |
1054 /// \return The number of components. |
1054 /// \return The number of components. |
1055 template <typename UndirGraph> |
1055 template <typename UndirGraph> |
1056 int countEdgeBiconnectedComponents(const UndirGraph& graph) { |
1056 int countBiEdgeConnectedComponents(const UndirGraph& graph) { |
1057 checkConcept<concept::UndirGraph, UndirGraph>(); |
1057 checkConcept<concept::UndirGraph, UndirGraph>(); |
1058 typedef typename UndirGraph::NodeIt NodeIt; |
1058 typedef typename UndirGraph::NodeIt NodeIt; |
1059 |
1059 |
1060 using namespace _topology_bits; |
1060 using namespace _topology_bits; |
1061 |
1061 |
1062 typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor; |
1062 typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor; |
1063 |
1063 |
1064 int compNum = 0; |
1064 int compNum = 0; |
1065 Visitor visitor(graph, compNum); |
1065 Visitor visitor(graph, compNum); |
1066 |
1066 |
1067 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1067 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1102 typedef typename UndirGraph::Node Node; |
1102 typedef typename UndirGraph::Node Node; |
1103 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
1103 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
1104 |
1104 |
1105 using namespace _topology_bits; |
1105 using namespace _topology_bits; |
1106 |
1106 |
1107 typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor; |
1107 typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor; |
1108 |
1108 |
1109 int compNum = 0; |
1109 int compNum = 0; |
1110 Visitor visitor(graph, compMap, compNum); |
1110 Visitor visitor(graph, compMap, compNum); |
1111 |
1111 |
1112 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1112 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1143 typedef typename UndirGraph::UndirEdge UndirEdge; |
1143 typedef typename UndirGraph::UndirEdge UndirEdge; |
1144 checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>(); |
1144 checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>(); |
1145 |
1145 |
1146 using namespace _topology_bits; |
1146 using namespace _topology_bits; |
1147 |
1147 |
1148 typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor; |
1148 typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor; |
1149 |
1149 |
1150 int cutNum = 0; |
1150 int cutNum = 0; |
1151 Visitor visitor(graph, cutMap, cutNum); |
1151 Visitor visitor(graph, cutMap, cutNum); |
1152 |
1152 |
1153 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1153 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1386 return true; |
1386 return true; |
1387 } |
1387 } |
1388 |
1388 |
1389 /// \ingroup topology |
1389 /// \ingroup topology |
1390 /// |
1390 /// |
1391 /// \brief Check that the given undirected graph is bipartite. |
1391 /// \brief Check if the given undirected graph is bipartite or not |
1392 /// |
1392 /// |
1393 /// Check that the given undirected graph is bipartite. |
1393 /// The function checks if the given undirected \c graph graph is bipartite |
|
1394 /// or not. The \ref Bfs algorithm is used to calculate the result. |
1394 /// \param graph The undirected graph. |
1395 /// \param graph The undirected graph. |
1395 /// \return %True when the nodes can be separated into two sets that |
1396 /// \return %True if \c graph is bipartite, %false otherwise. |
1396 /// there are not connected nodes in neither sets. |
1397 /// \sa bipartitePartitions |
1397 template <typename UndirGraph> |
1398 /// |
1398 bool bipartite(const UndirGraph& graph) { |
1399 /// \author Balazs Attila Mihaly |
|
1400 template<typename UndirGraph> |
|
1401 inline bool bipartite(const UndirGraph &graph){ |
1399 checkConcept<concept::UndirGraph, UndirGraph>(); |
1402 checkConcept<concept::UndirGraph, UndirGraph>(); |
|
1403 |
|
1404 typedef typename UndirGraph::NodeIt NodeIt; |
|
1405 typedef typename UndirGraph::EdgeIt EdgeIt; |
|
1406 |
|
1407 Bfs<UndirGraph> bfs(graph); |
|
1408 bfs.init(); |
|
1409 for(NodeIt i(graph);i!=INVALID;++i){ |
|
1410 if(!bfs.reached(i)){ |
|
1411 bfs.run(i); |
|
1412 } |
|
1413 } |
|
1414 for(EdgeIt i(graph);i!=INVALID;++i){ |
|
1415 if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false; |
|
1416 } |
|
1417 return true; |
|
1418 }; |
|
1419 |
|
1420 /// \ingroup topology |
|
1421 /// |
|
1422 /// \brief Check if the given undirected graph is bipartite or not |
|
1423 /// |
|
1424 /// The function checks if the given undirected graph is bipartite |
|
1425 /// or not. The \ref Bfs algorithm is used to calculate the result. |
|
1426 /// During the execution, the \c partMap will be set as the two |
|
1427 /// partitions of the graph. |
|
1428 /// \param graph The undirected graph. |
|
1429 /// \retval partMap A writeable bool map of nodes. It will be set as the |
|
1430 /// two partitions of the graph. |
|
1431 /// \return %True if \c graph is bipartite, %false otherwise. |
|
1432 /// |
|
1433 /// \author Balazs Attila Mihaly |
|
1434 /// |
|
1435 /// \image html bipartite_partitions.png |
|
1436 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
|
1437 template<typename UndirGraph, typename NodeMap> |
|
1438 inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){ |
|
1439 checkConcept<concept::UndirGraph, UndirGraph>(); |
|
1440 |
1400 typedef typename UndirGraph::Node Node; |
1441 typedef typename UndirGraph::Node Node; |
1401 typedef typename UndirGraph::NodeIt NodeIt; |
1442 typedef typename UndirGraph::NodeIt NodeIt; |
1402 typedef typename UndirGraph::Edge Edge; |
1443 typedef typename UndirGraph::EdgeIt EdgeIt; |
1403 if (NodeIt(graph) == INVALID) return false; |
1444 |
1404 Dfs<UndirGraph> dfs(graph); |
1445 Bfs<UndirGraph> bfs(graph); |
1405 dfs.init(); |
1446 bfs.init(); |
1406 typename UndirGraph::template NodeMap<bool> red(graph); |
1447 for(NodeIt i(graph);i!=INVALID;++i){ |
1407 for (NodeIt it(graph); it != INVALID; ++it) { |
1448 if(!bfs.reached(i)){ |
1408 if (!dfs.reached(it)) { |
1449 bfs.addSource(i); |
1409 dfs.addSource(it); |
1450 for(Node j=bfs.processNextNode();!bfs.emptyQueue(); |
1410 red[it] = true; |
1451 j=bfs.processNextNode()){ |
1411 while (!dfs.emptyQueue()) { |
1452 partMap.set(j,bfs.dist(j)%2==0); |
1412 Edge edge = dfs.nextEdge(); |
1453 } |
1413 Node source = graph.source(edge); |
1454 } |
1414 Node target = graph.target(edge); |
1455 } |
1415 if (dfs.reached(target) && red[source] == red[target]) { |
1456 for(EdgeIt i(graph);i!=INVALID;++i){ |
1416 return false; |
1457 if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false; |
1417 } else { |
|
1418 red[target] = !red[source]; |
|
1419 } |
|
1420 dfs.processNextEdge(); |
|
1421 } |
|
1422 } |
|
1423 } |
1458 } |
1424 return true; |
1459 return true; |
1425 } |
1460 }; |
1426 |
1461 |
1427 } //namespace lemon |
1462 } //namespace lemon |
1428 |
1463 |
1429 #endif //LEMON_TOPOLOGY_H |
1464 #endif //LEMON_TOPOLOGY_H |