Changeset 792:147eb3a58706 in lemon-0.x
- Timestamp:
- 09/02/04 19:56:40 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1086
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/graph_wrapper.h
r777 r792 101 101 102 102 typedef typename Graph::Node Node; 103 // class Node : public Graph::Node {104 // friend class GraphWrapper<Graph>;105 // public:106 // Node() { }107 // Node(const typename Graph::Node& _n) : Graph::Node(_n) { }108 // // /// \bug construction throughrthr multiple levels should be109 // // /// handled better110 // // Node(const typename ParentGraph::ParentGraph::Node& _n) :111 // // Graph::Node(_n) { }112 // Node(const Invalid& i) : Graph::Node(i) { }113 // };114 103 class NodeIt : public Node { 115 104 const GraphWrapper<Graph>* gw; … … 130 119 }; 131 120 typedef typename Graph::Edge Edge; 132 // class Edge : public Graph::Edge {133 // friend class GraphWrapper<Graph>;134 // public:135 // Edge() { }136 // Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }137 // Edge(const Invalid& i) : Graph::Edge(i) { }138 // };139 121 class OutEdgeIt : public Edge { 140 122 const GraphWrapper<Graph>* gw; … … 278 260 typedef typename GraphWrapper<Graph>::Node Node; 279 261 typedef typename GraphWrapper<Graph>::Edge Edge; 280 //If Graph::OutEdgeIt is not defined 281 //and we do not want to use RevGraphWrapper::InEdgeIt, 282 //the typdef techinque does not work. 283 //Unfortunately all the typedefs are instantiated in templates. 284 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; 285 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; 286 262 //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other 263 //because this does not work is some of them are not defined in the 264 //original graph. The problem with this is that typedef-ed stuff 265 //are instantiated in c++. 287 266 class OutEdgeIt : public Edge { 288 267 const RevGraphWrapper<Graph>* gw; … … 383 362 384 363 typedef typename GraphWrapper<Graph>::Node Node; 385 // class NodeIt {386 // friend class GraphWrapper<Graph>;387 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;388 // typename Graph::NodeIt n;389 // public:390 // NodeIt() { }391 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }392 // NodeIt(const Invalid& i) : n(i) { }393 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :394 // n(*(_G.graph)) {395 // while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])396 // _G.graph->next(n);397 // }398 // operator Node() const { return Node(typename Graph::Node(n)); }399 // };400 364 class NodeIt : public Node { 401 365 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; … … 561 525 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 562 526 563 /// This is a linear time operation and works only if564 /// NodeIt is defined.527 /// \warning This is a linear time operation and works only if 528 /// \c Graph::NodeIt is defined. 565 529 int nodeNum() const { 566 530 int i=0; 567 NodeIt n; 568 for (this->first(n); this->valid(n); this->next(n)) ++i; 531 for (NodeIt n(*this); n!=INVALID; ++n) ++i; 569 532 return i; 570 533 } 571 534 572 /// This is a linear time operation and works only if573 /// EdgeIt is defined.535 /// \warning This is a linear time operation and works only if 536 /// \c Graph::EdgeIt is defined. 574 537 int edgeNum() const { 575 538 int i=0; 576 EdgeIt e; 577 for (this->first(e); this->valid(e); this->next(e)) ++i; 539 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 578 540 return i; 579 541 } … … 690 652 691 653 ///\brief A wrapper for composing a subgraph of a 692 /// bidirected graph composed from a directed one. 693 /// experimental, for fezso's sake. 654 /// bidirected graph made from a directed one. 694 655 /// 695 /// A wrapper for composing a subgraps of a 696 /// bidirected graph composed from a directed one. 697 /// experimental, for fezso's sake. 698 /// A bidirected graph is composed over the directed one without physical 699 /// storage. As the oppositely directed edges are logically different ones 700 /// the maps are able to attach different values for them. 656 /// Suppose that for a directed graph $G=(V, A)$, 657 /// two predicates on the edge-set, $forward_filter$, and $backward_filter$ 658 /// is given, and we are dealing with the directed graph 659 /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$. 660 /// The purpose of writing + instead of union is because parallel 661 /// edges can arose. 662 /// In other words, a subgraph of the bidirected graph obtained, which 663 /// is given by orienting the edges of the original graph in both directions. 664 /// An example for such a construction is the \c RevGraphWrapper where the 665 /// forward_filter is everywhere false and the backward_filter is 666 /// everywhere true. We note that for sake of efficiency, 667 /// \c RevGraphWrapper is implemented in a different way. 668 /// But BidirGraphWrapper is obtained from 669 /// SubBidirGraphWrapper by considering everywhere true 670 /// predicates both forward_filter and backward_filter. 671 /// Finally, one of the most important applications of SubBidirGraphWrapper 672 /// is ResGraphWrapper, which stands for the residual graph in directed 673 /// flow and circulation problems. 674 /// As wrappers usually, the SubBidirGraphWrapper implements the 675 /// above mentioned graph structure without its physical storage, 676 /// that is the whole stuff eats constant memory. 677 /// As the oppositely directed edges are logical different, 678 /// the maps are able to attach different values for them. 701 679 template<typename Graph, 702 680 typename ForwardFilterMap, typename BackwardFilterMap> … … 708 686 BackwardFilterMap* backward_filter; 709 687 710 SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 711 capacity(0), flow(0)*/ { } 688 SubBidirGraphWrapper() : GraphWrapper<Graph>() { } 712 689 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 713 690 forward_filter=&_forward_filter; … … 734 711 friend class OutEdgeIt; 735 712 736 //template<typename T> class NodeMap;737 713 template<typename T> class EdgeMap; 738 714 739 715 typedef typename GraphWrapper<Graph>::Node Node; 740 //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;741 716 742 717 typedef typename Graph::Edge GraphEdge; 718 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 719 /// Graph::Edge. It contains an extra bool flag which shows if the 720 /// edge is the backward version of the original edge. 743 721 class Edge : public Graph::Edge { 744 722 friend class SubBidirGraphWrapper<Graph, 745 723 ForwardFilterMap, BackwardFilterMap>; 746 ///\bug ez nem is kell747 //template<typename T> friend class NodeMap;748 724 template<typename T> friend class EdgeMap; 749 725 protected: 750 726 bool backward; //true, iff backward 751 // typename Graph::Edge e;752 727 public: 753 728 Edge() { } 754 ///\bug =false kell-e? zsoltnak kell az addEdge miatt 729 /// \todo =false is needed, or causes problems? 730 /// If \c _backward is false, then we get an edge corresponding to the 731 /// original one, otherwise its oppositely directed pair is obtained. 755 732 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 756 733 Graph::Edge(e), backward(_backward) { } … … 959 936 i=OutEdgeIt(*this, p); return i; 960 937 } 961 // FIXME not tested962 938 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 963 939 i=InEdgeIt(*this, p); return i; … … 1053 1029 } 1054 1030 1055 // int nodeNum() const { return graph->nodeNum(); } 1056 //FIXME 1057 void edgeNum() const { } 1058 //int edgeNum() const { return graph->edgeNum(); } 1059 1060 1061 // int id(Node v) const { return graph->id(v); } 1062 1063 // bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } 1064 // bool valid(Edge e) const { 1065 // return this->graph->valid(e); 1066 // //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 1067 // } 1031 /// \warning This is a linear time operation and works only if 1032 /// \c Graph::EdgeIt is defined. 1033 int edgeNum() const { 1034 int i=0; 1035 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 1036 return i; 1037 } 1068 1038 1069 1039 bool forward(const Edge& e) const { return !e.backward; } 1070 1040 bool backward(const Edge& e) const { return e.backward; } 1071 1041 1072 // void augment(const Edge& e, Number a) const {1073 // if (!e.backward)1074 // // flow->set(e.out, flow->get(e.out)+a);1075 // flow->set(e, (*flow)[e]+a);1076 // else1077 // // flow->set(e.in, flow->get(e.in)-a);1078 // flow->set(e, (*flow)[e]-a);1079 // }1080 1081 // bool enabled(const Edge& e) const {1082 // if (!e.backward)1083 // // return (capacity->get(e.out)-flow->get(e.out));1084 // //return ((*capacity)[e]-(*flow)[e]);1085 // return true;1086 // else1087 // // return (flow->get(e.in));1088 // //return ((*flow)[e]);1089 // return true;1090 // }1091 1092 // Number enabled(typename Graph::OutEdgeIt out) const {1093 // // return (capacity->get(out)-flow->get(out));1094 // return ((*capacity)[out]-(*flow)[out]);1095 // }1096 1097 // Number enabled(typename Graph::InEdgeIt in) const {1098 // // return (flow->get(in));1099 // return ((*flow)[in]);1100 // }1101 1042 1102 1043 template <typename T> 1044 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 1045 /// Graph::EdgeMap one for the forward edges and 1046 /// one for the backward edges. 1103 1047 class EdgeMap { 1104 1048 typename Graph::template EdgeMap<T> forward_map, backward_map; … … 1114 1058 void set(Edge e, T a) { 1115 1059 if (!e.backward) 1116 forward_map.set(e /*.out*/, a);1060 forward_map.set(e, a); 1117 1061 else 1118 backward_map.set(e /*.in*/, a);1062 backward_map.set(e, a); 1119 1063 } 1120 1064 T operator[](Edge e) const { 1121 1065 if (!e.backward) 1122 return forward_map[e /*.out*/];1066 return forward_map[e]; 1123 1067 else 1124 return backward_map[e /*.in*/];1068 return backward_map[e]; 1125 1069 } 1126 1070 void update() { … … 1138 1082 1139 1083 1140 1141 1084 ///\brief A wrapper for composing bidirected graph from a directed one. 1142 /// experimental, for fezso's sake.1143 1085 /// 1144 1086 /// A wrapper for composing bidirected graph from a directed one. 1145 /// experimental, for fezso's sake.1146 1087 /// A bidirected graph is composed over the directed one without physical 1147 1088 /// storage. As the oppositely directed edges are logically different ones … … 1160 1101 protected: 1161 1102 ConstMap<typename Graph::Edge, bool> cm; 1162 //const CapacityMap* capacity;1163 //FlowMap* flow;1164 1103 1165 1104 BidirGraphWrapper() : Parent(), cm(true) { … … 1167 1106 Parent::setBackwardFilterMap(cm); 1168 1107 } 1169 // void setCapacityMap(const CapacityMap& _capacity) { 1170 // capacity=&_capacity; 1171 // } 1172 // void setFlowMap(FlowMap& _flow) { 1173 // flow=&_flow; 1174 // } 1175 1176 public: 1177 1108 public: 1178 1109 BidirGraphWrapper(Graph& _graph) : Parent() { 1179 1110 Parent::setGraph(_graph); … … 1189 1120 1190 1121 1191 1122 // this is a direct implementation of the bidirected-graph wrapper. 1123 // in early hugo, it was implemented that way. 1192 1124 template<typename Graph> 1193 1125 class OldBidirGraphWrapper : public GraphWrapper<Graph> { … … 1195 1127 typedef GraphWrapper<Graph> Parent; 1196 1128 protected: 1197 //const CapacityMap* capacity; 1198 //FlowMap* flow; 1199 1200 OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 1201 capacity(0), flow(0)*/ { } 1202 // void setCapacityMap(const CapacityMap& _capacity) { 1203 // capacity=&_capacity; 1204 // } 1205 // void setFlowMap(FlowMap& _flow) { 1206 // flow=&_flow; 1207 // } 1208 1209 public: 1210 1211 OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 1212 FlowMap& _flow*/) : 1213 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } 1129 OldBidirGraphWrapper() : GraphWrapper<Graph>() { } 1130 1131 public: 1132 1133 OldBidirGraphWrapper(Graph& _graph) : 1134 GraphWrapper<Graph>(_graph) { } 1214 1135 1215 1136 class Edge; … … 1460 1381 bool backward(const Edge& e) const { return e.backward; } 1461 1382 1462 // void augment(const Edge& e, Number a) const {1463 // if (!e.backward)1464 // // flow->set(e.out, flow->get(e.out)+a);1465 // flow->set(e, (*flow)[e]+a);1466 // else1467 // // flow->set(e.in, flow->get(e.in)-a);1468 // flow->set(e, (*flow)[e]-a);1469 // }1470 1471 1383 bool enabled(const Edge& e) const { 1472 1384 if (!e.backward) … … 1663 1575 /// \brief Residual capacity map. 1664 1576 /// 1665 /// In generic residual graphs the residual capacity can be obtained as a map. 1577 /// In generic residual graphs the residual capacity can be obtained as a map. Not tested. 1666 1578 class ResCap { 1667 1579 protected: … … 2008 1920 /// For blocking flows. 2009 1921 2010 /// This graph wrapper is used for Dinits blocking flow computations. 1922 /// This graph wrapper is used for on-the-fly 1923 /// Dinits blocking flow computations. 2011 1924 /// For each node, an out-edge is stored which is used when the 2012 1925 /// \code … … 2015 1928 /// is called. 2016 1929 /// 2017 /// \author Marton Makai1930 /// \author Marton Makai 2018 1931 template<typename Graph, typename FirstOutEdgesMap> 2019 1932 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { … … 2028 1941 2029 1942 typedef typename GraphWrapper<Graph>::Node Node; 2030 // class NodeIt {2031 // friend class GraphWrapper<Graph>;2032 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;2033 // typename Graph::NodeIt n;2034 // public:2035 // NodeIt() { }2036 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }2037 // NodeIt(const Invalid& i) : n(i) { }2038 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :2039 // n(*(_G.graph)) { }2040 // operator Node() const { return Node(typename Graph::Node(n)); }2041 // };2042 1943 typedef typename GraphWrapper<Graph>::Edge Edge; 2043 1944 class OutEdgeIt : public Edge {
Note: See TracChangeset
for help on using the changeset viewer.