Changeset 1800:d391ea416aa0 in lemon-0.x
- Timestamp:
- 11/16/05 10:10:24 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2343
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/topology.h
r1793 r1800 481 481 482 482 template <typename Graph> 483 class Count NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {483 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { 484 484 public: 485 485 typedef typename Graph::Node Node; … … 487 487 typedef typename Graph::UndirEdge UndirEdge; 488 488 489 Count NodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)489 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) 490 490 : _graph(graph), _compNum(compNum), 491 491 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} … … 539 539 540 540 template <typename Graph, typename EdgeMap> 541 class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {541 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { 542 542 public: 543 543 typedef typename Graph::Node Node; … … 545 545 typedef typename Graph::UndirEdge UndirEdge; 546 546 547 NodeBiconnectedComponentsVisitor(const Graph& graph,547 BiNodeConnectedComponentsVisitor(const Graph& graph, 548 548 EdgeMap& compMap, int &compNum) 549 549 : _graph(graph), _compMap(compMap), _compNum(compNum), … … 619 619 620 620 template <typename Graph, typename NodeMap> 621 class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {621 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> { 622 622 public: 623 623 typedef typename Graph::Node Node; … … 625 625 typedef typename Graph::UndirEdge UndirEdge; 626 626 627 NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,627 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, 628 628 int& cutNum) 629 629 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), … … 697 697 698 698 template <typename UndirGraph> 699 int count NodeBiconnectedComponents(const UndirGraph& graph);699 int countBiNodeConnectedComponents(const UndirGraph& graph); 700 700 701 701 /// \ingroup topology … … 712 712 template <typename UndirGraph> 713 713 bool biNodeConnected(const UndirGraph& graph) { 714 return count NodeBiconnectedComponents(graph) == 1;714 return countBiNodeConnectedComponents(graph) == 1; 715 715 } 716 716 … … 727 727 /// \return The number of components. 728 728 template <typename UndirGraph> 729 int count NodeBiconnectedComponents(const UndirGraph& graph) {729 int countBiNodeConnectedComponents(const UndirGraph& graph) { 730 730 checkConcept<concept::UndirGraph, UndirGraph>(); 731 731 typedef typename UndirGraph::NodeIt NodeIt; … … 733 733 using namespace _topology_bits; 734 734 735 typedef Count NodeBiconnectedComponentsVisitor<UndirGraph> Visitor;735 typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor; 736 736 737 737 int compNum = 0; … … 779 779 using namespace _topology_bits; 780 780 781 typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;781 typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor; 782 782 783 783 int compNum = 0; … … 819 819 using namespace _topology_bits; 820 820 821 typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;821 typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor; 822 822 823 823 int cutNum = 0; … … 839 839 840 840 template <typename Graph> 841 class Count EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {841 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { 842 842 public: 843 843 typedef typename Graph::Node Node; … … 845 845 typedef typename Graph::UndirEdge UndirEdge; 846 846 847 Count EdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)847 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) 848 848 : _graph(graph), _compNum(compNum), 849 849 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} … … 895 895 896 896 template <typename Graph, typename NodeMap> 897 class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {897 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { 898 898 public: 899 899 typedef typename Graph::Node Node; … … 901 901 typedef typename Graph::UndirEdge UndirEdge; 902 902 903 EdgeBiconnectedComponentsVisitor(const Graph& graph,903 BiEdgeConnectedComponentsVisitor(const Graph& graph, 904 904 NodeMap& compMap, int &compNum) 905 905 : _graph(graph), _compMap(compMap), _compNum(compNum), … … 962 962 963 963 template <typename Graph, typename EdgeMap> 964 class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {964 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> { 965 965 public: 966 966 typedef typename Graph::Node Node; … … 968 968 typedef typename Graph::UndirEdge UndirEdge; 969 969 970 EdgeBiconnectedCutEdgesVisitor(const Graph& graph,970 BiEdgeConnectedCutEdgesVisitor(const Graph& graph, 971 971 EdgeMap& cutMap, int &cutNum) 972 972 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), … … 1024 1024 1025 1025 template <typename UndirGraph> 1026 int count EdgeBiconnectedComponents(const UndirGraph& graph);1026 int countbiEdgeConnectedComponents(const UndirGraph& graph); 1027 1027 1028 1028 /// \ingroup topology … … 1039 1039 template <typename UndirGraph> 1040 1040 bool biEdgeConnected(const UndirGraph& graph) { 1041 return count EdgeBiconnectedComponents(graph) == 1;1041 return countBiEdgeConnectedComponents(graph) == 1; 1042 1042 } 1043 1043 … … 1054 1054 /// \return The number of components. 1055 1055 template <typename UndirGraph> 1056 int count EdgeBiconnectedComponents(const UndirGraph& graph) {1056 int countBiEdgeConnectedComponents(const UndirGraph& graph) { 1057 1057 checkConcept<concept::UndirGraph, UndirGraph>(); 1058 1058 typedef typename UndirGraph::NodeIt NodeIt; … … 1060 1060 using namespace _topology_bits; 1061 1061 1062 typedef Count EdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;1062 typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor; 1063 1063 1064 1064 int compNum = 0; … … 1105 1105 using namespace _topology_bits; 1106 1106 1107 typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;1107 typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor; 1108 1108 1109 1109 int compNum = 0; … … 1146 1146 using namespace _topology_bits; 1147 1147 1148 typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;1148 typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor; 1149 1149 1150 1150 int cutNum = 0; … … 1389 1389 /// \ingroup topology 1390 1390 /// 1391 /// \brief Check that the given undirected graph is bipartite. 1392 /// 1393 /// Check that the given undirected graph is bipartite. 1391 /// \brief Check if the given undirected graph is bipartite or not 1392 /// 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 1395 /// \param graph The undirected graph. 1395 /// \return %True when the nodes can be separated into two sets that 1396 /// there are not connected nodes in neither sets. 1397 template <typename UndirGraph> 1398 bool bipartite(const UndirGraph& graph) { 1396 /// \return %True if \c graph is bipartite, %false otherwise. 1397 /// \sa bipartitePartitions 1398 /// 1399 /// \author Balazs Attila Mihaly 1400 template<typename UndirGraph> 1401 inline bool bipartite(const UndirGraph &graph){ 1399 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 1441 typedef typename UndirGraph::Node Node; 1401 1442 typedef typename UndirGraph::NodeIt NodeIt; 1402 typedef typename UndirGraph::Edge Edge; 1403 if (NodeIt(graph) == INVALID) return false; 1404 Dfs<UndirGraph> dfs(graph); 1405 dfs.init(); 1406 typename UndirGraph::template NodeMap<bool> red(graph); 1407 for (NodeIt it(graph); it != INVALID; ++it) { 1408 if (!dfs.reached(it)) { 1409 dfs.addSource(it); 1410 red[it] = true; 1411 while (!dfs.emptyQueue()) { 1412 Edge edge = dfs.nextEdge(); 1413 Node source = graph.source(edge); 1414 Node target = graph.target(edge); 1415 if (dfs.reached(target) && red[source] == red[target]) { 1416 return false; 1417 } else { 1418 red[target] = !red[source]; 1419 } 1420 dfs.processNextEdge(); 1421 } 1422 } 1443 typedef typename UndirGraph::EdgeIt EdgeIt; 1444 1445 Bfs<UndirGraph> bfs(graph); 1446 bfs.init(); 1447 for(NodeIt i(graph);i!=INVALID;++i){ 1448 if(!bfs.reached(i)){ 1449 bfs.addSource(i); 1450 for(Node j=bfs.processNextNode();!bfs.emptyQueue(); 1451 j=bfs.processNextNode()){ 1452 partMap.set(j,bfs.dist(j)%2==0); 1453 } 1454 } 1455 } 1456 for(EdgeIt i(graph);i!=INVALID;++i){ 1457 if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false; 1423 1458 } 1424 1459 return true; 1425 } 1460 }; 1426 1461 1427 1462 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.