Changeset 1991:d7442141d9ef in lemon0.x for lemon/graph_adaptor.h
 Timestamp:
 03/01/06 11:25:30 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2593
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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 edgedisjoint \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 edgeset, 1053 ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$. 1054 /// SubBidirGraphAdaptor implements the graph structure with nodeset 1055 ///\f$ V \f$ and edgeset 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
Note: See TracChangeset
for help on using the changeset viewer.