Changeset 1991:d7442141d9ef in lemon-0.x
- Timestamp:
- 03/01/06 11:25:30 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2593
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/edge_set_extender.h
r1979 r1991 69 69 public: 70 70 71 using Parent::getNotifier; 72 71 73 /// \brief Gives back the edge alteration notifier. 72 74 /// … … 323 325 324 326 public: 327 328 using Parent::getNotifier; 325 329 326 330 EdgeNotifier& getNotifier(Edge) const { -
lemon/bits/graph_extender.h
r1983 r1991 1569 1569 1570 1570 template <typename _Value> 1571 class NodeMapBase : public NodeNotifier::ObserverBase{1571 class NodeMapBase { 1572 1572 public: 1573 1573 typedef BpUGraphExtender Graph; … … 1591 1591 1592 1592 NodeMapBase(const Graph& _g) 1593 : graph(&_g), bNodeMap(_g), aNodeMap(_g) { 1594 NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 1595 } 1593 : aNodeMap(_g), bNodeMap(_g) {} 1596 1594 NodeMapBase(const Graph& _g, const _Value& _v) 1597 : graph(&_g), bNodeMap(_g, _v), 1598 aNodeMap(_g, _v) { 1599 NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 1600 } 1601 1602 virtual ~NodeMapBase() { 1603 if (NodeNotifier::ObserverBase::attached()) { 1604 NodeNotifier::ObserverBase::detach(); 1605 } 1606 } 1607 1595 : aNodeMap(_g, _v), bNodeMap(_g, _v) {} 1596 1608 1597 ConstReference operator[](const Key& node) const { 1609 1598 if (Parent::aNode(node)) { … … 1630 1619 } 1631 1620 1632 protected: 1633 1634 virtual void add(const Node&) {} 1635 virtual void add(const std::vector<Node>&) {} 1636 virtual void erase(const Node&) {} 1637 virtual void erase(const std::vector<Node>&) {} 1638 virtual void clear() {} 1639 virtual void build() {} 1640 1641 const Graph* getGraph() const { return graph; } 1642 1621 const Graph* getGraph() const { 1622 return aNodeMap.getGraph(); 1623 } 1624 1643 1625 private: 1644 const Graph* graph;1626 ANodeMap<_Value> aNodeMap; 1645 1627 BNodeMap<_Value> bNodeMap; 1646 ANodeMap<_Value> aNodeMap;1647 1628 }; 1648 1629 -
lemon/graph_adaptor.h
r1989 r1991 114 114 int id(const Node& v) const { return graph->id(v); } 115 115 int id(const Edge& e) const { return graph->id(e); } 116 117 int maxNodeId() const { 118 return graph->maxNodeId(); 119 } 120 121 int maxEdgeId() const { 122 return graph->maxEdgeId(); 123 } 124 125 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 126 127 NodeNotifier& getNotifier(Node) const { 128 return graph->getNotifier(Node()); 129 } 130 131 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 132 133 EdgeNotifier& getNotifier(Edge) const { 134 return graph->getNotifier(Edge()); 135 } 116 136 117 137 template <typename _Value> … … 119 139 public: 120 140 typedef typename _Graph::template NodeMap<_Value> Parent; 121 explicit NodeMap(const GraphAdaptorBase<_Graph>& g w)122 : Parent(*g w.graph) { }123 NodeMap(const GraphAdaptorBase<_Graph>& g w, const _Value& value)124 : Parent(*g w.graph, value) { }141 explicit NodeMap(const GraphAdaptorBase<_Graph>& ga) 142 : Parent(*ga.graph) { } 143 NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value) 144 : Parent(*ga.graph, value) { } 125 145 }; 126 146 … … 129 149 public: 130 150 typedef typename _Graph::template EdgeMap<_Value> Parent; 131 explicit EdgeMap(const GraphAdaptorBase<_Graph>& g w)132 : Parent(*g w.graph) { }133 EdgeMap(const GraphAdaptorBase<_Graph>& g w, const _Value& value)134 : Parent(*g w.graph, value) { }151 explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga) 152 : Parent(*ga.graph) { } 153 EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value) 154 : Parent(*ga.graph, value) { } 135 155 }; 136 156 … … 150 170 }; 151 171 172 /// \brief Just gives back a graph adaptor 173 /// 174 /// Just gives back a graph adaptor which 175 /// should be provide original graph 176 template<typename Graph> 177 GraphAdaptor<const Graph> 178 graphAdaptor(const Graph& graph) { 179 return GraphAdaptor<const Graph>(graph); 180 } 181 182 152 183 template <typename _Graph> 153 184 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> { … … 169 200 Node source(const Edge& e) const { return Parent::target(e); } 170 201 Node target(const Edge& e) const { return Parent::source(e); } 202 203 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 204 Edge findEdge(const Node& source, const Node& target, 205 const Edge& prev = INVALID) { 206 return Parent::findEdge(target, source, prev); 207 } 208 171 209 }; 172 210 … … 185 223 /// then 186 224 ///\code 187 /// RevGraphAdaptor<ListGraph> g w(g);225 /// RevGraphAdaptor<ListGraph> ga(g); 188 226 ///\endcode 189 227 ///implements the graph obtained from \c g by … … 203 241 }; 204 242 205 243 /// \brief Just gives back a reverse graph adaptor 244 /// 245 /// Just gives back a reverse graph adaptor 246 template<typename Graph> 247 RevGraphAdaptor<const Graph> 248 revGraphAdaptor(const Graph& graph) { 249 return RevGraphAdaptor<const Graph>(graph); 250 } 251 206 252 template <typename _Graph, typename NodeFilterMap, 207 253 typename EdgeFilterMap, bool checked = true> … … 316 362 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 317 363 318 typedef False FindEdgeTag;319 364 typedef False NodeNumTag; 320 365 typedef False EdgeNumTag; 366 367 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 368 Edge findEdge(const Node& source, const Node& target, 369 const Edge& prev = INVALID) { 370 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { 371 return INVALID; 372 } 373 Edge edge = Parent::findEdge(source, target, prev); 374 while (edge != INVALID && !(*edge_filter_map)[edge]) { 375 edge = Parent::findEdge(source, target, edge); 376 } 377 return edge; 378 } 321 379 }; 322 380 … … 423 481 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 424 482 425 typedef False FindEdgeTag;426 483 typedef False NodeNumTag; 427 484 typedef False EdgeNumTag; 485 486 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 487 Edge findEdge(const Node& source, const Node& target, 488 const Edge& prev = INVALID) { 489 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { 490 return INVALID; 491 } 492 Edge edge = Parent::findEdge(source, target, prev); 493 while (edge != INVALID && !(*edge_filter_map)[edge]) { 494 edge = Parent::findEdge(source, target, edge); 495 } 496 return edge; 497 } 428 498 }; 429 499 … … 469 539 /// Graph::EdgeMap<bool> em(g, true); 470 540 /// em.set(e, false); 471 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubG W;472 /// SubG W gw(g, nm, em);473 /// for (SubG W::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;541 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA; 542 /// SubGA ga(g, nm, em); 543 /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 474 544 /// std::cout << ":-)" << std::endl; 475 /// for (SubG W::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;545 /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 476 546 ///\endcode 477 547 /// The output of the above code is the following. … … 481 551 /// 1 482 552 ///\endcode 483 /// Note that \c n is of type \c SubG W::NodeIt, but it can be converted to553 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to 484 554 /// \c Graph::Node that is why \c g.id(n) can be applied. 485 555 /// … … 508 578 } 509 579 }; 580 581 /// \brief Just gives back a sub graph adaptor 582 /// 583 /// Just gives back a sub graph adaptor 584 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap> 585 SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap> 586 subGraphAdaptor(const Graph& graph, 587 NodeFilterMap& nfm, EdgeFilterMap& efm) { 588 return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap> 589 (graph, nfm, efm); 590 } 591 592 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap> 593 SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap> 594 subGraphAdaptor(const Graph& graph, 595 NodeFilterMap& nfm, EdgeFilterMap& efm) { 596 return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap> 597 (graph, nfm, efm); 598 } 599 600 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap> 601 SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap> 602 subGraphAdaptor(const Graph& graph, 603 NodeFilterMap& nfm, EdgeFilterMap& efm) { 604 return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap> 605 (graph, nfm, efm); 606 } 607 608 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap> 609 SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap> 610 subGraphAdaptor(const Graph& graph, 611 NodeFilterMap& nfm, EdgeFilterMap& efm) { 612 return SubGraphAdaptor<const Graph, const NodeFilterMap, 613 const EdgeFilterMap>(graph, nfm, efm); 614 } 510 615 511 616 … … 534 639 protected: 535 640 ConstMap<typename Graph::Edge, bool> const_true_map; 641 642 NodeSubGraphAdaptor() : const_true_map(true) { 643 Parent::setEdgeFilterMap(const_true_map); 644 } 645 536 646 public: 537 647 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : … … 543 653 }; 544 654 655 656 /// \brief Just gives back a node sub graph adaptor 657 /// 658 /// Just gives back a node sub graph adaptor 659 template<typename Graph, typename NodeFilterMap> 660 NodeSubGraphAdaptor<const Graph, NodeFilterMap> 661 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) { 662 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm); 663 } 664 665 template<typename Graph, typename NodeFilterMap> 666 NodeSubGraphAdaptor<const Graph, const NodeFilterMap> 667 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) { 668 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm); 669 } 545 670 546 671 ///\brief An adaptor for hiding edges from a graph. … … 631 756 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); 632 757 /// 633 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubG W;634 ///SubG W gw(g, tight_edge_filter);758 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA; 759 ///SubGA ga(g, tight_edge_filter); 635 760 ///\endcode 636 761 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed … … 640 765 ///Graph::EdgeMap<int> flow(g, 0); 641 766 /// 642 ///Preflow<SubG W, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >643 /// preflow(g w, s, t, const_1_map, flow);767 ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 768 /// preflow(ga, s, t, const_1_map, flow); 644 769 ///preflow.run(); 645 770 ///\endcode … … 689 814 protected: 690 815 ConstMap<typename Graph::Node, bool> const_true_map; 816 817 EdgeSubGraphAdaptor() : const_true_map(true) { 818 Parent::setNodeFilterMap(const_true_map); 819 } 820 691 821 public: 692 822 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : … … 698 828 }; 699 829 700 template <typename _Graph> 830 /// \brief Just gives back an edge sub graph adaptor 831 /// 832 /// Just gives back an edge sub graph adaptor 833 template<typename Graph, typename EdgeFilterMap> 834 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap> 835 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) { 836 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm); 837 } 838 839 template<typename Graph, typename EdgeFilterMap> 840 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap> 841 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) { 842 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm); 843 } 844 845 template <typename _Graph, typename Enable = void> 701 846 class UndirGraphAdaptorBase : 702 847 public UGraphBaseExtender<GraphAdaptorBase<_Graph> > { … … 704 849 typedef _Graph Graph; 705 850 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent; 851 706 852 protected: 707 UndirGraphAdaptorBase() : Parent() { } 708 public: 853 854 UndirGraphAdaptorBase() : Parent() {} 855 856 public: 857 709 858 typedef typename Parent::UEdge UEdge; 710 859 typedef typename Parent::Edge Edge; 860 711 861 712 template <typename T>862 template <typename _Value> 713 863 class EdgeMap { 864 private: 865 866 typedef typename _Graph::template EdgeMap<_Value> MapImpl; 867 868 public: 869 870 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 871 872 typedef _Value Value; 873 typedef Edge Key; 874 875 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : 876 forward_map(*(_g.graph)), backward_map(*(_g.graph)) {} 877 878 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) 879 : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {} 880 881 void set(const Edge& e, const Value& a) { 882 if (Parent::direction(e)) { 883 forward_map.set(e, a); 884 } else { 885 backward_map.set(e, a); 886 } 887 } 888 889 typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const { 890 if (Parent::direction(e)) { 891 return forward_map[e]; 892 } else { 893 return backward_map[e]; 894 } 895 } 896 897 typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) { 898 if (Parent::direction(e)) { 899 return forward_map[e]; 900 } else { 901 return backward_map[e]; 902 } 903 } 904 714 905 protected: 715 const UndirGraphAdaptorBase<_Graph>* g; 716 template <typename TT> friend class EdgeMap; 717 typename _Graph::template EdgeMap<T> forward_map, backward_map; 718 public: 719 typedef T Value; 720 typedef Edge Key; 721 722 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g), 723 forward_map(*(g->graph)), backward_map(*(g->graph)) { } 724 725 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 726 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } 727 728 void set(Edge e, T a) { 729 if (g->direction(e)) 730 forward_map.set(e, a); 731 else 732 backward_map.set(e, a); 733 } 734 735 T operator[](Edge e) const { 736 if (g->direction(e)) 737 return forward_map[e]; 738 else 739 return backward_map[e]; 740 } 906 907 MapImpl forward_map, backward_map; 908 741 909 }; 742 910 743 template <typename T> 744 class UEdgeMap { 745 template <typename TT> friend class UEdgeMap; 746 typename _Graph::template EdgeMap<T> map; 911 template <typename _Value> 912 class UEdgeMap : public _Graph::template EdgeMap<_Value> { 747 913 public: 748 typedef T Value; 749 typedef UEdge Key; 750 751 UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) : 752 map(*(g.graph)) { } 753 754 UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) : 755 map(*(g.graph), a) { } 756 757 void set(UEdge e, T a) { 758 map.set(e, a); 759 } 760 761 T operator[](UEdge e) const { 762 return map[e]; 763 } 914 915 typedef typename _Graph::template EdgeMap<_Value> Parent; 916 917 UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) 918 : Parent(*(g.graph)) {} 919 920 UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) 921 : Parent(*(g.graph), a) {} 922 923 }; 924 925 }; 926 927 template <typename _Graph> 928 class UndirGraphAdaptorBase< 929 _Graph, typename enable_if< 930 typename _Graph::EdgeNotifier::Notifier>::type > 931 : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > { 932 public: 933 934 typedef _Graph Graph; 935 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent; 936 937 protected: 938 939 UndirGraphAdaptorBase() 940 : Parent(), edge_notifier(), edge_notifier_proxy(edge_notifier) {} 941 942 void setGraph(_Graph& graph) { 943 Parent::setGraph(graph); 944 edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge())); 945 } 946 947 public: 948 949 ~UndirGraphAdaptorBase() { 950 getNotifier(Edge()).clear(); 951 } 952 953 954 typedef typename Parent::UEdge UEdge; 955 typedef typename Parent::Edge Edge; 956 957 typedef typename Parent::EdgeNotifier UEdgeNotifier; 958 959 using Parent::getNotifier; 960 961 typedef AlterationNotifier<Edge> EdgeNotifier; 962 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } 963 964 protected: 965 966 class NotifierProxy : public UEdgeNotifier::ObserverBase { 967 public: 968 969 typedef typename UEdgeNotifier::ObserverBase Parent; 970 typedef UndirGraphAdaptorBase AdaptorBase; 971 972 NotifierProxy(EdgeNotifier& _edge_notifier) 973 : Parent(), edge_notifier(_edge_notifier) { 974 } 975 976 virtual ~NotifierProxy() { 977 if (Parent::attached()) { 978 Parent::detach(); 979 } 980 } 981 982 void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) { 983 Parent::attach(_uedge_notifier); 984 } 985 986 987 protected: 988 989 virtual void add(const UEdge& uedge) { 990 std::vector<Edge> edges; 991 edges.push_back(AdaptorBase::Parent::direct(uedge, true)); 992 edges.push_back(AdaptorBase::Parent::direct(uedge, false)); 993 edge_notifier.add(edges); 994 } 995 virtual void add(const std::vector<UEdge>& uedges) { 996 std::vector<Edge> edges; 997 for (int i = 0; i < (int)uedges.size(); ++i) { 998 edges.push_back(AdaptorBase::Parent::direct(uedges[i], true)); 999 edges.push_back(AdaptorBase::Parent::direct(uedges[i], false)); 1000 } 1001 edge_notifier.add(edges); 1002 } 1003 virtual void erase(const UEdge& uedge) { 1004 std::vector<Edge> edges; 1005 edges.push_back(AdaptorBase::Parent::direct(uedge, true)); 1006 edges.push_back(AdaptorBase::Parent::direct(uedge, false)); 1007 edge_notifier.erase(edges); 1008 } 1009 virtual void erase(const std::vector<UEdge>& uedges) { 1010 std::vector<Edge> edges; 1011 for (int i = 0; i < (int)uedges.size(); ++i) { 1012 edges.push_back(AdaptorBase::Parent::direct(uedges[i], true)); 1013 edges.push_back(AdaptorBase::Parent::direct(uedges[i], false)); 1014 } 1015 edge_notifier.erase(edges); 1016 } 1017 virtual void build() { 1018 edge_notifier.build(); 1019 } 1020 virtual void clear() { 1021 edge_notifier.clear(); 1022 } 1023 1024 EdgeNotifier& edge_notifier; 1025 }; 1026 1027 1028 mutable EdgeNotifier edge_notifier; 1029 NotifierProxy edge_notifier_proxy; 1030 1031 public: 1032 1033 1034 template <typename _Value> 1035 class EdgeMap { 1036 private: 1037 1038 typedef typename _Graph::template EdgeMap<_Value> MapImpl; 1039 1040 public: 1041 1042 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 1043 1044 typedef _Value Value; 1045 typedef Edge Key; 1046 1047 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : 1048 forward_map(*(_g.graph)), backward_map(*(_g.graph)) {} 1049 1050 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) 1051 : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {} 1052 1053 void set(const Edge& e, const Value& a) { 1054 if (Parent::direction(e)) { 1055 forward_map.set(e, a); 1056 } else { 1057 backward_map.set(e, a); 1058 } 1059 } 1060 1061 typename MapTraits<MapImpl>::ConstReturnValue 1062 operator[](const Edge& e) const { 1063 if (Parent::direction(e)) { 1064 return forward_map[e]; 1065 } else { 1066 return backward_map[e]; 1067 } 1068 } 1069 1070 typename MapTraits<MapImpl>::ReturnValue 1071 operator[](const Edge& e) { 1072 if (Parent::direction(e)) { 1073 return forward_map[e]; 1074 } else { 1075 return backward_map[e]; 1076 } 1077 } 1078 1079 protected: 1080 1081 MapImpl forward_map, backward_map; 1082 1083 }; 1084 1085 template <typename _Value> 1086 class UEdgeMap : public _Graph::template EdgeMap<_Value> { 1087 public: 1088 1089 typedef typename _Graph::template EdgeMap<_Value> Parent; 1090 1091 UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) 1092 : Parent(*(g.graph)) {} 1093 1094 UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) 1095 : Parent(*(g.graph), a) {} 1096 764 1097 }; 765 1098 … … 787 1120 setGraph(_graph); 788 1121 } 1122 1123 template <typename _ForwardMap, typename _BackwardMap> 1124 class CombinedEdgeMap { 1125 public: 1126 1127 typedef _ForwardMap ForwardMap; 1128 typedef _BackwardMap BackwardMap; 1129 1130 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 1131 1132 typedef typename ForwardMap::Value Value; 1133 typedef typename Parent::Edge Key; 1134 1135 CombinedEdgeMap() : forward_map(0), backward_map(0) {} 1136 1137 CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map) 1138 : forward_map(&_forward_map), backward_map(&_backward_map) {} 1139 1140 void set(const Key& e, const Value& a) { 1141 if (Parent::direction(e)) { 1142 forward_map->set(e, a); 1143 } else { 1144 backward_map->set(e, a); 1145 } 1146 } 1147 1148 typename MapTraits<ForwardMap>::ConstReturnValue 1149 operator[](const Key& e) const { 1150 if (Parent::direction(e)) { 1151 return (*forward_map)[e]; 1152 } else { 1153 return (*backward_map)[e]; 1154 } 1155 } 1156 1157 typename MapTraits<ForwardMap>::ReturnValue 1158 operator[](const Key& e) { 1159 if (Parent::direction(e)) { 1160 return (*forward_map)[e]; 1161 } else { 1162 return (*backward_map)[e]; 1163 } 1164 } 1165 1166 void setForwardMap(ForwardMap& _forward_map) { 1167 forward_map = &_forward_map; 1168 } 1169 1170 void setBackwardMap(BackwardMap& _backward_map) { 1171 backward_map = &_backward_map; 1172 } 1173 1174 protected: 1175 1176 ForwardMap* forward_map; 1177 BackwardMap* backward_map; 1178 1179 }; 1180 789 1181 }; 790 1182 791 792 template <typename _Graph, 793 typename ForwardFilterMap, typename BackwardFilterMap> 794 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> { 795 public: 796 typedef _Graph Graph; 797 typedef GraphAdaptorBase<_Graph> Parent; 798 protected: 799 ForwardFilterMap* forward_filter; 800 BackwardFilterMap* backward_filter; 801 SubBidirGraphAdaptorBase() : Parent(), 802 forward_filter(0), backward_filter(0) { } 803 804 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 805 forward_filter=&_forward_filter; 806 } 807 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { 808 backward_filter=&_backward_filter; 809 } 810 811 public: 812 // SubGraphAdaptorBase(Graph& _graph, 813 // NodeFilterMap& _node_filter_map, 814 // EdgeFilterMap& _edge_filter_map) : 815 // Parent(&_graph), 816 // node_filter_map(&node_filter_map), 817 // edge_filter_map(&edge_filter_map) { } 818 819 typedef typename Parent::Node Node; 820 typedef typename _Graph::Edge GraphEdge; 821 template <typename T> class EdgeMap; 822 // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 823 // _Graph::Edge. It contains an extra bool flag which is true 824 // if and only if the 825 // edge is the backward version of the original edge. 826 class Edge : public _Graph::Edge { 827 friend class SubBidirGraphAdaptorBase< 828 Graph, ForwardFilterMap, BackwardFilterMap>; 829 template<typename T> friend class EdgeMap; 830 protected: 831 bool backward; //true, iff backward 832 public: 833 Edge() { } 834 // \todo =false is needed, or causes problems? 835 // If \c _backward is false, then we get an edge corresponding to the 836 // original one, otherwise its oppositely directed pair is obtained. 837 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 838 _Graph::Edge(e), backward(_backward) { } 839 Edge(Invalid i) : _Graph::Edge(i), backward(true) { } 840 bool operator==(const Edge& v) const { 841 return (this->backward==v.backward && 842 static_cast<typename _Graph::Edge>(*this)== 843 static_cast<typename _Graph::Edge>(v)); 844 } 845 bool operator!=(const Edge& v) const { 846 return (this->backward!=v.backward || 847 static_cast<typename _Graph::Edge>(*this)!= 848 static_cast<typename _Graph::Edge>(v)); 849 } 850 }; 851 852 void first(Node& i) const { 853 Parent::first(i); 854 } 855 856 void first(Edge& i) const { 857 Parent::first(i); 858 i.backward=false; 859 while (*static_cast<GraphEdge*>(&i)!=INVALID && 860 !(*forward_filter)[i]) Parent::next(i); 861 if (*static_cast<GraphEdge*>(&i)==INVALID) { 862 Parent::first(i); 863 i.backward=true; 864 while (*static_cast<GraphEdge*>(&i)!=INVALID && 865 !(*backward_filter)[i]) Parent::next(i); 866 } 867 } 868 869 void firstIn(Edge& i, const Node& n) const { 870 Parent::firstIn(i, n); 871 i.backward=false; 872 while (*static_cast<GraphEdge*>(&i)!=INVALID && 873 !(*forward_filter)[i]) Parent::nextIn(i); 874 if (*static_cast<GraphEdge*>(&i)==INVALID) { 875 Parent::firstOut(i, n); 876 i.backward=true; 877 while (*static_cast<GraphEdge*>(&i)!=INVALID && 878 !(*backward_filter)[i]) Parent::nextOut(i); 879 } 880 } 881 882 void firstOut(Edge& i, const Node& n) const { 883 Parent::firstOut(i, n); 884 i.backward=false; 885 while (*static_cast<GraphEdge*>(&i)!=INVALID && 886 !(*forward_filter)[i]) Parent::nextOut(i); 887 if (*static_cast<GraphEdge*>(&i)==INVALID) { 888 Parent::firstIn(i, n); 889 i.backward=true; 890 while (*static_cast<GraphEdge*>(&i)!=INVALID && 891 !(*backward_filter)[i]) Parent::nextIn(i); 892 } 893 } 894 895 void next(Node& i) const { 896 Parent::next(i); 897 } 898 899 void next(Edge& i) const { 900 if (!(i.backward)) { 901 Parent::next(i); 902 while (*static_cast<GraphEdge*>(&i)!=INVALID && 903 !(*forward_filter)[i]) Parent::next(i); 904 if (*static_cast<GraphEdge*>(&i)==INVALID) { 905 Parent::first(i); 906 i.backward=true; 907 while (*static_cast<GraphEdge*>(&i)!=INVALID && 908 !(*backward_filter)[i]) Parent::next(i); 909 } 910 } else { 911 Parent::next(i); 912 while (*static_cast<GraphEdge*>(&i)!=INVALID && 913 !(*backward_filter)[i]) Parent::next(i); 914 } 915 } 916 917 void nextIn(Edge& i) const { 918 if (!(i.backward)) { 919 Node n=Parent::target(i); 920 Parent::nextIn(i); 921 while (*static_cast<GraphEdge*>(&i)!=INVALID && 922 !(*forward_filter)[i]) Parent::nextIn(i); 923 if (*static_cast<GraphEdge*>(&i)==INVALID) { 924 Parent::firstOut(i, n); 925 i.backward=true; 926 while (*static_cast<GraphEdge*>(&i)!=INVALID && 927 !(*backward_filter)[i]) Parent::nextOut(i); 928 } 929 } else { 930 Parent::nextOut(i); 931 while (*static_cast<GraphEdge*>(&i)!=INVALID && 932 !(*backward_filter)[i]) Parent::nextOut(i); 933 } 934 } 935 936 void nextOut(Edge& i) const { 937 if (!(i.backward)) { 938 Node n=Parent::source(i); 939 Parent::nextOut(i); 940 while (*static_cast<GraphEdge*>(&i)!=INVALID && 941 !(*forward_filter)[i]) Parent::nextOut(i); 942 if (*static_cast<GraphEdge*>(&i)==INVALID) { 943 Parent::firstIn(i, n); 944 i.backward=true; 945 while (*static_cast<GraphEdge*>(&i)!=INVALID && 946 !(*backward_filter)[i]) Parent::nextIn(i); 947 } 948 } else { 949 Parent::nextIn(i); 950 while (*static_cast<GraphEdge*>(&i)!=INVALID && 951 !(*backward_filter)[i]) Parent::nextIn(i); 952 } 953 } 954 955 Node source(Edge e) const { 956 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } 957 Node target(Edge e) const { 958 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } 959 960 /// Gives back the opposite edge. 961 962 ///\e 963 /// 964 Edge opposite(const Edge& e) const { 965 Edge f=e; 966 f.backward=!f.backward; 967 return f; 968 } 969 970 ///\e 971 972 /// \warning This is a linear time operation and works only if 973 /// \c Graph::EdgeIt is defined. 974 /// \todo hmm 975 int edgeNum() const { 976 int i=0; 977 Edge e; 978 for (first(e); e!=INVALID; next(e)) ++i; 979 return i; 980 } 981 982 bool forward(const Edge& e) const { return !e.backward; } 983 bool backward(const Edge& e) const { return e.backward; } 984 985 ///\e 986 987 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 988 /// _Graph::EdgeMap one for the forward edges and 989 /// one for the backward edges. 990 template <typename T> 991 class EdgeMap { 992 template <typename TT> friend class EdgeMap; 993 typename _Graph::template EdgeMap<T> forward_map, backward_map; 994 public: 995 typedef T Value; 996 typedef Edge Key; 997 998 EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 999 ForwardFilterMap, BackwardFilterMap>& g) : 1000 forward_map(*(g.graph)), backward_map(*(g.graph)) { } 1001 1002 EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 1003 ForwardFilterMap, BackwardFilterMap>& g, T a) : 1004 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 1005 1006 void set(Edge e, T a) { 1007 if (!e.backward) 1008 forward_map.set(e, a); 1009 else 1010 backward_map.set(e, a); 1011 } 1012 1013 // typename _Graph::template EdgeMap<T>::ConstReference 1014 // operator[](Edge e) const { 1015 // if (!e.backward) 1016 // return forward_map[e]; 1017 // else 1018 // return backward_map[e]; 1019 // } 1020 1021 // typename _Graph::template EdgeMap<T>::Reference 1022 T operator[](Edge e) const { 1023 if (!e.backward) 1024 return forward_map[e]; 1025 else 1026 return backward_map[e]; 1027 } 1028 1029 void update() { 1030 forward_map.update(); 1031 backward_map.update(); 1032 } 1033 }; 1034 1035 }; 1036 1037 1038 ///\brief An adaptor for composing a subgraph of a 1039 /// bidirected graph made from a directed one. 1040 ///\ingroup graph_adaptors 1041 /// 1042 /// An adaptor for composing a subgraph of a 1043 /// bidirected graph made from a directed one. 1044 /// 1045 ///\warning Graph adaptors are in even more experimental state 1046 ///than the other 1047 ///parts of the lib. Use them at you own risk. 1048 /// 1049 /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge 1050 ///\f$ e\in A \f$, let \f$ \bar e \f$ denote the edge obtained by 1051 /// reversing its orientation. We are given moreover two bool valued 1052 /// maps on the edge-set, 1053 ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$. 1054 /// SubBidirGraphAdaptor implements the graph structure with node-set 1055 ///\f$ V \f$ and edge-set 1056 ///\f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$. 1057 /// The purpose of writing + instead of union is because parallel 1058 /// edges can arise. (Similarly, antiparallel edges also can arise). 1059 /// In other words, a subgraph of the bidirected graph obtained, which 1060 /// is given by orienting the edges of the original graph in both directions. 1061 /// As the oppositely directed edges are logically different, 1062 /// the maps are able to attach different values for them. 1063 /// 1064 /// An example for such a construction is \c RevGraphAdaptor where the 1065 /// forward_filter is everywhere false and the backward_filter is 1066 /// everywhere true. We note that for sake of efficiency, 1067 /// \c RevGraphAdaptor is implemented in a different way. 1068 /// But BidirGraphAdaptor is obtained from 1069 /// SubBidirGraphAdaptor by considering everywhere true 1070 /// valued maps both for forward_filter and backward_filter. 1071 /// 1072 /// The most important application of SubBidirGraphAdaptor 1073 /// is ResGraphAdaptor, which stands for the residual graph in directed 1074 /// flow and circulation problems. 1075 /// As adaptors usually, the SubBidirGraphAdaptor implements the 1076 /// above mentioned graph structure without its physical storage, 1077 /// that is the whole stuff is stored in constant memory. 1078 template<typename _Graph, 1079 typename ForwardFilterMap, typename BackwardFilterMap> 1080 class SubBidirGraphAdaptor : 1081 public GraphAdaptorExtender< 1082 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { 1083 public: 1084 typedef _Graph Graph; 1085 typedef GraphAdaptorExtender< 1086 SubBidirGraphAdaptorBase< 1087 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; 1088 protected: 1089 SubBidirGraphAdaptor() { } 1090 public: 1091 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 1092 BackwardFilterMap& _backward_filter) { 1093 setGraph(_graph); 1094 setForwardFilterMap(_forward_filter); 1095 setBackwardFilterMap(_backward_filter); 1096 } 1097 }; 1098 1099 1100 1101 ///\brief An adaptor for composing bidirected graph from a directed one. 1102 ///\ingroup graph_adaptors 1103 /// 1104 ///\warning Graph adaptors are in even more experimental state 1105 ///than the other 1106 ///parts of the lib. Use them at you own risk. 1107 /// 1108 /// An adaptor for composing bidirected graph from a directed one. 1109 /// A bidirected graph is composed over the directed one without physical 1110 /// storage. As the oppositely directed edges are logically different ones 1111 /// the maps are able to attach different values for them. 1183 /// \brief Just gives back an undir graph adaptor 1184 /// 1185 /// Just gives back an undir graph adaptor 1112 1186 template<typename Graph> 1113 class BidirGraphAdaptor : 1114 public SubBidirGraphAdaptor< 1115 Graph, 1116 ConstMap<typename Graph::Edge, bool>, 1117 ConstMap<typename Graph::Edge, bool> > { 1118 public: 1119 typedef SubBidirGraphAdaptor< 1120 Graph, 1121 ConstMap<typename Graph::Edge, bool>, 1122 ConstMap<typename Graph::Edge, bool> > Parent; 1123 protected: 1124 ConstMap<typename Graph::Edge, bool> cm; 1125 1126 BidirGraphAdaptor() : Parent(), cm(true) { 1127 Parent::setForwardFilterMap(cm); 1128 Parent::setBackwardFilterMap(cm); 1129 } 1130 public: 1131 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 1132 Parent::setGraph(_graph); 1133 Parent::setForwardFilterMap(cm); 1134 Parent::setBackwardFilterMap(cm); 1135 } 1136 1137 int edgeNum() const { 1138 return 2*this->graph->edgeNum(); 1139 } 1140 }; 1141 1187 UndirGraphAdaptor<const Graph> 1188 undirGraphAdaptor(const Graph& graph) { 1189 return UndirGraphAdaptor<const Graph>(graph); 1190 } 1142 1191 1143 1192 template<typename Graph, typename Number, 1144 1193 typename CapacityMap, typename FlowMap> 1145 1194 class ResForwardFilter { 1146 // const Graph* graph;1147 1195 const CapacityMap* capacity; 1148 1196 const FlowMap* flow; 1149 1197 public: 1150 ResForwardFilter(/*const Graph& _graph, */ 1151 const CapacityMap& _capacity, const FlowMap& _flow) : 1152 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } 1153 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } 1154 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } 1155 void setFlow(const FlowMap& _flow) { flow=&_flow; } 1198 typedef typename Graph::Edge Key; 1199 typedef bool Value; 1200 1201 ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 1202 : capacity(&_capacity), flow(&_flow) { } 1203 ResForwardFilter() : capacity(0), flow(0) { } 1204 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } 1205 void setFlow(const FlowMap& _flow) { flow = &_flow; } 1156 1206 bool operator[](const typename Graph::Edge& e) const { 1157 1207 return (Number((*flow)[e]) < Number((*capacity)[e])); … … 1165 1215 const FlowMap* flow; 1166 1216 public: 1167 ResBackwardFilter(/*const Graph& _graph,*/ 1168 const CapacityMap& _capacity, const FlowMap& _flow) : 1169 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } 1170 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } 1171 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } 1172 void setFlow(const FlowMap& _flow) { flow=&_flow; } 1217 typedef typename Graph::Edge Key; 1218 typedef bool Value; 1219 1220 ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 1221 : capacity(&_capacity), flow(&_flow) { } 1222 ResBackwardFilter() : capacity(0), flow(0) { } 1223 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } 1224 void setFlow(const FlowMap& _flow) { flow = &_flow; } 1173 1225 bool operator[](const typename Graph::Edge& e) const { 1174 1226 return (Number(0) < Number((*flow)[e])); … … 1208 1260 ///Graph::EdgeMap<int> f(g); 1209 1261 ///Graph::EdgeMap<int> c(g); 1210 ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > g w(g);1262 ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g); 1211 1263 ///\endcode 1212 1264 ///\author Marton Makai … … 1215 1267 typename CapacityMap, typename FlowMap> 1216 1268 class ResGraphAdaptor : 1217 public SubBidirGraphAdaptor< 1218 Graph, 1269 public EdgeSubGraphAdaptor< 1270 UndirGraphAdaptor<Graph>, 1271 typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap< 1219 1272 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 1220 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > { 1221 public: 1222 typedef SubBidirGraphAdaptor< 1223 Graph, 1224 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 1225 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent; 1273 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > { 1274 public: 1275 1276 typedef UndirGraphAdaptor<Graph> UGraph; 1277 1278 typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap> 1279 ForwardFilter; 1280 1281 typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> 1282 BackwardFilter; 1283 1284 typedef typename UGraph:: 1285 template CombinedEdgeMap<ForwardFilter, BackwardFilter> 1286 EdgeFilter; 1287 1288 typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent; 1289 1226 1290 protected: 1291 1227 1292 const CapacityMap* capacity; 1228 1293 FlowMap* flow; 1229 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter; 1230 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter; 1231 ResGraphAdaptor() : Parent(), 1232 capacity(0), flow(0) { } 1294 1295 UGraph ugraph; 1296 ForwardFilter forward_filter; 1297 BackwardFilter backward_filter; 1298 EdgeFilter edge_filter; 1299 1233 1300 void setCapacityMap(const CapacityMap& _capacity) { 1234 1301 capacity=&_capacity; … … 1236 1303 backward_filter.setCapacity(_capacity); 1237 1304 } 1305 1238 1306 void setFlowMap(FlowMap& _flow) { 1239 1307 flow=&_flow; … … 1241 1309 backward_filter.setFlow(_flow); 1242 1310 } 1243 public: 1311 1312 public: 1313 1244 1314 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 1245 FlowMap& _flow) : 1246 Parent(), capacity(&_capacity), flow(&_flow), 1247 forward_filter(/*_graph,*/ _capacity, _flow), 1248 backward_filter(/*_graph,*/ _capacity, _flow) { 1249 Parent::setGraph(_graph); 1250 Parent::setForwardFilterMap(forward_filter); 1251 Parent::setBackwardFilterMap(backward_filter); 1315 FlowMap& _flow) 1316 : Parent(), capacity(&_capacity), flow(&_flow), 1317 ugraph(_graph), 1318 forward_filter(_capacity, _flow), 1319 backward_filter(_capacity, _flow), 1320 edge_filter(forward_filter, backward_filter) { 1321 Parent::setGraph(ugraph); 1322 Parent::setEdgeFilterMap(edge_filter); 1252 1323 } 1253 1324 … … 1255 1326 1256 1327 void augment(const Edge& e, Number a) const { 1257 if ( Parent::forward(e))1328 if (UGraph::direction(e)) { 1258 1329 flow->set(e, (*flow)[e]+a); 1259 else1330 } else { 1260 1331 flow->set(e, (*flow)[e]-a); 1261 } 1332 } 1333 } 1334 1335 static bool forward(const Edge& e) { 1336 return UGraph::direction(e); 1337 } 1338 1339 static bool backward(const Edge& e) { 1340 return !UGraph::direction(e); 1341 } 1342 1343 static Edge forward(const typename Graph::Edge& e) { 1344 return UGraph::direct(e, true); 1345 } 1346 1347 static Edge backward(const typename Graph::Edge& e) { 1348 return UGraph::direct(e, false); 1349 } 1350 1262 1351 1263 1352 /// \brief Residual capacity map. … … 1267 1356 class ResCap { 1268 1357 protected: 1269 const ResGraphAdaptor <Graph, Number, CapacityMap, FlowMap>* res_graph;1358 const ResGraphAdaptor* res_graph; 1270 1359 public: 1271 1360 typedef Number Value; 1272 1361 typedef Edge Key; 1273 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>& 1274 _res_graph) : res_graph(&_res_graph) { } 1362 ResCap(const ResGraphAdaptor& _res_graph) 1363 : res_graph(&_res_graph) {} 1364 1275 1365 Number operator[](const Edge& e) const { 1276 if ( res_graph->forward(e))1366 if (ResGraphAdaptor::direction(e)) 1277 1367 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 1278 1368 else 1279 1369 return (*(res_graph->flow))[e]; 1280 1370 } 1371 1281 1372 }; 1282 1373 1283 // KEEP_MAPS(Parent, ResGraphAdaptor);1284 1374 }; 1285 1375 -
lemon/list_graph.h
r1984 r1991 963 963 /// 964 964 /// This is a bipartite undirected graph implementation. 965 /// Except from this it conforms to966 /// the \ref concept::BpUGraph "BpUGraph"concept.965 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 966 /// concept. 967 967 /// \sa concept::BpUGraph. 968 968 /// -
lemon/ugraph_adaptor.h
r1985 r1991 43 43 /// \brief Base type for the Graph Adaptors 44 44 /// 45 /// \warning Graph adaptors are in even more experimental state than the46 /// other parts of the lib. Use them at you own risk.47 ///48 45 /// This is the base type for most of LEMON graph adaptors. 49 46 /// This class implements a trivial graph adaptor i.e. it only wraps the … … 94 91 void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); } 95 92 96 97 93 Node source(const UEdge& e) const { return graph->source(e); } 98 94 Node target(const UEdge& e) const { return graph->target(e); } … … 112 108 return graph->findEdge(source, target, prev); 113 109 } 114 115 110 UEdge findUEdge(const Node& source, const Node& target, 116 111 const UEdge& prev = INVALID) { … … 133 128 bool direction(const Edge& e) const { return graph->direction(e); } 134 129 Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); } 135 Edge direct(const UEdge& e, const Node& n) const { 136 return graph->direct(e, n); 137 } 138 139 Node oppositeNode(const Node& n, const Edge& e) const { 140 return graph->oppositeNode(n, e); 141 } 142 143 Edge oppositeEdge(const Edge& e) const { 144 return graph->oppositeEdge(e); 145 } 146 130 131 int maxNodeId() const { 132 return graph->maxNodeId(); 133 } 134 135 int maxEdgeId() const { 136 return graph->maxEdgeId(); 137 } 138 139 int maxUEdgeId() const { 140 return graph->maxEdgeId(); 141 } 142 143 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 144 145 NodeNotifier& getNotifier(Node) const { 146 return graph->getNotifier(Node()); 147 } 148 149 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 150 151 EdgeNotifier& getNotifier(Edge) const { 152 return graph->getNotifier(Edge()); 153 } 154 155 typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier; 156 157 UEdgeNotifier& getNotifier(UEdge) const { 158 return graph->getNotifier(UEdge()); 159 } 147 160 148 161 template <typename _Value> … … 380 393 typedef False NodeNumTag; 381 394 typedef False EdgeNumTag; 395 396 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 397 Edge findEdge(const Node& source, const Node& target, 398 const Edge& prev = INVALID) { 399 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { 400 return INVALID; 401 } 402 Edge edge = Parent::findEdge(source, target, prev); 403 while (edge != INVALID && !(*uedge_filter_map)[edge]) { 404 edge = Parent::findEdge(source, target, edge); 405 } 406 return edge; 407 } 408 UEdge findUEdge(const Node& source, const Node& target, 409 const UEdge& prev = INVALID) { 410 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { 411 return INVALID; 412 } 413 UEdge uedge = Parent::findUEdge(source, target, prev); 414 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) { 415 uedge = Parent::findUEdge(source, target, uedge); 416 } 417 return uedge; 418 } 382 419 }; 383 420 … … 505 542 typedef False NodeNumTag; 506 543 typedef False EdgeNumTag; 544 545 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 546 Edge findEdge(const Node& source, const Node& target, 547 const Edge& prev = INVALID) { 548 Edge edge = Parent::findEdge(source, target, prev); 549 while (edge != INVALID && !(*uedge_filter_map)[edge]) { 550 edge = Parent::findEdge(source, target, edge); 551 } 552 return edge; 553 } 554 UEdge findUEdge(const Node& source, const Node& target, 555 const UEdge& prev = INVALID) { 556 UEdge uedge = Parent::findUEdge(source, target, prev); 557 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) { 558 uedge = Parent::findUEdge(source, target, uedge); 559 } 560 return uedge; 561 } 507 562 }; 508 563 … … 582 637 /// \brief An adaptor for hiding nodes from an undirected graph. 583 638 /// 584 ///585 639 /// An adaptor for hiding nodes from an undirected graph. 586 640 /// This adaptor specializes SubUGraphAdaptor in the way that only … … 599 653 protected: 600 654 ConstMap<typename _UGraph::UEdge, bool> const_true_map; 655 656 NodeSubUGraphAdaptor() : const_true_map(true) { 657 Parent::setUEdgeFilterMap(const_true_map); 658 } 659 601 660 public: 602 661 NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : … … 640 699 protected: 641 700 ConstMap<typename Graph::Node, bool> const_true_map; 701 702 EdgeSubUGraphAdaptor() : const_true_map(true) { 703 Parent::setNodeFilterMap(const_true_map); 704 } 705 642 706 public: 643 707 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : … … 671 735 typedef typename _UGraph::UEdge Edge; 672 736 737 void reverseEdge(const Edge& edge) { 738 direction->set(edge, !(*direction)[edge]); 739 } 740 673 741 void first(Node& i) const { graph->first(i); } 674 742 void first(Edge& i) const { graph->first(i); } … … 747 815 int id(const Edge& e) const { return graph->id(e); } 748 816 749 void reverseEdge(const Edge& edge) { 750 direction->set(edge, !(*direction)[edge]); 751 } 817 int maxNodeId() const { 818 return graph->maxNodeId(); 819 } 820 821 int maxEdgeId() const { 822 return graph->maxEdgeId(); 823 } 824 825 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 826 827 NodeNotifier& getNotifier(Node) const { 828 return graph->getNotifier(Node()); 829 } 830 831 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 832 833 EdgeNotifier& getNotifier(Edge) const { 834 return graph->getNotifier(Edge()); 835 } 752 836 753 837 template <typename _Value> … … 789 873 790 874 /// \ingroup graph_adaptors 791 /// \brief A directed graph is made from a undirected graph by an adaptor 875 /// 876 /// \brief A directed graph is made from an undirected graph by an adaptor 792 877 /// 793 878 /// This adaptor gives a direction for each uedge in the undirected graph. -
test/graph_adaptor_test.cc
r1980 r1991 59 59 Graph::EdgeMap<bool> > >(); 60 60 61 checkConcept<StaticGraph, SubBidirGraphAdaptor<Graph,62 Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > >();63 // checkConcept<StaticGraph, BidirGraph<Graph> >();64 61 checkConcept<StaticGraph, ResGraphAdaptor<Graph, int, 65 62 Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
Note: See TracChangeset
for help on using the changeset viewer.