Changeset 174:44700ed9ffaa in lemon-0.x for src/work
- Timestamp:
- 03/12/04 10:19:54 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@250
- Location:
- src/work
- Files:
-
- 5 added
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/alpar/emptygraph.h
r165 r174 1 // -*-mode: c++; -*- 1 // -*- c++ -*- 2 #ifndef EMPTYGRAPH_H 3 #define EMPTYGRAPH_H 2 4 3 5 #include <invalid.h> … … 35 37 Node() {} //FIXME 36 38 /// Initialize the iterator to be invalid 37 Node(Invalid) {} ;39 Node(Invalid) {} 38 40 //Node(const Node &) {} 39 41 bool operator==(Node n) const { return true; } //FIXME … … 48 50 NodeIt() {} //FIXME 49 51 /// Initialize the iterator to be invalid 50 NodeIt(Invalid) {} ;52 NodeIt(Invalid) {} 51 53 /// Sets the iterator to the first node of \c G. 52 54 NodeIt(const EmptyGraph &G) {} … … 62 64 Edge() {} //FIXME 63 65 /// Initialize the iterator to be invalid 64 Edge(Invalid) {} ;66 Edge(Invalid) {} 65 67 //Edge(const Edge &) {} 66 68 bool operator==(Edge n) const { return true; } //FIXME … … 76 78 OutEdgeIt() {} 77 79 /// Initialize the iterator to be invalid 78 OutEdgeIt(Invalid) {} ;80 OutEdgeIt(Invalid) {} 79 81 /// This constructor sets the iterator to first outgoing edge. 80 82 … … 92 94 InEdgeIt() {} 93 95 /// Initialize the iterator to be invalid 94 InEdgeIt(Invalid) {} ;96 InEdgeIt(Invalid) {} 95 97 InEdgeIt(const EmptyGraph &, Node) {} 96 98 }; … … 102 104 EdgeIt() {} 103 105 /// Initialize the iterator to be invalid 104 EdgeIt(Invalid) {} ;106 EdgeIt(Invalid) {} 105 107 EdgeIt(const EmptyGraph &) {} 106 108 }; … … 150 152 151 153 /// Checks if a node iterator is valid 152 bool valid(const Node) const { return true;} ;154 bool valid(const Node) const { return true;} 153 155 /// Checks if an edge iterator is valid 154 bool valid(const Edge) const { return true;} ;156 bool valid(const Edge) const { return true;} 155 157 156 158 ///Gives back the \e id of a node. 157 int id(const Node) const { return 0;} ;159 int id(const Node) const { return 0;} 158 160 ///Gives back the \e id of an edge. 159 int id(const Edge) const { return 0;} ;161 int id(const Edge) const { return 0;} 160 162 161 163 //void setInvalid(Node &) const {}; … … 173 175 int edgeNum() { return 0;} 174 176 175 EmptyGraph() {} ;176 EmptyGraph(const EmptyGraph &G) {} ;177 EmptyGraph() {} 178 EmptyGraph(const EmptyGraph &G) {} 177 179 178 180 … … 218 220 // @} 219 221 220 } ;222 } //namespace hugo 221 223 222 224 … … 237 239 238 240 // } 241 242 #endif // EMPTYGRAPH_H -
src/work/alpar/smart_graph.h
r164 r174 97 97 Node head(Edge e) const { return edges[e.n].head; } 98 98 99 // Node aNode(const OutEdgeIt& e) const { return tail(e); } 100 // Node aNode(const InEdgeIt& e) const { return head(e); } 99 // Marci 100 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } 101 Node aNode(InEdgeIt e) const { return edges[e.n].head; } 101 102 // //Node aNode(const SymEdge& e) const { return e.aNode(); } 102 103 103 // Node bNode(const OutEdgeIt& e) const { return head(e); } 104 // Node bNode(const InEdgeIt& e) const { return tail(e); } 104 // Marci 105 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } 106 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } 105 107 // //Node bNode(const SymEdge& e) const { return e.bNode(); } 106 108 … … 117 119 It first() const { 118 120 It e; 119 getFirst(e); 121 //Marci 122 /*getF*/first(e); 120 123 return e; 121 124 } … … 124 127 It first(Node v) const { 125 128 It e; 126 getFirst(e, v); 129 //Marci 130 /*getF*/first(e, v); 127 131 return e; 128 132 } … … 139 143 //{ It tmp; tmp.n=it.n+1; return tmp; } 140 144 141 Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; } 145 //FIXME correction Marci: I changed to NodeIt from Node 146 //NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; } 147 NodeIt& next(NodeIt& it) const { 148 it.n=(it.n+2)%(nodes.size()+1)-1; 149 return it; 150 } 142 151 OutEdgeIt& next(OutEdgeIt& it) const 143 152 { it.n=edges[it.n].next_out; return it; } … … 217 226 public: 218 227 Edge() { } 219 Edge (Invalid i) { n=-1; } 228 // Marci: kiszedtem az Invalid i-bol az i-t 229 Edge (Invalid) { n=-1; } 220 230 bool operator==(const Edge i) const {return n==i.n;} 221 231 bool operator!=(const Edge i) const {return n!=i.n;} -
src/work/iterator_bfs_demo.cc
r158 r174 1 // -*- c++ -*- 1 2 #include <iostream> 2 3 #include <vector> 3 4 #include <string> 4 5 5 #include <list_graph.hh> 6 #include <bfs_iterator.hh> 6 #include <list_graph.h> 7 #include <smart_graph.h> 8 #include <bfs_iterator.h> 7 9 #include <graph_wrapper.h> 8 10 … … 19 21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 20 22 graph(_graph), node_name_map(_node_name_map) { } 21 string get(typename Graph::Edge Ite) const {23 string get(typename Graph::Edge e) const { 22 24 return 23 25 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); … … 27 29 int main (int, char*[]) 28 30 { 29 typedef ListGraph::NodeIt NodeIt; 30 typedef ListGraph::EdgeIt EdgeIt; 31 //typedef ListGraph::EachNodeIt EachNodeIt; 32 //typedef ListGraph::EachEdgeIt EachEdgeIt; 33 //typedef ListGraph::OutEdgeIt OutEdgeIt; 34 //typedef ListGraph::InEdgeIt InEdgeIt; 35 //typedef ListGraph::SymEdgeIt SymEdgeIt; 31 //typedef SmartGraph Graph; 32 typedef ListGraph Graph; 33 34 typedef Graph::Node Node; 35 typedef Graph::Edge Edge; 36 //typedef Graph::NodeIt NodeIt; 37 //typedef Graph::EdgeIt EdgeIt; 38 //typedef Graph::OutEdgeIt OutEdgeIt; 39 //typedef Graph::InEdgeIt InEdgeIt; 40 //typedef Graph::SymEdgeIt SymEdgeIt; 36 41 37 ListGraph G;38 39 Node Its=G.addNode();40 Node Itv1=G.addNode();41 Node Itv2=G.addNode();42 Node Itv3=G.addNode();43 Node Itv4=G.addNode();44 Node Itt=G.addNode();42 Graph G; 43 44 Node s=G.addNode(); 45 Node v1=G.addNode(); 46 Node v2=G.addNode(); 47 Node v3=G.addNode(); 48 Node v4=G.addNode(); 49 Node t=G.addNode(); 45 50 46 ListGraph::NodeMap<string> node_name(G);51 Graph::NodeMap<string> node_name(G); 47 52 node_name.set(s, "s"); 48 53 node_name.set(v1, "v1"); … … 73 78 cout << " \\--> -------------> "<< endl; 74 79 75 /* 76 { 77 cout << "iterator bfs demo 4 ..." << endl; 78 BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); 79 bfs.pushAndSetReached(s); 80 while (!bfs.finished()) { 81 if (OutEdgeIt(bfs).valid()) { 82 cout << "OutEdgeIt: " << bfs; 83 cout << " aNode: " << G.aNode(bfs); 84 cout << " bNode: " << G.bNode(bfs) << " "; 85 } else { 86 cout << "OutEdgeIt: " << "invalid"; 87 cout << " aNode: " << bfs.aNode(); 88 cout << " bNode: " << "invalid" << " "; 89 } 90 if (bfs.isBNodeNewlyReached()) { 91 cout << "bNodeIsNewlyReached "; 92 } else { 93 cout << "bNodeIsNotNewlyReached "; 94 } 95 if (bfs.isANodeExamined()) { 96 cout << "aNodeIsExamined "; 97 } else { 98 cout << "aNodeIsNotExamined "; 99 } 100 cout << endl; 101 ++bfs; 102 } 103 } 104 105 { 106 cout << "iterator dfs demo 4 ..." << endl; 107 DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); 108 dfs.pushAndSetReached(s); 109 while (!dfs.finished()) { 110 ++dfs; 111 if (OutEdgeIt(dfs).valid()) { 112 cout << "OutEdgeIt: " << dfs; 113 cout << " aNode: " << G.aNode(dfs); 114 cout << " bNode: " << G.bNode(dfs) << " "; 115 } else { 116 cout << "OutEdgeIt: " << "invalid"; 117 cout << " aNode: " << dfs.aNode(); 118 cout << " bNode: " << "invalid" << " "; 119 } 120 if (dfs.isBNodeNewlyReached()) { 121 cout << "bNodeIsNewlyReached "; 122 } else { 123 cout << "bNodeIsNotNewlyReached "; 124 } 125 if (dfs.isANodeExamined()) { 126 cout << "aNodeIsExamined "; 127 } else { 128 cout << "aNodeIsNotExamined "; 129 } 130 cout << endl; 131 //++dfs; 132 } 133 } 134 */ 135 136 // typedef TrivGraphWrapper<const ListGraph> CGW; 80 // typedef TrivGraphWrapper<const Graph> CGW; 137 81 // CGW wG(G); 138 82 139 83 // cout << "bfs and dfs demo on the directed graph" << endl; 140 // for(CGW:: EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) {84 // for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) { 141 85 // cout << n << ": "; 142 86 // cout << "out edges: "; … … 150 94 151 95 { 152 typedef TrivGraphWrapper<const ListGraph> GW;96 typedef TrivGraphWrapper<const Graph> GW; 153 97 GW wG(G); 154 98 155 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); 156 100 157 101 cout << "bfs and dfs iterator demo on the directed graph" << endl; 158 for(GW:: EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {102 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 159 103 cout << node_name.get(n) << ": "; 160 104 cout << "out edges: "; … … 226 170 227 171 { 228 typedef RevGraphWrapper<const ListGraph> GW;172 typedef RevGraphWrapper<const Graph> GW; 229 173 GW wG(G); 230 174 231 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); 232 176 233 177 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; 234 for(GW:: EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {178 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 235 179 cout << node_name.get(n) << ": "; 236 180 cout << "out edges: "; … … 301 245 302 246 { 303 typedef UndirGraphWrapper<const ListGraph> GW;247 typedef UndirGraphWrapper<const Graph> GW; 304 248 GW wG(G); 305 249 306 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); 307 251 308 252 cout << "bfs and dfs iterator demo on the undirected graph" << endl; 309 for(GW:: EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {253 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 310 254 cout << node_name.get(n) << ": "; 311 255 cout << "out edges: "; -
src/work/jacint/preflow.h
r113 r174 527 527 528 528 }; 529 }//namespace marci 530 #endif 531 532 533 534 529 530 } //namespace hugo 531 532 #endif //PREFLOW_H 533 534 535 536 -
src/work/marci/edmonds_karp_demo.cc
r168 r174 1 // -*- c++ -*- 1 2 #include <iostream> 2 3 #include <fstream> 3 4 4 #include <list_graph.hh> 5 #include <dimacs.hh> 6 #include <edmonds_karp.hh> 5 #include <list_graph.h> 6 #include <smart_graph.h> 7 #include <dimacs.h> 8 #include <edmonds_karp.h> 7 9 #include <time_measure.h> 8 10 #include <graph_wrapper.h> … … 13 15 // read_dimacs_demo < dimacs_max_flow_file 14 16 15 /* 16 struct Ize {17 };17 18 // struct Ize { 19 // }; 18 20 19 struct Mize {20 Ize bumm;21 };21 // struct Mize { 22 // Ize bumm; 23 // }; 22 24 23 template <typename B>24 class Huha {25 public:26 int u;27 B brr;28 };29 */ 25 // template <typename B> 26 // class Huha { 27 // public: 28 // int u; 29 // B brr; 30 // }; 31 30 32 31 33 int main(int, char **) { 32 typedef ListGraph::NodeIt NodeIt;33 typedef ListGraph::EachEdgeIt EachEdgeIt;34 34 35 /* 36 Mize mize[10]; 37 Mize bize[0]; 38 Mize zize; 39 typedef Mize Tize[0]; 35 typedef ListGraph MutableGraph; 40 36 41 std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; 42 std::cout << sizeof(bize) << std::endl; 37 typedef SmartGraph Graph; 38 typedef Graph::Node Node; 39 typedef Graph::EdgeIt EdgeIt; 43 40 44 41 45 Huha<Tize> k; 46 std::cout << sizeof(k) << std::endl; 42 // Mize mize[10]; 43 // Mize bize[0]; 44 // Mize zize; 45 // typedef Mize Tize[0]; 46 47 // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; 48 // std::cout << sizeof(bize) << std::endl; 47 49 48 50 49 struct Bumm { 50 //int a; 51 bool b; 52 }; 51 // Huha<Tize> k; 52 // std::cout << sizeof(k) << std::endl; 53 53 54 std::cout << sizeof(Bumm) << std::endl;55 */56 54 57 ListGraph G; 58 NodeIt s, t; 59 ListGraph::EdgeMap<int> cap(G); 55 // struct Bumm { 56 // //int a; 57 // bool b; 58 // }; 59 60 // std::cout << sizeof(Bumm) << std::endl; 61 62 63 Graph G; 64 Node s, t; 65 Graph::EdgeMap<int> cap(G); 60 66 readDimacsMaxFlow(std::cin, G, s, t, cap); 61 /*62 typedef TrivGraphWrapper<ListGraph> TGW;63 TGW gw(G);64 TGW::EachNodeIt sw;65 gw.getFirst(sw);66 std::cout << "p1:" << gw.nodeNum() << std::endl;67 gw.erase(sw);68 std::cout << "p2:" << gw.nodeNum() << std::endl;69 67 70 typedef const ListGraph cLG; 71 typedef TrivGraphWrapper<const cLG> CTGW; 72 CTGW cgw(G); 73 CTGW::EachNodeIt csw; 74 cgw.getFirst(csw); 75 std::cout << "p1:" << cgw.nodeNum() << std::endl; 76 //cgw.erase(csw); 77 std::cout << "p2:" << cgw.nodeNum() << std::endl; 78 */ 68 // typedef TrivGraphWrapper<Graph> TGW; 69 // TGW gw(G); 70 // TGW::NodeIt sw; 71 // gw./*getF*/first(sw); 72 // std::cout << "p1:" << gw.nodeNum() << std::endl; 73 // gw.erase(sw); 74 // std::cout << "p2:" << gw.nodeNum() << std::endl; 75 76 // typedef const Graph cLG; 77 // typedef TrivGraphWrapper<const cLG> CTGW; 78 // CTGW cgw(G); 79 // CTGW::NodeIt csw; 80 // cgw./*getF*/first(csw); 81 // std::cout << "p1:" << cgw.nodeNum() << std::endl; 82 // //cgw.erase(csw); 83 // std::cout << "p2:" << cgw.nodeNum() << std::endl; 84 79 85 80 86 { 81 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; 82 ListGraph::EdgeMap<int> flow(G); //0 flow 87 std::cout << "SmartGraph..." << std::endl; 88 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 89 Graph::EdgeMap<int> flow(G); //0 flow 83 90 84 Timer ts;85 ts.reset();86 //double pre_time=currTime(); 87 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);88 //max_flow_test.augmentWithBlockingFlow<ListGraph>();89 int i=0;90 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {91 // for(E achEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {91 Timer ts; 92 ts.reset(); 93 94 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 95 //max_flow_test.augmentWithBlockingFlow<Graph>(); 96 int i=0; 97 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 98 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 92 99 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 93 100 // } 94 101 // std::cout<<std::endl; 95 ++i; 96 } 97 //double post_time=currTime(); 102 ++i; 103 } 98 104 99 //std::cout << "maximum flow: "<< std::endl;100 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {101 //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";102 //}103 //std::cout<<std::endl;104 std::cout << "elapsed time: " << ts << std::endl;105 std::cout << "number of augmentation phases: " << i << std::endl;106 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;105 // std::cout << "maximum flow: "<< std::endl; 106 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 107 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 108 // } 109 // std::cout<<std::endl; 110 std::cout << "elapsed time: " << ts << std::endl; 111 std::cout << "number of augmentation phases: " << i << std::endl; 112 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 107 113 } 108 114 109 115 { 110 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;111 ListGraph::EdgeMap<int> flow(G); //0 flow116 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; 117 Graph::EdgeMap<int> flow(G); //0 flow 112 118 113 Timer ts;114 ts.reset();115 //double pre_time=currTime(); 116 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);117 //max_flow_test.augmentWithBlockingFlow<ListGraph>();118 int i=0;119 while (max_flow_test.augmentOnBlockingFlow2()) {120 // for(E achEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {119 Timer ts; 120 ts.reset(); 121 122 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 123 //max_flow_test.augmentWithBlockingFlow<Graph>(); 124 int i=0; 125 while (max_flow_test.augmentOnBlockingFlow2()) { 126 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 121 127 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 122 128 // } 123 129 // std::cout<<std::endl; 124 ++i; 125 } 126 //double post_time=currTime(); 130 ++i; 131 } 127 132 128 //std::cout << "maximum flow: "<< std::endl;129 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {130 //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";131 //}132 //std::cout<<std::endl;133 std::cout << "elapsed time: " << ts << std::endl;134 std::cout << "number of augmentation phases: " << i << std::endl;135 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;133 // std::cout << "maximum flow: "<< std::endl; 134 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 135 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 136 // } 137 // std::cout<<std::endl; 138 std::cout << "elapsed time: " << ts << std::endl; 139 std::cout << "number of augmentation phases: " << i << std::endl; 140 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 136 141 } 137 142 138 143 { 139 std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;140 ListGraph::EdgeMap<int> flow(G); //0 flow144 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; 145 Graph::EdgeMap<int> flow(G); //0 flow 141 146 142 Timer ts;143 ts.reset();144 //double pre_time=currTime(); 145 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);146 //max_flow_test.augmentWithBlockingFlow<ListGraph>();147 int i=0;148 while (max_flow_test.augmentOnShortestPath()) {149 // for(E achEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {147 Timer ts; 148 ts.reset(); 149 150 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 151 //max_flow_test.augmentWithBlockingFlow<Graph>(); 152 int i=0; 153 while (max_flow_test.augmentOnShortestPath()) { 154 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 150 155 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 151 156 // } 152 157 // std::cout<<std::endl; 153 ++i; 158 ++i; 159 } 160 161 // std::cout << "maximum flow: "<< std::endl; 162 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 163 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 164 // } 165 // std::cout<<std::endl; 166 std::cout << "elapsed time: " << ts << std::endl; 167 std::cout << "number of augmentation phases: " << i << std::endl; 168 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 154 169 } 155 //double post_time=currTime();156 170 157 //std::cout << "maximum flow: "<< std::endl;158 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {159 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";160 //}161 //std::cout<<std::endl;162 std::cout << "elapsed time: " << ts << std::endl;163 std::cout << "number of augmentation phases: " << i << std::endl;164 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;165 }166 171 167 172 return 0; -
src/work/marci/graph_wrapper.h
r168 r174 1 // -*- mode: c++;-*-1 // -*- c++ -*- 2 2 #ifndef GRAPH_WRAPPER_H 3 3 #define GRAPH_WRAPPER_H 4 5 #include <invalid.h> 4 6 5 7 namespace hugo { … … 12 14 typedef Graph BaseGraph; 13 15 16 typedef typename Graph::Node Node; 14 17 typedef typename Graph::NodeIt NodeIt; 15 typedef typename Graph::EachNodeIt EachNodeIt; 16 17 typedef typename Graph::EdgeIt EdgeIt; 18 19 typedef typename Graph::Edge Edge; 18 20 typedef typename Graph::OutEdgeIt OutEdgeIt; 19 21 typedef typename Graph::InEdgeIt InEdgeIt; 20 22 //typedef typename Graph::SymEdgeIt SymEdgeIt; 21 typedef typename Graph::E achEdgeIt EachEdgeIt;23 typedef typename Graph::EdgeIt EdgeIt; 22 24 23 25 //TrivGraphWrapper() : graph(0) { } … … 27 29 Graph& getGraph() const { return (*graph); } 28 30 29 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }30 template<typename I, typename P> I& getFirst(I& i, const P& p) const {31 return graph-> getFirst(i, p); }31 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } 32 template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 33 return graph->/*getF*/first(i, p); } 32 34 33 35 template<typename I> I getNext(const I& i) const { … … 36 38 37 39 template< typename It > It first() const { 38 It e; getFirst(e); return e; }39 40 template< typename It > It first(const Node It& v) const {41 It e; getFirst(e, v); return e; }42 43 Node It head(const EdgeIt& e) const { return graph->head(e); }44 Node It tail(const EdgeIt& e) const { return graph->tail(e); }40 It e; /*getF*/first(e); return e; } 41 42 template< typename It > It first(const Node& v) const { 43 It e; /*getF*/first(e, v); return e; } 44 45 Node head(const Edge& e) const { return graph->head(e); } 46 Node tail(const Edge& e) const { return graph->tail(e); } 45 47 46 48 template<typename I> bool valid(const I& i) const … … 53 55 int edgeNum() const { return graph->edgeNum(); } 54 56 55 template<typename I> Node ItaNode(const I& e) const {57 template<typename I> Node aNode(const I& e) const { 56 58 return graph->aNode(e); } 57 template<typename I> Node ItbNode(const I& e) const {59 template<typename I> Node bNode(const I& e) const { 58 60 return graph->bNode(e); } 59 61 60 Node ItaddNode() const { return graph->addNode(); }61 Edge It addEdge(const NodeIt& tail, const NodeIt& head) const {62 Node addNode() const { return graph->addNode(); } 63 Edge addEdge(const Node& tail, const Node& head) const { 62 64 return graph->addEdge(tail, head); } 63 65 … … 91 93 typedef Graph BaseGraph; 92 94 93 typedef typename Graph::Node It NodeIt;94 typedef typename Graph:: EachNodeIt EachNodeIt;95 96 typedef typename Graph::Edge It EdgeIt;95 typedef typename Graph::Node Node; 96 typedef typename Graph::NodeIt NodeIt; 97 98 typedef typename Graph::Edge Edge; 97 99 typedef typename Graph::OutEdgeIt InEdgeIt; 98 100 typedef typename Graph::InEdgeIt OutEdgeIt; 99 101 //typedef typename Graph::SymEdgeIt SymEdgeIt; 100 typedef typename Graph::E achEdgeIt EachEdgeIt;102 typedef typename Graph::EdgeIt EdgeIt; 101 103 102 104 //RevGraphWrapper() : graph(0) { } … … 106 108 Graph& getGraph() const { return (*graph); } 107 109 108 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }109 template<typename I, typename P> I& getFirst(I& i, const P& p) const {110 return graph-> getFirst(i, p); }110 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } 111 template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 112 return graph->/*getF*/first(i, p); } 111 113 112 114 template<typename I> I getNext(const I& i) const { … … 115 117 116 118 template< typename It > It first() const { 117 It e; getFirst(e); return e; }118 119 template< typename It > It first(const Node It& v) const {120 It e; getFirst(e, v); return e; }121 122 Node It head(const EdgeIt& e) const { return graph->tail(e); }123 Node It tail(const EdgeIt& e) const { return graph->head(e); }119 It e; /*getF*/first(e); return e; } 120 121 template< typename It > It first(const Node& v) const { 122 It e; /*getF*/first(e, v); return e; } 123 124 Node head(const Edge& e) const { return graph->tail(e); } 125 Node tail(const Edge& e) const { return graph->head(e); } 124 126 125 127 template<typename I> bool valid(const I& i) const … … 129 131 //{ return graph->setInvalid(i); } 130 132 131 template<typename I> Node ItaNode(const I& e) const {133 template<typename I> Node aNode(const I& e) const { 132 134 return graph->aNode(e); } 133 template<typename I> Node ItbNode(const I& e) const {135 template<typename I> Node bNode(const I& e) const { 134 136 return graph->bNode(e); } 135 137 136 Node ItaddNode() const { return graph->addNode(); }137 Edge It addEdge(const NodeIt& tail, const NodeIt& head) const {138 Node addNode() const { return graph->addNode(); } 139 Edge addEdge(const Node& tail, const Node& head) const { 138 140 return graph->addEdge(tail, head); } 139 141 … … 170 172 typedef Graph BaseGraph; 171 173 174 typedef typename Graph::Node Node; 172 175 typedef typename Graph::NodeIt NodeIt; 173 typedef typename Graph::EachNodeIt EachNodeIt; 174 175 //typedef typename Graph::EdgeIt EdgeIt; 176 177 //typedef typename Graph::Edge Edge; 176 178 //typedef typename Graph::OutEdgeIt OutEdgeIt; 177 179 //typedef typename Graph::InEdgeIt InEdgeIt; 178 180 //typedef typename Graph::SymEdgeIt SymEdgeIt; 179 //typedef typename Graph::E achEdgeIt EachEdgeIt;181 //typedef typename Graph::EdgeIt EdgeIt; 180 182 181 183 //private: 182 typedef typename Graph::Edge It GraphEdgeIt;184 typedef typename Graph::Edge GraphEdge; 183 185 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 184 186 typedef typename Graph::InEdgeIt GraphInEdgeIt; … … 191 193 Graph& getGraph() const { return (*graph); } 192 194 193 class Edge It{195 class Edge { 194 196 friend class UndirGraphWrapper<Graph>; 195 197 bool out_or_in; //true iff out … … 197 199 GraphInEdgeIt in; 198 200 public: 199 EdgeIt() : out_or_in(true), out(), in() { } 200 operator GraphEdgeIt() const { 201 Edge() : out_or_in(), out(), in() { } 202 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 203 operator GraphEdge() const { 201 204 if (out_or_in) return(out); else return(in); 202 205 } 203 }; 204 205 class OutEdgeIt : public EdgeIt { 206 friend bool operator==(const Edge& u, const Edge& v) { 207 if (v.out_or_in) 208 return (u.out_or_in && u.out==v.out); 209 else 210 return (!u.out_or_in && u.in==v.in); 211 } 212 friend bool operator!=(const Edge& u, const Edge& v) { 213 if (v.out_or_in) 214 return (!u.out_or_in || u.out!=v.out); 215 else 216 return (u.out_or_in || u.in!=v.in); 217 } 218 }; 219 220 class OutEdgeIt : public Edge { 206 221 friend class UndirGraphWrapper<Graph>; 207 222 public: 208 OutEdgeIt() : EdgeIt() { } 209 OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { 210 _G.graph->getFirst(out, n); 223 OutEdgeIt() : Edge() { } 224 OutEdgeIt(const Invalid& i) : Edge(i) { } 225 OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { 226 out_or_in=true; 227 _G.graph->/*getF*/first(out, n); 211 228 if (!(_G.graph->valid(out))) { 212 229 out_or_in=false; 213 _G.graph-> getFirst(in, n);230 _G.graph->/*getF*/first(in, n); 214 231 } 215 232 } 216 233 }; 217 234 218 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {235 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { 219 236 e.out_or_in=true; 220 graph-> getFirst(e.out, n);237 graph->/*getF*/first(e.out, n); 221 238 if (!(graph->valid(e.out))) { 222 239 e.out_or_in=false; 223 graph-> getFirst(e.in, n);240 graph->/*getF*/first(e.in, n); 224 241 } 225 242 return e; … … 228 245 OutEdgeIt& next(OutEdgeIt& e) const { 229 246 if (e.out_or_in) { 230 Node Itn=graph->tail(e.out);247 Node n=graph->tail(e.out); 231 248 graph->next(e.out); 232 249 if (!graph->valid(e.out)) { 233 250 e.out_or_in=false; 234 graph-> getFirst(e.in, n);251 graph->/*getF*/first(e.in, n); 235 252 } 236 253 } else { … … 240 257 } 241 258 242 Node ItaNode(const OutEdgeIt& e) const {259 Node aNode(const OutEdgeIt& e) const { 243 260 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } 244 Node ItbNode(const OutEdgeIt& e) const {261 Node bNode(const OutEdgeIt& e) const { 245 262 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } 246 263 247 264 typedef OutEdgeIt InEdgeIt; 248 265 249 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }250 // template<typename I, typename P> I& getFirst(I& i, const P& p) const {251 // return graph-> getFirst(i, p); }266 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } 267 // template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 268 // return graph->/*getF*/first(i, p); } 252 269 253 270 template<typename I> I getNext(const I& i) const { … … 256 273 257 274 template< typename It > It first() const { 258 It e; getFirst(e); return e; }259 260 template< typename It > It first(const Node It& v) const {261 It e; getFirst(e, v); return e; }262 263 Node It head(const EdgeIt& e) const { return graph->head(e); }264 Node It tail(const EdgeIt& e) const { return graph->tail(e); }275 It e; /*getF*/first(e); return e; } 276 277 template< typename It > It first(const Node& v) const { 278 It e; /*getF*/first(e, v); return e; } 279 280 Node head(const Edge& e) const { return graph->head(e); } 281 Node tail(const Edge& e) const { return graph->tail(e); } 265 282 266 283 template<typename I> bool valid(const I& i) const … … 273 290 int edgeNum() const { return graph->edgeNum(); } 274 291 275 // template<typename I> Node ItaNode(const I& e) const {292 // template<typename I> Node aNode(const I& e) const { 276 293 // return graph->aNode(e); } 277 // template<typename I> Node ItbNode(const I& e) const {294 // template<typename I> Node bNode(const I& e) const { 278 295 // return graph->bNode(e); } 279 296 280 Node ItaddNode() const { return graph->addNode(); }281 Edge It addEdge(const NodeIt& tail, const NodeIt& head) const {297 Node addNode() const { return graph->addNode(); } 298 Edge addEdge(const Node& tail, const Node& head) const { 282 299 return graph->addEdge(tail, head); } 283 300 … … 313 330 // typedef Graph BaseGraph; 314 331 332 // typedef typename Graph::Node Node; 333 // typedef typename Graph::Edge Edge; 334 315 335 // typedef typename Graph::NodeIt NodeIt; 316 // typedef typename Graph::EdgeIt EdgeIt;317 318 // typedef typename Graph::EachNodeIt EachNodeIt;319 336 320 337 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon … … 324 341 // //typedef typename Graph::InEdgeIt SymEdgeIt; 325 342 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 326 // typedef typename Graph::E achEdgeIt EachEdgeIt;343 // typedef typename Graph::EdgeIt EdgeIt; 327 344 328 345 // int nodeNum() const { return graph->nodeNum(); } 329 346 // int edgeNum() const { return graph->edgeNum(); } 330 347 331 // template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }332 // template<typename I, typename P> I& getFirst(I& i, const P& p) const {333 // return graph-> getFirst(i, p); }348 // template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } 349 // template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 350 // return graph->/*getF*/first(i, p); } 334 351 // //template<typename I> I next(const I i); { return graph->goNext(i); } 335 352 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } 336 353 337 354 // template< typename It > It first() const { 338 // It e; getFirst(e); return e; }339 340 // template< typename It > It first(Node Itv) const {341 // It e; getFirst(e, v); return e; }342 343 // Node It head(const EdgeIt& e) const { return graph->head(e); }344 // Node It tail(const EdgeIt& e) const { return graph->tail(e); }345 346 // template<typename I> Node ItaNode(const I& e) const {355 // It e; /*getF*/first(e); return e; } 356 357 // template< typename It > It first(Node v) const { 358 // It e; /*getF*/first(e, v); return e; } 359 360 // Node head(const Edge& e) const { return graph->head(e); } 361 // Node tail(const Edge& e) const { return graph->tail(e); } 362 363 // template<typename I> Node aNode(const I& e) const { 347 364 // return graph->aNode(e); } 348 // template<typename I> Node ItbNode(const I& e) const {365 // template<typename I> Node bNode(const I& e) const { 349 366 // return graph->bNode(e); } 350 367 … … 355 372 // //{ return graph->setInvalid(i); } 356 373 357 // Node ItaddNode() { return graph->addNode(); }358 // Edge It addEdge(const NodeIt& tail, const NodeIt& head) {374 // Node addNode() { return graph->addNode(); } 375 // Edge addEdge(const Node& tail, const Node& head) { 359 376 // return graph->addEdge(tail, head); } 360 377 … … 378 395 public: 379 396 typedef Graph BaseGraph; 397 typedef typename Graph::Node Node; 380 398 typedef typename Graph::NodeIt NodeIt; 381 typedef typename Graph::EachNodeIt EachNodeIt;382 399 private: 383 400 typedef typename Graph::OutEdgeIt OldOutEdgeIt; 384 401 typedef typename Graph::InEdgeIt OldInEdgeIt; 385 const Graph* G;402 const Graph* graph; 386 403 FlowMap* flow; 387 404 const CapacityMap* capacity; … … 390 407 ResGraphWrapper(const Graph& _G, FlowMap& _flow, 391 408 const CapacityMap& _capacity) : 392 G(&_G), flow(&_flow), capacity(&_capacity) { } 393 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 394 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } 409 graph(&_G), flow(&_flow), capacity(&_capacity) { } 395 410 396 411 void setGraph(const Graph& _graph) { graph = &_graph; } 397 const Graph& getGraph() const { return (* G); }398 399 class Edge It;412 const Graph& getGraph() const { return (*graph); } 413 414 class Edge; 400 415 class OutEdgeIt; 401 friend class Edge It;416 friend class Edge; 402 417 friend class OutEdgeIt; 403 418 404 class Edge It{419 class Edge { 405 420 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 406 421 protected: … … 409 424 OldInEdgeIt in; 410 425 public: 411 EdgeIt() : out_or_in(true) { } 426 Edge() : out_or_in(true) { } 427 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 412 428 // bool valid() const { 413 429 // return out_or_in && out.valid() || in.valid(); } 414 }; 415 416 417 class OutEdgeIt : public EdgeIt { 430 friend bool operator==(const Edge& u, const Edge& v) { 431 if (v.out_or_in) 432 return (u.out_or_in && u.out==v.out); 433 else 434 return (!u.out_or_in && u.in==v.in); 435 } 436 friend bool operator!=(const Edge& u, const Edge& v) { 437 if (v.out_or_in) 438 return (!u.out_or_in || u.out!=v.out); 439 else 440 return (u.out_or_in || u.in!=v.in); 441 } 442 }; 443 444 445 class OutEdgeIt : public Edge { 418 446 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 419 447 public: 420 448 OutEdgeIt() { } 421 449 //FIXME 422 OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { } 450 OutEdgeIt(const Edge& e) : Edge(e) { } 451 OutEdgeIt(const Invalid& i) : Edge(i) { } 423 452 private: 424 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node It v) : EdgeIt() {425 resG. G->getFirst(out, v);426 while( out.valid() && !(resG.free(out)>0) ) { ++out; }427 if (! out.valid()) {453 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 454 resG.graph->/*getF*/first(out, v); 455 while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } 456 if (!resG.graph->valid(out)) { 428 457 out_or_in=0; 429 resG. G->getFirst(in, v);430 while( in.valid() && !(resG.free(in)>0) ) { ++in; }458 resG.graph->/*getF*/first(in, v); 459 while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } 431 460 } 432 461 } … … 434 463 // OutEdgeIt& operator++() { 435 464 // if (out_or_in) { 436 // Node Itv=/*resG->*/G->aNode(out);465 // Node v=/*resG->*/G->aNode(out); 437 466 // ++out; 438 // while( out.valid() && !(Edge It::free()>0) ) { ++out; }467 // while( out.valid() && !(Edge::free()>0) ) { ++out; } 439 468 // if (!out.valid()) { 440 469 // out_or_in=0; 441 // G-> getFirst(in, v);442 // while( in.valid() && !(Edge It::free()>0) ) { ++in; }470 // G->/*getF*/first(in, v); 471 // while( in.valid() && !(Edge::free()>0) ) { ++in; } 443 472 // } 444 473 // } else { 445 474 // ++in; 446 // while( in.valid() && !(Edge It::free()>0) ) { ++in; }475 // while( in.valid() && !(Edge::free()>0) ) { ++in; } 447 476 // } 448 477 // return *this; … … 450 479 }; 451 480 452 class E achEdgeIt : public EdgeIt{481 class EdgeIt : public Edge { 453 482 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 454 typename Graph::EachNodeIt v; 455 public: 456 EachEdgeIt() { } 457 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } 458 EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() { 459 resG.G->getFirst(v); 460 if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt(); 461 while (out.valid() && !(resG.free(out)>0) ) { ++out; } 462 while (v.valid() && !out.valid()) { 463 ++v; 464 if (v.valid()) resG.G->getFirst(out, v); 465 while (out.valid() && !(resG.free(out)>0) ) { ++out; } 483 typename Graph::NodeIt v; 484 public: 485 EdgeIt() { } 486 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } 487 EdgeIt(const Invalid& i) : Edge(i) { } 488 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 489 resG.graph->/*getF*/first(v); 490 if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID); 491 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } 492 while (resG.graph->valid(v) && !resG.graph->valid(out)) { 493 resG.graph->next(v); 494 if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); 495 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } 466 496 } 467 if (! out.valid()) {497 if (!resG.graph->valid(out)) { 468 498 out_or_in=0; 469 resG. G->getFirst(v);470 if ( v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();471 while ( in.valid() && !(resG.free(in)>0) ) { ++in; }472 while ( v.valid() && !in.valid()) {473 ++v;474 if ( v.valid()) resG.G->getFirst(in, v);475 while ( in.valid() && !(resG.free(in)>0) ) { ++in; }499 resG.graph->/*getF*/first(v); 500 if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID); 501 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } 502 while (resG.graph->valid(v) && !resG.graph->valid(in)) { 503 resG.graph->next(v); 504 if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); 505 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } 476 506 } 477 507 } 478 508 } 479 // E achEdgeIt& operator++() {509 // EdgeIt& operator++() { 480 510 // if (out_or_in) { 481 511 // ++out; 482 // while (out.valid() && !(Edge It::free()>0) ) { ++out; }512 // while (out.valid() && !(Edge::free()>0) ) { ++out; } 483 513 // while (v.valid() && !out.valid()) { 484 514 // ++v; 485 // if (v.valid()) G-> getFirst(out, v);486 // while (out.valid() && !(Edge It::free()>0) ) { ++out; }515 // if (v.valid()) G->/*getF*/first(out, v); 516 // while (out.valid() && !(Edge::free()>0) ) { ++out; } 487 517 // } 488 518 // if (!out.valid()) { 489 519 // out_or_in=0; 490 // G-> getFirst(v);491 // if (v.valid()) G-> getFirst(in, v); else in=OldInEdgeIt();492 // while (in.valid() && !(Edge It::free()>0) ) { ++in; }520 // G->/*getF*/first(v); 521 // if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt(); 522 // while (in.valid() && !(Edge::free()>0) ) { ++in; } 493 523 // while (v.valid() && !in.valid()) { 494 524 // ++v; 495 // if (v.valid()) G-> getFirst(in, v);496 // while (in.valid() && !(Edge It::free()>0) ) { ++in; }525 // if (v.valid()) G->/*getF*/first(in, v); 526 // while (in.valid() && !(Edge::free()>0) ) { ++in; } 497 527 // } 498 528 // } 499 529 // } else { 500 530 // ++in; 501 // while (in.valid() && !(Edge It::free()>0) ) { ++in; }531 // while (in.valid() && !(Edge::free()>0) ) { ++in; } 502 532 // while (v.valid() && !in.valid()) { 503 533 // ++v; 504 // if (v.valid()) G-> getFirst(in, v);505 // while (in.valid() && !(Edge It::free()>0) ) { ++in; }534 // if (v.valid()) G->/*getF*/first(in, v); 535 // while (in.valid() && !(Edge::free()>0) ) { ++in; } 506 536 // } 507 537 // } … … 510 540 }; 511 541 512 EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }513 OutEdgeIt& getFirst(OutEdgeIt& e, NodeItv) const {542 NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); } 543 OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { 514 544 e=OutEdgeIt(*this, v); 515 } 516 EachEdgeIt& getFirst(EachEdgeIt& e) const { 517 e=EachEdgeIt(*this); 545 return e; 546 } 547 EdgeIt& /*getF*/first(EdgeIt& e) const { 548 e=EdgeIt(*this); 549 return e; 518 550 } 519 551 520 EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }552 NodeIt& next(NodeIt& n) const { return graph->next(n); } 521 553 522 554 OutEdgeIt& next(OutEdgeIt& e) const { 523 555 if (e.out_or_in) { 524 Node It v=G->aNode(e.out);525 ++(e.out);526 while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }527 if (! G->valid(e.out)) {556 Node v=graph->aNode(e.out); 557 graph->next(e.out); 558 while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } 559 if (!graph->valid(e.out)) { 528 560 e.out_or_in=0; 529 G->getFirst(e.in, v);530 while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }561 graph->/*getF*/first(e.in, v); 562 while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 531 563 } 532 564 } else { 533 ++(e.in);534 while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }565 graph->next(e.in); 566 while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 535 567 } 536 568 return e; 537 569 } 538 570 539 E achEdgeIt& next(EachEdgeIt& e) const {571 EdgeIt& next(EdgeIt& e) const { 540 572 if (e.out_or_in) { 541 ++(e.out);542 while ( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }543 while ( G->valid(e.v) && !G->valid(e.out)) {544 ++(e.v);545 if ( G->valid(e.v)) G->getFirst(e.out, e.v);546 while ( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }573 graph->next(e.out); 574 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } 575 while (graph->valid(e.v) && !graph->valid(e.out)) { 576 graph->next(e.v); 577 if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v); 578 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } 547 579 } 548 if (! G->valid(e.out)) {580 if (!graph->valid(e.out)) { 549 581 e.out_or_in=0; 550 G->getFirst(e.v);551 if ( G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();552 while ( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }553 while ( G->valid(e.v) && !G->valid(e.in)) {554 ++(e.v);555 if ( G->valid(e.v)) G->getFirst(e.in, e.v);556 while ( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }582 graph->/*getF*/first(e.v); 583 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); 584 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 585 while (graph->valid(e.v) && !graph->valid(e.in)) { 586 graph->next(e.v); 587 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); 588 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 557 589 } 558 590 } 559 591 } else { 560 ++(e.in);561 while ( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }562 while ( G->valid(e.v) && !G->valid(e.in)) {563 ++(e.v);564 if ( G->valid(e.v)) G->getFirst(e.in, e.v);565 while ( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }592 graph->next(e.in); 593 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 594 while (graph->valid(e.v) && !graph->valid(e.in)) { 595 graph->next(e.v); 596 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); 597 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 566 598 } 567 599 } … … 573 605 It first() const { 574 606 It e; 575 getFirst(e);607 /*getF*/first(e); 576 608 return e; 577 609 } 578 610 579 611 template< typename It > 580 It first(Node Itv) const {612 It first(Node v) const { 581 613 It e; 582 getFirst(e, v);614 /*getF*/first(e, v); 583 615 return e; 584 616 } 585 617 586 Node It tail(EdgeIte) const {587 return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }588 Node It head(EdgeIte) const {589 return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }590 591 Node ItaNode(OutEdgeIt e) const {592 return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }593 Node ItbNode(OutEdgeIt e) const {594 return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }595 596 int id(Node It v) const { return G->id(v); }597 598 bool valid(Node It n) const { return G->valid(n); }599 bool valid(Edge Ite) const {600 return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }601 602 void augment(const Edge It& e, Number a) const {618 Node tail(Edge e) const { 619 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 620 Node head(Edge e) const { 621 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 622 623 Node aNode(OutEdgeIt e) const { 624 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 625 Node bNode(OutEdgeIt e) const { 626 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 627 628 int id(Node v) const { return graph->id(v); } 629 630 bool valid(Node n) const { return graph->valid(n); } 631 bool valid(Edge e) const { 632 return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } 633 634 void augment(const Edge& e, Number a) const { 603 635 if (e.out_or_in) 604 636 flow->set(e.out, flow->get(e.out)+a); … … 607 639 } 608 640 609 Number free(const Edge It& e) const {641 Number free(const Edge& e) const { 610 642 if (e.out_or_in) 611 643 return (capacity->get(e.out)-flow->get(e.out)); … … 634 666 // typename Graph::NodeMap<T> node_map; 635 667 // public: 636 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G. G)) { }637 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G. G), a) { }638 // void set(Node Itnit, T a) { node_map.set(nit, a); }639 // T get(Node Itnit) const { return node_map.get(nit); }668 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { } 669 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { } 670 // void set(Node nit, T a) { node_map.set(nit, a); } 671 // T get(Node nit) const { return node_map.get(nit); } 640 672 // }; 641 673 … … 646 678 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { } 647 679 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { } 648 void set(Edge Ite, T a) {680 void set(Edge e, T a) { 649 681 if (e.out_or_in) 650 682 forward_map.set(e.out, a); … … 652 684 backward_map.set(e.in, a); 653 685 } 654 T get(Edge Ite) {686 T get(Edge e) { 655 687 if (e.out_or_in) 656 688 return forward_map.get(e.out); … … 671 703 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), 672 704 first_out_edges(*this) /*, dist(*this)*/ { 673 for( EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {705 for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) { 674 706 OutEdgeIt e; 675 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: getFirst(e, n);707 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n); 676 708 first_out_edges.set(n, e); 677 709 } … … 686 718 //typedef Graph BaseGraph; 687 719 720 //typedef typename Graph::Node Node; 688 721 //typedef typename Graph::NodeIt NodeIt; 689 //typedef typename Graph::EachNodeIt EachNodeIt; 690 691 //typedef typename Graph::EdgeIt EdgeIt; 722 723 //typedef typename Graph::Edge Edge; 692 724 //typedef typename Graph::OutEdgeIt OutEdgeIt; 693 725 //typedef typename Graph::InEdgeIt InEdgeIt; 694 726 //typedef typename Graph::SymEdgeIt SymEdgeIt; 695 //typedef typename Graph::EachEdgeIt EachEdgeIt; 696 727 //typedef typename Graph::EdgeIt EdgeIt; 728 729 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node; 697 730 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; 698 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt; 699 700 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; 731 732 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge; 701 733 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; 702 734 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; 703 735 //typedef typename Graph::SymEdgeIt SymEdgeIt; 704 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::E achEdgeIt EachEdgeIt;705 706 EachNodeIt& getFirst(EachNodeIt& n) const {707 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: getFirst(n);708 } 709 710 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {736 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; 737 738 NodeIt& /*getF*/first(NodeIt& n) const { 739 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n); 740 } 741 742 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { 711 743 e=first_out_edges.get(n); 712 744 return e; 713 745 } 714 746 715 //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }716 //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {717 // return getFirst(i, p); }747 //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); } 748 //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 749 // return /*getF*/first(i, p); } 718 750 719 751 //template<typename I> I getNext(const I& i) const { … … 722 754 723 755 template< typename It > It first() const { 724 It e; getFirst(e); return e; }725 726 template< typename It > It first(const Node It& v) const {727 It e; getFirst(e, v); return e; }728 729 //Node It head(const EdgeIt& e) const { return graph->head(e); }730 //Node It tail(const EdgeIt& e) const { return graph->tail(e); }756 It e; /*getF*/first(e); return e; } 757 758 template< typename It > It first(const Node& v) const { 759 It e; /*getF*/first(e, v); return e; } 760 761 //Node head(const Edge& e) const { return graph->head(e); } 762 //Node tail(const Edge& e) const { return graph->tail(e); } 731 763 732 764 //template<typename I> bool valid(const I& i) const … … 736 768 //int edgeNum() const { return graph->edgeNum(); } 737 769 738 //template<typename I> Node ItaNode(const I& e) const {770 //template<typename I> Node aNode(const I& e) const { 739 771 // return graph->aNode(e); } 740 //template<typename I> Node ItbNode(const I& e) const {772 //template<typename I> Node bNode(const I& e) const { 741 773 // return graph->bNode(e); } 742 774 743 //Node ItaddNode() const { return graph->addNode(); }744 //Edge It addEdge(const NodeIt& tail, const NodeIt& head) const {775 //Node addNode() const { return graph->addNode(); } 776 //Edge addEdge(const Node& tail, const Node& head) const { 745 777 // return graph->addEdge(tail, head); } 746 778 … … 748 780 // first_out_edge(this->tail(e))=e; 749 781 //} 750 void erase(const Edge It& e) {782 void erase(const Edge& e) { 751 783 OutEdgeIt f(e); 752 784 next(f); … … 786 818 //typedef Graph BaseGraph; 787 819 820 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node; 788 821 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; 789 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt; 790 791 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; 822 823 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge; 792 824 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; 793 825 //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; 794 826 //typedef typename Graph::SymEdgeIt SymEdgeIt; 795 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::E achEdgeIt EachEdgeIt;827 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; 796 828 797 829 //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges; … … 803 835 } 804 836 805 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {806 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: getFirst(e, n);837 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { 838 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n); 807 839 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 808 840 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); … … 810 842 } 811 843 812 EachNodeIt& next(EachNodeIt& e) const {844 NodeIt& next(NodeIt& e) const { 813 845 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 814 846 } … … 821 853 } 822 854 823 EachNodeIt& getFirst(EachNodeIt& n) const {824 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: getFirst(n);825 } 826 827 void erase(const Edge It& e) {855 NodeIt& /*getF*/first(NodeIt& n) const { 856 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n); 857 } 858 859 void erase(const Edge& e) { 828 860 OutEdgeIt f(e); 829 861 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); … … 839 871 //Graph& getGraph() const { return (*graph); } 840 872 841 //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }842 //template<typename I, typename P> I& getFirst(I& i, const P& p) const {843 // return graph-> getFirst(i, p); }873 //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } 874 //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 875 // return graph->/*getF*/first(i, p); } 844 876 845 877 //template<typename I> I getNext(const I& i) const { … … 848 880 849 881 template< typename It > It first() const { 850 It e; getFirst(e); return e; }851 852 template< typename It > It first(const Node It& v) const {853 It e; getFirst(e, v); return e; }854 855 //Node It head(const EdgeIt& e) const { return graph->head(e); }856 //Node It tail(const EdgeIt& e) const { return graph->tail(e); }882 It e; /*getF*/first(e); return e; } 883 884 template< typename It > It first(const Node& v) const { 885 It e; /*getF*/first(e, v); return e; } 886 887 //Node head(const Edge& e) const { return graph->head(e); } 888 //Node tail(const Edge& e) const { return graph->tail(e); } 857 889 858 890 //template<typename I> bool valid(const I& i) const … … 865 897 //int edgeNum() const { return graph->edgeNum(); } 866 898 867 //template<typename I> Node ItaNode(const I& e) const {899 //template<typename I> Node aNode(const I& e) const { 868 900 // return graph->aNode(e); } 869 //template<typename I> Node ItbNode(const I& e) const {901 //template<typename I> Node bNode(const I& e) const { 870 902 // return graph->bNode(e); } 871 903 872 //Node ItaddNode() const { return graph->addNode(); }873 //Edge It addEdge(const NodeIt& tail, const NodeIt& head) const {904 //Node addNode() const { return graph->addNode(); } 905 //Edge addEdge(const Node& tail, const Node& head) const { 874 906 // return graph->addEdge(tail, head); } 875 907 … … 910 942 // typedef Graph BaseGraph; 911 943 944 // typedef typename Graph::Node Node; 945 // typedef typename Graph::Edge Edge; 946 912 947 // typedef typename Graph::NodeIt NodeIt; 913 // typedef typename Graph::EdgeIt EdgeIt;914 915 // typedef typename Graph::EachNodeIt EachNodeIt;916 948 917 949 // class OutEdgeIt { 918 950 // public: 919 // //Graph::Node Itn;951 // //Graph::Node n; 920 952 // bool out_or_in; 921 953 // typename Graph::OutEdgeIt o; … … 924 956 // class InEdgeIt { 925 957 // public: 926 // //Graph::Node Itn;958 // //Graph::Node n; 927 959 // bool out_or_in; 928 960 // typename Graph::OutEdgeIt o; … … 930 962 // }; 931 963 // typedef typename Graph::SymEdgeIt SymEdgeIt; 932 // typedef typename Graph::E achEdgeIt EachEdgeIt;964 // typedef typename Graph::EdgeIt EdgeIt; 933 965 934 966 // int nodeNum() const { return graph->nodeNum(); } 935 967 // int edgeNum() const { return graph->edgeNum(); } 936 968 937 // Node It& getFirst(NodeIt& n) const { return graph->getFirst(n); }938 939 // // E achEdge and SymEdge is missing!!!!940 // // Edge It<-> In/OutEdgeIt conversion is missing!!!!969 // Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); } 970 971 // // Edge and SymEdge is missing!!!! 972 // // Edge <-> In/OutEdgeIt conversion is missing!!!! 941 973 942 974 // //FIXME 943 // OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const975 // OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const 944 976 // { 945 977 // e.n=n; 946 // graph-> getFirst(e.o,n);978 // graph->/*getF*/first(e.o,n); 947 979 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) 948 980 // graph->goNext(e.o); 949 981 // if(!graph->valid(e.o)) { 950 // graph-> getFirst(e.i,n);982 // graph->/*getF*/first(e.i,n); 951 983 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) 952 984 // graph->goNext(e.i); … … 961 993 // graph->goNext(e.o); 962 994 // if(graph->valid(e.o)) return e; 963 // else graph-> getFirst(e.i,e.n);995 // else graph->/*getF*/first(e.i,e.n); 964 996 // } 965 997 // else { … … 974 1006 975 1007 // //FIXME 976 // InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const1008 // InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const 977 1009 // { 978 1010 // e.n=n; 979 // graph-> getFirst(e.i,n);1011 // graph->/*getF*/first(e.i,n); 980 1012 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) 981 1013 // graph->goNext(e.i); 982 1014 // if(!graph->valid(e.i)) { 983 // graph-> getFirst(e.o,n);1015 // graph->/*getF*/first(e.o,n); 984 1016 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) 985 1017 // graph->goNext(e.o); … … 994 1026 // graph->goNext(e.i); 995 1027 // if(graph->valid(e.i)) return e; 996 // else graph-> getFirst(e.o,e.n);1028 // else graph->/*getF*/first(e.o,e.n); 997 1029 // } 998 1030 // else { … … 1010 1042 1011 1043 // template< typename It > It first() const { 1012 // It e; getFirst(e); return e; }1013 1014 // template< typename It > It first(Node Itv) const {1015 // It e; getFirst(e, v); return e; }1016 1017 // Node It head(const EdgeIt& e) const { return graph->head(e); }1018 // Node It tail(const EdgeIt& e) const { return graph->tail(e); }1019 1020 // template<typename I> Node ItaNode(const I& e) const {1044 // It e; /*getF*/first(e); return e; } 1045 1046 // template< typename It > It first(Node v) const { 1047 // It e; /*getF*/first(e, v); return e; } 1048 1049 // Node head(const Edge& e) const { return graph->head(e); } 1050 // Node tail(const Edge& e) const { return graph->tail(e); } 1051 1052 // template<typename I> Node aNode(const I& e) const { 1021 1053 // return graph->aNode(e); } 1022 // template<typename I> Node ItbNode(const I& e) const {1054 // template<typename I> Node bNode(const I& e) const { 1023 1055 // return graph->bNode(e); } 1024 1056 … … 1029 1061 // //{ return graph->setInvalid(i); } 1030 1062 1031 // Node ItaddNode() { return graph->addNode(); }1032 // Edge It addEdge(const NodeIt& tail, const NodeIt& head) {1063 // Node addNode() { return graph->addNode(); } 1064 // Edge addEdge(const Node& tail, const Node& head) { 1033 1065 // return graph->addEdge(tail, head); } 1034 1066 -
src/work/marci/makefile
r168 r174 2 2 CXX2 = g++-2.95 3 3 CXX3.3 = g++ 4 CXXFLAGS = -W -Wall -ansi -pedantic 4 CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar 5 5 LEDAROOT ?= /ledasrc/LEDA-4.1 6 6 7 BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos 7 BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos lg_vs_sg 8 8 9 9 all: $(BINARIES) … … 17 17 18 18 edmonds_karp_demo: 19 $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc 20 $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc 19 $(CXX3) $(CXXFLAGS) -g -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc 20 $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc 21 22 lg_vs_sg: 23 $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o lg_vs_sg lg_vs_sg.cc 21 24 22 25 edmonds_karp_demo_alpar:
Note: See TracChangeset
for help on using the changeset viewer.