Changeset 986:e997802b855c in lemon-0.x
- Timestamp:
- 11/13/04 13:53:28 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
- Files:
-
- 104 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/graphs.dox
r959 r986 126 126 std::cout << "Edges:"; 127 127 for (EdgeIt i(g); i!=INVALID; ++i) 128 std::cout << " (" << g.id(g. tail(i)) << "," << g.id(g.head(i)) << ")";128 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 129 129 std::cout << std::endl; 130 130 \endcode … … 134 134 \endcode 135 135 136 We can also iterate through all edges of the graph very similarly. The headand137 tailmember functions can be used to access the endpoints of an edge.136 We can also iterate through all edges of the graph very similarly. The target and 137 source member functions can be used to access the endpoints of an edge. 138 138 139 139 \code … … 142 142 std::cout << "Out-edges of node " << g.id(first_node) << ":"; 143 143 for (OutEdgeIt i(g, first_node); i!=INVALID; ++i) 144 std::cout << " (" << g.id(g. tail(i)) << "," << g.id(g.head(i)) << ")";144 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 145 145 std::cout << std::endl; 146 146 147 147 std::cout << "In-edges of node " << g.id(first_node) << ":"; 148 148 for (InEdgeIt i(g, first_node); i!=INVALID; ++i) 149 std::cout << " (" << g.id(g. tail(i)) << "," << g.id(g.head(i)) << ")";149 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 150 150 std::cout << std::endl; 151 151 \endcode … … 167 167 std::cout << "Id Edge Value" << std::endl; 168 168 for (EdgeIt e(g); e!=INVALID; ++e) 169 std::cout << g.id(e) << " (" << g.id(g. tail(e)) << "," << g.id(g.head(e))169 std::cout << g.id(e) << " (" << g.id(g.source(e)) << "," << g.id(g.target(e)) 170 170 << ") " << m[e] << std::endl; 171 171 \endcode -
doc/maps.dox
r927 r986 113 113 public: 114 114 ValueType operator[](KeyType e) const { 115 return orig_len.get(e)-pot.get(G. head(e))-pot.get(G.tail(e));115 return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e)); 116 116 } 117 117 -
src/benchmark/bfs-bench.cc
r921 r986 47 47 Q.pop(); 48 48 for(OutEdgeIt e(G,n);e!=INVALID;++e) 49 if(!visited[m=G. head(e)]) {49 if(!visited[m=G.target(e)]) { 50 50 Q.push(m); 51 51 visited.set(m,true); … … 75 75 Node n=Q[Qt++]; 76 76 for(OutEdgeIt e(G,n);e!=INVALID;++e) 77 if(!visited[m=G. head(e)]) {77 if(!visited[m=G.target(e)]) { 78 78 Q[Qh++]=m; 79 79 visited.set(m,true); -
src/demo/dim_to_dot.cc
r931 r986 52 52 cout << " edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];" << endl; 53 53 for(EdgeIt e(g); e!=INVALID; ++e) { 54 cout << " n" << g.id(g. tail(e)) << " -> " << " n" << g.id(g.head(e))54 cout << " n" << g.id(g.source(e)) << " -> " << " n" << g.id(g.target(e)) 55 55 << " [ label=\"" << g.id(e) 56 56 << ", length:" << length[e] << "\" ]; " << endl; -
src/demo/sub_graph_wrapper_demo.cc
r932 r986 38 38 readDimacs(std::cin, g, length, s, t); 39 39 40 cout << "edges with lengths (of form id, tail--length->head): " << endl;40 cout << "edges with lengths (of form id, source--length->target): " << endl; 41 41 for(EdgeIt e(g); e!=INVALID; ++e) 42 cout << " " << g.id(e) << ", " << g.id(g. tail(e)) << "--"43 << length[e] << "->" << g.id(g. head(e)) << endl;42 cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" 43 << length[e] << "->" << g.id(g.target(e)) << endl; 44 44 45 45 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; … … 76 76 if (flow[e]) 77 77 cout << " " << g.id(e) << ", " 78 << g.id(g. tail(e)) << "--"79 << length[e] << "->" << g.id(g. head(e)) << endl;78 << g.id(g.source(e)) << "--" 79 << length[e] << "->" << g.id(g.target(e)) << endl; 80 80 } -
src/demo/tight_edge_filter_map.h
r929 r986 32 32 /// A node-map node_potential is said to be a potential w.r.t. 33 33 /// an edge-map edge_distance 34 /// if and only if for each edge e, node_potential[g. head(e)]35 /// <= edge_distance[e]+node_potential[g. tail(e)]34 /// if and only if for each edge e, node_potential[g.target(e)] 35 /// <= edge_distance[e]+node_potential[g.source(e)] 36 36 /// (or the reverse inequality holds for each edge). 37 37 /// An edge is said to be tight if this inequality holds with equality, … … 52 52 edge_distance(&_edge_distance) { } 53 53 bool operator[](const typename Graph::Edge& e) const { 54 return ((*node_potential)[g-> head(e)] ==55 (*edge_distance)[e]+(*node_potential)[g-> tail(e)]);54 return ((*node_potential)[g->target(e)] == 55 (*edge_distance)[e]+(*node_potential)[g->source(e)]); 56 56 } 57 57 }; -
src/lemon/bfs.h
r977 r986 210 210 211 211 for(OutEdgeIt e(*G,n);e!=INVALID;++e) 212 if((m=G-> head(e))!=s && (*predecessor)[m]==INVALID) {212 if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) { 213 213 Q[Qh++]=m; 214 214 predecessor->set(m,e); -
src/lemon/concept/graph.h
r961 r986 364 364 // EdgeIt& first(EdgeIt& i) const { return i; } 365 365 366 // ///Gives back the headnode of an edge.367 368 // ///Gives back the headnode of an edge.369 // /// 370 // Node head(Edge) const { return INVALID; }371 // ///Gives back the tailnode of an edge.372 373 // ///Gives back the tailnode of an edge.374 // /// 375 // Node tail(Edge) const { return INVALID; }366 // ///Gives back the target node of an edge. 367 368 // ///Gives back the target node of an edge. 369 // /// 370 // Node target(Edge) const { return INVALID; } 371 // ///Gives back the source node of an edge. 372 373 // ///Gives back the source node of an edge. 374 // /// 375 // Node source(Edge) const { return INVALID; } 376 376 377 377 // ///Gives back the \e id of a node. … … 539 539 // Edge e; 540 540 // e=INVALID; 541 // n=G. tail(e);542 // n=G. head(e);541 // n=G.source(e); 542 // n=G.target(e); 543 543 // } 544 544 // // id tests … … 666 666 // ///Add a new edge to the graph. 667 667 668 // ///Add a new edge to the graph with tailnode \c t669 // ///and headnode \c h.668 // ///Add a new edge to the graph with source node \c t 669 // ///and target node \c h. 670 670 // ///\return the new edge. 671 671 // Edge addEdge(Node h, Node t) { return INVALID; } … … 801 801 void nextInEdge(Edge &e) const { } 802 802 803 Node head(Edge) const { return Node(); }804 Node tail(Edge) const { return Node(); }803 Node target(Edge) const { return Node(); } 804 Node source(Edge) const { return Node(); } 805 805 806 806 -
src/lemon/concept/graph_component.h
r980 r986 243 243 }; 244 244 245 ///Gives back the headnode of an edge.246 247 ///Gives back the headnode of an edge.248 /// 249 Node head(const Edge&) const { return INVALID;}250 251 ///Gives back the tailnode of an edge.252 253 ///Gives back the tailnode of an edge.254 /// 255 Node tail(const Edge&) const { return INVALID;}245 ///Gives back the target node of an edge. 246 247 ///Gives back the target node of an edge. 248 /// 249 Node target(const Edge&) const { return INVALID;} 250 251 ///Gives back the source node of an edge. 252 253 ///Gives back the source node of an edge. 254 /// 255 Node source(const Edge&) const { return INVALID;} 256 256 }; 257 257 … … 273 273 Node n; 274 274 Edge e; 275 n = graph. tail(e);276 n = graph. head(e);275 n = graph.source(e); 276 n = graph.target(e); 277 277 } 278 278 } -
src/lemon/concept/path.h
r967 r986 67 67 /// Starting point of the path. 68 68 /// Returns INVALID if the path is empty. 69 GraphNode/*It*/ head() const {return INVALID;}69 GraphNode/*It*/ target() const {return INVALID;} 70 70 /// \brief End point of the path. 71 71 /// 72 72 /// End point of the path. 73 73 /// Returns INVALID if the path is empty. 74 GraphNode/*It*/ tail() const {return INVALID;}74 GraphNode/*It*/ source() const {return INVALID;} 75 75 76 76 /// \brief First NodeIt/EdgeIt. … … 81 81 It& first(It &i) const { return i=It(*this); } 82 82 83 /// \brief The headof an edge.84 /// 85 /// Returns node iterator pointing to the headnode of the83 /// \brief The target of an edge. 84 /// 85 /// Returns node iterator pointing to the target node of the 86 86 /// given edge iterator. 87 NodeIt head(const EdgeIt& e) const {return INVALID;}88 89 /// \brief The tailof an edge.90 /// 91 /// Returns node iterator pointing to the tailnode of the87 NodeIt target(const EdgeIt& e) const {return INVALID;} 88 89 /// \brief The source of an edge. 90 /// 91 /// Returns node iterator pointing to the source node of the 92 92 /// given edge iterator. 93 NodeIt tail(const EdgeIt& e) const {return INVALID;}93 NodeIt source(const EdgeIt& e) const {return INVALID;} 94 94 95 95 -
src/lemon/concept/sym_graph.h
r959 r986 451 451 SymEdgeIt& first(SymEdgeIt& i) const { return i; } 452 452 453 ///Gives back the headnode of an edge.454 455 ///Gives back the headnode of an edge.456 /// 457 Node head(Edge) const { return INVALID; }458 ///Gives back the tailnode of an edge.459 460 ///Gives back the tailnode of an edge.461 /// 462 Node tail(Edge) const { return INVALID; }453 ///Gives back the target node of an edge. 454 455 ///Gives back the target node of an edge. 456 /// 457 Node target(Edge) const { return INVALID; } 458 ///Gives back the source node of an edge. 459 460 ///Gives back the source node of an edge. 461 /// 462 Node source(Edge) const { return INVALID; } 463 463 464 464 ///Gives back the first node of an symmetric edge. … … 466 466 ///Gives back the first node of an symmetric edge. 467 467 /// 468 Node head(SymEdge) const { return INVALID; }468 Node target(SymEdge) const { return INVALID; } 469 469 ///Gives back the second node of an symmetric edge. 470 470 471 471 ///Gives back the second node of an symmetric edge. 472 472 /// 473 Node tail(SymEdge) const { return INVALID; }473 Node source(SymEdge) const { return INVALID; } 474 474 ///Gives back the \e id of a node. 475 475 … … 608 608 ///Add a new edge to the graph. 609 609 610 ///Add a new symmetric edge to the graph with tailnode \c t611 ///and headnode \c h.610 ///Add a new symmetric edge to the graph with source node \c t 611 ///and target node \c h. 612 612 ///\return the new edge. 613 613 SymEdge addEdge(Node h, Node t) { return INVALID; } -
src/lemon/concept/undir_graph.h
r962 r986 48 48 49 49 Node n; 50 n = graph. head(ue);51 n = graph. tail(ue);50 n = graph.target(ue); 51 n = graph.source(ue); 52 52 53 53 graph.first(ue); -
src/lemon/concept_check.h
r946 r986 26 26 "inline" is used for ignore_unused_variable_warning() 27 27 and function_requires() to make sure there is no 28 over headwith g++.28 overtarget with g++. 29 29 */ 30 30 -
src/lemon/dfs.h
r946 r986 207 207 do { 208 208 if((e=Q[Qh])!=INVALID) 209 if((m=G-> head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) {209 if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) { 210 210 predecessor->set(m,e); 211 211 pred_node->set(m,n); … … 215 215 } 216 216 else ++Q[Qh]; 217 else if(--Qh>=0) n=G-> tail(Q[Qh]);217 else if(--Qh>=0) n=G->source(Q[Qh]); 218 218 } while(Qh>=0); 219 219 } -
src/lemon/dijkstra.h
r959 r986 255 255 256 256 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { 257 Node w=G-> head(e);257 Node w=G->target(e); 258 258 switch(heap.state(w)) { 259 259 case HeapType::PRE_HEAP: -
src/lemon/dimacs.h
r964 r986 209 209 210 210 for(EdgeIt e(g); e!=INVALID; ++e) { 211 os << "a " << nodes[g. tail(e)] << " " << nodes[g.head(e)] << std::endl;211 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; 212 212 } 213 213 -
src/lemon/full_graph.h
r985 r986 79 79 int maxId(Edge = INVALID) const { return EdgeNum-1; } 80 80 81 Node tail(Edge e) const { return e.id % NodeNum; }82 Node head(Edge e) const { return e.id / NodeNum; }81 Node source(Edge e) const { return e.id % NodeNum; } 82 Node target(Edge e) const { return e.id / NodeNum; } 83 83 84 84 … … 137 137 138 138 protected: 139 int id; // NodeNum * head + tail;139 int id; // NodeNum * target + source; 140 140 141 141 Edge(int _id) : id(_id) {} 142 142 143 Edge(const FullGraphBase& _graph, int tail, int head)144 : id(_graph.NodeNum * head+tail) {}143 Edge(const FullGraphBase& _graph, int source, int target) 144 : id(_graph.NodeNum * target+source) {} 145 145 public: 146 146 Edge() { } … … 251 251 int maxId(Edge = INVALID) const { return EdgeNum-1; } 252 252 253 Node tail(Edge e) const {253 Node source(Edge e) const { 254 254 /// \todo we may do it faster 255 255 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; 256 256 } 257 257 258 Node head(Edge e) const {259 int tail= ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;260 return e.id - ( tail) * (tail- 1) / 2;258 Node target(Edge e) const { 259 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 260 return e.id - (source) * (source - 1) / 2; 261 261 } 262 262 … … 316 316 317 317 protected: 318 int id; // NodeNum * head + tail;318 int id; // NodeNum * target + source; 319 319 320 320 Edge(int _id) : id(_id) {} 321 321 322 Edge(const UndirFullGraphBase& _graph, int tail, int head)323 : id(_graph.NodeNum * head+tail) {}322 Edge(const UndirFullGraphBase& _graph, int source, int target) 323 : id(_graph.NodeNum * target+source) {} 324 324 public: 325 325 Edge() { } … … 352 352 /// \todo with specialized iterators we can make faster iterating 353 353 void nextOut(Edge& e) const { 354 int tail= ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;355 int head = e.id - (tail) * (tail- 1) / 2;356 ++ head;357 e.id = head < tail ? tail * (tail - 1) / 2 + head: -1;354 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 355 int target = e.id - (source) * (source - 1) / 2; 356 ++target; 357 e.id = target < source ? source * (source - 1) / 2 + target : -1; 358 358 } 359 359 … … 363 363 364 364 void nextIn(Edge& e) const { 365 int tail= ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;366 int head = e.id - (tail) * (tail - 1) / 2; ++head;367 ++ tail;368 e.id = tail < NodeNum ? tail * (tail - 1) / 2 + head: -1;365 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 366 int target = e.id - (source) * (source - 1) / 2; ++target; 367 ++source; 368 e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1; 369 369 } 370 370 -
src/lemon/graph_utils.h
r977 r986 150 150 if(prev==INVALID) g.first(e,u); 151 151 else ++e; 152 while(e!=INVALID && g. tail(e)!=v) ++e;152 while(e!=INVALID && g.source(e)!=v) ++e; 153 153 return e; 154 154 } … … 193 193 const NodeBijection& _nb, EdgeBijection& _eb) { 194 194 for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) { 195 _eb[it] = _d.addEdge(_nb[_s. tail(it)], _nb[_s.head(it)]);195 _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]); 196 196 } 197 197 } -
src/lemon/graph_wrapper.h
r970 r986 151 151 void nextOut(Edge& i) const { graph->nextOut(i); } 152 152 153 Node tail(const Edge& e) const { return graph->tail(e); }154 Node head(const Edge& e) const { return graph->head(e); }155 // Node tail(const Edge& e) const {156 // return Node(graph-> tail(static_cast<typename Graph::Edge>(e))); }157 // Node head(const Edge& e) const {158 // return Node(graph-> head(static_cast<typename Graph::Edge>(e))); }153 Node source(const Edge& e) const { return graph->source(e); } 154 Node target(const Edge& e) const { return graph->target(e); } 155 // Node source(const Edge& e) const { 156 // return Node(graph->source(static_cast<typename Graph::Edge>(e))); } 157 // Node target(const Edge& e) const { 158 // return Node(graph->target(static_cast<typename Graph::Edge>(e))); } 159 159 160 160 int nodeNum() const { return graph->nodeNum(); } … … 162 162 163 163 Node addNode() const { return Node(graph->addNode()); } 164 Edge addEdge(const Node& tail, const Node& head) const {165 return Edge(graph->addEdge( tail, head)); }164 Edge addEdge(const Node& source, const Node& target) const { 165 return Edge(graph->addEdge(source, target)); } 166 166 167 167 void erase(const Node& i) const { graph->erase(i); } … … 291 291 } 292 292 293 Node tail(const Edge& e) const {294 return GraphWrapper<Graph>:: head(e); }295 Node head(const Edge& e) const {296 return GraphWrapper<Graph>:: tail(e); }293 Node source(const Edge& e) const { 294 return GraphWrapper<Graph>::target(e); } 295 Node target(const Edge& e) const { 296 return GraphWrapper<Graph>::source(e); } 297 297 298 298 // KEEP_MAPS(Parent, RevGraphWrapper); … … 626 626 readDimacs(std::cin, g, length, s, t); 627 627 628 cout << "edges with lengths (of form id, tail--length->head): " << endl;628 cout << "edges with lengths (of form id, source--length->target): " << endl; 629 629 for(EdgeIt e(g); e!=INVALID; ++e) 630 cout << g.id(e) << ", " << g.id(g. tail(e)) << "--"631 << length[e] << "->" << g.id(g. head(e)) << endl;630 cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 631 << length[e] << "->" << g.id(g.target(e)) << endl; 632 632 633 633 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; … … 666 666 for(EdgeIt e(g); e!=INVALID; ++e) 667 667 if (flow[e]) 668 cout << " " << g.id(g. tail(e)) << "--"669 << length[e] << "->" << g.id(g. head(e)) << endl;668 cout << " " << g.id(g.source(e)) << "--" 669 << length[e] << "->" << g.id(g.target(e)) << endl; 670 670 \endcode 671 671 The program has the following (expected :-)) output: 672 672 \code 673 edges with lengths (of form id, tail--length->head):673 edges with lengths (of form id, source--length->target): 674 674 9, 5--4->6 675 675 8, 4--2->6 … … 757 757 OutEdgeIt& next(OutEdgeIt& e) const { 758 758 if (e.out_or_in) { 759 typename Graph::Node n=this->graph-> tail(e.out);759 typename Graph::Node n=this->graph->source(e.out); 760 760 this->graph->next(e.out); 761 761 if (!this->graph->valid(e.out)) { … … 768 768 769 769 Node aNode(const OutEdgeIt& e) const { 770 if (e.out_or_in) return this->graph-> tail(e); else771 return this->graph-> head(e); }770 if (e.out_or_in) return this->graph->source(e); else 771 return this->graph->target(e); } 772 772 Node bNode(const OutEdgeIt& e) const { 773 if (e.out_or_in) return this->graph-> head(e); else774 return this->graph-> tail(e); }773 if (e.out_or_in) return this->graph->target(e); else 774 return this->graph->source(e); } 775 775 776 776 // KEEP_MAPS(Parent, UndirGraphWrapper); … … 938 938 OutEdgeIt& operator++() { 939 939 if (!this->backward) { 940 Node n=gw-> tail(*this);940 Node n=gw->source(*this); 941 941 *(static_cast<GraphEdge*>(this))= 942 942 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); … … 995 995 InEdgeIt& operator++() { 996 996 if (!this->backward) { 997 Node n=gw-> tail(*this);997 Node n=gw->source(*this); 998 998 *(static_cast<GraphEdge*>(this))= 999 999 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); … … 1090 1090 1091 1091 1092 Node tail(Edge e) const {1093 return ((!e.backward) ? this->graph-> tail(e) : this->graph->head(e)); }1094 Node head(Edge e) const {1095 return ((!e.backward) ? this->graph-> head(e) : this->graph->tail(e)); }1092 Node source(Edge e) const { 1093 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } 1094 Node target(Edge e) const { 1095 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } 1096 1096 1097 1097 /// Gives back the opposite edge. … … 1414 1414 // } 1415 1415 void erase(const Edge& e) const { 1416 Node n= tail(e);1416 Node n=source(e); 1417 1417 typename Graph::OutEdgeIt f(*Parent::graph, n); 1418 1418 ++f; -
src/lemon/kruskal.h
r921 r986 83 83 for (typename IN::const_iterator p = in.begin(); 84 84 p!=in.end(); ++p ) { 85 if ( uf.join(G. head((*p).first),86 G. tail((*p).first)) ) {85 if ( uf.join(G.target((*p).first), 86 G.source((*p).first)) ) { 87 87 out.set((*p).first, true); 88 88 tot_cost += (*p).second; -
src/lemon/list_graph.h
r980 r986 44 44 45 45 struct EdgeT { 46 int head, tail;46 int target, source; 47 47 int prev_in, prev_out; 48 48 int next_in, next_out; … … 112 112 int maxId(Edge = INVALID) const { return edges.size()-1; } 113 113 114 Node tail(Edge e) const { return edges[e.id].tail; }115 Node head(Edge e) const { return edges[e.id].head; }114 Node source(Edge e) const { return edges[e.id].source; } 115 Node target(Edge e) const { return edges[e.id].target; } 116 116 117 117 … … 138 138 } else { 139 139 int n; 140 for(n = nodes[edges[edge.id]. head].next;140 for(n = nodes[edges[edge.id].target].next; 141 141 n!=-1 && nodes[n].first_in == -1; 142 142 n = nodes[n].next); … … 199 199 } 200 200 201 edges[n]. tail= u.id;202 edges[n]. head= v.id;201 edges[n].source = u.id; 202 edges[n].target = v.id; 203 203 204 204 edges[n].next_out = nodes[u.id].first_out; … … 247 247 edges[edges[n].prev_in].next_in = edges[n].next_in; 248 248 } else { 249 nodes[edges[n]. head].first_in = edges[n].next_in;249 nodes[edges[n].target].first_in = edges[n].next_in; 250 250 } 251 251 … … 258 258 edges[edges[n].prev_out].next_out = edges[n].next_out; 259 259 } else { 260 nodes[edges[n]. tail].first_out = edges[n].next_out;260 nodes[edges[n].source].first_out = edges[n].next_out; 261 261 } 262 262 … … 273 273 274 274 protected: 275 void _move Head(Edge e, Node n)275 void _moveTarget(Edge e, Node n) 276 276 { 277 277 if(edges[e.id].next_in != -1) … … 279 279 if(edges[e.id].prev_in != -1) 280 280 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; 281 else nodes[edges[e.id]. head].first_in = edges[e.id].next_in;282 edges[e.id]. head= n.id;281 else nodes[edges[e.id].target].first_in = edges[e.id].next_in; 282 edges[e.id].target = n.id; 283 283 edges[e.id].prev_in = -1; 284 284 edges[e.id].next_in = nodes[n.id].first_in; 285 285 nodes[n.id].first_in = e.id; 286 286 } 287 void _move Tail(Edge e, Node n)287 void _moveSource(Edge e, Node n) 288 288 { 289 289 if(edges[e.id].next_out != -1) … … 291 291 if(edges[e.id].prev_out != -1) 292 292 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; 293 else nodes[edges[e.id]. tail].first_out = edges[e.id].next_out;294 edges[e.id]. tail= n.id;293 else nodes[edges[e.id].source].first_out = edges[e.id].next_out; 294 edges[e.id].source = n.id; 295 295 edges[e.id].prev_out = -1; 296 296 edges[e.id].next_out = nodes[n.id].first_out; … … 321 321 { 322 322 public: 323 /// Moves the headof \c e to \c n324 325 /// Moves the headof \c e to \c n323 /// Moves the target of \c e to \c n 324 325 /// Moves the target of \c e to \c n 326 326 /// 327 void move Head(Edge e, Node n) { _moveHead(e,n); }328 /// Moves the tailof \c e to \c n329 330 /// Moves the tailof \c e to \c n327 void moveTarget(Edge e, Node n) { _moveTarget(e,n); } 328 /// Moves the source of \c e to \c n 329 330 /// Moves the source of \c e to \c n 331 331 /// 332 void move Tail(Edge e, Node n) { _moveTail(e,n); }332 void moveSource(Edge e, Node n) { _moveSource(e,n); } 333 333 334 334 ///Using this it possible to avoid the superfluous memory allocation. -
src/lemon/min_cost_flow.h
r941 r986 104 104 ValueType operator[](typename ResGW::Edge e) const { 105 105 if (g.forward(e)) 106 return length[e]-(pot[g. head(e)]-pot[g.tail(e)]);106 return length[e]-(pot[g.target(e)]-pot[g.source(e)]); 107 107 else 108 return -length[e]-(pot[g. head(e)]-pot[g.tail(e)]);108 return -length[e]-(pot[g.target(e)]-pot[g.source(e)]); 109 109 } 110 110 … … 236 236 for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 237 237 //C^{\Pi}_{i,j} 238 mod_pot = length[e]-potential[g. head(e)]+potential[g.tail(e)];238 mod_pot = length[e]-potential[g.target(e)]+potential[g.source(e)]; 239 239 fl_e = flow[e]; 240 240 if (0<fl_e && fl_e<capacity[e]) { -
src/lemon/path.h
r959 r986 112 112 /// Starting point of the path. 113 113 /// Returns INVALID if the path is empty. 114 GraphNode tail() const {115 return empty() ? INVALID : gr-> tail(edges[0]);114 GraphNode source() const { 115 return empty() ? INVALID : gr->source(edges[0]); 116 116 } 117 117 /// \brief End point of the path. … … 119 119 /// End point of the path. 120 120 /// Returns INVALID if the path is empty. 121 GraphNode head() const {122 return empty() ? INVALID : gr-> head(edges[length()-1]);121 GraphNode target() const { 122 return empty() ? INVALID : gr->target(edges[length()-1]); 123 123 } 124 124 … … 140 140 } 141 141 142 /// \brief Returns node iterator pointing to the headnode of the142 /// \brief Returns node iterator pointing to the target node of the 143 143 /// given edge iterator. 144 NodeIt head(const EdgeIt& e) const {144 NodeIt target(const EdgeIt& e) const { 145 145 return NodeIt(*this, e.idx+1); 146 146 } 147 147 148 /// \brief Returns node iterator pointing to the tailnode of the148 /// \brief Returns node iterator pointing to the source node of the 149 149 /// given edge iterator. 150 NodeIt tail(const EdgeIt& e) const {150 NodeIt source(const EdgeIt& e) const { 151 151 return NodeIt(*this, e.idx); 152 152 } … … 231 231 operator const GraphNode& () const { 232 232 if(idx >= p->length()) 233 return p-> head();233 return p->target(); 234 234 else if(idx >= 0) 235 return p->gr-> tail(p->edges[idx]);235 return p->gr->source(p->edges[idx]); 236 236 else 237 237 return INVALID; … … 336 336 } 337 337 338 GraphNode tail() const {338 GraphNode source() const { 339 339 if( ! front.empty() ) 340 return P.gr-> tail(front[front.size()-1]);340 return P.gr->source(front[front.size()-1]); 341 341 else if( ! P.empty() ) 342 return P.gr-> tail(P.edges[0]);342 return P.gr->source(P.edges[0]); 343 343 else if( ! back.empty() ) 344 return P.gr-> tail(back[0]);344 return P.gr->source(back[0]); 345 345 else 346 346 return INVALID; 347 347 } 348 GraphNode head() const {348 GraphNode target() const { 349 349 if( ! back.empty() ) 350 return P.gr-> head(back[back.size()-1]);350 return P.gr->target(back[back.size()-1]); 351 351 else if( ! P.empty() ) 352 return P.gr-> head(P.edges[P.length()-1]);352 return P.gr->target(P.edges[P.length()-1]); 353 353 else if( ! front.empty() ) 354 return P.gr-> head(front[0]);354 return P.gr->target(front[0]); 355 355 else 356 356 return INVALID; … … 438 438 /// Starting point of the path. 439 439 /// Returns INVALID if the path is empty. 440 GraphNode tail() const {441 return empty() ? INVALID : gr-> tail(edges[0]);440 GraphNode source() const { 441 return empty() ? INVALID : gr->source(edges[0]); 442 442 } 443 443 /// \brief End point of the path. … … 445 445 /// End point of the path. 446 446 /// Returns INVALID if the path is empty. 447 GraphNode head() const {448 return empty() ? INVALID : gr-> head(edges[length()-1]);447 GraphNode target() const { 448 return empty() ? INVALID : gr->target(edges[length()-1]); 449 449 } 450 450 … … 478 478 } 479 479 480 /// \brief Returns node iterator pointing to the headnode of the480 /// \brief Returns node iterator pointing to the target node of the 481 481 /// given edge iterator. 482 NodeIt head(const EdgeIt& e) const {482 NodeIt target(const EdgeIt& e) const { 483 483 return NodeIt(*this, e.idx+1); 484 484 } 485 485 486 /// \brief Returns node iterator pointing to the tailnode of the486 /// \brief Returns node iterator pointing to the source node of the 487 487 /// given edge iterator. 488 NodeIt tail(const EdgeIt& e) const {488 NodeIt source(const EdgeIt& e) const { 489 489 return NodeIt(*this, e.idx); 490 490 } … … 571 571 operator const GraphNode& () const { 572 572 if(idx >= p->length()) 573 return p-> head();573 return p->target(); 574 574 else if(idx >= 0) 575 return p->gr-> tail(p->edges[idx]);575 return p->gr->source(p->edges[idx]); 576 576 else 577 577 return INVALID; … … 677 677 } 678 678 679 GraphNode tail() const {679 GraphNode source() const { 680 680 if( ! front.empty() ) 681 return P.gr-> tail(front[front.size()-1]);681 return P.gr->source(front[front.size()-1]); 682 682 else if( ! P.empty() ) 683 return P.gr-> tail(P.edges[0]);683 return P.gr->source(P.edges[0]); 684 684 else if( ! back.empty() ) 685 return P.gr-> tail(back[0]);685 return P.gr->source(back[0]); 686 686 else 687 687 return INVALID; 688 688 } 689 GraphNode head() const {689 GraphNode target() const { 690 690 if( ! back.empty() ) 691 return P.gr-> head(back[back.size()-1]);691 return P.gr->target(back[back.size()-1]); 692 692 else if( ! P.empty() ) 693 return P.gr-> head(P.edges[P.length()-1]);693 return P.gr->target(P.edges[P.length()-1]); 694 694 else if( ! front.empty() ) 695 return P.gr-> head(front[0]);695 return P.gr->target(front[0]); 696 696 else 697 697 return INVALID; -
src/lemon/preflow.h
r977 r986 306 306 for(InEdgeIt e(*g,v); e!=INVALID; ++e) { 307 307 if ( (*capacity)[e] <= (*flow)[e] ) continue; 308 Node u=g-> tail(e);308 Node u=g->source(e); 309 309 if ( level[u] >= n ) { 310 310 bfs_queue.push(u); … … 319 319 for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { 320 320 if ( 0 >= (*flow)[e] ) continue; 321 Node u=g-> head(e);321 Node u=g->target(e); 322 322 if ( level[u] >= n ) { 323 323 bfs_queue.push(u); … … 411 411 412 412 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { 413 Node v=g-> head(e);413 Node v=g->target(e); 414 414 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 415 415 queue.push(v); … … 419 419 420 420 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { 421 Node v=g-> tail(e);421 Node v=g->source(e); 422 422 if (!M[v] && (*flow)[e] > 0 ) { 423 423 queue.push(v); … … 449 449 450 450 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { 451 Node v=g-> tail(e);451 Node v=g->source(e); 452 452 if (M[v] && (*flow)[e] < (*capacity)[e] ) { 453 453 queue.push(v); … … 457 457 458 458 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { 459 Node v=g-> head(e);459 Node v=g->target(e); 460 460 if (M[v] && (*flow)[e] > 0 ) { 461 461 queue.push(v); … … 516 516 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { 517 517 if ( (*flow)[e] >= (*capacity)[e] ) continue; 518 Node v=g-> head(e);518 Node v=g->target(e); 519 519 520 520 if( lev > level[v] ) { //Push is allowed now … … 548 548 549 549 if( (*flow)[e] <= 0 ) continue; 550 Node v=g-> tail(e);550 Node v=g->source(e); 551 551 552 552 if( lev > level[v] ) { //Push is allowed now … … 603 603 for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { 604 604 if ( (*capacity)[e] <= (*flow)[e] ) continue; 605 Node w=g-> tail(e);605 Node w=g->source(e); 606 606 if ( level[w] == n && w != s ) { 607 607 bfs_queue.push(w); … … 616 616 for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { 617 617 if ( 0 >= (*flow)[e] ) continue; 618 Node w=g-> head(e);618 Node w=g->target(e); 619 619 if ( level[w] == n && w != s ) { 620 620 bfs_queue.push(w); … … 647 647 648 648 for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { 649 Node w=g-> tail(e);649 Node w=g->source(e); 650 650 if ( level[w] == n && w != s ) { 651 651 bfs_queue.push(w); … … 663 663 Num c=(*capacity)[e]; 664 664 if ( c <= 0 ) continue; 665 Node w=g-> head(e);665 Node w=g->target(e); 666 666 if ( level[w] < n ) { 667 667 if ( excess[w] <= 0 && w!=t ) { //putting into the stack … … 688 688 Num rem=(*capacity)[e]-(*flow)[e]; 689 689 if ( rem <= 0 ) continue; 690 Node w=g-> head(e);690 Node w=g->target(e); 691 691 if ( level[w] < n ) { 692 692 if ( excess[w] <= 0 && w!=t ) { //putting into the stack … … 701 701 for(InEdgeIt e(*g,s); e!=INVALID; ++e) { 702 702 if ( (*flow)[e] <= 0 ) continue; 703 Node w=g-> tail(e);703 Node w=g->source(e); 704 704 if ( level[w] < n ) { 705 705 if ( excess[w] <= 0 && w!=t ) { … … 718 718 Num rem=(*capacity)[e]-(*flow)[e]; 719 719 if ( rem <= 0 ) continue; 720 Node w=g-> head(e);720 Node w=g->target(e); 721 721 if ( level[w] < n ) flow->set(e, (*capacity)[e]); 722 722 } … … 724 724 for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { 725 725 if ( (*flow)[e] <= 0 ) continue; 726 Node w=g-> tail(e);726 Node w=g->source(e); 727 727 if ( level[w] < n ) flow->set(e, 0); 728 728 } -
src/lemon/smart_graph.h
r980 r986 56 56 struct EdgeT 57 57 { 58 int head, tail, next_in, next_out;58 int target, source, next_in, next_out; 59 59 //FIXME: is this necessary? 60 60 EdgeT() : next_in(-1), next_out(-1) {} … … 98 98 int maxId(Edge = INVALID) const { return edges.size()-1; } 99 99 100 Node tail(Edge e) const { return edges[e.n].tail; }101 Node head(Edge e) const { return edges[e.n].head; }100 Node source(Edge e) const { return edges[e.n].source; } 101 Node target(Edge e) const { return edges[e.n].target; } 102 102 103 103 /// Node ID. … … 128 128 Edge addEdge(Node u, Node v) { 129 129 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... 130 edges[e.n]. tail=u.n; edges[e.n].head=v.n;130 edges[e.n].source=u.n; edges[e.n].target=v.n; 131 131 edges[e.n].next_out=nodes[u.n].first_out; 132 132 edges[e.n].next_in=nodes[v.n].first_in; … … 212 212 { 213 213 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; 214 while(e!=-1 && edges[e]. tail!=v.n) e = edges[e].next_out;214 while(e!=-1 && edges[e].source!=v.n) e = edges[e].next_out; 215 215 prev.n=e; 216 216 return prev; … … 308 308 while(s.edge_num>edges.size()) { 309 309 edge_observers.erase(Edge(edges.size()-1)); 310 nodes[edges.back(). head].first_in=edges.back().next_in;311 nodes[edges.back(). tail].first_out=edges.back().next_out;310 nodes[edges.back().target].first_in=edges.back().next_in; 311 nodes[edges.back().source].first_out=edges.back().next_out; 312 312 edges.pop_back(); 313 313 } -
src/lemon/suurballe.h
r968 r986 134 134 ++e; 135 135 } 136 n = G. head(e);136 n = G.target(e); 137 137 paths[j].push_back(e); 138 138 //total_length += length[e]; -
src/lemon/undir_graph_extender.h
r981 r986 71 71 } 72 72 73 /// Tailof the given Edge.74 Node tail(const Edge &e) const {75 return e.forward ? Parent:: tail(e) : Parent::head(e);73 /// Source of the given Edge. 74 Node source(const Edge &e) const { 75 return e.forward ? Parent::source(e) : Parent::target(e); 76 76 } 77 77 78 /// \todo Shouldn't the " tail" of an undirected edge be called "aNode"78 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" 79 79 /// or something??? 80 using Parent:: tail;80 using Parent::source; 81 81 82 /// Headof the given Edge.83 Node head(const Edge &e) const {84 return e.forward ? Parent:: head(e) : Parent::tail(e);82 /// Target of the given Edge. 83 Node target(const Edge &e) const { 84 return e.forward ? Parent::target(e) : Parent::source(e); 85 85 } 86 86 87 /// \todo Shouldn't the " head" of an undirected edge be called "bNode"87 /// \todo Shouldn't the "target" of an undirected edge be called "bNode" 88 88 /// or something??? 89 using Parent:: head;89 using Parent::target; 90 90 91 91 /// Returns whether the given directed edge is same orientation as the … … 97 97 98 98 Node oppsiteNode(const Node &n, const Edge &e) const { 99 if( n == Parent:: tail(e))100 return Parent:: head(e);101 else if( n == Parent:: head(e))102 return Parent:: tail(e);99 if( n == Parent::source(e)) 100 return Parent::target(e); 101 else if( n == Parent::target(e)) 102 return Parent::source(e); 103 103 else 104 104 return INVALID; … … 148 148 Parent::nextOut(e); 149 149 if( UndirEdge(e) == INVALID ) { 150 Parent::firstIn(e, Parent:: tail(e));150 Parent::firstIn(e, Parent::source(e)); 151 151 e.forward = false; 152 152 } … … 160 160 Parent::nextIn(e); 161 161 if( UndirEdge(e) == INVALID ) { 162 Parent::firstOut(e, Parent:: head(e));162 Parent::firstOut(e, Parent::target(e)); 163 163 e.forward = false; 164 164 } -
src/test/bfs_test.cc
r959 r986 84 84 85 85 for(EdgeIt e(G); e==INVALID; ++e) { 86 Node u=G. tail(e);87 Node v=G. head(e);86 Node u=G.source(e); 87 Node v=G.target(e); 88 88 check( !bfs_test.reached(u) || 89 89 (bfs_test.dist(v) > bfs_test.dist(u)+1), … … 95 95 if ( bfs_test.pred(v)!=INVALID ) { 96 96 Edge e=bfs_test.pred(v); 97 Node u=G. tail(e);97 Node u=G.source(e); 98 98 check(u==bfs_test.predNode(v),"Wrong tree."); 99 99 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, -
src/test/dfs_test.cc
r959 r986 84 84 if ( dfs_test.pred(v)!=INVALID ) { 85 85 Edge e=dfs_test.pred(v); 86 Node u=G. tail(e);86 Node u=G.source(e); 87 87 check(u==dfs_test.predNode(v),"Wrong tree."); 88 88 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, -
src/test/dijkstra_heap_test.cc
r921 r986 74 74 EdgeIt e; 75 75 for(G.first(e); e!=INVALID; ++e) { 76 Node u=G. tail(e);77 Node v=G. head(e);76 Node u=G.source(e); 77 Node v=G.target(e); 78 78 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) 79 79 if ( dijkstra_test.reached(u) ) { 80 std::cout<<"Error! dist( head)-dist(tail)- edge_length= "80 std::cout<<"Error! dist(target)-dist(source)- edge_length= " 81 81 <<dijkstra_test.dist(v) - dijkstra_test.dist(u) 82 82 - cap[e]<<std::endl; … … 89 89 if ( dijkstra_test.reached(v) ) { 90 90 Edge e=dijkstra_test.pred(v); 91 Node u=G. tail(e);91 Node u=G.source(e); 92 92 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) { 93 93 std::cout<<"Error in a shortest path tree edge! Difference: " … … 123 123 124 124 for(G.first(e); e!=INVALID; ++e) { 125 Node u=G. tail(e);126 Node v=G. head(e);125 Node u=G.source(e); 126 Node v=G.target(e); 127 127 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) 128 128 if ( dijkstra_test2.reached(u) ) { 129 std::cout<<"Error! dist( head)-dist(tail)- edge_length= "129 std::cout<<"Error! dist(target)-dist(source)- edge_length= " 130 130 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u) 131 131 - cap[e]<<std::endl; … … 137 137 if ( dijkstra_test2.reached(v) ) { 138 138 Edge e=dijkstra_test2.pred(v); 139 Node u=G. tail(e);139 Node u=G.source(e); 140 140 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) { 141 141 std::cout<<"Error in a shortest path tree edge! Difference: " -
src/test/dijkstra_test.cc
r959 r986 94 94 95 95 for(EdgeIt e(G); e!=INVALID; ++e) { 96 Node u=G. tail(e);97 Node v=G. head(e);96 Node u=G.source(e); 97 Node v=G.target(e); 98 98 check( !dijkstra_test.reached(u) || 99 99 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]), 100 "dist( head)-dist(tail)- edge_length= "100 "dist(target)-dist(source)- edge_length= " 101 101 << dijkstra_test.dist(v) - dijkstra_test.dist(u) 102 102 - cap[e]); … … 108 108 if ( dijkstra_test.pred(v)!=INVALID ) { 109 109 Edge e=dijkstra_test.pred(v); 110 Node u=G. tail(e);110 Node u=G.source(e); 111 111 check(u==dijkstra_test.predNode(v),"Wrong tree."); 112 112 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e], -
src/test/graph_factory_test.cc
r959 r986 29 29 This test makes consistency checks of list graph structures. 30 30 31 G.addNode(), G.addEdge(), G. tail(), G.head()31 G.addNode(), G.addEdge(), G.source(), G.target() 32 32 33 33 \todo Checks for empty graphs and isolated points. … … 49 49 50 50 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++) 51 G.addEdge(G. head(*p),G.tail(*p));51 G.addEdge(G.target(*p),G.source(*p)); 52 52 } 53 53 -
src/test/graph_test.h
r946 r986 54 54 for(int i=0;i<nn;i++) { 55 55 check(e!=INVALID,"Wrong OutEdge list linking."); 56 check(n==G. tail(e), "Wrong OutEdge list linking.");56 check(n==G.source(e), "Wrong OutEdge list linking."); 57 57 ++e; 58 58 } … … 66 66 for(int i=0;i<nn;i++) { 67 67 check(e!=INVALID,"Wrong InEdge list linking."); 68 check(n==G. head(e), "Wrong InEdge list linking.");68 check(n==G.target(e), "Wrong InEdge list linking."); 69 69 ++e; 70 70 } … … 82 82 83 83 ///\file 84 ///\todo Check head(), tail() as well;84 ///\todo Check target(), source() as well; 85 85 86 86 -
src/test/path_test.cc
r959 r986 48 48 P.clear(); //void clear() {} 49 49 50 gn=P. head(); //GraphNode/*It*/ head() const {return INVALID;}51 gn=P. tail(); //GraphNode/*It*/ tail() const {return INVALID;}50 gn=P.target(); //GraphNode/*It*/ target() const {return INVALID;} 51 gn=P.source(); //GraphNode/*It*/ source() const {return INVALID;} 52 52 53 53 ei=P.first(ei); //It& first(It &i) const { return i=It(*this); } 54 54 55 ni=P. head(ei); //NodeIt head(const EdgeIt& e) const {}56 ni=P. tail(ei); //NodeIt tail(const EdgeIt& e) const {}55 ni=P.target(ei); //NodeIt target(const EdgeIt& e) const {} 56 ni=P.source(ei); //NodeIt source(const EdgeIt& e) const {} 57 57 58 58 -
src/test/preflow_test.cc
r959 r986 68 68 int c=0; 69 69 for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) { 70 if (cut[g. tail(e)] && !cut[g.head(e)]) c+=cap[e];70 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; 71 71 } 72 72 return c; -
src/test/sym_graph_test.cc
r959 r986 31 31 This test makes consistency checks of list graph structures. 32 32 33 G.addNode(), G.addEdge(), G. tail(), G.head()33 G.addNode(), G.addEdge(), G.source(), G.target() 34 34 35 35 \todo Checks for empty graphs and isolated points. -
src/test/sym_graph_test.h
r959 r986 74 74 SymEdge se; 75 75 se=INVALID; 76 n=G. tail(se);77 n=G. head(se);76 n=G.source(se); 77 n=G.target(se); 78 78 } 79 79 // id tests … … 175 175 176 176 ///\file 177 ///\todo Check head(), tail() as well;177 ///\todo Check target(), source() as well; 178 178 179 179 -
src/test/test_tools.h
r978 r986 106 106 107 107 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++) 108 G.addEdge(G. head(*p),G.tail(*p));108 G.addEdge(G.target(*p),G.source(*p)); 109 109 } 110 110 -
src/work/alpar/bfs-named-param.cc
r945 r986 11 11 struct _BFS_CUSTOM_VIS {}; 12 12 13 template<class GT,class VT,class DVT,class PNT,class PET,class PT > 14 class _BFS 13 14 class _Bfs_Traits 15 { 16 typedef ListGraph Graph; 17 } 18 19 template<class T> 20 class _Bfs 15 21 { 16 22 public: 17 typedef GT Graph; 18 typedef VT Visited; 19 typedef PNT PredNode; 20 typedef PET PredEdge; 21 typedef PT Priority; 22 // typedef QDT QueueData; 23 typedef typename T::Graph Graph; 24 typedef typename T::Reached Reached; 25 typedef typename T::PredNode PredNode; 26 typedef typename T::PredEdge PredEdge; 27 typedef typename T::Priority Priority; 28 29 typedef typename T::DefaultReachedTag DefaultReachedTag; 23 30 24 31 typedef typename Graph::Node Node; 25 32 typedef typename Graph::OutEdgeIt OutEdgeIt; 26 33 27 typedef DVT DefaultVisitedTag;28 29 34 const Graph &_graph; 30 35 31 36 Node _source; 32 37 33 Visited *_visited;38 Reached *_visited; 34 39 PredNode _predNode; 35 40 PredEdge _predEdge; 36 41 Priority _priority; 37 42 38 _B FS(const Graph &g,43 _Bfs(const Graph &g, 39 44 Node s, 40 Visited *v,45 Reached *v, 41 46 PredNode &pn, 42 47 PredEdge &pe, … … 46 51 47 52 48 int run(const _B FS_CUSTOM_VIS &)53 int run(const _Bfs_CUSTOM_VIS &) 49 54 { 50 55 using namespace std; … … 64 69 Node n=Q[Qt++]; 65 70 for(OutEdgeIt e(_graph,n);e!=INVALID;++e) 66 if(!(*_visited)[m=_graph. head(e)]) {71 if(!(*_visited)[m=_graph.target(e)]) { 67 72 Q[Qh++]=m; 68 73 _visited->set(m,true); … … 76 81 int run(const _BFS_DEFAULT_VIS &) 77 82 { 78 _visited= new Visited(_graph);83 _visited= new Reached(_graph); 79 84 int r = run(_BFS_CUSTOM_VIS()); 80 85 delete _visited; 81 86 return r; 82 87 } 83 int run() { return run(Default VisitedTag());}84 85 template<class T> _B FS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>88 int run() { return run(DefaultReachedTag());} 89 90 template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> 86 91 setVisitMap(T &t) 87 92 { 88 return _B FS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>93 return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> 89 94 (_graph,_source,&t,_predNode,_predEdge,_priority); 90 95 } 91 96 92 97 template<class T> 93 _B FS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>98 _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> 94 99 setPredNodeMap(T &t) 95 100 { 96 return _BFS<Graph, Visited,DefaultVisitedTag,T,PredEdge,Priority>101 return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> 97 102 (_graph,_source, 98 103 _visited, … … 101 106 102 107 template<class T> 103 _BFS<Graph, Visited,DefaultVisitedTag,PredNode,T,Priority>108 _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> 104 109 setPredEdgeMap(T &t) 105 110 { 106 return _BFS<Graph, Visited,DefaultVisitedTag,PredNode,T,Priority>111 return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> 107 112 (_graph,_source, 108 113 _visited, … … 110 115 } 111 116 112 _B FS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>117 _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> 113 118 setNothing() 114 119 { 115 return _B FS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>120 return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> 116 121 (_graph,_source, 117 122 _visited, … … 122 127 123 128 template<class G> 124 _B FS<G,129 _Bfs<G, 125 130 typename G::template NodeMap<bool>, 126 131 _BFS_DEFAULT_VIS, … … 132 137 // typename G::template NodeMap<bool> v(g); 133 138 134 return _B FS< G,139 return _Bfs < G, 135 140 typename G::template NodeMap<bool>, 136 141 _BFS_DEFAULT_VIS, … … 147 152 148 153 149 class My VisitedMap : public SmartGraph::NodeMap<bool>154 class MyReachedMap : public SmartGraph::NodeMap<bool> 150 155 { 151 156 const SmartGraph &_G; 152 157 public: 153 My VisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}158 MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {} 154 159 void set(SmartGraph::Node n,bool b) 155 160 { … … 181 186 SmartGraph::NodeMap<SmartGraph::Edge> em(G); 182 187 183 My VisitedMap vm(G);188 MyReachedMap vm(G); 184 189 185 190 -
src/work/alpar/boolmap_iter.cc
r921 r986 120 120 121 121 for(EdgeIt e(G);G.valid(e);G.next(e)) 122 std::cout << G.id(G. tail(e)) << "->" << G.id(G.head(e))122 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) 123 123 << ": " << map[e] << '\n'; 124 124 std::cout << "True Edges:\n"; 125 125 for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i) 126 std::cout << G.id(G. tail(i)) << "->" << G.id(G.head(i)) << '\n';126 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; 127 127 std::cout << "False Edges:\n"; 128 128 for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i) 129 std::cout << G.id(G. tail(i)) << "->" << G.id(G.head(i)) << '\n';129 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; 130 130 } 131 131 -
src/work/alpar/dijkstra.h
r967 r986 394 394 395 395 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { 396 Node w=G-> head(e);396 Node w=G->target(e); 397 397 switch(heap.state(w)) { 398 398 case Heap::PRE_HEAP: -
src/work/alpar/f_ed_ka.h
r921 r986 85 85 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); 86 86 //FIXME: I would need 'G.opposite(e,n)' 87 gn = visited.get(t)==1 ? G. tail(tree.get(t)) : G.head(tree.get(t));87 gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(tree.get(t)); 88 88 while(gn!=s) if(visited.get(gn)==1) 89 89 { 90 90 //FIXME: nonstandard gcc extension! 91 91 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); 92 gn=G. tail(tree.get(gn));92 gn=G.source(tree.get(gn)); 93 93 } 94 94 else { 95 95 //FIXME: nonstandard gcc extension! 96 96 aug_val <?= f.get(tree.get(gn)); 97 gn=G. head(tree.get(gn));97 gn=G.target(tree.get(gn)); 98 98 } 99 99 … … 103 103 { 104 104 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); 105 gn=G. tail(tree.get(gn));105 gn=G.source(tree.get(gn)); 106 106 } 107 107 else { 108 108 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); 109 gn=G. head(tree.get(gn));109 gn=G.target(tree.get(gn)); 110 110 } 111 111 -
src/work/alpar/f_ed_ka_demo.cc
r921 r986 42 42 //std::cout << "maximum flow: "<< std::endl; 43 43 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 44 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";44 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 45 45 //} 46 46 //std::cout<<std::endl; -
src/work/alpar/graph.h
r253 r986 107 107 // Lehet, hogy ez a ketto nem kell!!! 108 108 109 NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}110 NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}109 NodeIterator source() const {NodeIterator i;i.G=G;i.n=e->From();return i;} 110 NodeIterator target() const {NodeIterator i;i.G=G;i.n=e->To();return i;} 111 111 NodeIterator opposite(const NodeIterator &n) const 112 {return n== tail()?head():tail();}112 {return n==source()?target():source();} 113 113 114 114 bool valid() {return e;} … … 191 191 {OutEdgeIterator tmp(*this); goNext(); return tmp;} 192 192 193 NodeIterator aNode() const {return tail();}194 NodeIterator bNode() const {return head();}193 NodeIterator aNode() const {return source();} 194 NodeIterator bNode() const {return target();} 195 195 196 196 operator const InEdgeIterator () … … 219 219 220 220 NodeIterator aNode() const {return n;} 221 NodeIterator bNode() const {return n.n== tail().n?head():tail();}221 NodeIterator bNode() const {return n.n==source().n?target():source();} 222 222 223 223 operator const InEdgeIterator () … … 255 255 256 256 NodeIterator aNode() const {return n;} 257 NodeIterator bNode() const {return n.n== tail().n?head():tail();}257 NodeIterator bNode() const {return n.n==source().n?target():source();} 258 258 259 259 operator const EdgeIterator () … … 464 464 { 465 465 return n? 466 reversed[n-1]?path[n-1]. tail():path[n-1].head():467 reversed[0]?path[0]. head():path[0].tail();466 reversed[n-1]?path[n-1].source():path[n-1].target(): 467 reversed[0]?path[0].target():path[0].source(); 468 468 } 469 469 void setRevert(int n,bool r=true) {reversed[n]=r;} … … 471 471 { 472 472 path[n]=i; 473 reversed[n] = i. head()==i.aNode();473 reversed[n] = i.target()==i.aNode(); 474 474 } 475 475 void setEdge(int n,EdgeIterator i,bool r) … … 479 479 } 480 480 481 NodeIterator tail() { return getNode(0); }482 NodeIterator head() { return getNode(getLength()); }481 NodeIterator source() { return getNode(0); } 482 NodeIterator target() { return getNode(getLength()); } 483 483 }; 484 484 -
src/work/alpar/gwrapper.h
r921 r986 28 28 template<typename I> I &goNext(I &i); { return graph->goNext(i); } 29 29 30 NodeIt head(const EdgeIt &e);31 { return graph-> head(e); }32 NodeIt tail(const EdgeIt &e);33 { return graph-> tail(e); }30 NodeIt target(const EdgeIt &e); 31 { return graph->target(e); } 32 NodeIt source(const EdgeIt &e); 33 { return graph->source(e); } 34 34 35 35 template<typename I> NodeIt aNode(const I e); … … 84 84 template<typename I> I &goNext(I &i); { return graph->goNext(i); } 85 85 86 NodeIt head(const EdgeIt &e);87 { return graph-> tail(e); }88 NodeIt tail(const EdgeIt &e);89 { return graph-> head(e); }86 NodeIt target(const EdgeIt &e); 87 { return graph->source(e); } 88 NodeIt source(const EdgeIt &e); 89 { return graph->target(e); } 90 90 91 91 template<typename I> NodeIt aNode(const I e); … … 138 138 // template<typename I> I &goNext(I &i); { return graph->goNext(i); } 139 139 140 NodeIt head(const EdgeIt &e);141 { return G:: tail(e); }142 NodeIt tail(const EdgeIt &e);143 { return G:: head(e); }140 NodeIt target(const EdgeIt &e); 141 { return G::source(e); } 142 NodeIt source(const EdgeIt &e); 143 { return G::target(e); } 144 144 145 145 // template<typename I> NodeIt aNode(const I e); … … 195 195 template<typename I> I &goNext(I &i); { return graph->goNext(i); } 196 196 197 NodeIt head(const EdgeIt &e);198 { return graph-> head(e); }199 NodeIt tail(const EdgeIt &e);200 { return graph-> tail(e); }197 NodeIt target(const EdgeIt &e); 198 { return graph->target(e); } 199 NodeIt source(const EdgeIt &e); 200 { return graph->source(e); } 201 201 202 202 template<typename I> NodeIt aNode(const I e); … … 344 344 template<typename I> I next(const I i); { return graph->goNext(i); } 345 345 346 NodeIt head(const EdgeIt &e);347 { return graph-> head(e); }348 NodeIt tail(const EdgeIt &e);349 { return graph-> tail(e); }346 NodeIt target(const EdgeIt &e); 347 { return graph->target(e); } 348 NodeIt source(const EdgeIt &e); 349 { return graph->source(e); } 350 350 351 351 template<typename I> NodeIt aNode(const I e); -
src/work/alpar/list_graph_demo.cc
r959 r986 112 112 for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); 113 113 for(EdgeIt e(G);G.valid(e);G.next(e)) 114 if(G. tail(e)<G.head(e)) sm[e]=G.id(e);114 if(G.source(e)<G.target(e)) sm[e]=G.id(e); 115 115 116 116 for(EdgeIt e(G);G.valid(e);G.next(e)) 117 std::cout << G.id(G. tail(e)) << "->" << G.id(G.head(e))117 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) 118 118 << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) 119 119 << " em=" << em[e] -
src/work/alpar/rw_nonref_map.cc
r921 r986 24 24 { 25 25 ValueType tmp; 26 std::cout << G.id(G. tail(e)) << "->"27 << G.id(G. head(e)) << ": ";26 std::cout << G.id(G.source(e)) << "->" 27 << G.id(G.target(e)) << ": "; 28 28 std::cin >> tmp; 29 29 return tmp; … … 31 31 ValueType operator = (ValueType v) const 32 32 { 33 std::cout << G.id(G. tail(e)) << "->"34 << G.id(G. head(e)) << ": " << v << '\n';33 std::cout << G.id(G.source(e)) << "->" 34 << G.id(G.target(e)) << ": " << v << '\n'; 35 35 return v; 36 36 } -
src/work/alpar/smart_graph_demo.cc
r921 r986 112 112 for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); 113 113 for(EdgeIt e(G);G.valid(e);G.next(e)) 114 if(G. tail(e)<G.head(e)) sm[e]=G.id(e);114 if(G.source(e)<G.target(e)) sm[e]=G.id(e); 115 115 116 116 for(EdgeIt e(G);G.valid(e);G.next(e)) 117 std::cout << G.id(G. tail(e)) << "->" << G.id(G.head(e))117 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) 118 118 << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) 119 119 << " em=" << em[e] -
src/work/athos/bfs_test.cc
r921 r986 42 42 OutEdgeIt e; 43 43 for(g.first(e,v); g.valid(e); g.next(e)) { 44 Node w=g. head(e);44 Node w=g.target(e); 45 45 if (!reached[w]) { 46 46 bfs_queue.push(w); -
src/work/athos/dijkstra_demo.cc
r921 r986 130 130 std::cout << "out edges: "; 131 131 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) 132 std::cout << node_name.get(flow_test. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";132 std::cout << node_name.get(flow_test.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.target(j)) << " "; 133 133 std::cout << "in edges: "; 134 134 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) 135 std::cout << node_name.get(flow_test. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";135 std::cout << node_name.get(flow_test.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.target(j)) << " "; 136 136 std::cout << std::endl; 137 137 } -
src/work/athos/mincostflow.h
r921 r986 74 74 ValueType operator[](typename ResGraph::Edge e) const { 75 75 if (res_graph.forward(e)) 76 return ol[e]-(pot[res_graph. head(e)]-pot[res_graph.tail(e)]);76 return ol[e]-(pot[res_graph.target(e)]-pot[res_graph.source(e)]); 77 77 else 78 return -ol[e]-(pot[res_graph. head(e)]-pot[res_graph.tail(e)]);78 return -ol[e]-(pot[res_graph.target(e)]-pot[res_graph.source(e)]); 79 79 } 80 80 … … 259 259 while ( i != nonabundant_arcs.end() ){ 260 260 if (flow[*i]>=buf){ 261 Node a = abundant_components.find(res_graph. head(*i));262 Node b = abundant_components.find(res_graph. tail(*i));261 Node a = abundant_components.find(res_graph.target(*i)); 262 Node b = abundant_components.find(res_graph.source(*i)); 263 263 //Merge 264 264 if (a != b){ … … 285 285 while (n!=non_root){ 286 286 e = bfs_pred[n]; 287 n = res_graph. tail(e);287 n = res_graph.source(e); 288 288 res_graph.augment(e,qty_to_augment); 289 289 } … … 455 455 FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){ 456 456 //C^{\Pi}_{i,j} 457 mod_pot = cost[e]-potential[graph. head(e)]+potential[graph.tail(e)];457 mod_pot = cost[e]-potential[graph.target(e)]+potential[graph.source(e)]; 458 458 fl_e = flow[e]; 459 459 // std::cout << fl_e << std::endl; … … 484 484 return false; 485 485 } 486 supdem[graph. tail(e)] += flow[e];487 supdem[graph. head(e)] -= flow[e];486 supdem[graph.source(e)] += flow[e]; 487 supdem[graph.target(e)] -= flow[e]; 488 488 } 489 489 //write_property_vector(supdem, "supdem"); -
src/work/athos/old/minlengthpaths.h
r921 r986 54 54 55 55 ValueType operator[](typename ResGraphType::Edge e) const { 56 //if ( (1-2*rev[e])*ol[e]-(pot[G. head(e)]-pot[G.tail(e)] ) <0 ){56 //if ( (1-2*rev[e])*ol[e]-(pot[G.target(e)]-pot[G.source(e)] ) <0 ){ 57 57 // std::cout<<"Negative length!!"<<std::endl; 58 58 //} 59 return (1-2*rev[e])*ol[e]-(pot[G. head(e)]-pot[G.tail(e)]);59 return (1-2*rev[e])*ol[e]-(pot[G.target(e)]-pot[G.source(e)]); 60 60 } 61 61 … … 162 162 G.next(e); 163 163 } 164 n = G. head(e);164 n = G.target(e); 165 165 paths[j].push_back(e); 166 166 total_length += length[e]; -
src/work/athos/preflow_push_wogw.h
r921 r986 140 140 //This private procedure is supposed to modify the preflow on edge j 141 141 //by value v (which can be positive or negative as well) 142 //and maintain the excess on the head and tail142 //and maintain the excess on the target and source 143 143 //Here we do not check whether this is possible or not 144 144 void modify_preflow(Edge j, const T& v){ … … 148 148 149 149 150 //Modifiyng the head151 modify_excess(G. head(j),v);152 153 //Modifiyng the tail154 modify_excess(G. tail(j),-v);150 //Modifiyng the target 151 modify_excess(G.target(j),v); 152 153 //Modifiyng the source 154 modify_excess(G.source(j),-v); 155 155 156 156 } … … 273 273 InEdgeIt e; 274 274 for(G.first(e,v); G.valid(e); G.next(e)) { 275 Node w=G. tail(e);275 Node w=G.source(e); 276 276 if ( level[w] == number_of_nodes && w != s ) { 277 277 bfs_queue.push(w); … … 311 311 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ 312 312 modify_preflow(j,capacity[j] ); 313 make_active(G. head(j));314 int lev=level[G. head(j)];313 make_active(G.target(j)); 314 int lev=level[G.target(j)]; 315 315 if(highest_active<lev){ 316 316 highest_active=lev; … … 326 326 327 327 if (capacity[j]>preflow[j]){ 328 if(level[G. tail(j)]==level[G.head(j)]+1){328 if(level[G.source(j)]==level[G.target(j)]+1){ 329 329 return true; 330 330 } 331 331 else{ 332 if (level[G. head(j)] < new_level)333 new_level=level[G. head(j)];332 if (level[G.target(j)] < new_level) 333 new_level=level[G.target(j)]; 334 334 } 335 335 } … … 342 342 343 343 if (0<preflow[j]){ 344 if(level[G. tail(j)]==level[G.head(j)]-1){344 if(level[G.source(j)]==level[G.target(j)]-1){ 345 345 346 346 return true; 347 347 } 348 348 else{ 349 if (level[G. tail(j)] < new_level)350 new_level=level[G. tail(j)];349 if (level[G.source(j)] < new_level) 350 new_level=level[G.source(j)]; 351 351 } 352 352 … … 389 389 e -= v; 390 390 //New node might become active 391 if (excess[G. head(j)]==0){392 make_active(G. head(j));391 if (excess[G.target(j)]==0){ 392 make_active(G.target(j)); 393 393 } 394 394 modify_preflow(j,v); … … 405 405 e -= v; 406 406 //New node might become active 407 if (excess[G. tail(j)]==0){408 make_active(G. tail(j));407 if (excess[G.source(j)]==0){ 408 make_active(G.source(j)); 409 409 } 410 410 modify_preflow(j,-v); -
src/work/deba/list_graph.h
r921 r986 44 44 struct EdgeT 45 45 { 46 int head, tail;46 int target, source; 47 47 int prev_in, prev_out; 48 48 int next_in, next_out; … … 105 105 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? 106 106 107 Node tail(Edge e) const { return edges[e.n].tail; }108 Node head(Edge e) const { return edges[e.n].head; }109 110 Node aNode(OutEdgeIt e) const { return edges[e.n]. tail; }111 Node aNode(InEdgeIt e) const { return edges[e.n]. head; }112 113 Node bNode(OutEdgeIt e) const { return edges[e.n]. head; }114 Node bNode(InEdgeIt e) const { return edges[e.n]. tail; }107 Node source(Edge e) const { return edges[e.n].source; } 108 Node target(Edge e) const { return edges[e.n].target; } 109 110 Node aNode(OutEdgeIt e) const { return edges[e.n].source; } 111 Node aNode(InEdgeIt e) const { return edges[e.n].target; } 112 113 Node bNode(OutEdgeIt e) const { return edges[e.n].target; } 114 Node bNode(InEdgeIt e) const { return edges[e.n].source; } 115 115 116 116 NodeIt& first(NodeIt& v) const { … … 152 152 else { 153 153 int n; 154 for(n=nodes[edges[it.n]. head].next;154 for(n=nodes[edges[it.n].target].next; 155 155 n!=-1 && nodes[n].first_in == -1; 156 156 n = nodes[n].next) ; … … 208 208 } 209 209 210 edges[n]. tail = u.n; edges[n].head= v.n;210 edges[n].source = u.n; edges[n].target = v.n; 211 211 212 212 edges[n].next_out = nodes[u.n].first_out; … … 233 233 if(edges[n].prev_in!=-1) 234 234 edges[edges[n].prev_in].next_in = edges[n].next_in; 235 else nodes[edges[n]. head].first_in = edges[n].next_in;235 else nodes[edges[n].target].first_in = edges[n].next_in; 236 236 237 237 if(edges[n].next_out!=-1) … … 239 239 if(edges[n].prev_out!=-1) 240 240 edges[edges[n].prev_out].next_out = edges[n].next_out; 241 else nodes[edges[n]. tail].first_out = edges[n].next_out;241 else nodes[edges[n].source].first_out = edges[n].next_out; 242 242 243 243 edges[n].next_in = first_free_edge; -
src/work/jacint/max_flow.h
r921 r986 327 327 OutEdgeIt e; 328 328 for(g->first(e,w) ; g->valid(e); g->next(e)) { 329 Node v=g-> head(e);329 Node v=g->target(e); 330 330 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 331 331 queue.push(v); … … 336 336 InEdgeIt f; 337 337 for(g->first(f,w) ; g->valid(f); g->next(f)) { 338 Node v=g-> tail(f);338 Node v=g->source(f); 339 339 if (!M[v] && (*flow)[f] > 0 ) { 340 340 queue.push(v); … … 371 371 InEdgeIt e; 372 372 for(g->first(e,w) ; g->valid(e); g->next(e)) { 373 Node v=g-> tail(e);373 Node v=g->source(e); 374 374 if (M[v] && (*flow)[e] < (*capacity)[e] ) { 375 375 queue.push(v); … … 380 380 OutEdgeIt f; 381 381 for(g->first(f,w) ; g->valid(f); g->next(f)) { 382 Node v=g-> head(f);382 Node v=g->target(f); 383 383 if (M[v] && (*flow)[f] > 0 ) { 384 384 queue.push(v); … … 434 434 435 435 if ( (*flow)[e] >= (*capacity)[e] ) continue; 436 Node v=g-> head(e);436 Node v=g->target(e); 437 437 438 438 if( lev > level[v] ) { //Push is allowed now … … 467 467 468 468 if( (*flow)[e] <= 0 ) continue; 469 Node v=g-> tail(e);469 Node v=g->source(e); 470 470 471 471 if( lev > level[v] ) { //Push is allowed now … … 522 522 InEdgeIt e; 523 523 for(g->first(e,v); g->valid(e); g->next(e)) { 524 Node w=g-> tail(e);524 Node w=g->source(e); 525 525 if ( level[w] == n && w != s ) { 526 526 bfs_queue.push(w); … … 540 540 Num c=(*capacity)[e]; 541 541 if ( c <= 0 ) continue; 542 Node w=g-> head(e);542 Node w=g->target(e); 543 543 if ( level[w] < n ) { 544 544 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 567 567 for(g->first(e,v); g->valid(e); g->next(e)) { 568 568 if ( (*capacity)[e] <= (*flow)[e] ) continue; 569 Node w=g-> tail(e);569 Node w=g->source(e); 570 570 if ( level[w] == n && w != s ) { 571 571 bfs_queue.push(w); … … 581 581 for(g->first(f,v); g->valid(f); g->next(f)) { 582 582 if ( 0 >= (*flow)[f] ) continue; 583 Node w=g-> head(f);583 Node w=g->target(f); 584 584 if ( level[w] == n && w != s ) { 585 585 bfs_queue.push(w); … … 600 600 Num rem=(*capacity)[e]-(*flow)[e]; 601 601 if ( rem <= 0 ) continue; 602 Node w=g-> head(e);602 Node w=g->target(e); 603 603 if ( level[w] < n ) { 604 604 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 612 612 { 613 613 if ( (*flow)[f] <= 0 ) continue; 614 Node w=g-> tail(f);614 Node w=g->source(f); 615 615 if ( level[w] < n ) { 616 616 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 711 711 // return dist[n]; } 712 712 // bool get(const typename MapGraphWrapper::Edge& e) const { 713 // return (dist.get(g-> tail(e))<dist.get(g->head(e))); }713 // return (dist.get(g->source(e))<dist.get(g->target(e))); } 714 714 bool operator[](const typename MapGraphWrapper::Edge& e) const { 715 return (dist[g-> tail(e)]<dist[g->head(e)]);715 return (dist[g->source(e)]<dist[g->target(e)]); 716 716 } 717 717 }; … … 861 861 for(g->first(e,v); g->valid(e); g->next(e)) { 862 862 if ( (*capacity)[e] <= (*flow)[e] ) continue; 863 Node u=g-> tail(e);863 Node u=g->source(e); 864 864 if ( level[u] >= n ) { 865 865 bfs_queue.push(u); … … 872 872 for(g->first(f,v); g->valid(f); g->next(f)) { 873 873 if ( 0 >= (*flow)[f] ) continue; 874 Node u=g-> head(f);874 Node u=g->target(f); 875 875 if ( level[u] >= n ) { 876 876 bfs_queue.push(u); … … 926 926 ResGWOutEdgeIt e=bfs; 927 927 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 928 Node v=res_graph. tail(e);929 Node w=res_graph. head(e);928 Node v=res_graph.source(e); 929 Node w=res_graph.target(e); 930 930 pred.set(w, e); 931 931 if (res_graph.valid(pred[v])) { … … 934 934 free.set(w, res_graph.resCap(e)); 935 935 } 936 if (res_graph. head(e)==t) { _augment=true; break; }936 if (res_graph.target(e)==t) { _augment=true; break; } 937 937 } 938 938 … … 946 946 ResGWEdge e=pred[n]; 947 947 res_graph.augment(e, augment_value); 948 n=res_graph. tail(e);948 n=res_graph.source(e); 949 949 } 950 950 } … … 984 984 ResGWOutEdgeIt e=bfs; 985 985 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 986 Node v=res_graph. tail(e);987 Node w=res_graph. head(e);986 Node v=res_graph.source(e); 987 Node w=res_graph.target(e); 988 988 pred.set(w, e); 989 989 if (res_graph.valid(pred[v])) { … … 992 992 free.set(w, res_graph.resCap(e)); 993 993 } 994 if (res_graph. head(e)==t) { _augment=true; break; }994 if (res_graph.target(e)==t) { _augment=true; break; } 995 995 } 996 996 … … 1004 1004 ResGWEdge e=pred[n]; 1005 1005 res_graph.augment(e, augment_value); 1006 n=res_graph. tail(e);1006 n=res_graph.source(e); 1007 1007 } 1008 1008 } … … 1051 1051 if (res_graph.valid(e)) { 1052 1052 if (bfs.isBNodeNewlyReached()) { 1053 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);1054 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)],1055 res_graph_to_F[res_graph. head(e)]);1053 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 1054 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], 1055 res_graph_to_F[res_graph.target(e)]); 1056 1056 original_edge.update(); 1057 1057 original_edge.set(f, e); … … 1059 1059 residual_capacity.set(f, res_graph.resCap(e)); 1060 1060 } else { 1061 if (dist[res_graph. head(e)]==(dist[res_graph.tail(e)]+1)) {1062 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)],1063 res_graph_to_F[res_graph. head(e)]);1061 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { 1062 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], 1063 res_graph_to_F[res_graph.target(e)]); 1064 1064 original_edge.update(); 1065 1065 original_edge.set(f, e); … … 1115 1115 typename MG::Edge e=pred[n]; 1116 1116 res_graph.augment(original_edge[e], augment_value); 1117 n=F. tail(e);1117 n=F.source(e); 1118 1118 if (residual_capacity[e]==augment_value) 1119 1119 F.erase(e); … … 1148 1148 ResGWOutEdgeIt e=bfs; 1149 1149 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 1150 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);1150 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 1151 1151 } 1152 1152 ++bfs; … … 1248 1248 typename ErasingResGW::OutEdgeIt e=pred[n]; 1249 1249 res_graph.augment(e, augment_value); 1250 n=erasing_res_graph. tail(e);1250 n=erasing_res_graph.source(e); 1251 1251 if (res_graph.resCap(e)==0) 1252 1252 erasing_res_graph.erase(e); -
src/work/jacint/max_flow_bug.cc
r921 r986 43 43 EdgeIt e; 44 44 for(G.first(e); G.valid(e); G.next(e)) { 45 if (mincut[G. tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];45 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; 46 46 } 47 47 … … 50 50 int min_cut_value=0; 51 51 for(G.first(e); G.valid(e); G.next(e)) { 52 if (cut[G. tail(e)] && !cut[G.head(e)])52 if (cut[G.source(e)] && !cut[G.target(e)]) 53 53 min_cut_value+=cap[e]; 54 54 } … … 58 58 int max_min_cut_value=0; 59 59 for(G.first(e); G.valid(e); G.next(e)) { 60 if (maxcut[G. tail(e)] && !maxcut[G.head(e)])60 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) 61 61 max_min_cut_value+=cap[e]; 62 62 } … … 89 89 int min_min_cut_value2=0; 90 90 for(G.first(e); G.valid(e); G.next(e)) { 91 if (mincut2[G. tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];91 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; 92 92 } 93 93 … … 96 96 int min_cut_value2=0; 97 97 for(G.first(e); G.valid(e); G.next(e)) { 98 if (cut2[G. tail(e)] && !cut2[G.head(e)])98 if (cut2[G.source(e)] && !cut2[G.target(e)]) 99 99 min_cut_value2+=cap[e]; 100 100 } … … 104 104 int max_min_cut_value2=0; 105 105 for(G.first(e); G.valid(e); G.next(e)) { 106 if (maxcut2[G. tail(e)] && !maxcut2[G.head(e)])106 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) 107 107 max_min_cut_value2+=cap[e]; 108 108 } … … 128 128 int min_min_cut_value3=0; 129 129 for(G.first(e); G.valid(e); G.next(e)) { 130 if (mincut3[G. tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];130 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; 131 131 } 132 132 … … 135 135 int min_cut_value3=0; 136 136 for(G.first(e); G.valid(e); G.next(e)) { 137 if (cut3[G. tail(e)] && !cut3[G.head(e)])137 if (cut3[G.source(e)] && !cut3[G.target(e)]) 138 138 min_cut_value3+=cap[e]; 139 139 } … … 143 143 int max_min_cut_value3=0; 144 144 for(G.first(e); G.valid(e); G.next(e)) { 145 if (maxcut3[G. tail(e)] && !maxcut3[G.head(e)])145 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) 146 146 max_min_cut_value3+=cap[e]; 147 147 } -
src/work/jacint/max_flow_test.cc
r921 r986 46 46 EdgeIt e; 47 47 for(G.first(e); G.valid(e); G.next(e)) { 48 if (mincut[G. tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];48 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; 49 49 } 50 50 … … 53 53 int min_cut_value=0; 54 54 for(G.first(e); G.valid(e); G.next(e)) { 55 if (cut[G. tail(e)] && !cut[G.head(e)])55 if (cut[G.source(e)] && !cut[G.target(e)]) 56 56 min_cut_value+=cap[e]; 57 57 } … … 61 61 int max_min_cut_value=0; 62 62 for(G.first(e); G.valid(e); G.next(e)) { 63 if (maxcut[G. tail(e)] && !maxcut[G.head(e)])63 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) 64 64 max_min_cut_value+=cap[e]; 65 65 } … … 92 92 int min_min_cut_value2=0; 93 93 for(G.first(e); G.valid(e); G.next(e)) { 94 if (mincut2[G. tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];94 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; 95 95 } 96 96 … … 99 99 int min_cut_value2=0; 100 100 for(G.first(e); G.valid(e); G.next(e)) { 101 if (cut2[G. tail(e)] && !cut2[G.head(e)])101 if (cut2[G.source(e)] && !cut2[G.target(e)]) 102 102 min_cut_value2+=cap[e]; 103 103 } … … 107 107 int max_min_cut_value2=0; 108 108 for(G.first(e); G.valid(e); G.next(e)) { 109 if (maxcut2[G. tail(e)] && !maxcut2[G.head(e)])109 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) 110 110 max_min_cut_value2+=cap[e]; 111 111 } … … 131 131 int min_min_cut_value3=0; 132 132 for(G.first(e); G.valid(e); G.next(e)) { 133 if (mincut3[G. tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];133 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; 134 134 } 135 135 … … 138 138 int min_cut_value3=0; 139 139 for(G.first(e); G.valid(e); G.next(e)) { 140 if (cut3[G. tail(e)] && !cut3[G.head(e)])140 if (cut3[G.source(e)] && !cut3[G.target(e)]) 141 141 min_cut_value3+=cap[e]; 142 142 } … … 146 146 int max_min_cut_value3=0; 147 147 for(G.first(e); G.valid(e); G.next(e)) { 148 if (maxcut3[G. tail(e)] && !maxcut3[G.head(e)])148 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) 149 149 max_min_cut_value3+=cap[e]; 150 150 } -
src/work/jacint/max_matching.cc
r921 r986 191 191 EdgeIt e; 192 192 for(G.first(e); G.valid(e); G.next(e) ) { 193 if ( (pos[G. head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) ||194 (pos[G. head(e)]==max_matching.D && pos[G.tail(e)]==max_matching.C) )193 if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) || 194 (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) ) 195 195 noedge=false; 196 196 } -
src/work/jacint/max_matching.h
r921 r986 154 154 Edge e=map[v]; 155 155 if ( G.valid(e) ) 156 G. tail(e) == v ? mate.set(v,G.head(e)) : mate.set(v,G.tail(e));156 G.source(e) == v ? mate.set(v,G.target(e)) : mate.set(v,G.source(e)); 157 157 } 158 158 } … … 173 173 NodeIt e; 174 174 for( G.first(e); G.valid(e); G.next(e)) { 175 if ( todo[G. head(e)] && todo[G.tail(e)] ) {176 Node u=G. tail(e);177 Node v=G. head(e);175 if ( todo[G.target(e)] && todo[G.source(e)] ) { 176 Node u=G.source(e); 177 Node v=G.target(e); 178 178 if ( mate[u]=v && mate[v]=u ) { 179 179 map.set(u,e); … … 197 197 for( G.first(e); G.valid(e); G.next(e)) { 198 198 if ( G.valid(e) ) { 199 Node u=G. tail(e);200 Node v=G. head(e);199 Node u=G.source(e); 200 Node v=G.target(e); 201 201 mate.set(u,v); 202 202 mate.set(v,u); … … 223 223 for( G.first(e); G.valid(e); G.next(e)) { 224 224 map.set(e,false); 225 if ( todo[G. head(e)] && todo[G.tail(e)] ) {226 Node u=G. tail(e);227 Node v=G. head(e);225 if ( todo[G.target(e)] && todo[G.source(e)] ) { 226 Node u=G.source(e); 227 Node v=G.target(e); 228 228 if ( mate[u]=v && mate[v]=u ) { 229 229 map.set(e,true); -
src/work/jacint/max_save.h
r921 r986 259 259 OutEdgeIt e; 260 260 for(g->first(e,w) ; g->valid(e); g->next(e)) { 261 Node v=g-> head(e);261 Node v=g->target(e); 262 262 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 263 263 queue.push(v); … … 268 268 InEdgeIt f; 269 269 for(g->first(f,w) ; g->valid(f); g->next(f)) { 270 Node v=g-> tail(f);270 Node v=g->source(f); 271 271 if (!M[v] && (*flow)[f] > 0 ) { 272 272 queue.push(v); … … 305 305 InEdgeIt e; 306 306 for(g->first(e,w) ; g->valid(e); g->next(e)) { 307 Node v=g-> tail(e);307 Node v=g->source(e); 308 308 if (M[v] && (*flow)[e] < (*capacity)[e] ) { 309 309 queue.push(v); … … 314 314 OutEdgeIt f; 315 315 for(g->first(f,w) ; g->valid(f); g->next(f)) { 316 Node v=g-> head(f);316 Node v=g->target(f); 317 317 if (M[v] && (*flow)[f] > 0 ) { 318 318 queue.push(v); … … 370 370 371 371 if ( (*flow)[e] >= (*capacity)[e] ) continue; 372 Node v=g-> head(e);372 Node v=g->target(e); 373 373 374 374 if( lev > level[v] ) { //Push is allowed now … … 403 403 404 404 if( (*flow)[e] <= 0 ) continue; 405 Node v=g-> tail(e);405 Node v=g->source(e); 406 406 407 407 if( lev > level[v] ) { //Push is allowed now … … 457 457 InEdgeIt e; 458 458 for(g->first(e,v); g->valid(e); g->next(e)) { 459 Node w=g-> tail(e);459 Node w=g->source(e); 460 460 if ( level[w] == n && w != s ) { 461 461 bfs_queue.push(w); … … 475 475 Num c=(*capacity)[e]; 476 476 if ( c <= 0 ) continue; 477 Node w=g-> head(e);477 Node w=g->target(e); 478 478 if ( level[w] < n ) { 479 479 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 502 502 for(g->first(e,v); g->valid(e); g->next(e)) { 503 503 if ( (*capacity)[e] <= (*flow)[e] ) continue; 504 Node w=g-> tail(e);504 Node w=g->source(e); 505 505 if ( level[w] == n && w != s ) { 506 506 bfs_queue.push(w); … … 516 516 for(g->first(f,v); g->valid(f); g->next(f)) { 517 517 if ( 0 >= (*flow)[f] ) continue; 518 Node w=g-> head(f);518 Node w=g->target(f); 519 519 if ( level[w] == n && w != s ) { 520 520 bfs_queue.push(w); … … 535 535 Num rem=(*capacity)[e]-(*flow)[e]; 536 536 if ( rem <= 0 ) continue; 537 Node w=g-> head(e);537 Node w=g->target(e); 538 538 if ( level[w] < n ) { 539 539 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 547 547 { 548 548 if ( (*flow)[f] <= 0 ) continue; 549 Node w=g-> tail(f);549 Node w=g->source(f); 550 550 if ( level[w] < n ) { 551 551 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 645 645 // return dist[n]; } 646 646 // bool get(const typename MapGraphWrapper::Edge& e) const { 647 // return (dist.get(g-> tail(e))<dist.get(g->head(e))); }647 // return (dist.get(g->source(e))<dist.get(g->target(e))); } 648 648 bool operator[](const typename MapGraphWrapper::Edge& e) const { 649 return (dist[g-> tail(e)]<dist[g->head(e)]);649 return (dist[g->source(e)]<dist[g->target(e)]); 650 650 } 651 651 }; … … 784 784 for(g->first(e,v); g->valid(e); g->next(e)) { 785 785 if ( (*capacity)[e] <= (*flow)[e] ) continue; 786 Node u=g-> tail(e);786 Node u=g->source(e); 787 787 if ( level[u] >= n ) { 788 788 bfs_queue.push(u); … … 795 795 for(g->first(f,v); g->valid(f); g->next(f)) { 796 796 if ( 0 >= (*flow)[f] ) continue; 797 Node u=g-> head(f);797 Node u=g->target(f); 798 798 if ( level[u] >= n ) { 799 799 bfs_queue.push(u); … … 847 847 ResGWOutEdgeIt e=bfs; 848 848 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 849 Node v=res_graph. tail(e);850 Node w=res_graph. head(e);849 Node v=res_graph.source(e); 850 Node w=res_graph.target(e); 851 851 pred.set(w, e); 852 852 if (res_graph.valid(pred[v])) { … … 855 855 free.set(w, res_graph.resCap(e)); 856 856 } 857 if (res_graph. head(e)==t) { _augment=true; break; }857 if (res_graph.target(e)==t) { _augment=true; break; } 858 858 } 859 859 … … 867 867 ResGWEdge e=pred[n]; 868 868 res_graph.augment(e, augment_value); 869 n=res_graph. tail(e);869 n=res_graph.source(e); 870 870 } 871 871 } … … 920 920 if (res_graph.valid(e)) { 921 921 if (bfs.isBNodeNewlyReached()) { 922 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);923 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);922 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 923 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 924 924 original_edge.update(); 925 925 original_edge.set(f, e); … … 927 927 residual_capacity.set(f, res_graph.resCap(e)); 928 928 } else { 929 if (dist[res_graph. head(e)]==(dist[res_graph.tail(e)]+1)) {930 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);929 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { 930 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 931 931 original_edge.update(); 932 932 original_edge.set(f, e); … … 982 982 typename MG::Edge e=pred[n]; 983 983 res_graph.augment(original_edge[e], augment_value); 984 n=F. tail(e);984 n=F.source(e); 985 985 if (residual_capacity[e]==augment_value) 986 986 F.erase(e); … … 1016 1016 ResGWOutEdgeIt e=bfs; 1017 1017 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 1018 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);1018 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 1019 1019 } 1020 1020 ++bfs; … … 1113 1113 typename ErasingResGW::OutEdgeIt e=pred[n]; 1114 1114 res_graph.augment(e, augment_value); 1115 n=erasing_res_graph. tail(e);1115 n=erasing_res_graph.source(e); 1116 1116 if (res_graph.resCap(e)==0) 1117 1117 erasing_res_graph.erase(e); -
src/work/jacint/preflow.cc
r921 r986 47 47 for(G.first(e); G.valid(e); G.next(e)) { 48 48 int c=cap[e]; 49 if (mincut[G. tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c;50 if (cut[G. tail(e)] && !cut[G.head(e)]) min_cut_value+=c;51 if (maxcut[G. tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c;49 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c; 50 if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c; 51 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c; 52 52 } 53 53 … … 87 87 for(G.first(e); G.valid(e); G.next(e)) { 88 88 int c=cap[e]; 89 if (mincut2[G. tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c;90 if (cut2[G. tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c;91 if (maxcut2[G. tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c;89 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c; 90 if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c; 91 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c; 92 92 } 93 93 … … 139 139 for(G.first(e); G.valid(e); G.next(e)) { 140 140 int c=cap[e]; 141 if (mincut3[G. tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c;142 if (cut3[G. tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c;143 if (maxcut3[G. tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c;144 if (actcut3[G. tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c;141 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c; 142 if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c; 143 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c; 144 if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c; 145 145 } 146 146 … … 196 196 for(G.first(e); G.valid(e); G.next(e)) { 197 197 int c=cap[e]; 198 if (mincut4[G. tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c;199 if (cut4[G. tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c;200 if (maxcut4[G. tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c;198 if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c; 199 if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c; 200 if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c; 201 201 } 202 202 … … 239 239 for(G.first(e); G.valid(e); G.next(e)) { 240 240 int c=cap[e]; 241 if (mincut5[G. tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c;242 if (cut5[G. tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c;243 if (maxcut5[G. tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c;241 if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c; 242 if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c; 243 if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c; 244 244 } 245 245 -
src/work/jacint/preflow_excess.h
r921 r986 137 137 InEdgeIt e; 138 138 for(G.first(e,v); G.valid(e); G.next(e)) { 139 Node w=G. tail(e);139 Node w=G.source(e); 140 140 if ( level[w] == n && w != s ) { 141 141 bfs_queue.push(w); … … 155 155 T c=capacity[e]; 156 156 if ( c == 0 ) continue; 157 Node w=G. head(e);157 Node w=G.target(e); 158 158 if ( level[w] < n ) { 159 159 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 183 183 for(G.first(e,v); G.valid(e); G.next(e)) { 184 184 if ( capacity[e] == flow[e] ) continue; 185 Node w=G. tail(e);185 Node w=G.source(e); 186 186 if ( level[w] == n && w != s ) { 187 187 bfs_queue.push(w); … … 197 197 for(G.first(f,v); G.valid(f); G.next(f)) { 198 198 if ( 0 == flow[f] ) continue; 199 Node w=G. head(f);199 Node w=G.target(f); 200 200 if ( level[w] == n && w != s ) { 201 201 bfs_queue.push(w); … … 248 248 T rem=capacity[e]-flow[e]; 249 249 if ( rem == 0 ) continue; 250 Node w=G. head(e);250 Node w=G.target(e); 251 251 if ( level[w] < n ) { 252 252 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 260 260 { 261 261 if ( flow[f] == 0 ) continue; 262 Node w=G. tail(f);262 Node w=G.source(f); 263 263 if ( level[w] < n ) { 264 264 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 304 304 for(G.first(e,v); G.valid(e); G.next(e)) { 305 305 if ( capacity[e] == flow[e] ) continue; 306 Node u=G. tail(e);306 Node u=G.source(e); 307 307 if ( level[u] >= n ) { 308 308 bfs_queue.push(u); … … 315 315 for(G.first(f,v); G.valid(f); G.next(f)) { 316 316 if ( 0 == flow[f] ) continue; 317 Node u=G. head(f);317 Node u=G.target(f); 318 318 if ( level[u] >= n ) { 319 319 bfs_queue.push(u); … … 344 344 345 345 if ( flow[e] == capacity[e] ) continue; 346 Node v=G. head(e);346 Node v=G.target(e); 347 347 //e=wv 348 348 … … 386 386 387 387 if( flow[e] == 0 ) continue; 388 Node v=G. tail(e);388 Node v=G.source(e); 389 389 //e=vw 390 390 … … 570 570 OutEdgeIt e; 571 571 for(G.first(e,w) ; G.valid(e); G.next(e)) { 572 Node v=G. head(e);572 Node v=G.target(e); 573 573 if (!M[v] && flow[e] < capacity[e] ) { 574 574 queue.push(v); … … 579 579 InEdgeIt f; 580 580 for(G.first(f,w) ; G.valid(f); G.next(f)) { 581 Node v=G. tail(f);581 Node v=G.source(f); 582 582 if (!M[v] && flow[f] > 0 ) { 583 583 queue.push(v); … … 610 610 InEdgeIt e; 611 611 for(G.first(e,w) ; G.valid(e); G.next(e)) { 612 Node v=G. tail(e);612 Node v=G.source(e); 613 613 if (!M[v] && flow[e] < capacity[e] ) { 614 614 queue.push(v); … … 619 619 OutEdgeIt f; 620 620 for(G.first(f,w) ; G.valid(f); G.next(f)) { 621 Node v=G. head(f);621 Node v=G.target(f); 622 622 if (!M[v] && flow[f] > 0 ) { 623 623 queue.push(v); -
src/work/jacint/preflow_excess_test.cc
r921 r986 53 53 EdgeIt e; 54 54 for(G.first(e); G.valid(e); G.next(e)) { 55 if (mincut[G. tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];55 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; 56 56 } 57 57 … … 60 60 int min_cut_value=0; 61 61 for(G.first(e); G.valid(e); G.next(e)) { 62 if (cut[G. tail(e)] && !cut[G.head(e)])62 if (cut[G.source(e)] && !cut[G.target(e)]) 63 63 min_cut_value+=cap[e]; 64 64 } … … 68 68 int max_min_cut_value=0; 69 69 for(G.first(e); G.valid(e); G.next(e)) { 70 if (maxcut[G. tail(e)] && !maxcut[G.head(e)])70 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) 71 71 max_min_cut_value+=cap[e]; 72 72 } … … 100 100 int min_min_cut_value2=0; 101 101 for(G.first(e); G.valid(e); G.next(e)) { 102 if (mincut2[G. tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];102 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; 103 103 } 104 104 … … 107 107 int min_cut_value2=0; 108 108 for(G.first(e); G.valid(e); G.next(e)) { 109 if (cut2[G. tail(e)] && !cut2[G.head(e)])109 if (cut2[G.source(e)] && !cut2[G.target(e)]) 110 110 min_cut_value2+=cap[e]; 111 111 } … … 115 115 int max_min_cut_value2=0; 116 116 for(G.first(e); G.valid(e); G.next(e)) { 117 if (maxcut2[G. tail(e)] && !maxcut2[G.head(e)])117 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) 118 118 max_min_cut_value2+=cap[e]; 119 119 } … … 145 145 int min_min_cut_value3=0; 146 146 for(G.first(e); G.valid(e); G.next(e)) { 147 if (mincut3[G. tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];147 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; 148 148 } 149 149 … … 152 152 int min_cut_value3=0; 153 153 for(G.first(e); G.valid(e); G.next(e)) { 154 if (cut3[G. tail(e)] && !cut3[G.head(e)])154 if (cut3[G.source(e)] && !cut3[G.target(e)]) 155 155 min_cut_value3+=cap[e]; 156 156 } … … 160 160 int max_min_cut_value3=0; 161 161 for(G.first(e); G.valid(e); G.next(e)) { 162 if (maxcut3[G. tail(e)] && !maxcut3[G.head(e)])162 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) 163 163 max_min_cut_value3+=cap[e]; 164 164 } -
src/work/jacint/preflow_res.h
r921 r986 103 103 for(res_graph.first(e,v); res_graph.valid(e); 104 104 res_graph.next(e)) { 105 Node w=res_graph. tail(e);105 Node w=res_graph.source(e); 106 106 if ( level[w] == n && w != s ) { 107 107 bfs_queue.push(w); … … 146 146 for(res_graph.first(e,s); res_graph.valid(e); 147 147 res_graph.next(e)) { 148 Node w=res_graph. head(e);148 Node w=res_graph.target(e); 149 149 if ( level[w] < n ) { 150 150 if ( excess[w] == 0 && w!=t ) { … … 191 191 for(res_graph.first(e,v); 192 192 res_graph.valid(e); res_graph.next(e)) { 193 Node u=res_graph. tail(e);193 Node u=res_graph.source(e); 194 194 if ( level[u] >= n ) { 195 195 bfs_queue.push(u); … … 222 222 for(res_graph.first(e,w); res_graph.valid(e); res_graph.next(e)) { 223 223 224 Node v=res_graph. head(e);224 Node v=res_graph.target(e); 225 225 if( lev > level[v] ) { 226 226 /*Push is allowed now*/ … … 401 401 OutEdgeIt e; 402 402 for(G.first(e,w) ; G.valid(e); G.next(e)) { 403 Node v=G. head(e);403 Node v=G.target(e); 404 404 if (!M[v] && flow[e] < capacity[e] ) { 405 405 queue.push(v); … … 410 410 InEdgeIt f; 411 411 for(G.first(f,w) ; G.valid(f); G.next(f)) { 412 Node v=G. tail(f);412 Node v=G.source(f); 413 413 if (!M[v] && flow[f] > 0 ) { 414 414 queue.push(v); … … 441 441 InEdgeIt e; 442 442 for(G.first(e,w) ; G.valid(e); G.next(e)) { 443 Node v=G. tail(e);443 Node v=G.source(e); 444 444 if (!M[v] && flow[e] < capacity[e] ) { 445 445 queue.push(v); … … 450 450 OutEdgeIt f; 451 451 for(G.first(f,w) ; G.valid(f); G.next(f)) { 452 Node v=G. head(f);452 Node v=G.target(f); 453 453 if (!M[v] && flow[f] > 0 ) { 454 454 queue.push(v); -
src/work/jacint/prim.h
r921 r986 96 96 OutEdgeIt e; 97 97 for( G.first(e,v); G.valid(e); G.next(e)) { 98 Node w=G. head(e);98 Node w=G.target(e); 99 99 100 100 if ( !scanned[w] ) { … … 112 112 InEdgeIt f; 113 113 for( G.first(f,v); G.valid(f); G.next(f)) { 114 Node w=G. tail(f);114 Node w=G.source(f); 115 115 116 116 if ( !scanned[w] ) { -
src/work/johanna/ma_order.h
r921 r986 58 58 G.first(e,a); 59 59 for (;G.valid(e);G.next(e)) { 60 Node v = G. head(e); // hmm60 Node v = G.target(e); // hmm 61 61 if (heap.state(v) == Heap::IN_HEAP ) { 62 62 heap.decrease(v, heap[v]+1); -
src/work/marci/augmenting_flow.h
r970 r986 211 211 OutEdgeIt e; 212 212 for(g->first(e,w) ; e!=INVALID; ++e) { 213 Node v=g-> head(e);213 Node v=g->target(e); 214 214 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 215 215 queue.push(v); … … 220 220 InEdgeIt f; 221 221 for(g->first(f,w) ; f!=INVALID; ++f) { 222 Node v=g-> tail(f);222 Node v=g->source(f); 223 223 if (!M[v] && (*flow)[f] > 0 ) { 224 224 queue.push(v); … … 271 271 ResGWEdge e=bfs; 272 272 if (e!=INVALID && bfs.isBNodeNewlyReached()) { 273 Node v=res_graph. tail(e);274 Node w=res_graph. head(e);273 Node v=res_graph.source(e); 274 Node w=res_graph.target(e); 275 275 pred.set(w, e); 276 276 if (pred[v]!=INVALID) { … … 279 279 free.set(w, res_cap[e]); 280 280 } 281 if (res_graph. head(e)==t) { _augment=true; break; }281 if (res_graph.target(e)==t) { _augment=true; break; } 282 282 } 283 283 … … 291 291 ResGWEdge e=pred[n]; 292 292 res_graph.augment(e, augment_value); 293 n=res_graph. tail(e);293 n=res_graph.source(e); 294 294 } 295 295 } … … 330 330 ResGWEdge e=bfs; 331 331 if (e!=INVALID && bfs.isBNodeNewlyReached()) { 332 Node v=res_graph. tail(e);333 Node w=res_graph. head(e);332 Node v=res_graph.source(e); 333 Node w=res_graph.target(e); 334 334 pred.set(w, e); 335 335 if (pred[v]!=INVALID) { … … 338 338 free.set(w, res_cap[e]); 339 339 } 340 if (res_graph. head(e)==t) { _augment=true; break; }340 if (res_graph.target(e)==t) { _augment=true; break; } 341 341 } 342 342 … … 350 350 ResGWEdge e=pred[n]; 351 351 res_graph.augment(e, augment_value); 352 n=res_graph. tail(e);352 n=res_graph.source(e); 353 353 } 354 354 } … … 396 396 if (e!=INVALID) { 397 397 if (bfs.isBNodeNewlyReached()) { 398 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);399 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)],400 res_graph_to_F[res_graph. head(e)]);398 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 399 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], 400 res_graph_to_F[res_graph.target(e)]); 401 401 //original_edge.update(); 402 402 original_edge.set(f, e); … … 404 404 residual_capacity.set(f, res_cap[e]); 405 405 } else { 406 if (dist[res_graph. head(e)]==(dist[res_graph.tail(e)]+1)) {407 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)],408 res_graph_to_F[res_graph. head(e)]);406 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { 407 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], 408 res_graph_to_F[res_graph.target(e)]); 409 409 //original_edge.update(); 410 410 original_edge.set(f, e); … … 434 434 if (typename MG::Edge(dfs)!=INVALID) { 435 435 if (dfs.isBNodeNewlyReached()) { 436 typename MG::Node v=F. tail(dfs);437 typename MG::Node w=F. head(dfs);436 typename MG::Node v=F.source(dfs); 437 typename MG::Node w=F.target(dfs); 438 438 pred.set(w, dfs); 439 439 if (pred[v]!=INVALID) { … … 460 460 typename MG::Edge e=pred[n]; 461 461 res_graph.augment(original_edge[e], augment_value); 462 n=F. tail(e);462 n=F.source(e); 463 463 if (residual_capacity[e]==augment_value) 464 464 F.erase(e); … … 499 499 ResGWEdge e=bfs; 500 500 if (e!=INVALID && bfs.isBNodeNewlyReached()) 501 potential.set(res_graph. head(e), potential[res_graph.tail(e)]+1);501 potential.set(res_graph.target(e), potential[res_graph.source(e)]+1); 502 502 ++bfs; 503 503 } … … 554 554 if (dfs.isBNodeNewlyReached()) { 555 555 556 typename ErasingResGW::Node v=erasing_res_graph. tail(dfs);557 typename ErasingResGW::Node w=erasing_res_graph. head(dfs);556 typename ErasingResGW::Node v=erasing_res_graph.source(dfs); 557 typename ErasingResGW::Node w=erasing_res_graph.target(dfs); 558 558 559 559 pred.set(w, typename ErasingResGW::Edge(dfs)); … … 586 586 typename ErasingResGW::Edge e=pred[n]; 587 587 res_graph.augment(e, augment_value); 588 n=erasing_res_graph. tail(e);588 n=erasing_res_graph.source(e); 589 589 if (res_cap[e]==0) 590 590 erasing_res_graph.erase(e); -
src/work/marci/bfs_dfs.h
r921 r986 64 64 //graph->first(actual_edge, s); 65 65 if (actual_edge!=INVALID) { 66 Node w=graph-> head(actual_edge);66 Node w=graph->target(actual_edge); 67 67 if (!reached[w]) { 68 68 bfs_queue.push(w); … … 86 86 //++actual_edge; 87 87 if (actual_edge!=INVALID) { 88 Node w=graph-> head(actual_edge);88 Node w=graph->target(actual_edge); 89 89 if (!reached[w]) { 90 90 bfs_queue.push(w); … … 101 101 //graph->first(actual_edge, bfs_queue.front()); 102 102 if (actual_edge!=INVALID) { 103 Node w=graph-> head(actual_edge);103 Node w=graph->target(actual_edge); 104 104 if (!reached[w]) { 105 105 bfs_queue.push(w); … … 125 125 bool isANodeExamined() const { return actual_edge==INVALID; } 126 126 /// Returns a-node of the actual edge, so does if the edge is invalid. 127 Node tail() const { return bfs_queue.front(); }127 Node source() const { return bfs_queue.front(); } 128 128 /// \pre The actual edge have to be valid. 129 Node head() const { return graph->head(actual_edge); }129 Node target() const { return graph->target(actual_edge); } 130 130 /// Guess what? 131 131 /// \deprecated … … 187 187 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 188 188 { 189 pred.set(this-> head(), this->actual_edge);190 dist.set(this-> head(), dist[this->tail()]);189 pred.set(this->target(), this->actual_edge); 190 dist.set(this->target(), dist[this->source()]); 191 191 } 192 192 return *this; … … 247 247 actual_edge=dfs_stack.top(); 248 248 if (actual_edge!=INVALID/*.valid()*/) { 249 Node w=graph-> head(actual_edge);249 Node w=graph->target(actual_edge); 250 250 actual_node=w; 251 251 if (!reached[w]) { … … 256 256 b_node_newly_reached=true; 257 257 } else { 258 actual_node=graph-> tail(actual_edge);258 actual_node=graph->source(actual_edge); 259 259 ++dfs_stack.top(); 260 260 b_node_newly_reached=false; … … 277 277 bool isANodeExamined() const { return actual_edge==INVALID; } 278 278 /// Returns a-node of the actual edge, so does if the edge is invalid. 279 Node tail() const { return actual_node; /*FIXME*/}279 Node source() const { return actual_node; /*FIXME*/} 280 280 /// Returns b-node of the actual edge. 281 281 /// \pre The actual edge have to be valid. 282 Node head() const { return graph->head(actual_edge); }282 Node target() const { return graph->target(actual_edge); } 283 283 /// Guess what? 284 284 /// \deprecated … … 334 334 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 335 335 { 336 pred.set(this-> head(), this->actual_edge);336 pred.set(this->target(), this->actual_edge); 337 337 } 338 338 return *this; -
src/work/marci/bfs_mm.h
r944 r986 72 72 //graph->first(actual_edge, s); 73 73 if (actual_edge!=INVALID) { 74 Node w=graph-> head(actual_edge);74 Node w=graph->target(actual_edge); 75 75 if (!(*reached_map)[w]) { 76 76 bfs_queue.push(w); … … 94 94 //++actual_edge; 95 95 if (actual_edge!=INVALID) { 96 Node w=graph-> head(actual_edge);96 Node w=graph->target(actual_edge); 97 97 if (!(*reached_map)[w]) { 98 98 bfs_queue.push(w); … … 109 109 //graph->first(actual_edge, bfs_queue.front()); 110 110 if (actual_edge!=INVALID) { 111 Node w=graph-> head(actual_edge);111 Node w=graph->target(actual_edge); 112 112 if (!(*reached_map)[w]) { 113 113 bfs_queue.push(w); … … 133 133 bool isANodeExamined() const { return actual_edge==INVALID; } 134 134 /// Returns a-node of the actual edge, so does if the edge is invalid. 135 Node tail() const { return bfs_queue.front(); }135 Node source() const { return bfs_queue.front(); } 136 136 /// \pre The actual edge have to be valid. 137 Node head() const { return graph->head(actual_edge); }137 Node target() const { return graph->target(actual_edge); } 138 138 /// Guess what? 139 139 /// \deprecated … … 232 232 if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) 233 233 { 234 pred_map->set(this-> head(), this->actual_edge);235 pred_node_map->set(this-> head(), this->tail());236 dist_map->set(this-> head(), (*dist_map)[this->tail()]);234 pred_map->set(this->target(), this->actual_edge); 235 pred_node_map->set(this->target(), this->source()); 236 dist_map->set(this->target(), (*dist_map)[this->source()]); 237 237 } 238 238 return *this; … … 458 458 actual_edge=dfs_stack.top(); 459 459 if (actual_edge!=INVALID/*.valid()*/) { 460 Node w=graph-> head(actual_edge);460 Node w=graph->target(actual_edge); 461 461 actual_node=w; 462 462 if (!reached[w]) { … … 467 467 b_node_newly_reached=true; 468 468 } else { 469 actual_node=graph-> tail(actual_edge);469 actual_node=graph->source(actual_edge); 470 470 ++dfs_stack.top(); 471 471 b_node_newly_reached=false; … … 488 488 bool isANodeExamined() const { return actual_edge==INVALID; } 489 489 /// Returns a-node of the actual edge, so does if the edge is invalid. 490 Node tail() const { return actual_node; /*FIXME*/}490 Node source() const { return actual_node; /*FIXME*/} 491 491 /// Returns b-node of the actual edge. 492 492 /// \pre The actual edge have to be valid. 493 Node head() const { return graph->head(actual_edge); }493 Node target() const { return graph->target(actual_edge); } 494 494 /// Guess what? 495 495 /// \deprecated … … 545 545 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 546 546 { 547 pred.set(this-> head(), this->actual_edge);547 pred.set(this->target(), this->actual_edge); 548 548 } 549 549 return *this; -
src/work/marci/bfs_mm_test.cc
r959 r986 92 92 93 93 // for(EdgeIt e(G); e==INVALID; ++e) { 94 // Node u=G. tail(e);95 // Node v=G. head(e);94 // Node u=G.source(e); 95 // Node v=G.target(e); 96 96 // check( !bfs_test.reached(u) || 97 97 // (bfs_test.dist(v) > bfs_test.dist(u)+1), … … 103 103 // if ( bfs_test.pred(v)!=INVALID ) { 104 104 // Edge e=bfs_test.pred(v); 105 // Node u=G. tail(e);105 // Node u=G.source(e); 106 106 // check(u==bfs_test.predNode(v),"Wrong tree."); 107 107 // check(bfs_test.dist(v) - bfs_test.dist(u) == 1, -
src/work/marci/bfsit_vs_byhand.cc
r944 r986 49 49 bfs_queue.pop(); 50 50 for(OutEdgeIt e(g,v); e!=INVALID; ++e) { 51 Node w=g. head(e);51 Node w=g.target(e); 52 52 if (!reached[w]) { 53 53 bfs_queue.push(w); … … 71 71 ++bfs; 72 72 if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) 73 pred.set(bfs. head(), Graph::Edge(bfs));73 pred.set(bfs.target(), Graph::Edge(bfs)); 74 74 } 75 75 } -
src/work/marci/bipartite_graph_wrapper.h
r921 r986 168 168 // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 169 169 170 // Node tail(const Edge& e) {171 // if (!(*(this->s_false_t_true_map))[this->graph-> tail(e)])172 // return Node(this->graph-> tail(e));170 // Node source(const Edge& e) { 171 // if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 172 // return Node(this->graph->source(e)); 173 173 // else 174 // return Node(this->graph-> head(e));175 // } 176 // Node head(const Edge& e) {177 // if (!(*(this->s_false_t_true_map))[this->graph-> tail(e)])178 // return Node(this->graph-> head(e));174 // return Node(this->graph->target(e)); 175 // } 176 // Node target(const Edge& e) { 177 // if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 178 // return Node(this->graph->target(e)); 179 179 // else 180 // return Node(this->graph-> tail(e));180 // return Node(this->graph->source(e)); 181 181 // } 182 182 … … 253 253 254 254 /// A new edge is inserted. 255 ///\pre \c tail have to be in \c S_Class and \c headin \c T_Class.256 Edge addEdge(const Node& tail, const Node& head) {257 return Parent::graph->addEdge( tail, head);255 ///\pre \c source have to be in \c S_Class and \c target in \c T_Class. 256 Edge addEdge(const Node& source, const Node& target) { 257 return Parent::graph->addEdge(source, target); 258 258 } 259 259 … … 696 696 } 697 697 698 Node tail(const Edge& e) const {698 Node source(const Edge& e) const { 699 699 switch (e.spec) { 700 700 case 0: 701 return Node(this->graph-> tail(e));701 return Node(this->graph->source(e)); 702 702 break; 703 703 case 1: … … 710 710 } 711 711 } 712 Node head(const Edge& e) const {712 Node target(const Edge& e) const { 713 713 switch (e.spec) { 714 714 case 0: 715 return Node(this->graph-> head(e));715 return Node(this->graph->target(e)); 716 716 break; 717 717 case 1: … … 733 733 } 734 734 735 Node aNode(const OutEdgeIt& e) const { return tail(e); }736 Node aNode(const InEdgeIt& e) const { return head(e); }737 Node bNode(const OutEdgeIt& e) const { return head(e); }738 Node bNode(const InEdgeIt& e) const { return tail(e); }735 Node aNode(const OutEdgeIt& e) const { return source(e); } 736 Node aNode(const InEdgeIt& e) const { return target(e); } 737 Node bNode(const OutEdgeIt& e) const { return target(e); } 738 Node bNode(const InEdgeIt& e) const { return source(e); } 739 739 740 740 void addNode() const { } … … 742 742 743 743 // Node addNode() const { return Node(this->graph->addNode()); } 744 // Edge addEdge(const Node& tail, const Node& head) const {745 // return Edge(this->graph->addEdge( tail, head)); }744 // Edge addEdge(const Node& source, const Node& target) const { 745 // return Edge(this->graph->addEdge(source, target)); } 746 746 747 747 // void erase(const Node& i) const { this->graph->erase(i); } -
src/work/marci/bipartite_graph_wrapper_test.cc
r921 r986 88 88 cout << "Edges of the bipartite graph:" << endl; 89 89 for (BGW::EdgeIt e(bgw); e!=INVALID; ++e) 90 cout << g.id(bgw. tail(e)) << "->" << g.id(bgw.head(e)) << endl;90 cout << g.id(bgw.source(e)) << "->" << g.id(bgw.target(e)) << endl; 91 91 92 92 BGW::NodeMap<int> dbyj(bgw); -
src/work/marci/experiment/edmonds_karp.h
r921 r986 41 41 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } 42 42 Number free() const { 43 if (resG->G.aNode(sym)==resG->G. tail(sym)) {43 if (resG->G.aNode(sym)==resG->G.source(sym)) { 44 44 return (resG->capacity.get(sym)-resG->flow.get(sym)); 45 45 } else { … … 49 49 bool valid() const { return sym.valid(); } 50 50 void augment(Number a) const { 51 if (resG->G.aNode(sym)==resG->G. tail(sym)) {51 if (resG->G.aNode(sym)==resG->G.source(sym)) { 52 52 resG->flow.set(sym, resG->flow.get(sym)+a); 53 53 //resG->flow[sym]+=a; … … 97 97 } 98 98 99 Node tail(Edge e) const { return G.aNode(e.sym); }100 Node head(Edge e) const { return G.bNode(e.sym); }99 Node source(Edge e) const { return G.aNode(e.sym); } 100 Node target(Edge e) const { return G.bNode(e.sym); } 101 101 102 102 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } … … 224 224 } 225 225 226 Node tail(Edge e) const {226 Node source(Edge e) const { 227 227 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 228 Node head(Edge e) const {228 Node target(Edge e) const { 229 229 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 230 230 … … 288 288 ResGWOutEdgeIt e=bfs; 289 289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 290 Node v=res_graph. tail(e);291 Node w=res_graph. head(e);290 Node v=res_graph.source(e); 291 Node w=res_graph.target(e); 292 292 pred.set(w, e); 293 293 if (res_graph.valid(pred.get(v))) { … … 296 296 free.set(w, res_graph.resCap(e)); 297 297 } 298 if (res_graph. head(e)==t) { _augment=true; break; }298 if (res_graph.target(e)==t) { _augment=true; break; } 299 299 } 300 300 … … 308 308 ResGWEdge e=pred.get(n); 309 309 res_graph.augment(e, augment_value); 310 n=res_graph. tail(e);310 n=res_graph.source(e); 311 311 } 312 312 } … … 325 325 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } 326 326 bool get(const typename MapGraphWrapper::Edge& e) const { 327 return (dist.get(gw. tail(e))<dist.get(gw.head(e)));327 return (dist.get(gw.source(e))<dist.get(gw.target(e))); 328 328 } 329 329 }; … … 344 344 ResGWOutEdgeIt e=bfs; 345 345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 346 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);346 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 347 347 } 348 348 ++bfs; … … 370 370 typename FilterResGW::EdgeIt e; 371 371 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 372 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));372 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 374 374 original_edge.update(); 375 375 original_edge.set(f, e); … … 424 424 typename MG::Edge e=pred.get(n); 425 425 res_graph.augment(original_edge.get(e), augment_value); 426 n=F. tail(e);426 n=F.source(e); 427 427 if (residual_capacity.get(e)==augment_value) 428 428 F.erase(e); … … 469 469 if (res_graph.valid(e)) { 470 470 if (bfs.isBNodeNewlyReached()) { 471 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));471 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 473 473 original_edge.update(); 474 474 original_edge.set(f, e); … … 476 476 residual_capacity.set(f, res_graph.resCap(e)); 477 477 } else { 478 if (dist.get(res_graph. head(e))==(dist.get(res_graph.tail(e))+1)) {479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));478 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { 479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 480 480 original_edge.update(); 481 481 original_edge.set(f, e); … … 532 532 typename MG::Edge e=pred.get(n); 533 533 res_graph.augment(original_edge.get(e), augment_value); 534 n=F. tail(e);534 n=F.source(e); 535 535 if (residual_capacity.get(e)==augment_value) 536 536 F.erase(e); … … 558 558 ResGWOutEdgeIt e=bfs; 559 559 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 560 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);560 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 561 561 } 562 562 ++bfs; … … 634 634 typename ErasingResGW::OutEdgeIt e=pred.get(n); 635 635 res_graph.augment(e, augment_value); 636 n=erasing_res_graph. tail(e);636 n=erasing_res_graph.source(e); 637 637 if (res_graph.resCap(e)==0) 638 638 erasing_res_graph.erase(e); … … 669 669 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 670 670 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 671 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);671 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 672 672 // } 673 673 // ++bfs; … … 723 723 // EAugEdge e=pred.get(n); 724 724 // res_graph.augment(e, augment_value); 725 // n=res_graph. tail(e);725 // n=res_graph.source(e); 726 726 // if (res_graph.free(e)==0) 727 727 // res_graph.erase(e); … … 818 818 // AugOutEdgeIt e=bfs; 819 819 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 820 // Node v=res_graph. tail(e);821 // Node w=res_graph. head(e);820 // Node v=res_graph.source(e); 821 // Node w=res_graph.target(e); 822 822 // pred.set(w, e); 823 823 // if (res_graph.valid(pred.get(v))) { … … 826 826 // free.set(w, res_graph.free(e)); 827 827 // } 828 // n=res_graph. head(e);828 // n=res_graph.target(e); 829 829 // if (T->get(n) && (used.get(n)<1) ) { 830 830 // //Number u=0; … … 848 848 // AugEdge e=pred.get(n); 849 849 // res_graph.augment(e, augment_value); 850 // n=res_graph. tail(e);850 // n=res_graph.source(e); 851 851 // } 852 852 // used.set(n, 1); //mind2 vegen jav … … 889 889 // // AugOutEdgeIt e=bfs; 890 890 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 891 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);891 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 892 892 // // } 893 893 … … 911 911 // // //which are in some shortest paths 912 912 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 913 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {914 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));913 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 914 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 915 915 // // original_edge.update(); 916 916 // // original_edge.set(f, e); … … 964 964 // // typename MutableGraph::Edge e=pred.get(n); 965 965 // // res_graph.augment(original_edge.get(e), augment_value); 966 // // n=F. tail(e);966 // // n=F.source(e); 967 967 // // if (residual_capacity.get(e)==augment_value) 968 968 // // F.erase(e); … … 1015 1015 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 1016 1016 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 1017 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);1017 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 1018 1018 // } 1019 1019 // ++bfs; … … 1092 1092 // EAugEdge e=pred.get(n); 1093 1093 // res_graph.augment(e, augment_value); 1094 // n=res_graph. tail(e);1094 // n=res_graph.source(e); 1095 1095 // if (res_graph.free(e)==0) 1096 1096 // res_graph.erase(e); … … 1185 1185 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 1186 1186 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 1187 // // Node v=res_graph. tail(e);1188 // // Node w=res_graph. head(e);1187 // // Node v=res_graph.source(e); 1188 // // Node w=res_graph.target(e); 1189 1189 // // pred.set(w, e); 1190 1190 // // if (pred.get(v).valid()) { … … 1193 1193 // // free.set(w, e.free()); 1194 1194 // // } 1195 // // if (TMap.get(res_graph. head(e))) {1195 // // if (TMap.get(res_graph.target(e))) { 1196 1196 // // _augment=true; 1197 // // reached_t_node=res_graph. head(e);1197 // // reached_t_node=res_graph.target(e); 1198 1198 // // break; 1199 1199 // // } … … 1209 1209 // // AugEdge e=pred.get(n); 1210 1210 // // e.augment(augment_value); 1211 // // n=res_graph. tail(e);1211 // // n=res_graph.source(e); 1212 1212 // // } 1213 1213 // // } -
src/work/marci/experiment/edmonds_karp_1.h
r921 r986 42 42 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } 43 43 Number free() const { 44 if (resG->G.aNode(sym)==resG->G. tail(sym)) {44 if (resG->G.aNode(sym)==resG->G.source(sym)) { 45 45 return (resG->capacity.get(sym)-resG->flow.get(sym)); 46 46 } else { … … 50 50 bool valid() const { return sym.valid(); } 51 51 void augment(Number a) const { 52 if (resG->G.aNode(sym)==resG->G. tail(sym)) {52 if (resG->G.aNode(sym)==resG->G.source(sym)) { 53 53 resG->flow.set(sym, resG->flow.get(sym)+a); 54 54 //resG->flow[sym]+=a; … … 98 98 } 99 99 100 Node tail(Edge e) const { return G.aNode(e.sym); }101 Node head(Edge e) const { return G.bNode(e.sym); }100 Node source(Edge e) const { return G.aNode(e.sym); } 101 Node target(Edge e) const { return G.bNode(e.sym); } 102 102 103 103 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } … … 225 225 } 226 226 227 Node tail(Edge e) const {227 Node source(Edge e) const { 228 228 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 229 Node head(Edge e) const {229 Node target(Edge e) const { 230 230 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 231 231 … … 287 287 ResGWOutEdgeIt e=bfs; 288 288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 289 Node v=res_graph. tail(e);290 Node w=res_graph. head(e);289 Node v=res_graph.source(e); 290 Node w=res_graph.target(e); 291 291 pred.set(w, e); 292 292 if (res_graph.valid(pred.get(v))) { … … 295 295 free.set(w, res_graph.resCap(e)); 296 296 } 297 if (res_graph. head(e)==t) { _augment=true; break; }297 if (res_graph.target(e)==t) { _augment=true; break; } 298 298 } 299 299 … … 307 307 ResGWEdge e=pred.get(n); 308 308 res_graph.augment(e, augment_value); 309 n=res_graph. tail(e);309 n=res_graph.source(e); 310 310 } 311 311 } … … 324 324 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } 325 325 bool get(const typename MapGraphWrapper::Edge& e) const { 326 return (dist.get(g-> tail(e))<dist.get(g->head(e)));326 return (dist.get(g->source(e))<dist.get(g->target(e))); 327 327 } 328 328 }; … … 343 343 ResGWOutEdgeIt e=bfs; 344 344 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 345 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);345 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 346 346 } 347 347 ++bfs; … … 369 369 typename FilterResGW::EdgeIt e; 370 370 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 371 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));371 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 373 373 original_edge.update(); 374 374 original_edge.set(f, e); … … 423 423 typename MG::Edge e=pred.get(n); 424 424 res_graph.augment(original_edge.get(e), augment_value); 425 n=F. tail(e);425 n=F.source(e); 426 426 if (residual_capacity.get(e)==augment_value) 427 427 F.erase(e); … … 468 468 if (res_graph.valid(e)) { 469 469 if (bfs.isBNodeNewlyReached()) { 470 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));470 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 472 472 original_edge.update(); 473 473 original_edge.set(f, e); … … 475 475 residual_capacity.set(f, res_graph.resCap(e)); 476 476 } else { 477 if (dist.get(res_graph. head(e))==(dist.get(res_graph.tail(e))+1)) {478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));477 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { 478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 479 479 original_edge.update(); 480 480 original_edge.set(f, e); … … 531 531 typename MG::Edge e=pred.get(n); 532 532 res_graph.augment(original_edge.get(e), augment_value); 533 n=F. tail(e);533 n=F.source(e); 534 534 if (residual_capacity.get(e)==augment_value) 535 535 F.erase(e); … … 557 557 ResGWOutEdgeIt e=bfs; 558 558 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 559 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);559 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 560 560 } 561 561 ++bfs; … … 633 633 typename ErasingResGW::OutEdgeIt e=pred.get(n); 634 634 res_graph.augment(e, augment_value); 635 n=erasing_res_graph. tail(e);635 n=erasing_res_graph.source(e); 636 636 if (res_graph.resCap(e)==0) 637 637 erasing_res_graph.erase(e); … … 728 728 // AugOutEdgeIt e=bfs; 729 729 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 730 // Node v=res_graph. tail(e);731 // Node w=res_graph. head(e);730 // Node v=res_graph.source(e); 731 // Node w=res_graph.target(e); 732 732 // pred.set(w, e); 733 733 // if (res_graph.valid(pred.get(v))) { … … 736 736 // free.set(w, res_graph.free(e)); 737 737 // } 738 // n=res_graph. head(e);738 // n=res_graph.target(e); 739 739 // if (T->get(n) && (used.get(n)<1) ) { 740 740 // //Number u=0; … … 758 758 // AugEdge e=pred.get(n); 759 759 // res_graph.augment(e, augment_value); 760 // n=res_graph. tail(e);760 // n=res_graph.source(e); 761 761 // } 762 762 // used.set(n, 1); //mind2 vegen jav … … 799 799 // // AugOutEdgeIt e=bfs; 800 800 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 801 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);801 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 802 802 // // } 803 803 … … 821 821 // // //which are in some shortest paths 822 822 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 823 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));823 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 825 825 // // original_edge.update(); 826 826 // // original_edge.set(f, e); … … 874 874 // // typename MutableGraph::Edge e=pred.get(n); 875 875 // // res_graph.augment(original_edge.get(e), augment_value); 876 // // n=F. tail(e);876 // // n=F.source(e); 877 877 // // if (residual_capacity.get(e)==augment_value) 878 878 // // F.erase(e); … … 925 925 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 926 926 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 927 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);927 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 928 928 // } 929 929 // ++bfs; … … 1002 1002 // EAugEdge e=pred.get(n); 1003 1003 // res_graph.augment(e, augment_value); 1004 // n=res_graph. tail(e);1004 // n=res_graph.source(e); 1005 1005 // if (res_graph.free(e)==0) 1006 1006 // res_graph.erase(e); … … 1095 1095 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 1096 1096 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 1097 // // Node v=res_graph. tail(e);1098 // // Node w=res_graph. head(e);1097 // // Node v=res_graph.source(e); 1098 // // Node w=res_graph.target(e); 1099 1099 // // pred.set(w, e); 1100 1100 // // if (pred.get(v).valid()) { … … 1103 1103 // // free.set(w, e.free()); 1104 1104 // // } 1105 // // if (TMap.get(res_graph. head(e))) {1105 // // if (TMap.get(res_graph.target(e))) { 1106 1106 // // _augment=true; 1107 // // reached_t_node=res_graph. head(e);1107 // // reached_t_node=res_graph.target(e); 1108 1108 // // break; 1109 1109 // // } … … 1119 1119 // // AugEdge e=pred.get(n); 1120 1120 // // e.augment(augment_value); 1121 // // n=res_graph. tail(e);1121 // // n=res_graph.source(e); 1122 1122 // // } 1123 1123 // // } -
src/work/marci/experiment/edmonds_karp_demo.cc
r921 r986 105 105 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 106 106 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 107 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";107 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 116 116 // } 117 117 // std::cout<<std::endl; … … 136 136 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 137 137 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 138 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";138 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 147 147 // } 148 148 // std::cout<<std::endl; … … 167 167 while (max_flow_test.augmentOnBlockingFlow2()) { 168 168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 169 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";169 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 178 178 // } 179 179 // std::cout<<std::endl; … … 198 198 while (max_flow_test.augmentOnShortestPath()) { 199 199 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 200 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";200 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 209 209 // } 210 210 // std::cout<<std::endl; -
src/work/marci/experiment/edmonds_karp_demo_1.cc
r921 r986 105 105 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 106 106 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 107 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";107 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 116 116 // } 117 117 // std::cout<<std::endl; … … 136 136 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 137 137 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 138 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";138 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 147 147 // } 148 148 // std::cout<<std::endl; … … 167 167 while (max_flow_test.augmentOnBlockingFlow2()) { 168 168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 169 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";169 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 178 178 // } 179 179 // std::cout<<std::endl; … … 198 198 while (max_flow_test.augmentOnShortestPath()) { 199 199 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 200 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";200 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 209 209 // } 210 210 // std::cout<<std::endl; -
src/work/marci/experiment/graph_wrapper.h
r921 r986 97 97 It e; first(e, v); return e; } 98 98 99 Node head(const Edge& e) const { return graph->head(e); }100 Node tail(const Edge& e) const { return graph->tail(e); }99 Node target(const Edge& e) const { return graph->target(e); } 100 Node source(const Edge& e) const { return graph->source(e); } 101 101 102 102 template<typename I> bool valid(const I& i) const … … 115 115 116 116 Node addNode() const { return graph->addNode(); } 117 Edge addEdge(const Node& tail, const Node& head) const {118 return graph->addEdge( tail, head); }117 Edge addEdge(const Node& source, const Node& target) const { 118 return graph->addEdge(source, target); } 119 119 120 120 template<typename I> void erase(const I& i) const { graph->erase(i); } … … 246 246 It e; this->first(e, v); return e; } 247 247 248 Node head(const Edge& e) const { return gw.head(e); }249 Node tail(const Edge& e) const { return gw.tail(e); }248 Node target(const Edge& e) const { return gw.target(e); } 249 Node source(const Edge& e) const { return gw.source(e); } 250 250 251 251 template<typename I> bool valid(const I& i) const { return gw.valid(i); } … … 261 261 262 262 Node addNode() const { return gw.addNode(); } 263 Edge addEdge(const Node& tail, const Node& head) const {264 return gw.addEdge( tail, head); }263 Edge addEdge(const Node& source, const Node& target) const { 264 return gw.addEdge(source, target); } 265 265 266 266 template<typename I> void erase(const I& i) const { gw.erase(i); } … … 323 323 // It e; first(e, v); return e; } 324 324 325 // Node head(const Edge& e) const { return graph->tail(e); }326 // Node tail(const Edge& e) const { return graph->head(e); }325 // Node target(const Edge& e) const { return graph->source(e); } 326 // Node source(const Edge& e) const { return graph->target(e); } 327 327 328 328 // template<typename I> bool valid(const I& i) const … … 338 338 339 339 // Node addNode() const { return graph->addNode(); } 340 // Edge addEdge(const Node& tail, const Node& head) const {341 // return graph->addEdge( tail, head); }340 // Edge addEdge(const Node& source, const Node& target) const { 341 // return graph->addEdge(source, target); } 342 342 343 343 // int nodeNum() const { return graph->nodeNum(); } … … 404 404 // // It e; first(e, v); return e; } 405 405 406 // //Node head(const Edge& e) const { return graph->tail(e); }407 // //Node tail(const Edge& e) const { return graph->head(e); }406 // //Node target(const Edge& e) const { return graph->source(e); } 407 // //Node source(const Edge& e) const { return graph->target(e); } 408 408 409 409 // //template<typename I> bool valid(const I& i) const … … 419 419 420 420 // //Node addNode() const { return graph->addNode(); } 421 // //Edge addEdge(const Node& tail, const Node& head) const {422 // // return graph->addEdge( tail, head); }421 // //Edge addEdge(const Node& source, const Node& target) const { 422 // // return graph->addEdge(source, target); } 423 423 424 424 // //int nodeNum() const { return graph->nodeNum(); } … … 468 468 GraphWrapper<GraphWrapper>(_gw) { } 469 469 470 Node head(const Edge& e) const471 { return GraphWrapper<GraphWrapper>:: tail(e); }472 Node tail(const Edge& e) const473 { return GraphWrapper<GraphWrapper>:: head(e); }470 Node target(const Edge& e) const 471 { return GraphWrapper<GraphWrapper>::source(e); } 472 Node source(const Edge& e) const 473 { return GraphWrapper<GraphWrapper>::target(e); } 474 474 }; 475 475 … … 600 600 // OutEdgeIt& next(OutEdgeIt& e) const { 601 601 // if (e.out_or_in) { 602 // Node n=gw. tail(e.out);602 // Node n=gw.source(e.out); 603 603 // gw.next(e.out); 604 604 // if (!gw.valid(e.out)) { … … 613 613 614 614 // Node aNode(const OutEdgeIt& e) const { 615 // if (e.out_or_in) return gw. tail(e); else return gw.head(e); }615 // if (e.out_or_in) return gw.source(e); else return gw.target(e); } 616 616 // Node bNode(const OutEdgeIt& e) const { 617 // if (e.out_or_in) return gw. head(e); else return gw.tail(e); }617 // if (e.out_or_in) return gw.target(e); else return gw.source(e); } 618 618 619 619 // typedef OutEdgeIt InEdgeIt; … … 633 633 // It e; first(e, v); return e; } 634 634 635 // Node head(const Edge& e) const { return gw.head(e); }636 // Node tail(const Edge& e) const { return gw.tail(e); }635 // Node target(const Edge& e) const { return gw.target(e); } 636 // Node source(const Edge& e) const { return gw.source(e); } 637 637 638 638 // template<typename I> bool valid(const I& i) const … … 652 652 // Node addNode() const { return gw.addNode(); } 653 653 // // FIXME: ez igy nem jo, mert nem 654 // // Edge addEdge(const Node& tail, const Node& head) const {655 // // return graph->addEdge( tail, head); }654 // // Edge addEdge(const Node& source, const Node& target) const { 655 // // return graph->addEdge(source, target); } 656 656 657 657 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 799 799 OutEdgeIt& next(OutEdgeIt& e) const { 800 800 if (e.out_or_in) { 801 Node n=gw. tail(e.out);801 Node n=gw.source(e.out); 802 802 gw.next(e.out); 803 803 if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); } … … 809 809 810 810 EdgeIt& next(EdgeIt& e) const { 811 //NodeIt v= tail(e);811 //NodeIt v=source(e); 812 812 gw.next(e.out); 813 813 while (valid(e.v) && !gw.valid(e.out)) { … … 827 827 It e; first(e, v); return e; } 828 828 829 // Node head(const Edge& e) const { return gw.head(e); }830 // Node tail(const Edge& e) const { return gw.tail(e); }829 // Node target(const Edge& e) const { return gw.target(e); } 830 // Node source(const Edge& e) const { return gw.source(e); } 831 831 832 832 // template<typename I> bool valid(const I& i) const … … 842 842 843 843 Node aNode(const OutEdgeIt& e) const { 844 if (e.out_or_in) return gw. tail(e); else return gw.head(e); }844 if (e.out_or_in) return gw.source(e); else return gw.target(e); } 845 845 Node bNode(const OutEdgeIt& e) const { 846 if (e.out_or_in) return gw. head(e); else return gw.tail(e); }846 if (e.out_or_in) return gw.target(e); else return gw.source(e); } 847 847 848 848 // Node addNode() const { return gw.addNode(); } 849 849 850 850 // FIXME: ez igy nem jo, mert nem 851 // Edge addEdge(const Node& tail, const Node& head) const {852 // return graph->addEdge( tail, head); }851 // Edge addEdge(const Node& source, const Node& target) const { 852 // return graph->addEdge(source, target); } 853 853 854 854 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 914 914 // It e; first(e, v); return e; } 915 915 916 // Node head(const Edge& e) const { return graph->head(e); }917 // Node tail(const Edge& e) const { return graph->tail(e); }916 // Node target(const Edge& e) const { return graph->target(e); } 917 // Node source(const Edge& e) const { return graph->source(e); } 918 918 919 919 // template<typename I> Node aNode(const I& e) const { … … 929 929 930 930 // Node addNode() { return graph->addNode(); } 931 // Edge addEdge(const Node& tail, const Node& head) {932 // return graph->addEdge( tail, head); }931 // Edge addEdge(const Node& source, const Node& target) { 932 // return graph->addEdge(source, target); } 933 933 934 934 // template<typename I> void erase(const I& i) { graph->erase(i); } … … 1181 1181 } 1182 1182 1183 Node tail(Edge e) const {1183 Node source(Edge e) const { 1184 1184 return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); } 1185 Node head(Edge e) const {1185 Node target(Edge e) const { 1186 1186 return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); } 1187 1187 … … 1312 1312 OutEdgeIt f=e; 1313 1313 this->next(f); 1314 first_out_edges->set(this-> tail(e), f);1314 first_out_edges->set(this->source(e), f); 1315 1315 } 1316 1316 }; … … 1382 1382 // It e; first(e, v); return e; } 1383 1383 1384 // //Node head(const Edge& e) const { return gw.head(e); }1385 // //Node tail(const Edge& e) const { return gw.tail(e); }1384 // //Node target(const Edge& e) const { return gw.target(e); } 1385 // //Node source(const Edge& e) const { return gw.source(e); } 1386 1386 1387 1387 // //template<typename I> bool valid(const I& i) const … … 1397 1397 1398 1398 // //Node addNode() const { return gw.addNode(); } 1399 // //Edge addEdge(const Node& tail, const Node& head) const {1400 // // return gw.addEdge( tail, head); }1399 // //Edge addEdge(const Node& source, const Node& target) const { 1400 // // return gw.addEdge(source, target); } 1401 1401 1402 1402 // //void erase(const OutEdgeIt& e) { 1403 // // first_out_edge(this-> tail(e))=e;1403 // // first_out_edge(this->source(e))=e; 1404 1404 // //} 1405 1405 // void erase(const Edge& e) { 1406 1406 // OutEdgeIt f(e); 1407 1407 // next(f); 1408 // first_out_edges.set(this-> tail(e), f);1408 // first_out_edges.set(this->source(e), f); 1409 1409 // } 1410 1410 // //template<typename I> void erase(const I& i) const { gw.erase(i); } … … 1460 1460 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 1461 1461 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n); 1462 // while (valid(e) && (dist.get( tail(e))/*+1!=*/>=dist.get(head(e))))1462 // while (valid(e) && (dist.get(source(e))/*+1!=*/>=dist.get(target(e)))) 1463 1463 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 1464 1464 // return e; … … 1471 1471 // OutEdgeIt& next(OutEdgeIt& e) const { 1472 1472 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 1473 // while (valid(e) && (dist.get( tail(e))/*+1!*/>=dist.get(head(e))))1473 // while (valid(e) && (dist.get(source(e))/*+1!*/>=dist.get(target(e)))) 1474 1474 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 1475 1475 // return e; … … 1483 1483 // OutEdgeIt f(e); 1484 1484 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); 1485 // while (valid(f) && (dist.get( tail(f))/*+1!=*/>=dist.get(head(f))))1485 // while (valid(f) && (dist.get(source(f))/*+1!=*/>=dist.get(target(f)))) 1486 1486 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); 1487 // first_out_edges.set(this-> tail(e), f);1487 // first_out_edges.set(this->source(e), f); 1488 1488 // } 1489 1489 … … 1508 1508 // It e; first(e, v); return e; } 1509 1509 1510 // //Node head(const Edge& e) const { return gw.head(e); }1511 // //Node tail(const Edge& e) const { return gw.tail(e); }1510 // //Node target(const Edge& e) const { return gw.target(e); } 1511 // //Node source(const Edge& e) const { return gw.source(e); } 1512 1512 1513 1513 // //template<typename I> bool valid(const I& i) const … … 1526 1526 1527 1527 // //Node addNode() const { return gw.addNode(); } 1528 // //Edge addEdge(const Node& tail, const Node& head) const {1529 // // return gw.addEdge( tail, head); }1528 // //Edge addEdge(const Node& source, const Node& target) const { 1529 // // return gw.addEdge(source, target); } 1530 1530 1531 1531 // //template<typename I> void erase(const I& i) const { gw.erase(i); } … … 1670 1670 // It e; first(e, v); return e; } 1671 1671 1672 // Node head(const Edge& e) const { return gw.head(e); }1673 // Node tail(const Edge& e) const { return gw.tail(e); }1672 // Node target(const Edge& e) const { return gw.target(e); } 1673 // Node source(const Edge& e) const { return gw.source(e); } 1674 1674 1675 1675 // template<typename I> Node aNode(const I& e) const { … … 1685 1685 1686 1686 // Node addNode() { return gw.addNode(); } 1687 // Edge addEdge(const Node& tail, const Node& head) {1688 // return gw.addEdge( tail, head); }1687 // Edge addEdge(const Node& source, const Node& target) { 1688 // return gw.addEdge(source, target); } 1689 1689 1690 1690 // template<typename I> void erase(const I& i) { gw.erase(i); } -
src/work/marci/experiment/graph_wrapper_1.h
r921 r986 91 91 It e; this->first(e, v); return e; } 92 92 93 Node head(const Edge& e) const { return graph->head(e); }94 Node tail(const Edge& e) const { return graph->tail(e); }93 Node target(const Edge& e) const { return graph->target(e); } 94 Node source(const Edge& e) const { return graph->source(e); } 95 95 96 96 template<typename I> bool valid(const I& i) const { … … 109 109 110 110 Node addNode() const { return graph->addNode(); } 111 Edge addEdge(const Node& tail, const Node& head) const {112 return graph->addEdge( tail, head); }111 Edge addEdge(const Node& source, const Node& target) const { 112 return graph->addEdge(source, target); } 113 113 114 114 template<typename I> void erase(const I& i) const { graph->erase(i); } … … 236 236 It e; this->first(e, v); return e; } 237 237 238 Node head(const Edge& e) const { return graph->head(e); }239 Node tail(const Edge& e) const { return graph->tail(e); }238 Node target(const Edge& e) const { return graph->target(e); } 239 Node source(const Edge& e) const { return graph->source(e); } 240 240 241 241 template<typename I> bool valid(const I& i) const { … … 254 254 255 255 Node addNode() const { return graph->addNode(); } 256 Edge addEdge(const Node& tail, const Node& head) const {257 return graph->addEdge( tail, head); }256 Edge addEdge(const Node& source, const Node& target) const { 257 return graph->addEdge(source, target); } 258 258 259 259 template<typename I> void erase(const I& i) const { graph->erase(i); } … … 317 317 // It e; first(e, v); return e; } 318 318 319 // Node head(const Edge& e) const { return graph->tail(e); }320 // Node tail(const Edge& e) const { return graph->head(e); }319 // Node target(const Edge& e) const { return graph->source(e); } 320 // Node source(const Edge& e) const { return graph->target(e); } 321 321 322 322 // template<typename I> bool valid(const I& i) const … … 332 332 333 333 // Node addNode() const { return graph->addNode(); } 334 // Edge addEdge(const Node& tail, const Node& head) const {335 // return graph->addEdge( tail, head); }334 // Edge addEdge(const Node& source, const Node& target) const { 335 // return graph->addEdge(source, target); } 336 336 337 337 // int nodeNum() const { return graph->nodeNum(); } … … 379 379 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 380 380 381 Node head(const Edge& e) const382 { return GraphWrapper<Graph>:: tail(e); }383 Node tail(const Edge& e) const384 { return GraphWrapper<Graph>:: head(e); }381 Node target(const Edge& e) const 382 { return GraphWrapper<Graph>::source(e); } 383 Node source(const Edge& e) const 384 { return GraphWrapper<Graph>::target(e); } 385 385 }; 386 386 … … 512 512 // OutEdgeIt& next(OutEdgeIt& e) const { 513 513 // if (e.out_or_in) { 514 // Node n=gw. tail(e.out);514 // Node n=gw.source(e.out); 515 515 // gw.next(e.out); 516 516 // if (!gw.valid(e.out)) { … … 525 525 526 526 // Node aNode(const OutEdgeIt& e) const { 527 // if (e.out_or_in) return gw. tail(e); else return gw.head(e); }527 // if (e.out_or_in) return gw.source(e); else return gw.target(e); } 528 528 // Node bNode(const OutEdgeIt& e) const { 529 // if (e.out_or_in) return gw. head(e); else return gw.tail(e); }529 // if (e.out_or_in) return gw.target(e); else return gw.source(e); } 530 530 531 531 // typedef OutEdgeIt InEdgeIt; … … 545 545 // It e; first(e, v); return e; } 546 546 547 // Node head(const Edge& e) const { return gw.head(e); }548 // Node tail(const Edge& e) const { return gw.tail(e); }547 // Node target(const Edge& e) const { return gw.target(e); } 548 // Node source(const Edge& e) const { return gw.source(e); } 549 549 550 550 // template<typename I> bool valid(const I& i) const … … 564 564 // Node addNode() const { return gw.addNode(); } 565 565 // // FIXME: ez igy nem jo, mert nem 566 // // Edge addEdge(const Node& tail, const Node& head) const {567 // // return graph->addEdge( tail, head); }566 // // Edge addEdge(const Node& source, const Node& target) const { 567 // // return graph->addEdge(source, target); } 568 568 569 569 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 693 693 OutEdgeIt& next(OutEdgeIt& e) const { 694 694 if (e.out_or_in) { 695 Node n=graph-> tail(e.out);695 Node n=graph->source(e.out); 696 696 graph->next(e.out); 697 697 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } … … 703 703 704 704 EdgeIt& next(EdgeIt& e) const { 705 //NodeIt v= tail(e);705 //NodeIt v=source(e); 706 706 graph->next(e.out); 707 707 while (valid(e.v) && !graph->valid(e.out)) { … … 721 721 It e; this->first(e, v); return e; } 722 722 723 // Node head(const Edge& e) const { return gw.head(e); }724 // Node tail(const Edge& e) const { return gw.tail(e); }723 // Node target(const Edge& e) const { return gw.target(e); } 724 // Node source(const Edge& e) const { return gw.source(e); } 725 725 726 726 // template<typename I> bool valid(const I& i) const … … 736 736 737 737 Node aNode(const OutEdgeIt& e) const { 738 if (e.out_or_in) return graph-> tail(e); else return graph->head(e); }738 if (e.out_or_in) return graph->source(e); else return graph->target(e); } 739 739 Node bNode(const OutEdgeIt& e) const { 740 if (e.out_or_in) return graph-> head(e); else return graph->tail(e); }740 if (e.out_or_in) return graph->target(e); else return graph->source(e); } 741 741 742 742 // Node addNode() const { return gw.addNode(); } 743 743 744 744 // FIXME: ez igy nem jo, mert nem 745 // Edge addEdge(const Node& tail, const Node& head) const {746 // return graph->addEdge( tail, head); }745 // Edge addEdge(const Node& source, const Node& target) const { 746 // return graph->addEdge(source, target); } 747 747 748 748 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 808 808 // It e; first(e, v); return e; } 809 809 810 // Node head(const Edge& e) const { return graph->head(e); }811 // Node tail(const Edge& e) const { return graph->tail(e); }810 // Node target(const Edge& e) const { return graph->target(e); } 811 // Node source(const Edge& e) const { return graph->source(e); } 812 812 813 813 // template<typename I> Node aNode(const I& e) const { … … 823 823 824 824 // Node addNode() { return graph->addNode(); } 825 // Edge addEdge(const Node& tail, const Node& head) {826 // return graph->addEdge( tail, head); }825 // Edge addEdge(const Node& source, const Node& target) { 826 // return graph->addEdge(source, target); } 827 827 828 828 // template<typename I> void erase(const I& i) { graph->erase(i); } … … 1064 1064 } 1065 1065 1066 Node tail(Edge e) const {1066 Node source(Edge e) const { 1067 1067 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1068 Node head(Edge e) const {1068 Node target(Edge e) const { 1069 1069 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1070 1070 … … 1193 1193 OutEdgeIt f=e; 1194 1194 this->next(f); 1195 first_out_edges->set(this-> tail(e), f);1195 first_out_edges->set(this->source(e), f); 1196 1196 } 1197 1197 }; … … 1311 1311 // It e; first(e, v); return e; } 1312 1312 1313 // Node head(const Edge& e) const { return gw.head(e); }1314 // Node tail(const Edge& e) const { return gw.tail(e); }1313 // Node target(const Edge& e) const { return gw.target(e); } 1314 // Node source(const Edge& e) const { return gw.source(e); } 1315 1315 1316 1316 // template<typename I> Node aNode(const I& e) const { … … 1326 1326 1327 1327 // Node addNode() { return gw.addNode(); } 1328 // Edge addEdge(const Node& tail, const Node& head) {1329 // return gw.addEdge( tail, head); }1328 // Edge addEdge(const Node& source, const Node& target) { 1329 // return gw.addEdge(source, target); } 1330 1330 1331 1331 // template<typename I> void erase(const I& i) { gw.erase(i); } -
src/work/marci/experiment/graph_wrapper_st_ostream_op.h
r921 r986 167 167 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } 168 168 169 Node tail(const Edge& e) const {170 return Node(graph-> tail(static_cast<typename Graph::Edge>(e))); }171 Node head(const Edge& e) const {172 return Node(graph-> head(static_cast<typename Graph::Edge>(e))); }169 Node source(const Edge& e) const { 170 return Node(graph->source(static_cast<typename Graph::Edge>(e))); } 171 Node target(const Edge& e) const { 172 return Node(graph->target(static_cast<typename Graph::Edge>(e))); } 173 173 174 174 bool valid(const Node& n) const { … … 186 186 187 187 Node addNode() const { return Node(graph->addNode()); } 188 Edge addEdge(const Node& tail, const Node& head) const {189 return Edge(graph->addEdge( tail, head)); }188 Edge addEdge(const Node& source, const Node& target) const { 189 return Edge(graph->addEdge(source, target)); } 190 190 191 191 void erase(const Node& i) const { graph->erase(i); } … … 273 273 return Node(this->graph->bNode(e.e)); } 274 274 275 Node tail(const Edge& e) const {276 return GraphWrapper<Graph>:: head(e); }277 Node head(const Edge& e) const {278 return GraphWrapper<Graph>:: tail(e); }275 Node source(const Edge& e) const { 276 return GraphWrapper<Graph>::target(e); } 277 Node target(const Edge& e) const { 278 return GraphWrapper<Graph>::source(e); } 279 279 280 280 }; … … 490 490 OutEdgeIt& next(OutEdgeIt& e) const { 491 491 if (e.out_or_in) { 492 typename Graph::Node n=this->graph-> tail(e.out);492 typename Graph::Node n=this->graph->source(e.out); 493 493 this->graph->next(e.out); 494 494 if (!this->graph->valid(e.out)) { … … 507 507 508 508 Node aNode(const OutEdgeIt& e) const { 509 if (e.out_or_in) return this->graph-> tail(e); else510 return this->graph-> head(e); }509 if (e.out_or_in) return this->graph->source(e); else 510 return this->graph->target(e); } 511 511 Node bNode(const OutEdgeIt& e) const { 512 if (e.out_or_in) return this->graph-> head(e); else513 return this->graph-> tail(e); }512 if (e.out_or_in) return this->graph->target(e); else 513 return this->graph->source(e); } 514 514 }; 515 515 … … 725 725 } 726 726 727 Node tail(Edge e) const {728 return ((e.forward) ? this->graph-> tail(e) : this->graph->head(e)); }729 Node head(Edge e) const {730 return ((e.forward) ? this->graph-> head(e) : this->graph->tail(e)); }727 Node source(Edge e) const { 728 return ((e.forward) ? this->graph->source(e) : this->graph->target(e)); } 729 Node target(Edge e) const { 730 return ((e.forward) ? this->graph->target(e) : this->graph->source(e)); } 731 731 732 732 Node aNode(OutEdgeIt e) const { … … 914 914 OutEdgeIt f=e; 915 915 this->next(f); 916 first_out_edges->set(this-> tail(e), f.e);916 first_out_edges->set(this->source(e), f.e); 917 917 } 918 918 }; … … 1042 1042 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 1043 1043 1044 Node tail(const Edge& e) {1045 if (!(*(this->s_false_t_true_map))[this->graph-> tail(e)])1046 return Node(this->graph-> tail(e));1044 Node source(const Edge& e) { 1045 if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 1046 return Node(this->graph->source(e)); 1047 1047 else 1048 return Node(this->graph-> head(e));1049 } 1050 Node head(const Edge& e) {1051 if (!(*(this->s_false_t_true_map))[this->graph-> tail(e)])1052 return Node(this->graph-> head(e));1048 return Node(this->graph->target(e)); 1049 } 1050 Node target(const Edge& e) { 1051 if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 1052 return Node(this->graph->target(e)); 1053 1053 else 1054 return Node(this->graph-> tail(e));1054 return Node(this->graph->source(e)); 1055 1055 } 1056 1056 … … 1470 1470 } 1471 1471 1472 Node tail(const Edge& e) const {1472 Node source(const Edge& e) const { 1473 1473 switch (e.spec) { 1474 1474 case 0: 1475 return Node(this->graph-> tail(e));1475 return Node(this->graph->source(e)); 1476 1476 break; 1477 1477 case 1: … … 1484 1484 } 1485 1485 } 1486 Node head(const Edge& e) const {1486 Node target(const Edge& e) const { 1487 1487 switch (e.spec) { 1488 1488 case 0: 1489 return Node(this->graph-> head(e));1489 return Node(this->graph->target(e)); 1490 1490 break; 1491 1491 case 1: … … 1507 1507 } 1508 1508 1509 Node aNode(const OutEdgeIt& e) const { return tail(e); }1510 Node aNode(const InEdgeIt& e) const { return head(e); }1511 Node bNode(const OutEdgeIt& e) const { return head(e); }1512 Node bNode(const InEdgeIt& e) const { return tail(e); }1509 Node aNode(const OutEdgeIt& e) const { return source(e); } 1510 Node aNode(const InEdgeIt& e) const { return target(e); } 1511 Node bNode(const OutEdgeIt& e) const { return target(e); } 1512 Node bNode(const InEdgeIt& e) const { return source(e); } 1513 1513 1514 1514 void addNode() const { } … … 1516 1516 1517 1517 // Node addNode() const { return Node(this->graph->addNode()); } 1518 // Edge addEdge(const Node& tail, const Node& head) const {1519 // return Edge(this->graph->addEdge( tail, head)); }1518 // Edge addEdge(const Node& source, const Node& target) const { 1519 // return Edge(this->graph->addEdge(source, target)); } 1520 1520 1521 1521 // void erase(const Node& i) const { this->graph->erase(i); } -
src/work/marci/experiment/iterator_bfs_demo.cc
r921 r986 23 23 string get(typename Graph::Edge e) const { 24 24 return 25 (node_name_map.get(graph. tail(e))+"->"+node_name_map.get(graph.head(e)));25 (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); 26 26 } 27 27 }; -
src/work/marci/experiment/iterator_bfs_demo_1.cc
r921 r986 23 23 string get(typename Graph::Edge e) const { 24 24 return 25 (node_name_map.get(graph. tail(e))+"->"+node_name_map.get(graph.head(e)));25 (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); 26 26 } 27 27 }; -
src/work/marci/experiment/list_graph.h
r921 r986 123 123 //ListGraph* G; 124 124 int id; 125 node_item* _ tail;126 node_item* _ head;125 node_item* _source; 126 node_item* _target; 127 127 edge_item* _next_out; 128 128 edge_item* _prev_out; … … 150 150 } 151 151 152 edge_item* _add_edge(node_item* _ tail, node_item* _head) {152 edge_item* _add_edge(node_item* _source, node_item* _target) { 153 153 edge_item* e=new edge_item; 154 154 e->id=edge_id++; 155 e->_ tail=_tail;156 e->_ head=_head;157 158 e->_prev_out=_ tail->_last_out_edge;159 if (_ tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;160 _ tail->_last_out_edge=e;161 if (!_ tail->_first_out_edge) _tail->_first_out_edge=e;155 e->_source=_source; 156 e->_target=_target; 157 158 e->_prev_out=_source->_last_out_edge; 159 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; 160 _source->_last_out_edge=e; 161 if (!_source->_first_out_edge) _source->_first_out_edge=e; 162 162 e->_next_out=0; 163 163 164 e->_prev_in=_ head->_last_in_edge;165 if (_ head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;166 _ head->_last_in_edge=e;167 if (!_ head->_first_in_edge) { _head->_first_in_edge=e; }164 e->_prev_in=_target->_last_in_edge; 165 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; 166 _target->_last_in_edge=e; 167 if (!_target->_first_in_edge) { _target->_first_in_edge=e; } 168 168 e->_next_in=0; 169 169 … … 185 185 void _delete_edge(edge_item* e) { 186 186 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 187 (e->_ tail)->_last_out_edge=e->_prev_out;187 (e->_source)->_last_out_edge=e->_prev_out; 188 188 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 189 (e->_ tail)->_first_out_edge=e->_next_out;189 (e->_source)->_first_out_edge=e->_next_out; 190 190 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 191 (e->_ head)->_last_in_edge=e->_prev_in;191 (e->_target)->_last_in_edge=e->_prev_in; 192 192 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 193 (e->_ head)->_first_in_edge=e->_next_in;193 (e->_target)->_first_in_edge=e->_next_in; 194 194 195 195 delete e; … … 197 197 } 198 198 199 void _set_ tail(edge_item* e, node_item* _tail) {199 void _set_source(edge_item* e, node_item* _source) { 200 200 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 201 (e->_ tail)->_last_out_edge=e->_prev_out;201 (e->_source)->_last_out_edge=e->_prev_out; 202 202 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 203 (e->_ tail)->_first_out_edge=e->_next_out;204 205 e->_ tail=_tail;206 207 e->_prev_out=_ tail->_last_out_edge;208 if (_ tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;209 _ tail->_last_out_edge=e;210 if (!_ tail->_first_out_edge) _tail->_first_out_edge=e;203 (e->_source)->_first_out_edge=e->_next_out; 204 205 e->_source=_source; 206 207 e->_prev_out=_source->_last_out_edge; 208 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; 209 _source->_last_out_edge=e; 210 if (!_source->_first_out_edge) _source->_first_out_edge=e; 211 211 e->_next_out=0; 212 212 } 213 213 214 void _set_ head(edge_item* e, node_item* _head) {214 void _set_target(edge_item* e, node_item* _target) { 215 215 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 216 (e->_ head)->_last_in_edge=e->_prev_in;216 (e->_target)->_last_in_edge=e->_prev_in; 217 217 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 218 (e->_ head)->_first_in_edge=e->_next_in;219 220 e->_ head=_head;221 222 e->_prev_in=_ head->_last_in_edge;223 if (_ head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;224 _ head->_last_in_edge=e;225 if (!_ head->_first_in_edge) { _head->_first_in_edge=e; }218 (e->_target)->_first_in_edge=e->_next_in; 219 220 e->_target=_target; 221 222 e->_prev_in=_target->_last_in_edge; 223 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; 224 _target->_last_in_edge=e; 225 if (!_target->_first_in_edge) { _target->_first_in_edge=e; } 226 226 e->_next_in=0; 227 227 } … … 248 248 //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); } 249 249 //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); } 250 Node tail(Edge e) const { return e.tailNode(); }251 Node head(Edge e) const { return e.headNode(); }250 Node source(Edge e) const { return e.sourceNode(); } 251 Node target(Edge e) const { return e.targetNode(); } 252 252 253 253 Node aNode(const OutEdgeIt& e) const { return e.aNode(); } … … 278 278 SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const { 279 279 e=SymEdgeIt(*this, v); return e; } 280 //void get Tail(Node& n, const Edge& e) const { n=tail(e); }281 //void get Head(Node& n, const Edge& e) const { n=head(e); }280 //void getSource(Node& n, const Edge& e) const { n=source(e); } 281 //void getTarget(Node& n, const Edge& e) const { n=target(e); } 282 282 283 283 //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); } … … 346 346 } 347 347 348 void set Tail(Edge e, Node tail) {349 _set_ tail(e.edge, tail.node);350 } 351 352 void set Head(Edge e, Node head) {353 _set_ head(e.edge, head.node);348 void setSource(Edge e, Node source) { 349 _set_source(e.edge, source.node); 350 } 351 352 void setTarget(Edge e, Node target) { 353 _set_target(e.edge, target.node); 354 354 } 355 355 … … 360 360 } 361 361 friend std::ostream& operator<<(std::ostream& os, const Edge& i) { 362 os << "(" << i.edge->_ tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";362 os << "(" << i.edge->_source->id << "--" << i.edge->id << "->" << i.edge->_target->id << ")"; 363 363 return os; 364 364 } … … 427 427 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; } 428 428 protected: 429 Node tailNode() const { return Node(edge->_tail); }430 Node headNode() const { return Node(edge->_head); }429 Node sourceNode() const { return Node(edge->_source); } 430 Node targetNode() const { return Node(edge->_target); } 431 431 public: 432 432 friend std::ostream& operator<<(std::ostream& os, const Edge& i); … … 448 448 EdgeIt(edge_item* _e) : Edge(_e) { } 449 449 EdgeIt& operator++() { 450 node_item* v=edge->_ tail;450 node_item* v=edge->_source; 451 451 edge=edge->_next_out; 452 452 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } … … 468 468 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } 469 469 protected: 470 Node aNode() const { return Node(edge->_ tail); }471 Node bNode() const { return Node(edge->_ head); }470 Node aNode() const { return Node(edge->_source); } 471 Node bNode() const { return Node(edge->_target); } 472 472 }; 473 473 … … 485 485 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } 486 486 protected: 487 Node aNode() const { return Node(edge->_ head); }488 Node bNode() const { return Node(edge->_ tail); }487 Node aNode() const { return Node(edge->_target); } 488 Node bNode() const { return Node(edge->_source); } 489 489 }; 490 490 … … 511 511 SymEdgeIt& operator++() { 512 512 if (out_or_in) { 513 node_item* v=edge->_ tail;513 node_item* v=edge->_source; 514 514 edge=edge->_next_out; 515 515 if (!edge) { out_or_in=0; edge=v->_first_in_edge; } … … 521 521 protected: 522 522 Node aNode() const { 523 return (out_or_in) ? Node(edge->_ tail) : Node(edge->_head); }523 return (out_or_in) ? Node(edge->_source) : Node(edge->_target); } 524 524 Node bNode() const { 525 return (out_or_in) ? Node(edge->_ head) : Node(edge->_tail); }525 return (out_or_in) ? Node(edge->_target) : Node(edge->_source); } 526 526 }; 527 527 -
src/work/marci/graph_concept.h
r921 r986 104 104 105 105 106 /// Gives back the headnode of an edge.107 Node head(const Edge&) const { return INVALID; }108 /// Gives back the tailnode of an edge.109 Node tail(const Edge&) const { return INVALID; }106 /// Gives back the target node of an edge. 107 Node target(const Edge&) const { return INVALID; } 108 /// Gives back the source node of an edge. 109 Node source(const Edge&) const { return INVALID; } 110 110 111 111 // Node aNode(SymEdgeIt) const {} … … 143 143 /// \brief Add a new edge to the graph. 144 144 /// 145 /// Add a new edge to the graph with tail node \c tail146 /// and head node \c head.145 /// Add a new edge to the graph with source node \c source 146 /// and target node \c target. 147 147 /// \return the new edge. 148 Edge addEdge(const Node& tail, const Node& head) { return INVALID; }148 Edge addEdge(const Node& source, const Node& target) { return INVALID; } 149 149 150 150 /// \brief Resets the graph. -
src/work/marci/iterator_bfs_demo.cc
r921 r986 24 24 string operator[](typename Graph::Edge e) const { 25 25 return 26 (node_name_map[graph. tail(e)]+"->"+node_name_map[graph.head(e)]);26 (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]); 27 27 } 28 28 }; … … 96 96 if (Graph::Edge(bfs)!=INVALID) { 97 97 cout << edge_name[bfs] << /*endl*/", " << 98 node_name[G. tail(bfs)] <<99 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 100 node_name[G. head(bfs)] <<98 node_name[G.source(bfs)] << 99 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 100 node_name[G.target(bfs)] << 101 101 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 102 102 ": is not newly reached."); 103 103 } else { 104 104 cout << "invalid" << /*endl*/", " << 105 node_name[bfs. tail()] <<105 node_name[bfs.source()] << 106 106 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 107 107 … … 130 130 if (Graph::Edge(dfs)!=INVALID) { 131 131 cout << edge_name[dfs] << /*endl*/", " << 132 node_name[G. tail(dfs)] <<133 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 134 node_name[G. head(dfs)] <<132 node_name[G.source(dfs)] << 133 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 134 node_name[G.target(dfs)] << 135 135 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 136 136 ": is not newly reached."); 137 137 } else { 138 138 cout << "invalid" << /*endl*/", " << 139 node_name[dfs. tail()] <<139 node_name[dfs.source()] << 140 140 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 141 141 … … 172 172 if (GW::Edge(bfs)!=INVALID) { 173 173 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 174 node_name[gw. tail(bfs)] <<175 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 176 node_name[gw. head(bfs)] <<174 node_name[gw.source(bfs)] << 175 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 176 node_name[gw.target(bfs)] << 177 177 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 178 178 ": is not newly reached."); 179 179 } else { 180 180 cout << "invalid" << /*endl*/", " << 181 node_name[bfs. tail()] <<181 node_name[bfs.source()] << 182 182 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 183 183 … … 206 206 if (GW::Edge(dfs)!=INVALID) { 207 207 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 208 node_name[gw. tail(dfs)] <<209 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 210 node_name[gw. head(dfs)] <<208 node_name[gw.source(dfs)] << 209 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 210 node_name[gw.target(dfs)] << 211 211 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 212 212 ": is not newly reached."); 213 213 } else { 214 214 cout << "invalid" << /*endl*/", " << 215 node_name[dfs. tail()] <<215 node_name[dfs.source()] << 216 216 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 217 217 … … 311 311 cout << "bfs and dfs iterator demo on the bidirected graph" << endl; 312 312 // for(GW::EdgeIt e(gw); e!=INVALID; ++e) { 313 // cout << node_name[gw. tail(e)] << "->" << node_name[gw.head(e)] << " ";313 // cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " "; 314 314 // } 315 315 for(GW::NodeIt n(gw); n!=INVALID; ++n) { … … 335 335 if (GW::Edge(bfs)!=INVALID) { 336 336 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 337 node_name[gw. tail(bfs)] <<338 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 339 node_name[gw. head(bfs)] <<337 node_name[gw.source(bfs)] << 338 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 339 node_name[gw.target(bfs)] << 340 340 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 341 341 ": is not newly reached."); 342 342 } else { 343 343 cout << "invalid" << /*endl*/", " << 344 node_name[bfs. tail()] <<344 node_name[bfs.source()] << 345 345 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 346 346 … … 369 369 if (GW::Edge(dfs)!=INVALID) { 370 370 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 371 node_name[gw. tail(dfs)] <<372 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 373 node_name[gw. head(dfs)] <<371 node_name[gw.source(dfs)] << 372 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 373 node_name[gw.target(dfs)] << 374 374 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 375 375 ": is not newly reached."); 376 376 } else { 377 377 cout << "invalid" << /*endl*/", " << 378 node_name[dfs. tail()] <<378 node_name[dfs.source()] << 379 379 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 380 380 -
src/work/marci/leda/bipartite_matching_comparison.cc
r921 r986 130 130 131 131 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) 132 hg.addEdge(b_s_nodes[bgw. tail(e)], b_t_nodes[bgw.head(e)]);132 hg.addEdge(b_s_nodes[bgw.source(e)], b_t_nodes[bgw.target(e)]); 133 133 134 134 ConstMap<SageGraph::Edge, int> cm(1); -
src/work/marci/leda/leda_graph_wrapper.h
r921 r986 214 214 // } 215 215 216 ///Gives back the headnode of an edge.217 Node head(Edge e) const {216 ///Gives back the target node of an edge. 217 Node target(Edge e) const { 218 218 return Node(l_graph->target(e.l_e)); 219 219 } 220 ///Gives back the tailnode of an edge.221 Node tail(Edge e) const {220 ///Gives back the source node of an edge. 221 Node source(Edge e) const { 222 222 return Node(l_graph->source(e.l_e)); 223 223 } 224 224 225 Node aNode(InEdgeIt e) const { return head(e); }226 Node aNode(OutEdgeIt e) const { return tail(e); }225 Node aNode(InEdgeIt e) const { return target(e); } 226 Node aNode(OutEdgeIt e) const { return source(e); } 227 227 // Node aNode(SymEdgeIt) const {} 228 228 229 Node bNode(InEdgeIt e) const { return tail(e); }230 Node bNode(OutEdgeIt e) const { return head(e); }229 Node bNode(InEdgeIt e) const { return source(e); } 230 Node bNode(OutEdgeIt e) const { return target(e); } 231 231 // Node bNode(SymEdgeIt) const {} 232 232 … … 245 245 246 246 Node addNode() const { return Node(l_graph->new_node()); } 247 Edge addEdge(Node tail, Node head) const {248 return Edge(l_graph->new_edge( tail.l_n, head.l_n));247 Edge addEdge(Node source, Node target) const { 248 return Edge(l_graph->new_edge(source.l_n, target.l_n)); 249 249 } 250 250 -
src/work/marci/leda/max_bipartite_matching_demo.cc
r921 r986 104 104 // cout << "out edges: "; 105 105 // for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 106 // cout << G.id(G. tail(e)) << "->" << G.id(G.head(e)) << " ";106 // cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << " "; 107 107 // cout << "in edges: "; 108 108 // for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 109 // cout << G.id(G. tail(e)) << "->" << G.id(G.head(e)) << " ";109 // cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << " "; 110 110 // cout << endl; 111 111 // } … … 124 124 while (max_flow_test.augmentOnShortestPath()) { 125 125 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 126 // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";126 // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 127 127 // std::cout<<std::endl; 128 128 ++i; … … 132 132 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 133 133 // if (flow.get(e)) 134 // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";134 // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 135 135 // std::cout<<std::endl; 136 136 // std::cout << "edges which are not in this maximum matching: "<< std::endl; 137 137 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 138 138 // if (!flow.get(e)) 139 // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";139 // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 140 140 // std::cout<<std::endl; 141 141 … … 157 157 // while (max_flow_test.augmentOnBlockingFlow2()) { 158 158 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 159 // // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";159 // // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 160 160 // // std::cout<<std::endl; 161 161 // ++i; … … 165 165 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 166 166 // // if (flow.get(e)) 167 // // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";167 // // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 168 168 // // std::cout<<std::endl; 169 169 // // std::cout << "edges which are not in this maximum matching: "<< std::endl; 170 170 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 171 171 // // if (!flow.get(e)) 172 // // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";172 // // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 173 173 // // std::cout<<std::endl; 174 174 … … 199 199 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 200 200 // if (flow.get(e)) 201 // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";201 // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 202 202 // std::cout<<std::endl; 203 203 // std::cout << "edges which are not in this maximum matching: "<< std::endl; 204 204 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 205 205 // if (!flow.get(e)) 206 // std::cout << G.id(G. tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";206 // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; 207 207 // std::cout<<std::endl; 208 208 -
src/work/marci/leda_bfs_dfs.cc
r921 r986 26 26 string get(typename Graph::Edge e) const { 27 27 return 28 (node_name_map.get(graph. tail(e))+"->"+node_name_map.get(graph.head(e)));28 (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); 29 29 } 30 30 }; -
src/work/marci/leda_graph_demo.cc
r921 r986 39 39 // cout << "out edges: "; 40 40 // for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 41 // cout << G.id(G. tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " ";41 // cout << G.id(G.source(e)) << "-" << cap.get(e) << "->" << G.id(G.target(e)) << " "; 42 42 // cout << "in edges: "; 43 43 // for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 44 // cout << G.id(G. tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " ";44 // cout << G.id(G.source(e)) << "-" << cap.get(e) << "->" << G.id(G.target(e)) << " "; 45 45 // cout << endl; 46 46 // } … … 65 65 while (max_flow_test.augmentOnShortestPath()) { 66 66 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 67 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";67 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 68 68 // } 69 69 // std::cout<<std::endl; … … 73 73 // std::cout << "maximum flow: "<< std::endl; 74 74 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 75 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";75 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 76 76 // } 77 77 // std::cout<<std::endl; -
src/work/marci/lp/max_flow_by_lp.cc
r921 r986 64 64 65 65 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 66 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])67 std::cout << "Slackness does not hold!" << std::endl; 68 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)66 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 67 std::cout << "Slackness does not hold!" << std::endl; 68 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 69 69 std::cout << "Slackness does not hold!" << std::endl; 70 70 } … … 80 80 81 81 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 82 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])83 // std::cout << "Slackness does not hold!" << std::endl; 84 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)82 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 83 // std::cout << "Slackness does not hold!" << std::endl; 84 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 85 85 // std::cout << "Slackness does not hold!" << std::endl; 86 86 // } … … 107 107 108 108 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 109 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])110 std::cout << "Slackness does not hold!" << std::endl; 111 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)109 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 110 std::cout << "Slackness does not hold!" << std::endl; 111 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 112 112 std::cout << "Slackness does not hold!" << std::endl; 113 113 } … … 136 136 137 137 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 138 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])139 std::cout << "Slackness does not hold!" << std::endl; 140 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)138 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 139 std::cout << "Slackness does not hold!" << std::endl; 140 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 141 141 std::cout << "Slackness does not hold!" << std::endl; 142 142 } … … 154 154 155 155 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 156 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])157 // std::cout << "Slackness does not hold!" << std::endl; 158 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)156 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 157 // std::cout << "Slackness does not hold!" << std::endl; 158 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 159 159 // std::cout << "Slackness does not hold!" << std::endl; 160 160 // } … … 172 172 173 173 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 174 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])175 // std::cout << "Slackness does not hold!" << std::endl; 176 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)174 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 175 // std::cout << "Slackness does not hold!" << std::endl; 176 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 177 177 // std::cout << "Slackness does not hold!" << std::endl; 178 178 // } -
src/work/marci/max_flow_demo.cc
r921 r986 48 48 49 49 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 50 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])50 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 51 51 std::cout << "Slackness does not hold!" << std::endl; 52 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)52 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 53 53 std::cout << "Slackness does not hold!" << std::endl; 54 54 } … … 64 64 65 65 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 66 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])66 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 67 67 std::cout << "Slackness does not hold!" << std::endl; 68 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)68 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 69 69 std::cout << "Slackness does not hold!" << std::endl; 70 70 } … … 91 91 92 92 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 93 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])93 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 94 94 std::cout << "Slackness does not hold!" << std::endl; 95 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)95 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 96 96 std::cout << "Slackness does not hold!" << std::endl; 97 97 } … … 109 109 110 110 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 111 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])111 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 112 112 std::cout << "Slackness does not hold!" << std::endl; 113 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)113 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 114 114 std::cout << "Slackness does not hold!" << std::endl; 115 115 } … … 127 127 128 128 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 129 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])129 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 130 130 std::cout << "Slackness does not hold!" << std::endl; 131 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)131 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 132 132 std::cout << "Slackness does not hold!" << std::endl; 133 133 } … … 145 145 146 146 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 147 if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])147 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 148 148 std::cout << "Slackness does not hold!" << std::endl; 149 if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)149 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 150 150 std::cout << "Slackness does not hold!" << std::endl; 151 151 } -
src/work/marci/oldies/edmonds_karp.h
r921 r986 60 60 ResGWOutEdgeIt e=bfs; 61 61 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 62 Node v=res_graph. tail(e);63 Node w=res_graph. head(e);62 Node v=res_graph.source(e); 63 Node w=res_graph.target(e); 64 64 pred.set(w, e); 65 65 if (res_graph.valid(pred[v])) { … … 68 68 free.set(w, res_graph.resCap(e)); 69 69 } 70 if (res_graph. head(e)==t) { _augment=true; break; }70 if (res_graph.target(e)==t) { _augment=true; break; } 71 71 } 72 72 … … 80 80 ResGWEdge e=pred[n]; 81 81 res_graph.augment(e, augment_value); 82 n=res_graph. tail(e);82 n=res_graph.source(e); 83 83 } 84 84 } … … 102 102 // return dist[n]; } 103 103 // bool get(const typename MapGraphWrapper::Edge& e) const { 104 // return (dist.get(g-> tail(e))<dist.get(g->head(e))); }104 // return (dist.get(g->source(e))<dist.get(g->target(e))); } 105 105 bool operator[](const typename MapGraphWrapper::Edge& e) const { 106 return (dist[g-> tail(e)]<dist[g->head(e)]);106 return (dist[g->source(e)]<dist[g->target(e)]); 107 107 } 108 108 }; … … 124 124 ResGWOutEdgeIt e=bfs; 125 125 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 126 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);126 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 127 127 } 128 128 ++bfs; … … 153 153 typename FilterResGW::EdgeIt e; 154 154 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 155 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);155 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 157 157 original_edge.update(); 158 158 original_edge.set(f, e); … … 207 207 typename MG::Edge e=pred[n]; 208 208 res_graph.augment(original_edge[e], augment_value); 209 n=F. tail(e);209 n=F.source(e); 210 210 if (residual_capacity[e]==augment_value) 211 211 F.erase(e); … … 255 255 if (res_graph.valid(e)) { 256 256 if (bfs.isBNodeNewlyReached()) { 257 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);257 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 259 259 original_edge.update(); 260 260 original_edge.set(f, e); … … 262 262 residual_capacity.set(f, res_graph.resCap(e)); 263 263 } else { 264 if (dist[res_graph. head(e)]==(dist[res_graph.tail(e)]+1)) {265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);264 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { 265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 266 266 original_edge.update(); 267 267 original_edge.set(f, e); … … 317 317 typename MG::Edge e=pred[n]; 318 318 res_graph.augment(original_edge[e], augment_value); 319 n=F. tail(e);319 n=F.source(e); 320 320 if (residual_capacity[e]==augment_value) 321 321 F.erase(e); … … 344 344 ResGWOutEdgeIt e=bfs; 345 345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 346 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);346 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 347 347 } 348 348 ++bfs; … … 441 441 typename ErasingResGW::OutEdgeIt e=pred[n]; 442 442 res_graph.augment(e, augment_value); 443 n=erasing_res_graph. tail(e);443 n=erasing_res_graph.source(e); 444 444 if (res_graph.resCap(e)==0) 445 445 erasing_res_graph.erase(e); … … 536 536 // AugOutEdgeIt e=bfs; 537 537 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 538 // Node v=res_graph. tail(e);539 // Node w=res_graph. head(e);538 // Node v=res_graph.source(e); 539 // Node w=res_graph.target(e); 540 540 // pred.set(w, e); 541 541 // if (res_graph.valid(pred.get(v))) { … … 544 544 // free.set(w, res_graph.free(e)); 545 545 // } 546 // n=res_graph. head(e);546 // n=res_graph.target(e); 547 547 // if (T->get(n) && (used.get(n)<1) ) { 548 548 // //Num u=0; … … 566 566 // AugEdge e=pred.get(n); 567 567 // res_graph.augment(e, augment_value); 568 // n=res_graph. tail(e);568 // n=res_graph.source(e); 569 569 // } 570 570 // used.set(n, 1); //mind2 vegen jav … … 607 607 // // AugOutEdgeIt e=bfs; 608 608 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 609 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);609 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 610 610 // // } 611 611 … … 629 629 // // //which are in some shortest paths 630 630 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 631 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));631 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 633 633 // // original_edge.update(); 634 634 // // original_edge.set(f, e); … … 682 682 // // typename MutableGraph::Edge e=pred.get(n); 683 683 // // res_graph.augment(original_edge.get(e), augment_value); 684 // // n=F. tail(e);684 // // n=F.source(e); 685 685 // // if (residual_capacity.get(e)==augment_value) 686 686 // // F.erase(e); … … 733 733 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs; 734 734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 735 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);735 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 736 736 // } 737 737 // ++bfs; … … 810 810 // EAugEdge e=pred.get(n); 811 811 // res_graph.augment(e, augment_value); 812 // n=res_graph. tail(e);812 // n=res_graph.source(e); 813 813 // if (res_graph.free(e)==0) 814 814 // res_graph.erase(e); … … 903 903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 904 904 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 905 // // Node v=res_graph. tail(e);906 // // Node w=res_graph. head(e);905 // // Node v=res_graph.source(e); 906 // // Node w=res_graph.target(e); 907 907 // // pred.set(w, e); 908 908 // // if (pred.get(v).valid()) { … … 911 911 // // free.set(w, e.free()); 912 912 // // } 913 // // if (TMap.get(res_graph. head(e))) {913 // // if (TMap.get(res_graph.target(e))) { 914 914 // // _augment=true; 915 // // reached_t_node=res_graph. head(e);915 // // reached_t_node=res_graph.target(e); 916 916 // // break; 917 917 // // } … … 927 927 // // AugEdge e=pred.get(n); 928 928 // // e.augment(augment_value); 929 // // n=res_graph. tail(e);929 // // n=res_graph.source(e); 930 930 // // } 931 931 // // } -
src/work/marci/oldies/marci_graph_demo.cc
r921 r986 32 32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 33 33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 34 std::cout << "(" << G.id(G. tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";34 std::cout << "(" << G.id(G.source(j)) << "--" << G.id(j) << "->" << G.id(G.target(j)) << ") "; 35 35 } 36 36 std::cout << std::endl; … … 90 90 } 91 91 92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;92 std::cout << "node and edge property values on the sources and targets of edges..." << std::endl; 93 93 for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) { 94 std::cout << my_property_vector.get(G. tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";94 std::cout << my_property_vector.get(G.source(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.target(j)) << " "; 95 95 } 96 96 std::cout << std::endl; … … 159 159 std::cout << "out edges: "; 160 160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 161 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";161 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 162 162 std::cout << "in edges: "; 163 163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 164 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";164 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 165 165 std::cout << std::endl; 166 166 } … … 172 172 173 173 174 //flowG.set Tail(v3_t, v2);175 //flowG.set Head(v3_t, s);174 //flowG.setSource(v3_t, v2); 175 //flowG.setTarget(v3_t, s); 176 176 /* 177 177 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { … … 179 179 std::cout << "out edges: "; 180 180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 181 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";181 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 182 182 std::cout << "in edges: "; 183 183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 184 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";184 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 185 185 std::cout << std::endl; 186 186 } 187 187 188 188 for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 189 std::cout << node_name.get(flowG. tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";189 std::cout << node_name.get(flowG.source(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.target(e)) << " "; 190 190 } 191 191 */ … … 197 197 std::cout << "out edges: "; 198 198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 199 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";199 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 200 200 std::cout << "in edges: "; 201 201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 202 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";202 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 203 203 std::cout << std::endl; 204 204 } … … 211 211 std::cout << "out edges: "; 212 212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 213 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";213 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 214 214 std::cout << "in edges: "; 215 215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 216 std::cout << node_name.get(flowG. tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";216 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; 217 217 std::cout << std::endl; 218 218 } … … 229 229 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 230 230 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 231 std::cout<<"("<<flowG. tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";231 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; 232 232 } 233 233 std::cout<<std::endl; 234 234 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 235 235 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 236 std::cout<<"("<<flowG. tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";236 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; 237 237 } 238 238 std::cout<<std::endl;*/ … … 242 242 while (max_flow_test.augmentOnShortestPath()) { 243 243 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 244 std::cout<<"("<<flowG. tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";244 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; 245 245 } 246 246 std::cout<<std::endl; … … 261 261 std::cout << "maximum flow: "<< std::endl; 262 262 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 263 std::cout<<"("<<flowG. tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";263 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; 264 264 } 265 265 std::cout<<std::endl; -
src/work/marci/preflow_bug.cc
r921 r986 46 46 Graph::EdgeIt e; 47 47 for (g.first(e); g.valid(e); g.next(e)) 48 cout << 1+g.id(g. tail(e)) << "->" << 1+g.id(g.head(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;48 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl; 49 49 } 50 50 { … … 76 76 Graph::EdgeIt e; 77 77 for (g.first(e); g.valid(e); g.next(e)) { 78 if (cut[g. tail(e)] && !cut[g.head(e)]) {79 cout << 1+g.id(g. tail(e)) << "->" << 1+g.id(g.head(e))78 if (cut[g.source(e)] && !cut[g.target(e)]) { 79 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) 80 80 << "(forward edge) flow: " << flow[e] 81 81 << " cap: " << cap[e]<< endl; … … 83 83 std::cout << "Slackness does not hold!" << std::endl; 84 84 } 85 if (!cut[g. tail(e)] && cut[g.head(e)]) {86 cout << 1+g.id(g. tail(e)) << "->" << 1+g.id(g.head(e))85 if (!cut[g.source(e)] && cut[g.target(e)]) { 86 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) 87 87 << "(backward edge) flow: " << flow[e] << endl; 88 88 if (flow[e]!=0) … … 106 106 107 107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 108 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])109 // std::cout << "Slackness does not hold!" << std::endl; 110 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)108 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 109 // std::cout << "Slackness does not hold!" << std::endl; 110 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 111 111 // std::cout << "Slackness does not hold!" << std::endl; 112 112 // } … … 122 122 123 123 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 124 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])125 // std::cout << "Slackness does not hold!" << std::endl; 126 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)124 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 125 // std::cout << "Slackness does not hold!" << std::endl; 126 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 127 127 // std::cout << "Slackness does not hold!" << std::endl; 128 128 // } … … 149 149 150 150 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 151 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])152 // std::cout << "Slackness does not hold!" << std::endl; 153 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)151 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 152 // std::cout << "Slackness does not hold!" << std::endl; 153 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 154 154 // std::cout << "Slackness does not hold!" << std::endl; 155 155 // } … … 178 178 179 179 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 180 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])181 // std::cout << "Slackness does not hold!" << std::endl; 182 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)180 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 181 // std::cout << "Slackness does not hold!" << std::endl; 182 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 183 183 // std::cout << "Slackness does not hold!" << std::endl; 184 184 // } … … 196 196 197 197 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 198 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])199 // std::cout << "Slackness does not hold!" << std::endl; 200 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)198 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 199 // std::cout << "Slackness does not hold!" << std::endl; 200 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 201 201 // std::cout << "Slackness does not hold!" << std::endl; 202 202 // } … … 214 214 215 215 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 216 // if (cut[g. tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])217 // std::cout << "Slackness does not hold!" << std::endl; 218 // if (!cut[g. tail(e)] && cut[g.head(e)] && flow[e]>0)216 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 217 // std::cout << "Slackness does not hold!" << std::endl; 218 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 219 219 // std::cout << "Slackness does not hold!" << std::endl; 220 220 // } -
src/work/marci/preflow_demo_athos.cc
r921 r986 29 29 //int cut_value=0; 30 30 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 31 // if (cut.get(G. tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);31 // if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); 32 32 //} 33 33 double post_time=currTime(); 34 34 //std::cout << "maximum flow: "<< std::endl; 35 35 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 36 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";36 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 37 37 //} 38 38 //std::cout<<std::endl; -
src/work/marci/preflow_demo_jacint.cc
r921 r986 32 32 int cut_value=0; 33 33 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 34 if (cut.get(G. tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);34 if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); 35 35 } 36 36 double post_time=currTime(); 37 37 //std::cout << "maximum flow: "<< std::endl; 38 38 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 39 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";39 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 40 40 //} 41 41 //std::cout<<std::endl; … … 56 56 int cut_value=0; 57 57 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 58 if (cut.get(G. tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);58 if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); 59 59 } 60 60 double post_time=currTime(); 61 61 //std::cout << "maximum flow: "<< std::endl; 62 62 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 63 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";63 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 64 64 //} 65 65 //std::cout<<std::endl; -
src/work/peter/edgepathgraph.h
r921 r986 74 74 PEdgeIt f; 75 75 76 //dep//cout << "Edge " << id( tail(e)) << " - " << id(head(e)) << " in actual layer is";76 //dep//cout << "Edge " << id(source(e)) << " - " << id(target(e)) << " in actual layer is"; 77 77 T1 incr=actmap[e]; 78 78 //cout << incr << endl; … … 83 83 for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) 84 84 { 85 //dep//cout << " " << sublayer->id(sublayer-> tail(f)) << "-" << sublayer->id(sublayer->head(f));85 //dep//cout << " " << sublayer->id(sublayer->source(f)) << "-" << sublayer->id(sublayer->target(f)); 86 86 submap[f]+=incr; 87 87 } 88 //dep////cout << EPGr2.id(EPGr2. head(f)) << endl;88 //dep////cout << EPGr2.id(EPGr2.target(f)) << endl; 89 89 //dep//cout << endl; 90 90 } … … 108 108 PEdgeIt f; 109 109 110 cout << "Edge " << id( tail(e)) << " - " << id(head(e)) << " in actual layer is";110 cout << "Edge " << id(source(e)) << " - " << id(target(e)) << " in actual layer is"; 111 111 if(edgepath[e]) 112 112 { … … 114 114 for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) 115 115 { 116 cout << " " << sublayer->id(sublayer-> tail(f)) << "-" << sublayer->id(sublayer->head(f));116 cout << " " << sublayer->id(sublayer->source(f)) << "-" << sublayer->id(sublayer->target(f)); 117 117 } 118 //cout << EPGr2.id(EPGr2. head(f)) << endl;118 //cout << EPGr2.id(EPGr2.target(f)) << endl; 119 119 cout << endl; 120 120 } … … 235 235 typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);} 236 236 237 ///Gives back the headnode of an edge.238 typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }239 ///Gives back the tailnode of an edge.240 typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }237 ///Gives back the target node of an edge. 238 typename Gact::Node target(typename Gact::Edge edge) const { return actuallayer.target(edge); } 239 ///Gives back the source node of an edge. 240 typename Gact::Node source(typename Gact::Edge edge) const { return actuallayer.source(edge); } 241 241 242 242 // Node aNode(InEdgeIt) const {} … … 280 280 ///Add a new edge to the graph. 281 281 282 ///Add a new edge to the graph with tail node \c tail283 ///and head node \c head.282 ///Add a new edge to the graph with source node \c source 283 ///and target node \c target. 284 284 ///\return the new edge. 285 285 typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);} -
src/work/peter/edgepathgraph_test.cc
r921 r986 136 136 PEdgeIt f; 137 137 138 cout << "Edge " << EPGr.id(EPGr. tail(e)) << " - " << EPGr.id(EPGr.head(e)) << " in actual layer is";138 cout << "Edge " << EPGr.id(EPGr.source(e)) << " - " << EPGr.id(EPGr.target(e)) << " in actual layer is"; 139 139 if(EPGr.edgepath[e]) 140 140 { … … 142 142 for(EPGr.edgepath[e]->first(f); EPGr.edgepath[e]->valid(f); EPGr.edgepath[e]->next(f)) 143 143 { 144 cout << " " << EPGr2.id(EPGr2. tail(f)) << "-" << EPGr2.id(EPGr2.head(f));144 cout << " " << EPGr2.id(EPGr2.source(f)) << "-" << EPGr2.id(EPGr2.target(f)); 145 145 } 146 //cout << EPGr2.id(EPGr2. head(f)) << endl;146 //cout << EPGr2.id(EPGr2.target(f)) << endl; 147 147 cout << endl; 148 148 } … … 170 170 for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e)) 171 171 { 172 cout << EPGr.id(EPGr. tail(e)) << "-" << EPGr.id(EPGr.head(e)) << ":" << actlaymap[e] << " ";172 cout << EPGr.id(EPGr.source(e)) << "-" << EPGr.id(EPGr.target(e)) << ":" << actlaymap[e] << " "; 173 173 } 174 174 cout << endl; … … 176 176 for(ListGraph::EdgeIt e(EPGr2.actuallayer);EPGr2.actuallayer.valid(e);EPGr2.actuallayer.next(e)) 177 177 { 178 cout << EPGr2.id(EPGr2. tail(e)) << "-" << EPGr2.id(EPGr2.head(e)) << ":" << sublaymap[e] << " ";178 cout << EPGr2.id(EPGr2.source(e)) << "-" << EPGr2.id(EPGr2.target(e)) << ":" << sublaymap[e] << " "; 179 179 } 180 180 cout << endl; … … 191 191 for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e)) 192 192 { 193 cout << EPGr.id(EPGr. tail(e)) << "-" << EPGr.id(EPGr.head(e)) << ":" << actlaymap[e] << " ";193 cout << EPGr.id(EPGr.source(e)) << "-" << EPGr.id(EPGr.target(e)) << ":" << actlaymap[e] << " "; 194 194 } 195 195 cout << endl; … … 197 197 for(ListGraph::EdgeIt e(EPGr2.actuallayer);EPGr2.actuallayer.valid(e);EPGr2.actuallayer.next(e)) 198 198 { 199 cout << EPGr2.id(EPGr2. tail(e)) << "-" << EPGr2.id(EPGr2.head(e)) << ":" << sublaymap[e] << " ";199 cout << EPGr2.id(EPGr2.source(e)) << "-" << EPGr2.id(EPGr2.target(e)) << ":" << sublaymap[e] << " "; 200 200 } 201 201 cout << endl; -
src/work/peter/hierarchygraph.h
r921 r986 61 61 return -1; 62 62 } 63 else if ((actuallayer->id (actuallayer-> tail(actedge)) !=63 else if ((actuallayer->id (actuallayer->source (actedge)) != 64 64 actuallayer->id (*actuallayernode)) 65 && (actuallayer->id (actuallayer-> head(actedge)) !=65 && (actuallayer->id (actuallayer->target (actedge)) != 66 66 actuallayer->id (*actuallayernode))) 67 67 { … … 133 133 for (iei = actuallayer->first (iei, (*actuallayernode)); 134 134 ((actuallayer->valid (iei)) 135 && (actuallayer-> head(iei) == (*actuallayernode)));135 && (actuallayer->target (iei) == (*actuallayernode))); 136 136 actuallayer->next (iei)) 137 137 { 138 138 cout << actuallayer->id (actuallayer-> 139 tail(iei)) << " " << actuallayer->140 id (actuallayer-> head(iei)) << endl;139 source (iei)) << " " << actuallayer-> 140 id (actuallayer->target (iei)) << endl; 141 141 edgenumber++; 142 142 } … … 144 144 for (oei = actuallayer->first (oei, (*actuallayernode)); 145 145 ((actuallayer->valid (oei)) 146 && (actuallayer-> tail(oei) == (*actuallayernode)));146 && (actuallayer->source (oei) == (*actuallayernode))); 147 147 actuallayer->next (oei)) 148 148 { 149 149 cout << actuallayer->id (actuallayer-> 150 tail(oei)) << " " << actuallayer->151 id (actuallayer-> head(oei)) << endl;150 source (oei)) << " " << actuallayer-> 151 id (actuallayer->target (oei)) << endl; 152 152 edgenumber++; 153 153 } … … 328 328 } 329 329 330 ///Gives back the headnode of an edge.331 typename Gact::Node head(typename Gact::Edge edge) const332 { 333 return actuallayer. head(edge);334 } 335 ///Gives back the tailnode of an edge.336 typename Gact::Node tail(typename Gact::Edge edge) const337 { 338 return actuallayer. tail(edge);330 ///Gives back the target node of an edge. 331 typename Gact::Node target (typename Gact::Edge edge) const 332 { 333 return actuallayer.target (edge); 334 } 335 ///Gives back the source node of an edge. 336 typename Gact::Node source (typename Gact::Edge edge) const 337 { 338 return actuallayer.source (edge); 339 339 } 340 340 … … 394 394 ///Add a new edge to the graph. 395 395 396 ///Add a new edge to the graph with tail node \c tail397 ///and head node \c head.396 ///Add a new edge to the graph with source node \c source 397 ///and target node \c target. 398 398 ///\return the new edge. 399 399 typename Gact::Edge addEdge (typename Gact::Node node1, -
src/work/peter/path/path.h
r959 r986 109 109 /// Returns INVALID if the path is empty. 110 110 GraphNode from() const { 111 return empty() ? INVALID : gr-> tail(edges[0]);111 return empty() ? INVALID : gr->source(edges[0]); 112 112 } 113 113 /// \brief End point of the path. … … 116 116 /// Returns INVALID if the path is empty. 117 117 GraphNode to() const { 118 return empty() ? INVALID : gr-> head(edges[length()-1]);118 return empty() ? INVALID : gr->target(edges[length()-1]); 119 119 } 120 120 … … 154 154 } 155 155 156 /// \brief Returns node iterator pointing to the headnode of the156 /// \brief Returns node iterator pointing to the target node of the 157 157 /// given edge iterator. 158 NodeIt head(const EdgeIt& e) const {158 NodeIt target(const EdgeIt& e) const { 159 159 if( DM::range_check && !e.valid() ) 160 fault("DirPath:: head() on invalid iterator");160 fault("DirPath::target() on invalid iterator"); 161 161 return NodeIt(*this, e.idx+1); 162 162 } 163 163 164 /// \brief Returns node iterator pointing to the tailnode of the164 /// \brief Returns node iterator pointing to the source node of the 165 165 /// given edge iterator. 166 NodeIt tail(const EdgeIt& e) const {166 NodeIt source(const EdgeIt& e) const { 167 167 if( DM::range_check && !e.valid() ) 168 fault("DirPath:: tail() on invalid iterator");168 fault("DirPath::source() on invalid iterator"); 169 169 return NodeIt(*this, e.idx); 170 170 } … … 255 255 return p->to(); 256 256 else if(idx >= 0) 257 return p->gr-> tail(p->edges[idx]);257 return p->gr->source(p->edges[idx]); 258 258 else 259 259 return INVALID; … … 313 313 ///\sa setStartNode 314 314 void pushFront(const GraphEdge& e) { 315 if( DM::consistensy_check && !empty() && P.gr-> head(e)!=from() ) {315 if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) { 316 316 fault("DirPath::Builder::pushFront: nonincident edge"); 317 317 } … … 324 324 ///\sa setStartNode 325 325 void pushBack(const GraphEdge& e) { 326 if( DM::consistensy_check && !empty() && P.gr-> tail(e)!=to() ) {326 if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) { 327 327 fault("DirPath::Builder::pushBack: nonincident edge"); 328 328 } … … 363 363 GraphNode from() const { 364 364 if( ! front.empty() ) 365 return P.gr-> tail(front[front.size()-1]);365 return P.gr->source(front[front.size()-1]); 366 366 else if( ! P.empty() ) 367 return P.gr-> tail(P.edges[0]);367 return P.gr->source(P.edges[0]); 368 368 else if( ! back.empty() ) 369 return P.gr-> tail(back[0]);369 return P.gr->source(back[0]); 370 370 else 371 371 return INVALID; … … 373 373 GraphNode to() const { 374 374 if( ! back.empty() ) 375 return P.gr-> head(back[back.size()-1]);375 return P.gr->target(back[back.size()-1]); 376 376 else if( ! P.empty() ) 377 return P.gr-> head(P.edges[P.length()-1]);377 return P.gr->target(P.edges[P.length()-1]); 378 378 else if( ! front.empty() ) 379 return P.gr-> head(front[0]);379 return P.gr->target(front[0]); 380 380 else 381 381 return INVALID; … … 472 472 /// Returns INVALID if the path is empty. 473 473 GraphNode from() const { 474 return empty() ? INVALID : gr-> tail(edges[0]);474 return empty() ? INVALID : gr->source(edges[0]); 475 475 } 476 476 /// \brief End point of the path. … … 479 479 /// Returns INVALID if the path is empty. 480 480 GraphNode to() const { 481 return empty() ? INVALID : gr-> head(edges[length()-1]);481 return empty() ? INVALID : gr->target(edges[length()-1]); 482 482 } 483 483 … … 517 517 } 518 518 519 /// \brief Returns node iterator pointing to the headnode of the519 /// \brief Returns node iterator pointing to the target node of the 520 520 /// given edge iterator. 521 NodeIt head(const EdgeIt& e) const {521 NodeIt target(const EdgeIt& e) const { 522 522 if( DM::range_check && !e.valid() ) 523 fault("UndirPath:: head() on invalid iterator");523 fault("UndirPath::target() on invalid iterator"); 524 524 return NodeIt(*this, e.idx+1); 525 525 } 526 526 527 /// \brief Returns node iterator pointing to the tailnode of the527 /// \brief Returns node iterator pointing to the source node of the 528 528 /// given edge iterator. 529 NodeIt tail(const EdgeIt& e) const {529 NodeIt source(const EdgeIt& e) const { 530 530 if( DM::range_check && !e.valid() ) 531 fault("UndirPath:: tail() on invalid iterator");531 fault("UndirPath::source() on invalid iterator"); 532 532 return NodeIt(*this, e.idx); 533 533 } … … 616 616 return p->to(); 617 617 else if(idx >= 0) 618 return p->gr-> tail(p->edges[idx]);618 return p->gr->source(p->edges[idx]); 619 619 else 620 620 return INVALID; … … 674 674 ///\sa setStartNode 675 675 void pushFront(const GraphEdge& e) { 676 if( DM::consistensy_check && !empty() && P.gr-> head(e)!=from() ) {676 if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) { 677 677 fault("UndirPath::Builder::pushFront: nonincident edge"); 678 678 } … … 685 685 ///\sa setStartNode 686 686 void pushBack(const GraphEdge& e) { 687 if( DM::consistensy_check && !empty() && P.gr-> tail(e)!=to() ) {687 if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) { 688 688 fault("UndirPath::Builder::pushBack: nonincident edge"); 689 689 } … … 724 724 GraphNode from() const { 725 725 if( ! front.empty() ) 726 return P.gr-> tail(front[front.size()-1]);726 return P.gr->source(front[front.size()-1]); 727 727 else if( ! P.empty() ) 728 return P.gr-> tail(P.edges[0]);728 return P.gr->source(P.edges[0]); 729 729 else if( ! back.empty() ) 730 return P.gr-> tail(back[0]);730 return P.gr->source(back[0]); 731 731 else 732 732 return INVALID; … … 734 734 GraphNode to() const { 735 735 if( ! back.empty() ) 736 return P.gr-> head(back[back.size()-1]);736 return P.gr->target(back[back.size()-1]); 737 737 else if( ! P.empty() ) 738 return P.gr-> head(P.edges[P.length()-1]);738 return P.gr->target(P.edges[P.length()-1]); 739 739 else if( ! front.empty() ) 740 return P.gr-> head(front[0]);740 return P.gr->target(front[0]); 741 741 else 742 742 return INVALID; … … 841 841 bool setTo(const GraphNode &n); 842 842 843 // WARNING: these two functions return the head/tailof an edge with843 // WARNING: these two functions return the target/source of an edge with 844 844 // respect to the direction of the path! 845 // So G. head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if845 // So G.target(P.graphEdge(e)) == P.graphNode(P.target(e)) holds only if 846 846 // P.forward(e) is true (or the edge is a loop)! 847 NodeIt head(const EdgeIt& e) const;848 NodeIt tail(const EdgeIt& e) const;847 NodeIt target(const EdgeIt& e) const; 848 NodeIt source(const EdgeIt& e) const; 849 849 850 850 // FIXME: ezeknek valami jobb nev kellene!!! … … 874 874 875 875 size_t idx; 876 bool tail; // Is this node the tailof the edge with same idx?876 bool source; // Is this node the source of the edge with same idx? 877 877 878 878 public: … … 897 897 return e; 898 898 899 GraphNode common_node = ( e.forw ? G. head(*e.it) : G.tail(*e.it) );899 GraphNode common_node = ( e.forw ? G.target(*e.it) : G.source(*e.it) ); 900 900 ++e.it; 901 901 … … 906 906 } 907 907 908 e.forw = ( G. tail(*e.it) == common_node );908 e.forw = ( G.source(*e.it) == common_node ); 909 909 return e; 910 910 } … … 919 919 920 920 921 GraphNode next_node = ( n. tail ? G.head(edges[n.idx]) :922 G. tail(edges[n.idx]) );921 GraphNode next_node = ( n.source ? G.target(edges[n.idx]) : 922 G.source(edges[n.idx]) ); 923 923 ++n.idx; 924 924 if( n.idx < length() ) { 925 n. tail = ( next_node == G.tail(edges[n.idx]) );925 n.source = ( next_node == G.source(edges[n.idx]) ); 926 926 } 927 927 else { 928 n. tail= true;928 n.source = true; 929 929 } 930 930 … … 935 935 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a, 936 936 GraphNode &b) { 937 if( G. tail(e) == a ) {938 b=G. head(e);937 if( G.source(e) == a ) { 938 b=G.target(e); 939 939 return true; 940 940 } 941 if( G. head(e) == a ) {942 b=G. tail(e);941 if( G.target(e) == a ) { 942 b=G.source(e); 943 943 return true; 944 944 } … … 949 949 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e, 950 950 const GraphEdge &f) { 951 if( edgeIncident(f, G. tail(e), _last) ) {952 _first = G. head(e);951 if( edgeIncident(f, G.source(e), _last) ) { 952 _first = G.target(e); 953 953 return true; 954 954 } 955 if( edgeIncident(f, G. head(e), _last) ) {956 _first = G. tail(e);955 if( edgeIncident(f, G.target(e), _last) ) { 956 _first = G.source(e); 957 957 return true; 958 958 } … … 1040 1040 template<typename Gr> 1041 1041 typename DynamicPath<Gr>::NodeIt 1042 DynamicPath<Gr>:: tail(const EdgeIt& e) const {1042 DynamicPath<Gr>::source(const EdgeIt& e) const { 1043 1043 NodeIt n; 1044 1044 … … 1046 1046 // FIXME: invalid-> invalid 1047 1047 n.idx = length() + 1; 1048 n. tail= true;1048 n.source = true; 1049 1049 return n; 1050 1050 } 1051 1051 1052 1052 n.idx = e.it-edges.begin(); 1053 n. tail= e.forw;1053 n.source = e.forw; 1054 1054 return n; 1055 1055 } … … 1057 1057 template<typename Gr> 1058 1058 typename DynamicPath<Gr>::NodeIt 1059 DynamicPath<Gr>:: head(const EdgeIt& e) const {1059 DynamicPath<Gr>::target(const EdgeIt& e) const { 1060 1060 if( e.it == edges.end()-1 ) { 1061 1061 return _last; … … 1064 1064 EdgeIt next_edge = e; 1065 1065 next(next_edge); 1066 return tail(next_edge);1066 return source(next_edge); 1067 1067 } 1068 1068 … … 1082 1082 DynamicPath<Gr>::graphNode(const NodeIt& n) const { 1083 1083 if( n.idx < length() ) { 1084 return n. tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);1084 return n.source ? G.source(edges[n.idx]) : G.target(edges[n.idx]); 1085 1085 } 1086 1086 else if( n.idx == length() ) { … … 1104 1104 e.it = edges.begin()+k; 1105 1105 if(k==0) { 1106 e.forw = ( G. tail(*e.it) == _first );1106 e.forw = ( G.source(*e.it) == _first ); 1107 1107 } 1108 1108 else { 1109 e.forw = ( G. tail(*e.it) == G.tail(edges[k-1]) ||1110 G. tail(*e.it) == G.head(edges[k-1]) );1109 e.forw = ( G.source(*e.it) == G.source(edges[k-1]) || 1110 G.source(*e.it) == G.target(edges[k-1]) ); 1111 1111 } 1112 1112 return e; … … 1119 1119 // FIXME: invalid NodeIt 1120 1120 n.idx = length()+1; 1121 n. tail= true;1121 n.source = true; 1122 1122 return n; 1123 1123 } 1124 1124 if( k==length() ) { 1125 1125 n.idx = length(); 1126 n. tail= true;1126 n.source = true; 1127 1127 return n; 1128 1128 } 1129 n = tail(nth<EdgeIt>(k));1129 n = source(nth<EdgeIt>(k)); 1130 1130 return n; 1131 1131 } … … 1140 1140 { 1141 1141 if( G.valid(P._first) && a.it < P.edges.end() ) { 1142 _first = ( a.forw ? G. tail(*a.it) : G.head(*a.it) );1142 _first = ( a.forw ? G.source(*a.it) : G.target(*a.it) ); 1143 1143 if( b.it < P.edges.end() ) { 1144 _last = ( b.forw ? G. tail(*b.it) : G.head(*b.it) );1144 _last = ( b.forw ? G.source(*b.it) : G.target(*b.it) ); 1145 1145 } 1146 1146 else { -
src/work/peter/path/path_skeleton.h
r959 r986 54 54 /// Starting point of the path. 55 55 /// Returns INVALID if the path is empty. 56 GraphNode head() const {}56 GraphNode target() const {} 57 57 /// \brief End point of the path. 58 58 /// 59 59 /// End point of the path. 60 60 /// Returns INVALID if the path is empty. 61 GraphNode tail() const {}61 GraphNode source() const {} 62 62 63 63 /// \brief First NodeIt/EdgeIt. … … 68 68 It& first(It &i) const { return i=It(*this); } 69 69 70 /// \brief The headof an edge.71 /// 72 /// Returns node iterator pointing to the headnode of the70 /// \brief The target of an edge. 71 /// 72 /// Returns node iterator pointing to the target node of the 73 73 /// given edge iterator. 74 NodeIt head(const EdgeIt& e) const {}75 76 /// \brief The tailof an edge.77 /// 78 /// Returns node iterator pointing to the tailnode of the74 NodeIt target(const EdgeIt& e) const {} 75 76 /// \brief The source of an edge. 77 /// 78 /// Returns node iterator pointing to the source node of the 79 79 /// given edge iterator. 80 NodeIt tail(const EdgeIt& e) const {}80 NodeIt source(const EdgeIt& e) const {} 81 81 82 82 -
src/work/peter/path/path_test.cc
r959 r986 67 67 68 68 #ifdef SKELETON 69 cout << "P. tail() valid? " << (P.tail()!=INVALID) << endl;70 check(! (P. tail()!=INVALID));69 cout << "P.source() valid? " << (P.source()!=INVALID) << endl; 70 check(! (P.source()!=INVALID)); 71 71 #else 72 cout << "P. tail() valid? " << (P.from()!=INVALID) << endl;72 cout << "P.source() valid? " << (P.from()!=INVALID) << endl; 73 73 check(! (P.to()!=INVALID)); 74 74 #endif … … 90 90 91 91 #ifdef SKELETON 92 cout << "P. tail() valid? " << (P.tail()!=INVALID) << endl;93 check(P. tail()!=INVALID);94 cout << "P. tail()==v1 ? " << (P.tail()==v1) << endl;95 check(P. tail() == v1);92 cout << "P.source() valid? " << (P.source()!=INVALID) << endl; 93 check(P.source()!=INVALID); 94 cout << "P.source()==v1 ? " << (P.source()==v1) << endl; 95 check(P.source() == v1); 96 96 #else 97 cout << "P. tail() valid? " << (P.from()!=INVALID) << endl;97 cout << "P.source() valid? " << (P.from()!=INVALID) << endl; 98 98 check(P.from()!=INVALID); 99 cout << "P. tail()==v1 ? " << (P.from()==v1) << endl;99 cout << "P.source()==v1 ? " << (P.from()==v1) << endl; 100 100 check(P.from() == v1); 101 101 #endif … … 129 129 130 130 #ifdef SKELETON 131 cout << "P. head()==v3 ? " << (P.head()==v3) << endl;132 check(P. head() == v3);131 cout << "P.target()==v3 ? " << (P.target()==v3) << endl; 132 check(P.target() == v3); 133 133 #else 134 cout << "P. head()==v3 ? " << (P.to()==v3) << endl;134 cout << "P.target()==v3 ? " << (P.to()==v3) << endl; 135 135 check(P.to() == v3); 136 136 #endif -
src/work/sage_graph.h
r921 r986 97 97 struct edge_item { 98 98 int id; 99 node_item* _ tail;100 node_item* _ head;99 node_item* _source; 100 node_item* _target; 101 101 edge_item* _next_out; 102 102 edge_item* _prev_out; … … 122 122 } 123 123 124 edge_item* _add_edge(node_item* _ tail, node_item* _head) {124 edge_item* _add_edge(node_item* _source, node_item* _target) { 125 125 edge_item* e=new edge_item; 126 126 e->id=edge_id++; 127 e->_ tail=_tail;128 e->_ head=_head;127 e->_source=_source; 128 e->_target=_target; 129 129 130 e->_prev_out=_ tail->_last_out_edge;131 if (_ tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;132 _ tail->_last_out_edge=e;133 if (!_ tail->_first_out_edge) _tail->_first_out_edge=e;130 e->_prev_out=_source->_last_out_edge; 131 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; 132 _source->_last_out_edge=e; 133 if (!_source->_first_out_edge) _source->_first_out_edge=e; 134 134 e->_next_out=0; 135 135 136 e->_prev_in=_ head->_last_in_edge;137 if (_ head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;138 _ head->_last_in_edge=e;139 if (!_ head->_first_in_edge) { _head->_first_in_edge=e; }136 e->_prev_in=_target->_last_in_edge; 137 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; 138 _target->_last_in_edge=e; 139 if (!_target->_first_in_edge) { _target->_first_in_edge=e; } 140 140 e->_next_in=0; 141 141 … … 157 157 void _delete_edge(edge_item* e) { 158 158 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 159 (e->_ tail)->_last_out_edge=e->_prev_out;159 (e->_source)->_last_out_edge=e->_prev_out; 160 160 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 161 (e->_ tail)->_first_out_edge=e->_next_out;161 (e->_source)->_first_out_edge=e->_next_out; 162 162 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 163 (e->_ head)->_last_in_edge=e->_prev_in;163 (e->_target)->_last_in_edge=e->_prev_in; 164 164 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 165 (e->_ head)->_first_in_edge=e->_next_in;165 (e->_target)->_first_in_edge=e->_next_in; 166 166 167 167 delete e; … … 169 169 } 170 170 171 void _set_ tail(edge_item* e, node_item* _tail) {171 void _set_source(edge_item* e, node_item* _source) { 172 172 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 173 (e->_ tail)->_last_out_edge=e->_prev_out;173 (e->_source)->_last_out_edge=e->_prev_out; 174 174 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 175 (e->_ tail)->_first_out_edge=e->_next_out;175 (e->_source)->_first_out_edge=e->_next_out; 176 176 177 e->_ tail=_tail;177 e->_source=_source; 178 178 179 e->_prev_out=_ tail->_last_out_edge;180 if (_ tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;181 _ tail->_last_out_edge=e;182 if (!_ tail->_first_out_edge) _tail->_first_out_edge=e;179 e->_prev_out=_source->_last_out_edge; 180 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; 181 _source->_last_out_edge=e; 182 if (!_source->_first_out_edge) _source->_first_out_edge=e; 183 183 e->_next_out=0; 184 184 } 185 185 186 void _set_ head(edge_item* e, node_item* _head) {186 void _set_target(edge_item* e, node_item* _target) { 187 187 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 188 (e->_ head)->_last_in_edge=e->_prev_in;188 (e->_target)->_last_in_edge=e->_prev_in; 189 189 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 190 (e->_ head)->_first_in_edge=e->_next_in;190 (e->_target)->_first_in_edge=e->_next_in; 191 191 192 e->_ head=_head;192 e->_target=_target; 193 193 194 e->_prev_in=_ head->_last_in_edge;195 if (_ head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;196 _ head->_last_in_edge=e;197 if (!_ head->_first_in_edge) { _head->_first_in_edge=e; }194 e->_prev_in=_target->_last_in_edge; 195 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; 196 _target->_last_in_edge=e; 197 if (!_target->_first_in_edge) { _target->_first_in_edge=e; } 198 198 e->_next_in=0; 199 199 } … … 222 222 //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); } 223 223 //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); } 224 Node tail(Edge e) const { return e.tailNode(); }225 Node head(Edge e) const { return e.headNode(); }224 Node source(Edge e) const { return e.sourceNode(); } 225 Node target(Edge e) const { return e.targetNode(); } 226 226 227 227 Node aNode(const OutEdgeIt& e) const { return e.aNode(); } … … 252 252 SymEdgeIt& first(SymEdgeIt& e, Node v) const { 253 253 e=SymEdgeIt(*this, v); return e; } 254 //void get Tail(Node& n, const Edge& e) const { n=tail(e); }255 //void get Head(Node& n, const Edge& e) const { n=head(e); }254 //void getSource(Node& n, const Edge& e) const { n=source(e); } 255 //void getTarget(Node& n, const Edge& e) const { n=target(e); } 256 256 257 257 //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); } … … 330 330 } 331 331 332 void set Tail(Edge e, Node tail) {333 _set_ tail(e.edge, tail.node);334 } 335 336 void set Head(Edge e, Node head) {337 _set_ head(e.edge, head.node);332 void setSource(Edge e, Node source) { 333 _set_source(e.edge, source.node); 334 } 335 336 void setTarget(Edge e, Node target) { 337 _set_target(e.edge, target.node); 338 338 } 339 339 … … 349 349 // friend std::ostream& operator<<(std::ostream& os, const Edge& i) { 350 350 // if (i.valid()) 351 // os << "(" << i.edge->_ tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";351 // os << "(" << i.edge->_source->id << "--" << i.edge->id << "->" << i.edge->_target->id << ")"; 352 352 // else 353 353 // os << "invalid"; … … 420 420 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; } 421 421 protected: 422 Node tailNode() const { return Node(edge->_tail); }423 Node headNode() const { return Node(edge->_head); }422 Node sourceNode() const { return Node(edge->_source); } 423 Node targetNode() const { return Node(edge->_target); } 424 424 public: 425 425 friend std::ostream& operator<<(std::ostream& os, const Edge& i); … … 441 441 public: 442 442 EdgeIt& operator++() { 443 node_item* v=edge->_ tail;443 node_item* v=edge->_source; 444 444 edge=edge->_next_out; 445 445 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } … … 457 457 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } 458 458 protected: 459 Node aNode() const { return Node(edge->_ tail); }460 Node bNode() const { return Node(edge->_ head); }459 Node aNode() const { return Node(edge->_source); } 460 Node bNode() const { return Node(edge->_target); } 461 461 }; 462 462 … … 470 470 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } 471 471 protected: 472 Node aNode() const { return Node(edge->_ head); }473 Node bNode() const { return Node(edge->_ tail); }472 Node aNode() const { return Node(edge->_target); } 473 Node bNode() const { return Node(edge->_source); } 474 474 }; 475 475 … … 496 496 SymEdgeIt& operator++() { 497 497 if (out_or_in) { 498 node_item* v=edge->_ tail;498 node_item* v=edge->_source; 499 499 edge=edge->_next_out; 500 500 if (!edge) { out_or_in=0; edge=v->_first_in_edge; } … … 506 506 protected: 507 507 Node aNode() const { 508 return (out_or_in) ? Node(edge->_ tail) : Node(edge->_head); }508 return (out_or_in) ? Node(edge->_source) : Node(edge->_target); } 509 509 Node bNode() const { 510 return (out_or_in) ? Node(edge->_ head) : Node(edge->_tail); }510 return (out_or_in) ? Node(edge->_target) : Node(edge->_source); } 511 511 }; 512 512 }; … … 524 524 std::ostream& operator<<(std::ostream& os, const SageGraph::Edge& i) { 525 525 if (i.valid()) 526 os << "(" << i. tailNode() << "--" << i.edge->id << "->"527 << i. headNode() << ")";526 os << "(" << i.sourceNode() << "--" << i.edge->id << "->" 527 << i.targetNode() << ")"; 528 528 else 529 529 os << "invalid";
Note: See TracChangeset
for help on using the changeset viewer.