Changeset 986:e997802b855c in lemon-0.x for src/lemon
- Timestamp:
- 11/13/04 13:53:28 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
- Location:
- src/lemon
- Files:
-
- 21 edited
Legend:
- Unmodified
- Added
- Removed
-
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 }
Note: See TracChangeset
for help on using the changeset viewer.