COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 986:e997802b855c in lemon-0.x for src


Ignore:
Timestamp:
11/13/04 13:53:28 (18 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
Message:

Naming changes:

  • head -> target
  • tail -> source
Location:
src
Files:
102 edited

Legend:

Unmodified
Added
Removed

  • src/benchmark/bfs-bench.cc

    r921 r986  
    4747    Q.pop();
    4848    for(OutEdgeIt e(G,n);e!=INVALID;++e)
    49       if(!visited[m=G.head(e)]) {
     49      if(!visited[m=G.target(e)]) {
    5050        Q.push(m);
    5151        visited.set(m,true);
    … …  
    7575    Node n=Q[Qt++];
    7676    for(OutEdgeIt e(G,n);e!=INVALID;++e)
    77       if(!visited[m=G.head(e)]) {
     77      if(!visited[m=G.target(e)]) {
    7878        Q[Qh++]=m;
    7979        visited.set(m,true);

  • src/demo/dim_to_dot.cc

    r931 r986  
    5252  cout << "  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];" << endl;
    5353  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))
    5555         << " [ label=\"" << g.id(e)
    5656         << ", length:" << length[e] << "\" ]; " << endl;

  • src/demo/sub_graph_wrapper_demo.cc

    r932 r986  
    3838  readDimacs(std::cin, g, length, s, t);
    3939
    40   cout << "edges with lengths (of form id, tail--length->head): " << endl;
     40  cout << "edges with lengths (of form id, source--length->target): " << endl;
    4141  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;
    4444
    4545  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
    … …  
    7676    if (flow[e])
    7777      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;
    8080}

  • src/demo/tight_edge_filter_map.h

    r929 r986  
    3232  /// A node-map node_potential is said to be a potential w.r.t.
    3333  /// 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)]
    3636  /// (or the reverse inequality holds for each edge).
    3737  /// An edge is said to be tight if this inequality holds with equality,
    … …  
    5252      edge_distance(&_edge_distance) { }
    5353    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)]);
    5656    }
    5757  };

  • src/lemon/bfs.h

    r977 r986  
    210210       
    211211        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) {
    213213            Q[Qh++]=m;
    214214            predecessor->set(m,e);

  • src/lemon/concept/graph.h

    r961 r986  
    364364//       EdgeIt& first(EdgeIt& i) const { return i; }
    365365
    366 //       ///Gives back the head node of an edge.
    367 
    368 //       ///Gives back the head node of an edge.
    369 //       ///
    370 //       Node head(Edge) const { return INVALID; }
    371 //       ///Gives back the tail node of an edge.
    372 
    373 //       ///Gives back the tail node 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; }
    376376 
    377377//       ///Gives back the \e id of a node.
    … …  
    539539//      Edge e;
    540540//      e=INVALID;
    541 //      n=G.tail(e);
    542 //      n=G.head(e);
     541//      n=G.source(e);
     542//      n=G.target(e);
    543543//       }
    544544//       // id tests
    … …  
    666666//       ///Add a new edge to the graph.
    667667
    668 //       ///Add a new edge to the graph with tail node \c t
    669 //       ///and head node \c h.
     668//       ///Add a new edge to the graph with source node \c t
     669//       ///and target node \c h.
    670670//       ///\return the new edge.
    671671//       Edge addEdge(Node h, Node t) { return INVALID; }
    … …  
    801801      void nextInEdge(Edge &e) const { }
    802802
    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(); }
    805805     
    806806

  • src/lemon/concept/graph_component.h

    r980 r986  
    243243      };
    244244
    245       ///Gives back the head node of an edge.
    246 
    247       ///Gives back the head node of an edge.
    248       ///
    249       Node head(const Edge&) const { return INVALID;}
    250 
    251       ///Gives back the tail node of an edge.
    252 
    253       ///Gives back the tail node 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;}
    256256    };
    257257
    … …  
    273273          Node n;
    274274          Edge e;
    275           n = graph.tail(e);
    276           n = graph.head(e);
     275          n = graph.source(e);
     276          n = graph.target(e);
    277277        }     
    278278      }

  • src/lemon/concept/path.h

    r967 r986  
    6767      /// Starting point of the path.
    6868      /// Returns INVALID if the path is empty.
    69       GraphNode/*It*/ head() const {return INVALID;}
     69      GraphNode/*It*/ target() const {return INVALID;}
    7070      /// \brief End point of the path.
    7171      ///
    7272      /// End point of the path.
    7373      /// Returns INVALID if the path is empty.
    74       GraphNode/*It*/ tail() const {return INVALID;}
     74      GraphNode/*It*/ source() const {return INVALID;}
    7575
    7676      /// \brief First NodeIt/EdgeIt.
    … …  
    8181      It& first(It &i) const { return i=It(*this); }
    8282
    83       /// \brief The head of an edge.
    84       ///
    85       /// Returns node iterator pointing to the head node of the
     83      /// \brief The target of an edge.
     84      ///
     85      /// Returns node iterator pointing to the target node of the
    8686      /// given edge iterator.
    87       NodeIt head(const EdgeIt& e) const {return INVALID;}
    88 
    89       /// \brief The tail of an edge.
    90       ///
    91       /// Returns node iterator pointing to the tail node of the
     87      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
    9292      /// given edge iterator.
    93       NodeIt tail(const EdgeIt& e) const {return INVALID;}
     93      NodeIt source(const EdgeIt& e) const {return INVALID;}
    9494
    9595

  • src/lemon/concept/sym_graph.h

    r959 r986  
    451451      SymEdgeIt& first(SymEdgeIt& i) const { return i; }
    452452
    453       ///Gives back the head node of an edge.
    454 
    455       ///Gives back the head node of an edge.
    456       ///
    457       Node head(Edge) const { return INVALID; }
    458       ///Gives back the tail node of an edge.
    459 
    460       ///Gives back the tail node 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; }
    463463 
    464464      ///Gives back the first node of an symmetric edge.
    … …  
    466466      ///Gives back the first node of an symmetric edge.
    467467      ///
    468       Node head(SymEdge) const { return INVALID; }
     468      Node target(SymEdge) const { return INVALID; }
    469469      ///Gives back the second node of an symmetric edge.
    470470
    471471      ///Gives back the second node of an symmetric edge.
    472472      ///
    473       Node tail(SymEdge) const { return INVALID; }
     473      Node source(SymEdge) const { return INVALID; }
    474474      ///Gives back the \e id of a node.
    475475
    … …  
    608608      ///Add a new edge to the graph.
    609609
    610       ///Add a new symmetric edge to the graph with tail node \c t
    611       ///and head node \c h.
     610      ///Add a new symmetric edge to the graph with source node \c t
     611      ///and target node \c h.
    612612      ///\return the new edge.
    613613      SymEdge addEdge(Node h, Node t) { return INVALID; }

  • src/lemon/concept/undir_graph.h

    r962 r986  
    4848
    4949        Node n;
    50         n = graph.head(ue);
    51         n = graph.tail(ue);
     50        n = graph.target(ue);
     51        n = graph.source(ue);
    5252
    5353        graph.first(ue);

  • src/lemon/concept_check.h

    r946 r986  
    2626    "inline" is used for ignore_unused_variable_warning()
    2727    and function_requires() to make sure there is no
    28     overhead with g++.
     28    overtarget with g++.
    2929  */
    3030

  • src/lemon/dfs.h

    r946 r986  
    207207      do {
    208208        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) {
    210210            predecessor->set(m,e);
    211211            pred_node->set(m,n);
    … …  
    215215          }
    216216          else ++Q[Qh];
    217         else if(--Qh>=0) n=G->tail(Q[Qh]);
     217        else if(--Qh>=0) n=G->source(Q[Qh]);
    218218      } while(Qh>=0);
    219219    }

  • src/lemon/dijkstra.h

    r959 r986  
    255255       
    256256        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
    257           Node w=G->head(e);
     257          Node w=G->target(e);
    258258          switch(heap.state(w)) {
    259259          case HeapType::PRE_HEAP:

  • src/lemon/dimacs.h

    r964 r986  
    209209
    210210    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;
    212212    }
    213213

  • src/lemon/full_graph.h

    r985 r986  
    7979    int maxId(Edge = INVALID) const { return EdgeNum-1; }
    8080
    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; }
    8383
    8484
    … …  
    137137     
    138138    protected:
    139       int id;  // NodeNum * head + tail;
     139      int id;  // NodeNum * target + source;
    140140
    141141      Edge(int _id) : id(_id) {}
    142142
    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) {}
    145145    public:
    146146      Edge() { }
    … …  
    251251    int maxId(Edge = INVALID) const { return EdgeNum-1; }
    252252
    253     Node tail(Edge e) const {
     253    Node source(Edge e) const {
    254254      /// \todo we may do it faster
    255255      return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;
    256256    }
    257257
    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;
    261261    }
    262262
    … …  
    316316     
    317317    protected:
    318       int id;  // NodeNum * head + tail;
     318      int id;  // NodeNum * target + source;
    319319
    320320      Edge(int _id) : id(_id) {}
    321321
    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) {}
    324324    public:
    325325      Edge() { }
    … …  
    352352    /// \todo with specialized iterators we can make faster iterating
    353353    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;
    358358    }
    359359
    … …  
    363363   
    364364    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;
    369369    }
    370370

  • src/lemon/graph_utils.h

    r977 r986  
    150150    if(prev==INVALID) g.first(e,u);
    151151    else ++e;
    152     while(e!=INVALID && g.tail(e)!=v) ++e;
     152    while(e!=INVALID && g.source(e)!=v) ++e;
    153153    return e;
    154154  }
    … …  
    193193                 const NodeBijection& _nb, EdgeBijection& _eb) {   
    194194    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)]);
    196196    }
    197197  }

  • src/lemon/graph_wrapper.h

    r970 r986  
    151151    void nextOut(Edge& i) const { graph->nextOut(i); }
    152152
    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))); }
    159159
    160160    int nodeNum() const { return graph->nodeNum(); }
    … …  
    162162 
    163163    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)); }
    166166
    167167    void erase(const Node& i) const { graph->erase(i); }
    … …  
    291291    }
    292292
    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); }
    297297
    298298    //    KEEP_MAPS(Parent, RevGraphWrapper);
    … …  
    626626  readDimacs(std::cin, g, length, s, t);
    627627
    628   cout << "edges with lengths (of form id, tail--length->head): " << endl;
     628  cout << "edges with lengths (of form id, source--length->target): " << endl;
    629629  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;
    632632
    633633  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
    … …  
    666666  for(EdgeIt e(g); e!=INVALID; ++e)
    667667    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;
    670670  \endcode
    671671  The program has the following (expected :-)) output:
    672672  \code
    673   edges with lengths (of form id, tail--length->head):
     673  edges with lengths (of form id, source--length->target):
    674674   9, 5--4->6
    675675   8, 4--2->6
    … …  
    757757    OutEdgeIt& next(OutEdgeIt& e) const {
    758758      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);
    760760        this->graph->next(e.out);
    761761        if (!this->graph->valid(e.out)) {
    … …  
    768768
    769769    Node aNode(const OutEdgeIt& e) const {
    770       if (e.out_or_in) return this->graph->tail(e); else
    771         return this->graph->head(e); }
     770      if (e.out_or_in) return this->graph->source(e); else
     771        return this->graph->target(e); }
    772772    Node bNode(const OutEdgeIt& e) const {
    773       if (e.out_or_in) return this->graph->head(e); else
    774         return this->graph->tail(e); }
     773      if (e.out_or_in) return this->graph->target(e); else
     774        return this->graph->source(e); }
    775775
    776776    //    KEEP_MAPS(Parent, UndirGraphWrapper);
    … …  
    938938      OutEdgeIt& operator++() {
    939939        if (!this->backward) {
    940           Node n=gw->tail(*this);
     940          Node n=gw->source(*this);
    941941          *(static_cast<GraphEdge*>(this))=
    942942            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    … …  
    995995      InEdgeIt& operator++() {
    996996        if (!this->backward) {
    997           Node n=gw->tail(*this);
     997          Node n=gw->source(*this);
    998998          *(static_cast<GraphEdge*>(this))=
    999999            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    … …  
    10901090 
    10911091
    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)); }
    10961096
    10971097    /// Gives back the opposite edge.
    … …  
    14141414//     }
    14151415    void erase(const Edge& e) const {
    1416       Node n=tail(e);
     1416      Node n=source(e);
    14171417      typename Graph::OutEdgeIt f(*Parent::graph, n);
    14181418      ++f;

  • src/lemon/kruskal.h

    r921 r986  
    8383    for (typename IN::const_iterator p = in.begin();
    8484         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)) ) {
    8787        out.set((*p).first, true);
    8888        tot_cost += (*p).second;

  • src/lemon/list_graph.h

    r980 r986  
    4444 
    4545    struct EdgeT {
    46       int head, tail;
     46      int target, source;
    4747      int prev_in, prev_out;
    4848      int next_in, next_out;
    … …  
    112112    int maxId(Edge = INVALID) const { return edges.size()-1; }
    113113
    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; }
    116116
    117117
    … …  
    138138      } else {
    139139        int n;
    140         for(n = nodes[edges[edge.id].head].next;
     140        for(n = nodes[edges[edge.id].target].next;
    141141          n!=-1 && nodes[n].first_in == -1;
    142142          n = nodes[n].next);
    … …  
    199199      }
    200200     
    201       edges[n].tail = u.id;
    202       edges[n].head = v.id;
     201      edges[n].source = u.id;
     202      edges[n].target = v.id;
    203203
    204204      edges[n].next_out = nodes[u.id].first_out;
    … …  
    247247        edges[edges[n].prev_in].next_in = edges[n].next_in;
    248248      } else {
    249         nodes[edges[n].head].first_in = edges[n].next_in;
     249        nodes[edges[n].target].first_in = edges[n].next_in;
    250250      }
    251251
    … …  
    258258        edges[edges[n].prev_out].next_out = edges[n].next_out;
    259259      } else {
    260         nodes[edges[n].tail].first_out = edges[n].next_out;
     260        nodes[edges[n].source].first_out = edges[n].next_out;
    261261      }
    262262     
    … …  
    273273
    274274  protected:
    275     void _moveHead(Edge e, Node n)
     275    void _moveTarget(Edge e, Node n)
    276276    {
    277277      if(edges[e.id].next_in != -1)
    … …  
    279279      if(edges[e.id].prev_in != -1)
    280280        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;
    283283      edges[e.id].prev_in = -1;
    284284      edges[e.id].next_in = nodes[n.id].first_in;
    285285      nodes[n.id].first_in = e.id;
    286286    }
    287     void _moveTail(Edge e, Node n)
     287    void _moveSource(Edge e, Node n)
    288288    {
    289289      if(edges[e.id].next_out != -1)
    … …  
    291291      if(edges[e.id].prev_out != -1)
    292292        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;
    295295      edges[e.id].prev_out = -1;
    296296      edges[e.id].next_out = nodes[n.id].first_out;
    … …  
    321321  {
    322322  public:
    323     /// Moves the head of \c e to \c n
    324 
    325     /// Moves the head of \c e to \c n
     323    /// Moves the target of \c e to \c n
     324
     325    /// Moves the target of \c e to \c n
    326326    ///
    327     void moveHead(Edge e, Node n) { _moveHead(e,n); }
    328     /// Moves the tail of \c e to \c n
    329 
    330     /// Moves the tail of \c e to \c n
     327    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
    331331    ///
    332     void moveTail(Edge e, Node n) { _moveTail(e,n); }
     332    void moveSource(Edge e, Node n) { _moveSource(e,n); }
    333333
    334334    ///Using this it possible to avoid the superfluous memory allocation.

  • src/lemon/min_cost_flow.h

    r941 r986  
    104104      ValueType operator[](typename ResGW::Edge e) const {     
    105105        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)]);   
    107107        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)]);   
    109109      }     
    110110       
    … …  
    236236        for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
    237237        //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)];
    239239        fl_e = flow[e];
    240240        if (0<fl_e && fl_e<capacity[e]) {

  • src/lemon/path.h

    r959 r986  
    112112    /// Starting point of the path.
    113113    /// 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]);
    116116    }
    117117    /// \brief End point of the path.
    … …  
    119119    /// End point of the path.
    120120    /// 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]);
    123123    }
    124124
    … …  
    140140    }
    141141
    142     /// \brief Returns node iterator pointing to the head node of the
     142    /// \brief Returns node iterator pointing to the target node of the
    143143    /// given edge iterator.
    144     NodeIt head(const EdgeIt& e) const {
     144    NodeIt target(const EdgeIt& e) const {
    145145      return NodeIt(*this, e.idx+1);
    146146    }
    147147
    148     /// \brief Returns node iterator pointing to the tail node of the
     148    /// \brief Returns node iterator pointing to the source node of the
    149149    /// given edge iterator.
    150     NodeIt tail(const EdgeIt& e) const {
     150    NodeIt source(const EdgeIt& e) const {
    151151      return NodeIt(*this, e.idx);
    152152    }
    … …  
    231231      operator const GraphNode& () const {
    232232        if(idx >= p->length())
    233           return p->head();
     233          return p->target();
    234234        else if(idx >= 0)
    235           return p->gr->tail(p->edges[idx]);
     235          return p->gr->source(p->edges[idx]);
    236236        else
    237237          return INVALID;
    … …  
    336336      }
    337337
    338       GraphNode tail() const {
     338      GraphNode source() const {
    339339        if( ! front.empty() )
    340           return P.gr->tail(front[front.size()-1]);
     340          return P.gr->source(front[front.size()-1]);
    341341        else if( ! P.empty() )
    342           return P.gr->tail(P.edges[0]);
     342          return P.gr->source(P.edges[0]);
    343343        else if( ! back.empty() )
    344           return P.gr->tail(back[0]);
     344          return P.gr->source(back[0]);
    345345        else
    346346          return INVALID;
    347347      }
    348       GraphNode head() const {
     348      GraphNode target() const {
    349349        if( ! back.empty() )
    350           return P.gr->head(back[back.size()-1]);
     350          return P.gr->target(back[back.size()-1]);
    351351        else if( ! P.empty() )
    352           return P.gr->head(P.edges[P.length()-1]);
     352          return P.gr->target(P.edges[P.length()-1]);
    353353        else if( ! front.empty() )
    354           return P.gr->head(front[0]);
     354          return P.gr->target(front[0]);
    355355        else
    356356          return INVALID;
    … …  
    438438    /// Starting point of the path.
    439439    /// 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]);
    442442    }
    443443    /// \brief End point of the path.
    … …  
    445445    /// End point of the path.
    446446    /// 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]);
    449449    }
    450450
    … …  
    478478    }
    479479
    480     /// \brief Returns node iterator pointing to the head node of the
     480    /// \brief Returns node iterator pointing to the target node of the
    481481    /// given edge iterator.
    482     NodeIt head(const EdgeIt& e) const {
     482    NodeIt target(const EdgeIt& e) const {
    483483      return NodeIt(*this, e.idx+1);
    484484    }
    485485
    486     /// \brief Returns node iterator pointing to the tail node of the
     486    /// \brief Returns node iterator pointing to the source node of the
    487487    /// given edge iterator.
    488     NodeIt tail(const EdgeIt& e) const {
     488    NodeIt source(const EdgeIt& e) const {
    489489      return NodeIt(*this, e.idx);
    490490    }
    … …  
    571571      operator const GraphNode& () const {
    572572        if(idx >= p->length())
    573           return p->head();
     573          return p->target();
    574574        else if(idx >= 0)
    575           return p->gr->tail(p->edges[idx]);
     575          return p->gr->source(p->edges[idx]);
    576576        else
    577577          return INVALID;
    … …  
    677677      }
    678678
    679       GraphNode tail() const {
     679      GraphNode source() const {
    680680        if( ! front.empty() )
    681           return P.gr->tail(front[front.size()-1]);
     681          return P.gr->source(front[front.size()-1]);
    682682        else if( ! P.empty() )
    683           return P.gr->tail(P.edges[0]);
     683          return P.gr->source(P.edges[0]);
    684684        else if( ! back.empty() )
    685           return P.gr->tail(back[0]);
     685          return P.gr->source(back[0]);
    686686        else
    687687          return INVALID;
    688688      }
    689       GraphNode head() const {
     689      GraphNode target() const {
    690690        if( ! back.empty() )
    691           return P.gr->head(back[back.size()-1]);
     691          return P.gr->target(back[back.size()-1]);
    692692        else if( ! P.empty() )
    693           return P.gr->head(P.edges[P.length()-1]);
     693          return P.gr->target(P.edges[P.length()-1]);
    694694        else if( ! front.empty() )
    695           return P.gr->head(front[0]);
     695          return P.gr->target(front[0]);
    696696        else
    697697          return INVALID;

  • src/lemon/preflow.h

    r977 r986  
    306306        for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
    307307          if ( (*capacity)[e] <= (*flow)[e] ) continue;
    308           Node u=g->tail(e);
     308          Node u=g->source(e);
    309309          if ( level[u] >= n ) {
    310310            bfs_queue.push(u);
    … …  
    319319        for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
    320320          if ( 0 >= (*flow)[e] ) continue;
    321           Node u=g->head(e);
     321          Node u=g->target(e);
    322322          if ( level[u] >= n ) {
    323323            bfs_queue.push(u);
    … …  
    411411       
    412412        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    413           Node v=g->head(e);
     413          Node v=g->target(e);
    414414          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    415415            queue.push(v);
    … …  
    419419       
    420420        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    421           Node v=g->tail(e);
     421          Node v=g->source(e);
    422422          if (!M[v] && (*flow)[e] > 0 ) {
    423423            queue.push(v);
    … …  
    449449
    450450        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    451           Node v=g->tail(e);
     451          Node v=g->source(e);
    452452          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    453453            queue.push(v);
    … …  
    457457
    458458        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    459           Node v=g->head(e);
     459          Node v=g->target(e);
    460460          if (M[v] && (*flow)[e] > 0 ) {
    461461            queue.push(v);
    … …  
    516516      for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    517517        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    518         Node v=g->head(e);
     518        Node v=g->target(e);
    519519
    520520        if( lev > level[v] ) { //Push is allowed now
    … …  
    548548         
    549549          if( (*flow)[e] <= 0 ) continue;
    550           Node v=g->tail(e);
     550          Node v=g->source(e);
    551551
    552552          if( lev > level[v] ) { //Push is allowed now
    … …  
    603603          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
    604604            if ( (*capacity)[e] <= (*flow)[e] ) continue;
    605             Node w=g->tail(e);
     605            Node w=g->source(e);
    606606            if ( level[w] == n && w != s ) {
    607607              bfs_queue.push(w);
    … …  
    616616          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
    617617            if ( 0 >= (*flow)[e] ) continue;
    618             Node w=g->head(e);
     618            Node w=g->target(e);
    619619            if ( level[w] == n && w != s ) {
    620620              bfs_queue.push(w);
    … …  
    647647         
    648648          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
    649             Node w=g->tail(e);
     649            Node w=g->source(e);
    650650            if ( level[w] == n && w != s ) {
    651651              bfs_queue.push(w);
    … …  
    663663          Num c=(*capacity)[e];
    664664          if ( c <= 0 ) continue;
    665           Node w=g->head(e);
     665          Node w=g->target(e);
    666666          if ( level[w] < n ) {
    667667            if ( excess[w] <= 0 && w!=t ) { //putting into the stack
    … …  
    688688          Num rem=(*capacity)[e]-(*flow)[e];
    689689          if ( rem <= 0 ) continue;
    690           Node w=g->head(e);
     690          Node w=g->target(e);
    691691          if ( level[w] < n ) {
    692692            if ( excess[w] <= 0 && w!=t ) { //putting into the stack
    … …  
    701701        for(InEdgeIt e(*g,s); e!=INVALID; ++e) {
    702702          if ( (*flow)[e] <= 0 ) continue;
    703           Node w=g->tail(e);
     703          Node w=g->source(e);
    704704          if ( level[w] < n ) {
    705705            if ( excess[w] <= 0 && w!=t ) {
    … …  
    718718          Num rem=(*capacity)[e]-(*flow)[e];
    719719          if ( rem <= 0 ) continue;
    720           Node w=g->head(e);
     720          Node w=g->target(e);
    721721          if ( level[w] < n ) flow->set(e, (*capacity)[e]);
    722722        }
    … …  
    724724        for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
    725725          if ( (*flow)[e] <= 0 ) continue;
    726           Node w=g->tail(e);
     726          Node w=g->source(e);
    727727          if ( level[w] < n ) flow->set(e, 0);
    728728        }

  • src/lemon/smart_graph.h

    r980 r986  
    5656    struct EdgeT
    5757    {
    58       int head, tail, next_in, next_out;     
     58      int target, source, next_in, next_out;     
    5959      //FIXME: is this necessary?
    6060      EdgeT() : next_in(-1), next_out(-1) {} 
    … …  
    9898    int maxId(Edge = INVALID) const { return edges.size()-1; }
    9999
    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; }
    102102
    103103    /// Node ID.
    … …  
    128128    Edge addEdge(Node u, Node v) {
    129129      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;
    131131      edges[e.n].next_out=nodes[u.n].first_out;
    132132      edges[e.n].next_in=nodes[v.n].first_in;
    … …  
    212212    {
    213213      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;
    215215      prev.n=e;
    216216      return prev;
    … …  
    308308      while(s.edge_num>edges.size()) {
    309309        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;
    312312        edges.pop_back();
    313313      }

  • src/lemon/suurballe.h

    r968 r986  
    134134            ++e;
    135135          }
    136           n = G.head(e);
     136          n = G.target(e);
    137137          paths[j].push_back(e);
    138138          //total_length += length[e];

  • src/lemon/undir_graph_extender.h

    r981 r986  
    7171    }
    7272
    73     /// Tail of 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);
    7676    }
    7777
    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"
    7979    /// or something???
    80     using Parent::tail;
     80    using Parent::source;
    8181
    82     /// Head of 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);
    8585    }
    8686
    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"
    8888    /// or something???
    89     using Parent::head;
     89    using Parent::target;
    9090
    9191    /// Returns whether the given directed edge is same orientation as the
    … …  
    9797
    9898    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);
    103103      else
    104104        return INVALID;
    … …  
    148148        Parent::nextOut(e);
    149149        if( UndirEdge(e) == INVALID ) {
    150           Parent::firstIn(e, Parent::tail(e));
     150          Parent::firstIn(e, Parent::source(e));
    151151          e.forward = false;
    152152        }
    … …  
    160160        Parent::nextIn(e);
    161161        if( UndirEdge(e) == INVALID ) {
    162           Parent::firstOut(e, Parent::head(e));
     162          Parent::firstOut(e, Parent::target(e));
    163163          e.forward = false;
    164164        }

  • src/test/bfs_test.cc

    r959 r986  
    8484
    8585  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);
    8888    check( !bfs_test.reached(u) ||
    8989           (bfs_test.dist(v) > bfs_test.dist(u)+1),
    … …  
    9595    if ( bfs_test.pred(v)!=INVALID ) {
    9696      Edge e=bfs_test.pred(v);
    97       Node u=G.tail(e);
     97      Node u=G.source(e);
    9898      check(u==bfs_test.predNode(v),"Wrong tree.");
    9999      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,

  • src/test/dfs_test.cc

    r959 r986  
    8484    if ( dfs_test.pred(v)!=INVALID ) {
    8585      Edge e=dfs_test.pred(v);
    86       Node u=G.tail(e);
     86      Node u=G.source(e);
    8787      check(u==dfs_test.predNode(v),"Wrong tree.");
    8888      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,

  • src/test/dijkstra_heap_test.cc

    r921 r986  
    7474  EdgeIt e;
    7575  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);
    7878    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
    7979      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= "
    8181                 <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
    8282          - cap[e]<<std::endl;
    … …  
    8989    if ( dijkstra_test.reached(v) ) {
    9090      Edge e=dijkstra_test.pred(v);
    91       Node u=G.tail(e);
     91      Node u=G.source(e);
    9292      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
    9393        std::cout<<"Error in a shortest path tree edge! Difference: "
    … …  
    123123
    124124  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);
    127127    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
    128128      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= "
    130130                 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
    131131          - cap[e]<<std::endl;
    … …  
    137137    if ( dijkstra_test2.reached(v) ) {
    138138      Edge e=dijkstra_test2.pred(v);
    139       Node u=G.tail(e);
     139      Node u=G.source(e);
    140140      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
    141141        std::cout<<"Error in a shortest path tree edge! Difference: "

  • src/test/dijkstra_test.cc

    r959 r986  
    9494
    9595  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);
    9898    check( !dijkstra_test.reached(u) ||
    9999           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
    100            "dist(head)-dist(tail)- edge_length= "
     100           "dist(target)-dist(source)- edge_length= "
    101101           << dijkstra_test.dist(v) - dijkstra_test.dist(u)
    102102           - cap[e]);
    … …  
    108108    if ( dijkstra_test.pred(v)!=INVALID ) {
    109109      Edge e=dijkstra_test.pred(v);
    110       Node u=G.tail(e);
     110      Node u=G.source(e);
    111111      check(u==dijkstra_test.predNode(v),"Wrong tree.");
    112112      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],

  • src/test/graph_factory_test.cc

    r959 r986  
    2929This test makes consistency checks of list graph structures.
    3030
    31 G.addNode(), G.addEdge(), G.tail(), G.head()
     31G.addNode(), G.addEdge(), G.source(), G.target()
    3232
    3333\todo Checks for empty graphs and isolated points.
    … …  
    4949
    5050  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));
    5252}
    5353

  • src/test/graph_test.h

    r946 r986  
    5454    for(int i=0;i<nn;i++) {
    5555      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.");
    5757      ++e;
    5858    }
    … …  
    6666    for(int i=0;i<nn;i++) {
    6767      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.");
    6969      ++e;
    7070    }
    … …  
    8282
    8383  ///\file
    84   ///\todo Check head(), tail() as well;
     84  ///\todo Check target(), source() as well;
    8585
    8686 

  • src/test/path_test.cc

    r959 r986  
    4848  P.clear();                      //void clear() {}
    4949
    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;}
    5252
    5353  ei=P.first(ei);                 //It& first(It &i) const { return i=It(*this); }
    5454
    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 {}
    5757
    5858

  • src/test/preflow_test.cc

    r959 r986  
    6868  int c=0;
    6969  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];
    7171  }
    7272  return c;

  • src/test/sym_graph_test.cc

    r959 r986  
    3131This test makes consistency checks of list graph structures.
    3232
    33 G.addNode(), G.addEdge(), G.tail(), G.head()
     33G.addNode(), G.addEdge(), G.source(), G.target()
    3434
    3535\todo Checks for empty graphs and isolated points.

  • src/test/sym_graph_test.h

    r959 r986  
    7474        SymEdge se;
    7575        se=INVALID;
    76         n=G.tail(se);
    77         n=G.head(se);
     76        n=G.source(se);
     77        n=G.target(se);
    7878      }
    7979      // id tests
    … …  
    175175
    176176  ///\file
    177   ///\todo Check head(), tail() as well;
     177  ///\todo Check target(), source() as well;
    178178
    179179 

  • src/test/test_tools.h

    r978 r986  
    106106
    107107  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));
    109109}
    110110

  • src/work/alpar/bfs-named-param.cc

    r945 r986  
    1111struct _BFS_CUSTOM_VIS {};
    1212
    13 template<class GT,class VT,class DVT,class PNT,class PET,class PT >
    14 class _BFS
     13
     14class _Bfs_Traits
     15{
     16  typedef ListGraph Graph;
     17}
     18
     19template<class T>
     20class _Bfs
    1521{
    1622 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;
    2330 
    2431  typedef typename Graph::Node Node;
    2532  typedef typename Graph::OutEdgeIt OutEdgeIt;
    2633
    27   typedef DVT DefaultVisitedTag;
    28  
    2934  const Graph &_graph;
    3035
    3136  Node _source;
    3237 
    33   Visited *_visited;
     38  Reached *_visited;
    3439  PredNode _predNode;
    3540  PredEdge _predEdge;
    3641  Priority _priority;
    3742
    38   _BFS(const Graph &g,
     43  _Bfs(const Graph &g,
    3944       Node s,
    40        Visited *v,
     45       Reached *v,
    4146       PredNode &pn,
    4247       PredEdge &pe,
    … …  
    4651
    4752 
    48   int run(const _BFS_CUSTOM_VIS &)
     53  int run(const _Bfs_CUSTOM_VIS &)
    4954  {
    5055    using namespace std;
    … …  
    6469      Node n=Q[Qt++];
    6570      for(OutEdgeIt e(_graph,n);e!=INVALID;++e)
    66         if(!(*_visited)[m=_graph.head(e)]) {
     71        if(!(*_visited)[m=_graph.target(e)]) {
    6772          Q[Qh++]=m;
    6873          _visited->set(m,true);
    … …  
    7681  int run(const _BFS_DEFAULT_VIS &)
    7782  {
    78     _visited= new Visited(_graph);
     83    _visited= new Reached(_graph);
    7984    int r = run(_BFS_CUSTOM_VIS());
    8085    delete _visited;
    8186    return r;
    8287  }
    83   int run() { return run(DefaultVisitedTag());}
    84 
    85   template<class T> _BFS<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>
    8691  setVisitMap(T &t)
    8792  {
    88     return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
     93    return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
    8994      (_graph,_source,&t,_predNode,_predEdge,_priority);
    9095  }
    9196
    9297  template<class T>
    93   _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
     98  _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
    9499  setPredNodeMap(T &t)
    95100  {
    96     return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
     101    return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
    97102      (_graph,_source,
    98103       _visited,
    … …  
    101106
    102107  template<class T>
    103   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
     108  _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>
    104109  setPredEdgeMap(T &t)
    105110  {
    106     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
     111    return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>
    107112      (_graph,_source,
    108113       _visited,
    … …  
    110115  }
    111116
    112   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
     117  _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
    113118  setNothing()
    114119  {
    115     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
     120    return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
    116121      (_graph,_source,
    117122       _visited,
    … …  
    122127
    123128template<class G>
    124 _BFS<G,
     129_Bfs<G,
    125130     typename G::template NodeMap<bool>,
    126131     _BFS_DEFAULT_VIS,
    … …  
    132137  //  typename G::template NodeMap<bool> v(g);
    133138
    134   return _BFS < G,
     139  return _Bfs < G,
    135140    typename G::template NodeMap<bool>,
    136141    _BFS_DEFAULT_VIS,
    … …  
    147152
    148153
    149 class MyVisitedMap : public SmartGraph::NodeMap<bool>
     154class MyReachedMap : public SmartGraph::NodeMap<bool>
    150155{
    151156  const SmartGraph &_G;
    152157public:
    153   MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
     158  MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
    154159  void set(SmartGraph::Node n,bool b)
    155160  {
    … …  
    181186  SmartGraph::NodeMap<SmartGraph::Edge> em(G);
    182187
    183   MyVisitedMap vm(G);
     188  MyReachedMap vm(G);
    184189
    185190

  • src/work/alpar/boolmap_iter.cc

    r921 r986  
    120120
    121121  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))
    123123      << ": " << map[e] << '\n';
    124124  std::cout << "True Edges:\n";
    125125  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';
    127127  std::cout << "False Edges:\n";
    128128  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';
    130130}
    131131

  • src/work/alpar/dijkstra.h

    r967 r986  
    394394       
    395395        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
    396           Node w=G->head(e);
     396          Node w=G->target(e);
    397397          switch(heap.state(w)) {
    398398          case Heap::PRE_HEAP:

  • src/work/alpar/f_ed_ka.h

    r921 r986  
    8585      c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));
    8686    //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));
    8888    while(gn!=s) if(visited.get(gn)==1)
    8989      {
    9090        //FIXME: nonstandard gcc extension!
    9191        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));
    9393      }
    9494    else {
    9595      //FIXME: nonstandard gcc extension!
    9696      aug_val <?= f.get(tree.get(gn));
    97       gn=G.head(tree.get(gn));
     97      gn=G.target(tree.get(gn));
    9898    }
    9999       
    … …  
    103103      {
    104104        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));
    106106      }
    107107    else {
    108108      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));
    110110    }
    111111

  • src/work/alpar/f_ed_ka_demo.cc

    r921 r986  
    4242  //std::cout << "maximum flow: "<< std::endl;
    4343  //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)<<") ";
    4545  //}
    4646  //std::cout<<std::endl;

  • src/work/alpar/graph.h

    r253 r986  
    107107      // Lehet, hogy ez a ketto nem kell!!!
    108108     
    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;}
    111111      NodeIterator opposite(const NodeIterator &n) const
    112       {return n==tail()?head():tail();}
     112      {return n==source()?target():source();}
    113113     
    114114      bool valid() {return e;}
    … …  
    191191      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
    192192     
    193       NodeIterator aNode() const {return tail();}
    194       NodeIterator bNode() const {return head();}
     193      NodeIterator aNode() const {return source();}
     194      NodeIterator bNode() const {return target();}
    195195     
    196196      operator const InEdgeIterator ()
    … …  
    219219     
    220220      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();}
    222222     
    223223      operator const InEdgeIterator ()
    … …  
    255255     
    256256      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();}
    258258     
    259259      operator const EdgeIterator ()
    … …  
    464464    {
    465465      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();
    468468    }
    469469    void setRevert(int n,bool r=true) {reversed[n]=r;}
    … …  
    471471    {
    472472      path[n]=i;
    473       reversed[n] = i.head()==i.aNode();
     473      reversed[n] = i.target()==i.aNode();
    474474    }
    475475    void setEdge(int n,EdgeIterator i,bool r)
    … …  
    479479    }
    480480
    481     NodeIterator tail() { return getNode(0); }
    482     NodeIterator head() { return getNode(getLength()); }
     481    NodeIterator source() { return getNode(0); }
     482    NodeIterator target() { return getNode(getLength()); }
    483483  };
    484484 

  • src/work/alpar/gwrapper.h

    r921 r986  
    2828  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    2929
    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); }
    3434 
    3535  template<typename I> NodeIt aNode(const I e);
    … …  
    8484  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    8585
    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); }
    9090 
    9191  template<typename I> NodeIt aNode(const I e);
    … …  
    138138//   template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    139139
    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); }
    144144 
    145145//   template<typename I> NodeIt aNode(const I e);
    … …  
    195195  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    196196
    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); }
    201201 
    202202  template<typename I> NodeIt aNode(const I e);
    … …  
    344344  template<typename I> I next(const I i); { return graph->goNext(i); }
    345345
    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); }
    350350 
    351351  template<typename I> NodeIt aNode(const I e);

  • src/work/alpar/list_graph_demo.cc

    r959 r986  
    112112    for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e);
    113113    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);
    115115   
    116116    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))
    118118                << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e))
    119119                << " em=" << em[e]

  • src/work/alpar/rw_nonref_map.cc

    r921 r986  
    2424    {
    2525      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)) << ": ";
    2828      std::cin  >> tmp;
    2929      return tmp;
    … …  
    3131    ValueType operator = (ValueType v) const
    3232    {
    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';
    3535      return v;
    3636    }

  • src/work/alpar/smart_graph_demo.cc

    r921 r986  
    112112    for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e);
    113113    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);
    115115   
    116116    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))
    118118                << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e))
    119119                << " em=" << em[e]

  • src/work/athos/bfs_test.cc

    r921 r986  
    4242      OutEdgeIt e;
    4343      for(g.first(e,v); g.valid(e); g.next(e)) {
    44         Node w=g.head(e);
     44        Node w=g.target(e);
    4545        if (!reached[w]) {
    4646          bfs_queue.push(w);

  • src/work/athos/dijkstra_demo.cc

    r921 r986  
    130130    std::cout << "out edges: ";
    131131    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)) << " ";
    133133    std::cout << "in edges: ";
    134134    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)) << " ";
    136136    std::cout << std::endl;
    137137  }

  • src/work/athos/mincostflow.h

    r921 r986  
    7474      ValueType operator[](typename ResGraph::Edge e) const {     
    7575        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)]);   
    7777        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)]);   
    7979      }     
    8080       
    … …  
    259259          while ( i != nonabundant_arcs.end() ){
    260260            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));
    263263              //Merge
    264264              if (a != b){
    … …  
    285285                  while (n!=non_root){
    286286                    e = bfs_pred[n];
    287                     n = res_graph.tail(e);
     287                    n = res_graph.source(e);
    288288                    res_graph.augment(e,qty_to_augment);
    289289                  }
    … …  
    455455      FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
    456456        //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)];
    458458        fl_e = flow[e];
    459459        //      std::cout << fl_e << std::endl;
    … …  
    484484          return false;
    485485        }
    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];
    488488      }
    489489      //write_property_vector(supdem, "supdem");

  • src/work/athos/old/minlengthpaths.h

    r921 r986  
    5454       
    5555      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 ){
    5757        //  std::cout<<"Negative length!!"<<std::endl;
    5858        //}
    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)]);   
    6060      }     
    6161       
    … …  
    162162            G.next(e);
    163163          }
    164           n = G.head(e);
     164          n = G.target(e);
    165165          paths[j].push_back(e);
    166166          total_length += length[e];

  • src/work/athos/preflow_push_wogw.h

    r921 r986  
    140140    //This private procedure is supposed to modify the preflow on edge j
    141141    //by value v (which can be positive or negative as well)
    142     //and maintain the excess on the head and tail
     142    //and maintain the excess on the target and source
    143143    //Here we do not check whether this is possible or not
    144144    void modify_preflow(Edge j, const T& v){
    … …  
    148148
    149149
    150       //Modifiyng the head
    151       modify_excess(G.head(j),v);
    152        
    153       //Modifiyng the tail
    154       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);
    155155
    156156    }
    … …  
    273273        InEdgeIt e;
    274274        for(G.first(e,v); G.valid(e); G.next(e)) {
    275           Node w=G.tail(e);
     275          Node w=G.source(e);
    276276          if ( level[w] == number_of_nodes && w != s ) {
    277277            bfs_queue.push(w);
    … …  
    311311      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){
    312312        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)];
    315315        if(highest_active<lev){
    316316          highest_active=lev;
    … …  
    326326
    327327      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){
    329329          return true;
    330330        }
    331331        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)];
    334334        }
    335335      }
    … …  
    342342     
    343343      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){
    345345         
    346346          return true;
    347347        }
    348348        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)];
    351351        }
    352352       
    … …  
    389389              e -= v;
    390390              //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));
    393393              }
    394394              modify_preflow(j,v);
    … …  
    405405              e -= v;
    406406              //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));
    409409              }
    410410              modify_preflow(j,-v);

  • src/work/deba/list_graph.h

    r921 r986  
    4444    struct EdgeT
    4545    {
    46       int head, tail;
     46      int target, source;
    4747      int prev_in, prev_out;
    4848      int next_in, next_out;
    … …  
    105105    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
    106106
    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; }
    115115
    116116    NodeIt& first(NodeIt& v) const {
    … …  
    152152      else {
    153153        int n;
    154         for(n=nodes[edges[it.n].head].next;
     154        for(n=nodes[edges[it.n].target].next;
    155155            n!=-1 && nodes[n].first_in == -1;
    156156            n = nodes[n].next) ;
    … …  
    208208      }
    209209     
    210       edges[n].tail = u.n; edges[n].head = v.n;
     210      edges[n].source = u.n; edges[n].target = v.n;
    211211
    212212      edges[n].next_out = nodes[u.n].first_out;
    … …  
    233233      if(edges[n].prev_in!=-1)
    234234        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;
    236236     
    237237      if(edges[n].next_out!=-1)
    … …  
    239239      if(edges[n].prev_out!=-1)
    240240        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;
    242242     
    243243      edges[n].next_in = first_free_edge;

  • src/work/jacint/max_flow.h

    r921 r986  
    327327        OutEdgeIt e;
    328328        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    329           Node v=g->head(e);
     329          Node v=g->target(e);
    330330          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    331331            queue.push(v);
    … …  
    336336        InEdgeIt f;
    337337        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    338           Node v=g->tail(f);
     338          Node v=g->source(f);
    339339          if (!M[v] && (*flow)[f] > 0 ) {
    340340            queue.push(v);
    … …  
    371371        InEdgeIt e;
    372372        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    373           Node v=g->tail(e);
     373          Node v=g->source(e);
    374374          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    375375            queue.push(v);
    … …  
    380380        OutEdgeIt f;
    381381        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    382           Node v=g->head(f);
     382          Node v=g->target(f);
    383383          if (M[v] && (*flow)[f] > 0 ) {
    384384            queue.push(v);
    … …  
    434434
    435435        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    436         Node v=g->head(e);
     436        Node v=g->target(e);
    437437
    438438        if( lev > level[v] ) { //Push is allowed now
    … …  
    467467
    468468          if( (*flow)[e] <= 0 ) continue;
    469           Node v=g->tail(e);
     469          Node v=g->source(e);
    470470
    471471          if( lev > level[v] ) { //Push is allowed now
    … …  
    522522            InEdgeIt e;
    523523            for(g->first(e,v); g->valid(e); g->next(e)) {
    524               Node w=g->tail(e);
     524              Node w=g->source(e);
    525525              if ( level[w] == n && w != s ) {
    526526                bfs_queue.push(w);
    … …  
    540540              Num c=(*capacity)[e];
    541541              if ( c <= 0 ) continue;
    542               Node w=g->head(e);
     542              Node w=g->target(e);
    543543              if ( level[w] < n ) {
    544544                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    567567            for(g->first(e,v); g->valid(e); g->next(e)) {
    568568              if ( (*capacity)[e] <= (*flow)[e] ) continue;
    569               Node w=g->tail(e);
     569              Node w=g->source(e);
    570570              if ( level[w] == n && w != s ) {
    571571                bfs_queue.push(w);
    … …  
    581581            for(g->first(f,v); g->valid(f); g->next(f)) {
    582582              if ( 0 >= (*flow)[f] ) continue;
    583               Node w=g->head(f);
     583              Node w=g->target(f);
    584584              if ( level[w] == n && w != s ) {
    585585                bfs_queue.push(w);
    … …  
    600600              Num rem=(*capacity)[e]-(*flow)[e];
    601601              if ( rem <= 0 ) continue;
    602               Node w=g->head(e);
     602              Node w=g->target(e);
    603603              if ( level[w] < n ) {
    604604                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    612612            {
    613613              if ( (*flow)[f] <= 0 ) continue;
    614               Node w=g->tail(f);
     614              Node w=g->source(f);
    615615              if ( level[w] < n ) {
    616616                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    711711      //        return dist[n]; }
    712712      //       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))); }
    714714      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)]);
    716716      }
    717717    };
    … …  
    861861      for(g->first(e,v); g->valid(e); g->next(e)) {
    862862        if ( (*capacity)[e] <= (*flow)[e] ) continue;
    863         Node u=g->tail(e);
     863        Node u=g->source(e);
    864864        if ( level[u] >= n ) {
    865865          bfs_queue.push(u);
    … …  
    872872      for(g->first(f,v); g->valid(f); g->next(f)) {
    873873        if ( 0 >= (*flow)[f] ) continue;
    874         Node u=g->head(f);
     874        Node u=g->target(f);
    875875        if ( level[u] >= n ) {
    876876          bfs_queue.push(u);
    … …  
    926926      ResGWOutEdgeIt e=bfs;
    927927      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);
    930930        pred.set(w, e);
    931931        if (res_graph.valid(pred[v])) {
    … …  
    934934          free.set(w, res_graph.resCap(e));
    935935        }
    936         if (res_graph.head(e)==t) { _augment=true; break; }
     936        if (res_graph.target(e)==t) { _augment=true; break; }
    937937      }
    938938
    … …  
    946946        ResGWEdge e=pred[n];
    947947        res_graph.augment(e, augment_value);
    948         n=res_graph.tail(e);
     948        n=res_graph.source(e);
    949949      }
    950950    }
    … …  
    984984      ResGWOutEdgeIt e=bfs;
    985985      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);
    988988        pred.set(w, e);
    989989        if (res_graph.valid(pred[v])) {
    … …  
    992992          free.set(w, res_graph.resCap(e));
    993993        }
    994         if (res_graph.head(e)==t) { _augment=true; break; }
     994        if (res_graph.target(e)==t) { _augment=true; break; }
    995995      }
    996996
    … …  
    10041004        ResGWEdge e=pred[n];
    10051005        res_graph.augment(e, augment_value);
    1006         n=res_graph.tail(e);
     1006        n=res_graph.source(e);
    10071007      }
    10081008    }
    … …  
    10511051      if (res_graph.valid(e)) {
    10521052        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)]);
    10561056          original_edge.update();
    10571057          original_edge.set(f, e);
    … …  
    10591059          residual_capacity.set(f, res_graph.resCap(e));
    10601060        } 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)]);
    10641064            original_edge.update();
    10651065            original_edge.set(f, e);
    … …  
    11151115          typename MG::Edge e=pred[n];
    11161116          res_graph.augment(original_edge[e], augment_value);
    1117           n=F.tail(e);
     1117          n=F.source(e);
    11181118          if (residual_capacity[e]==augment_value)
    11191119            F.erase(e);
    … …  
    11481148      ResGWOutEdgeIt e=bfs;
    11491149      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);
    11511151      }
    11521152      ++bfs;
    … …  
    12481248          typename ErasingResGW::OutEdgeIt e=pred[n];
    12491249          res_graph.augment(e, augment_value);
    1250           n=erasing_res_graph.tail(e);
     1250          n=erasing_res_graph.source(e);
    12511251          if (res_graph.resCap(e)==0)
    12521252            erasing_res_graph.erase(e);

  • src/work/jacint/max_flow_bug.cc

    r921 r986  
    4343  EdgeIt e;
    4444  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];
    4646  }
    4747
    … …  
    5050  int min_cut_value=0;
    5151  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)])
    5353      min_cut_value+=cap[e];
    5454  }
    … …  
    5858  int max_min_cut_value=0;
    5959  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)])
    6161      max_min_cut_value+=cap[e];
    6262      }
    … …  
    8989  int min_min_cut_value2=0;
    9090    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];
    9292  }
    9393
    … …  
    9696  int min_cut_value2=0;
    9797  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)])
    9999      min_cut_value2+=cap[e];
    100100  }
    … …  
    104104  int max_min_cut_value2=0;
    105105  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)])
    107107      max_min_cut_value2+=cap[e];
    108108      }
    … …  
    128128  int min_min_cut_value3=0;
    129129  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];
    131131  }
    132132
    … …  
    135135  int min_cut_value3=0;
    136136  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)])
    138138      min_cut_value3+=cap[e];
    139139  }
    … …  
    143143  int max_min_cut_value3=0;
    144144  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)])
    146146      max_min_cut_value3+=cap[e];
    147147  }

  • src/work/jacint/max_flow_test.cc

    r921 r986  
    4646  EdgeIt e;
    4747  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];
    4949  }
    5050
    … …  
    5353  int min_cut_value=0;
    5454  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)])
    5656      min_cut_value+=cap[e];
    5757  }
    … …  
    6161  int max_min_cut_value=0;
    6262  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)])
    6464      max_min_cut_value+=cap[e];
    6565      }
    … …  
    9292  int min_min_cut_value2=0;
    9393    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];
    9595  }
    9696
    … …  
    9999  int min_cut_value2=0;
    100100  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)])
    102102      min_cut_value2+=cap[e];
    103103  }
    … …  
    107107  int max_min_cut_value2=0;
    108108  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)])
    110110      max_min_cut_value2+=cap[e];
    111111      }
    … …  
    131131  int min_min_cut_value3=0;
    132132  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];
    134134  }
    135135
    … …  
    138138  int min_cut_value3=0;
    139139  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)])
    141141      min_cut_value3+=cap[e];
    142142  }
    … …  
    146146  int max_min_cut_value3=0;
    147147  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)])
    149149      max_min_cut_value3+=cap[e];
    150150  }

  • src/work/jacint/max_matching.cc

    r921 r986  
    191191  EdgeIt e;
    192192  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) )
    195195      noedge=false;
    196196  }

  • src/work/jacint/max_matching.h

    r921 r986  
    154154        Edge e=map[v];
    155155        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));
    157157      }
    158158    }
    … …  
    173173      NodeIt e;
    174174      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);
    178178          if ( mate[u]=v && mate[v]=u ) {
    179179            map.set(u,e);
    … …  
    197197      for( G.first(e); G.valid(e); G.next(e)) {
    198198        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);
    201201          mate.set(u,v);
    202202          mate.set(v,u);
    … …  
    223223      for( G.first(e); G.valid(e); G.next(e)) {
    224224        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);
    228228          if ( mate[u]=v && mate[v]=u ) {
    229229            map.set(e,true);

  • src/work/jacint/max_save.h

    r921 r986  
    259259        OutEdgeIt e;
    260260        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    261           Node v=g->head(e);
     261          Node v=g->target(e);
    262262          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    263263            queue.push(v);
    … …  
    268268        InEdgeIt f;
    269269        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    270           Node v=g->tail(f);
     270          Node v=g->source(f);
    271271          if (!M[v] && (*flow)[f] > 0 ) {
    272272            queue.push(v);
    … …  
    305305        InEdgeIt e;
    306306        for(g->first(e,w) ; g->valid(e); g->next(e)) {
    307           Node v=g->tail(e);
     307          Node v=g->source(e);
    308308          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    309309            queue.push(v);
    … …  
    314314        OutEdgeIt f;
    315315        for(g->first(f,w) ; g->valid(f); g->next(f)) {
    316           Node v=g->head(f);
     316          Node v=g->target(f);
    317317          if (M[v] && (*flow)[f] > 0 ) {
    318318            queue.push(v);
    … …  
    370370           
    371371        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    372         Node v=g->head(e);           
     372        Node v=g->target(e);           
    373373           
    374374        if( lev > level[v] ) { //Push is allowed now
    … …  
    403403         
    404404          if( (*flow)[e] <= 0 ) continue;
    405           Node v=g->tail(e);
     405          Node v=g->source(e);
    406406         
    407407          if( lev > level[v] ) { //Push is allowed now
    … …  
    457457                                  InEdgeIt e;
    458458                                  for(g->first(e,v); g->valid(e); g->next(e)) {
    459                                     Node w=g->tail(e);
     459                                    Node w=g->source(e);
    460460                                    if ( level[w] == n && w != s ) {
    461461                                      bfs_queue.push(w);
    … …  
    475475                                    Num c=(*capacity)[e];
    476476                                    if ( c <= 0 ) continue;
    477                                     Node w=g->head(e);
     477                                    Node w=g->target(e);
    478478                                    if ( level[w] < n ) {         
    479479                                      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    502502                                  for(g->first(e,v); g->valid(e); g->next(e)) {
    503503                                    if ( (*capacity)[e] <= (*flow)[e] ) continue;
    504                                     Node w=g->tail(e);
     504                                    Node w=g->source(e);
    505505                                    if ( level[w] == n && w != s ) {
    506506                                      bfs_queue.push(w);
    … …  
    516516                                  for(g->first(f,v); g->valid(f); g->next(f)) {
    517517                                    if ( 0 >= (*flow)[f] ) continue;
    518                                     Node w=g->head(f);
     518                                    Node w=g->target(f);
    519519                                    if ( level[w] == n && w != s ) {
    520520                                      bfs_queue.push(w);
    … …  
    535535                                    Num rem=(*capacity)[e]-(*flow)[e];
    536536                                    if ( rem <= 0 ) continue;
    537                                     Node w=g->head(e);
     537                                    Node w=g->target(e);
    538538                                    if ( level[w] < n ) {         
    539539                                      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    547547                                  {
    548548                                    if ( (*flow)[f] <= 0 ) continue;
    549                                     Node w=g->tail(f);
     549                                    Node w=g->source(f);
    550550                                    if ( level[w] < n ) {         
    551551                                      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    … …  
    645645      //        return dist[n]; }
    646646      //       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))); }
    648648      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)]);
    650650      }
    651651    };
    … …  
    784784      for(g->first(e,v); g->valid(e); g->next(e)) {
    785785        if ( (*capacity)[e] <= (*flow)[e] ) continue;
    786         Node u=g->tail(e);
     786        Node u=g->source(e);
    787787        if ( level[u] >= n ) {
    788788          bfs_queue.push(u);
    … …  
    795795      for(g->first(f,v); g->valid(f); g->next(f)) {
    796796        if ( 0 >= (*flow)[f] ) continue;
    797         Node u=g->head(f);
     797        Node u=g->target(f);
    798798        if ( level[u] >= n ) {
    799799          bfs_queue.push(u);
    … …  
    847847      ResGWOutEdgeIt e=bfs;
    848848      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);
    851851        pred.set(w, e);
    852852        if (res_graph.valid(pred[v])) {
    … …  
    855855          free.set(w, res_graph.resCap(e));
    856856        }
    857         if (res_graph.head(e)==t) { _augment=true; break; }
     857        if (res_graph.target(e)==t) { _augment=true; break; }
    858858      }
    859859       
    … …  
    867867        ResGWEdge e=pred[n];
    868868        res_graph.augment(e, augment_value);
    869         n=res_graph.tail(e);
     869        n=res_graph.source(e);
    870870      }
    871871    }
    … …  
    920920      if (res_graph.valid(e)) {
    921921        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)]);
    924924          original_edge.update();
    925925          original_edge.set(f, e);
    … …  
    927927          residual_capacity.set(f, res_graph.resCap(e));
    928928        } 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)]);
    931931            original_edge.update();
    932932            original_edge.set(f, e);
    … …  
    982982          typename MG::Edge e=pred[n];
    983983          res_graph.augment(original_edge[e], augment_value);
    984           n=F.tail(e);
     984          n=F.source(e);
    985985          if (residual_capacity[e]==augment_value)
    986986            F.erase(e);
    … …  
    10161016      ResGWOutEdgeIt e=bfs;
    10171017      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);
    10191019      }
    10201020      ++bfs;
    … …  
    11131113          typename ErasingResGW::OutEdgeIt e=pred[n];
    11141114          res_graph.augment(e, augment_value);
    1115           n=erasing_res_graph.tail(e);
     1115          n=erasing_res_graph.source(e);
    11161116          if (res_graph.resCap(e)==0)
    11171117            erasing_res_graph.erase(e);

  • src/work/jacint/preflow.cc

    r921 r986  
    4747  for(G.first(e); G.valid(e); G.next(e)) {
    4848    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;
    5252  }
    5353
    … …  
    8787  for(G.first(e); G.valid(e); G.next(e)) {
    8888    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;
    9292  }
    9393
    … …  
    139139  for(G.first(e); G.valid(e); G.next(e)) {
    140140    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;
    145145  }
    146146
    … …  
    196196  for(G.first(e); G.valid(e); G.next(e)) {
    197197    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;
    201201  }
    202202
    … …  
    239239  for(G.first(e); G.valid(e); G.next(e)) {
    240240    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;
    244244  }
    245245

  • src/work/jacint/preflow_excess.h

    r921 r986  
    137137          InEdgeIt e;
    138138          for(G.first(e,v); G.valid(e); G.next(e)) {
    139             Node w=G.tail(e);
     139            Node w=G.source(e);
    140140            if ( level[w] == n && w != s ) {
    141141              bfs_queue.push(w);
    … …  
    155155          T c=capacity[e];
    156156          if ( c == 0 ) continue;
    157           Node w=G.head(e);
     157          Node w=G.target(e);
    158158          if ( level[w] < n ) {   
    159159            if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    183183          for(G.first(e,v); G.valid(e); G.next(e)) {
    184184            if ( capacity[e] == flow[e] ) continue;
    185             Node w=G.tail(e);
     185            Node w=G.source(e);
    186186            if ( level[w] == n && w != s ) {
    187187              bfs_queue.push(w);
    … …  
    197197          for(G.first(f,v); G.valid(f); G.next(f)) {
    198198            if ( 0 == flow[f] ) continue;
    199             Node w=G.head(f);
     199            Node w=G.target(f);
    200200            if ( level[w] == n && w != s ) {
    201201              bfs_queue.push(w);
    … …  
    248248          T rem=capacity[e]-flow[e];
    249249          if ( rem == 0 ) continue;
    250           Node w=G.head(e);
     250          Node w=G.target(e);
    251251          if ( level[w] < n ) {   
    252252            if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    260260        {
    261261          if ( flow[f] == 0 ) continue;
    262           Node w=G.tail(f);
     262          Node w=G.source(f);
    263263          if ( level[w] < n ) {   
    264264            if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    304304              for(G.first(e,v); G.valid(e); G.next(e)) {
    305305                if ( capacity[e] == flow[e] ) continue;
    306                 Node u=G.tail(e);
     306                Node u=G.source(e);
    307307                if ( level[u] >= n ) {
    308308                  bfs_queue.push(u);
    … …  
    315315              for(G.first(f,v); G.valid(f); G.next(f)) {
    316316                if ( 0 == flow[f] ) continue;
    317                 Node u=G.head(f);
     317                Node u=G.target(f);
    318318                if ( level[u] >= n ) {
    319319                  bfs_queue.push(u);
    … …  
    344344           
    345345            if ( flow[e] == capacity[e] ) continue;
    346             Node v=G.head(e);           
     346            Node v=G.target(e);           
    347347            //e=wv         
    348348           
    … …  
    386386           
    387387            if( flow[e] == 0 ) continue;
    388             Node v=G.tail(e); 
     388            Node v=G.source(e); 
    389389            //e=vw
    390390           
    … …  
    570570        OutEdgeIt e;
    571571        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    572           Node v=G.head(e);
     572          Node v=G.target(e);
    573573          if (!M[v] && flow[e] < capacity[e] ) {
    574574            queue.push(v);
    … …  
    579579        InEdgeIt f;
    580580        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    581           Node v=G.tail(f);
     581          Node v=G.source(f);
    582582          if (!M[v] && flow[f] > 0 ) {
    583583            queue.push(v);
    … …  
    610610        InEdgeIt e;
    611611        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    612           Node v=G.tail(e);
     612          Node v=G.source(e);
    613613          if (!M[v] && flow[e] < capacity[e] ) {
    614614            queue.push(v);
    … …  
    619619        OutEdgeIt f;
    620620        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    621           Node v=G.head(f);
     621          Node v=G.target(f);
    622622          if (!M[v] && flow[f] > 0 ) {
    623623            queue.push(v);

  • src/work/jacint/preflow_excess_test.cc

    r921 r986  
    5353  EdgeIt e;
    5454  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];
    5656  }
    5757
    … …  
    6060  int min_cut_value=0;
    6161  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)])
    6363      min_cut_value+=cap[e];
    6464  }
    … …  
    6868  int max_min_cut_value=0;
    6969  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)])
    7171      max_min_cut_value+=cap[e];
    7272      }
    … …  
    100100  int min_min_cut_value2=0;
    101101    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];
    103103  }
    104104
    … …  
    107107  int min_cut_value2=0;
    108108  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)])
    110110      min_cut_value2+=cap[e];
    111111  }
    … …  
    115115  int max_min_cut_value2=0;
    116116  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)])
    118118      max_min_cut_value2+=cap[e];
    119119      }
    … …  
    145145  int min_min_cut_value3=0;
    146146  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];
    148148  }
    149149
    … …  
    152152  int min_cut_value3=0;
    153153  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)])
    155155      min_cut_value3+=cap[e];
    156156  }
    … …  
    160160  int max_min_cut_value3=0;
    161161  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)])
    163163      max_min_cut_value3+=cap[e];
    164164      }

  • src/work/jacint/preflow_res.h

    r921 r986  
    103103        for(res_graph.first(e,v); res_graph.valid(e);
    104104            res_graph.next(e)) {
    105           Node w=res_graph.tail(e);
     105          Node w=res_graph.source(e);
    106106          if ( level[w] == n && w != s ) {
    107107            bfs_queue.push(w);
    … …  
    146146      for(res_graph.first(e,s); res_graph.valid(e);
    147147          res_graph.next(e)) {
    148           Node w=res_graph.head(e);
     148          Node w=res_graph.target(e);
    149149          if ( level[w] < n ) {   
    150150            if ( excess[w] == 0 && w!=t ) {
    … …  
    191191              for(res_graph.first(e,v);
    192192                  res_graph.valid(e); res_graph.next(e)) {
    193                 Node u=res_graph.tail(e);
     193                Node u=res_graph.source(e);
    194194                if ( level[u] >= n ) {
    195195                  bfs_queue.push(u);
    … …  
    222222          for(res_graph.first(e,w); res_graph.valid(e); res_graph.next(e)) {
    223223           
    224             Node v=res_graph.head(e);           
     224            Node v=res_graph.target(e);           
    225225            if( lev > level[v] ) {     
    226226              /*Push is allowed now*/
    … …  
    401401        OutEdgeIt e;
    402402        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    403           Node v=G.head(e);
     403          Node v=G.target(e);
    404404          if (!M[v] && flow[e] < capacity[e] ) {
    405405            queue.push(v);
    … …  
    410410        InEdgeIt f;
    411411        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    412           Node v=G.tail(f);
     412          Node v=G.source(f);
    413413          if (!M[v] && flow[f] > 0 ) {
    414414            queue.push(v);
    … …  
    441441        InEdgeIt e;
    442442        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    443           Node v=G.tail(e);
     443          Node v=G.source(e);
    444444          if (!M[v] && flow[e] < capacity[e] ) {
    445445            queue.push(v);
    … …  
    450450        OutEdgeIt f;
    451451        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    452           Node v=G.head(f);
     452          Node v=G.target(f);
    453453          if (!M[v] && flow[f] > 0 ) {
    454454            queue.push(v);

  • src/work/jacint/prim.h

    r921 r986  
    9696          OutEdgeIt e;
    9797          for( G.first(e,v); G.valid(e); G.next(e)) {
    98             Node w=G.head(e);
     98            Node w=G.target(e);
    9999           
    100100            if ( !scanned[w] ) {
    … …  
    112112          InEdgeIt f;
    113113          for( G.first(f,v); G.valid(f); G.next(f)) {
    114             Node w=G.tail(f);
     114            Node w=G.source(f);
    115115           
    116116            if ( !scanned[w] ) {

  • src/work/johanna/ma_order.h

    r921 r986  
    5858          G.first(e,a);
    5959          for (;G.valid(e);G.next(e)) {
    60             Node v = G.head(e); // hmm
     60            Node v = G.target(e); // hmm
    6161            if (heap.state(v) == Heap::IN_HEAP ) {
    6262              heap.decrease(v, heap[v]+1);

  • src/work/marci/augmenting_flow.h

    r970 r986  
    211211        OutEdgeIt e;
    212212        for(g->first(e,w) ; e!=INVALID; ++e) {
    213           Node v=g->head(e);
     213          Node v=g->target(e);
    214214          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    215215            queue.push(v);
    … …  
    220220        InEdgeIt f;
    221221        for(g->first(f,w) ; f!=INVALID; ++f) {
    222           Node v=g->tail(f);
     222          Node v=g->source(f);
    223223          if (!M[v] && (*flow)[f] > 0 ) {
    224224            queue.push(v);
    … …  
    271271      ResGWEdge e=bfs;
    272272      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);
    275275        pred.set(w, e);
    276276        if (pred[v]!=INVALID) {
    … …  
    279279          free.set(w, res_cap[e]);
    280280        }
    281         if (res_graph.head(e)==t) { _augment=true; break; }
     281        if (res_graph.target(e)==t) { _augment=true; break; }
    282282      }
    283283
    … …  
    291291        ResGWEdge e=pred[n];
    292292        res_graph.augment(e, augment_value);
    293         n=res_graph.tail(e);
     293        n=res_graph.source(e);
    294294      }
    295295    }
    … …  
    330330      ResGWEdge e=bfs;
    331331      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);
    334334        pred.set(w, e);
    335335        if (pred[v]!=INVALID) {
    … …  
    338338          free.set(w, res_cap[e]);
    339339        }
    340         if (res_graph.head(e)==t) { _augment=true; break; }
     340        if (res_graph.target(e)==t) { _augment=true; break; }
    341341      }
    342342
    … …  
    350350        ResGWEdge e=pred[n];
    351351        res_graph.augment(e, augment_value);
    352         n=res_graph.tail(e);
     352        n=res_graph.source(e);
    353353      }
    354354    }
    … …  
    396396      if (e!=INVALID) {
    397397        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)]);
    401401          //original_edge.update();
    402402          original_edge.set(f, e);
    … …  
    404404          residual_capacity.set(f, res_cap[e]);
    405405        } 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)]);
    409409            //original_edge.update();
    410410            original_edge.set(f, e);
    … …  
    434434        if (typename MG::Edge(dfs)!=INVALID) {
    435435          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);
    438438            pred.set(w, dfs);
    439439            if (pred[v]!=INVALID) {
    … …  
    460460          typename MG::Edge e=pred[n];
    461461          res_graph.augment(original_edge[e], augment_value);
    462           n=F.tail(e);
     462          n=F.source(e);
    463463          if (residual_capacity[e]==augment_value)
    464464            F.erase(e);
    … …  
    499499      ResGWEdge e=bfs;
    500500      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);
    502502      ++bfs;
    503503    }
    … …  
    554554          if (dfs.isBNodeNewlyReached()) {
    555555           
    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);
    558558
    559559            pred.set(w, typename ErasingResGW::Edge(dfs));
    … …  
    586586          typename ErasingResGW::Edge e=pred[n];
    587587          res_graph.augment(e, augment_value);
    588           n=erasing_res_graph.tail(e);
     588          n=erasing_res_graph.source(e);
    589589          if (res_cap[e]==0)
    590590            erasing_res_graph.erase(e);

  • src/work/marci/bfs_dfs.h

    r921 r986  
    6464        //graph->first(actual_edge, s);
    6565        if (actual_edge!=INVALID) {
    66           Node w=graph->head(actual_edge);
     66          Node w=graph->target(actual_edge);
    6767          if (!reached[w]) {
    6868            bfs_queue.push(w);
    … …  
    8686        //++actual_edge;
    8787        if (actual_edge!=INVALID) {
    88           Node w=graph->head(actual_edge);
     88          Node w=graph->target(actual_edge);
    8989          if (!reached[w]) {
    9090            bfs_queue.push(w);
    … …  
    101101          //graph->first(actual_edge, bfs_queue.front());
    102102          if (actual_edge!=INVALID) {
    103             Node w=graph->head(actual_edge);
     103            Node w=graph->target(actual_edge);
    104104            if (!reached[w]) {
    105105              bfs_queue.push(w);
    … …  
    125125    bool isANodeExamined() const { return actual_edge==INVALID; }
    126126    /// 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(); }
    128128    /// \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); }
    130130    /// Guess what?
    131131    /// \deprecated
    … …  
    187187      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
    188188      {
    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()]);
    191191      }
    192192      return *this;
    … …  
    247247      actual_edge=dfs_stack.top();
    248248      if (actual_edge!=INVALID/*.valid()*/) {
    249         Node w=graph->head(actual_edge);
     249        Node w=graph->target(actual_edge);
    250250        actual_node=w;
    251251        if (!reached[w]) {
    … …  
    256256          b_node_newly_reached=true;
    257257        } else {
    258           actual_node=graph->tail(actual_edge);
     258          actual_node=graph->source(actual_edge);
    259259          ++dfs_stack.top();
    260260          b_node_newly_reached=false;
    … …  
    277277    bool isANodeExamined() const { return actual_edge==INVALID; }
    278278    /// 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*/}
    280280    /// Returns b-node of the actual edge.
    281281    /// \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); }
    283283    /// Guess what?
    284284    /// \deprecated
    … …  
    334334      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
    335335      {
    336         pred.set(this->head(), this->actual_edge);
     336        pred.set(this->target(), this->actual_edge);
    337337      }
    338338      return *this;

  • src/work/marci/bfs_mm.h

    r944 r986  
    7272        //graph->first(actual_edge, s);
    7373        if (actual_edge!=INVALID) {
    74           Node w=graph->head(actual_edge);
     74          Node w=graph->target(actual_edge);
    7575          if (!(*reached_map)[w]) {
    7676            bfs_queue.push(w);
    … …  
    9494        //++actual_edge;
    9595        if (actual_edge!=INVALID) {
    96           Node w=graph->head(actual_edge);
     96          Node w=graph->target(actual_edge);
    9797          if (!(*reached_map)[w]) {
    9898            bfs_queue.push(w);
    … …  
    109109          //graph->first(actual_edge, bfs_queue.front());
    110110          if (actual_edge!=INVALID) {
    111             Node w=graph->head(actual_edge);
     111            Node w=graph->target(actual_edge);
    112112            if (!(*reached_map)[w]) {
    113113              bfs_queue.push(w);
    … …  
    133133    bool isANodeExamined() const { return actual_edge==INVALID; }
    134134    /// 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(); }
    136136    /// \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); }
    138138    /// Guess what?
    139139    /// \deprecated
    … …  
    232232      if ((this->actual_edge)!=INVALID && this->b_node_newly_reached)
    233233      {
    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()]);
    237237      }
    238238      return *this;
    … …  
    458458      actual_edge=dfs_stack.top();
    459459      if (actual_edge!=INVALID/*.valid()*/) {
    460         Node w=graph->head(actual_edge);
     460        Node w=graph->target(actual_edge);
    461461        actual_node=w;
    462462        if (!reached[w]) {
    … …  
    467467          b_node_newly_reached=true;
    468468        } else {
    469           actual_node=graph->tail(actual_edge);
     469          actual_node=graph->source(actual_edge);
    470470          ++dfs_stack.top();
    471471          b_node_newly_reached=false;
    … …  
    488488    bool isANodeExamined() const { return actual_edge==INVALID; }
    489489    /// 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*/}
    491491    /// Returns b-node of the actual edge.
    492492    /// \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); }
    494494    /// Guess what?
    495495    /// \deprecated
    … …  
    545545      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
    546546      {
    547         pred.set(this->head(), this->actual_edge);
     547        pred.set(this->target(), this->actual_edge);
    548548      }
    549549      return *this;

  • src/work/marci/bfs_mm_test.cc

    r959 r986  
    9292
    9393//   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);
    9696//     check( !bfs_test.reached(u) ||
    9797//         (bfs_test.dist(v) > bfs_test.dist(u)+1),
    … …  
    103103//     if ( bfs_test.pred(v)!=INVALID ) {
    104104//       Edge e=bfs_test.pred(v);
    105 //       Node u=G.tail(e);
     105//       Node u=G.source(e);
    106106//       check(u==bfs_test.predNode(v),"Wrong tree.");
    107107//       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,

  • src/work/marci/bfsit_vs_byhand.cc

    r944 r986  
    4949      bfs_queue.pop();
    5050      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
    51         Node w=g.head(e);
     51        Node w=g.target(e);
    5252        if (!reached[w]) {
    5353          bfs_queue.push(w);
    … …  
    7171      ++bfs;
    7272      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
    73         pred.set(bfs.head(), Graph::Edge(bfs));
     73        pred.set(bfs.target(), Graph::Edge(bfs));
    7474    }
    7575  }

  • src/work/marci/bipartite_graph_wrapper.h

    r921 r986  
    168168//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    169169
    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));
    173173//       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));
    179179//       else
    180 //      return Node(this->graph->tail(e));     
     180//      return Node(this->graph->source(e));   
    181181//     }
    182182
    … …  
    253253
    254254    /// A new edge is inserted.
    255     ///\pre \c tail have to be in \c S_Class and \c head in \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);
    258258    }
    259259
    … …  
    696696    }   
    697697
    698     Node tail(const Edge& e) const {
     698    Node source(const Edge& e) const {
    699699      switch (e.spec) {
    700700      case 0:
    701         return Node(this->graph->tail(e));
     701        return Node(this->graph->source(e));
    702702        break;
    703703      case 1:
    … …  
    710710      }
    711711    }
    712     Node head(const Edge& e) const {
     712    Node target(const Edge& e) const {
    713713      switch (e.spec) {
    714714      case 0:
    715         return Node(this->graph->head(e));
     715        return Node(this->graph->target(e));
    716716        break;
    717717      case 1:
    … …  
    733733    }
    734734 
    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); }
    739739
    740740    void addNode() const { }
    … …  
    742742   
    743743//    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)); }
    746746
    747747//    void erase(const Node& i) const { this->graph->erase(i); }

  • src/work/marci/bipartite_graph_wrapper_test.cc

    r921 r986  
    8888  cout << "Edges of the bipartite graph:" << endl;
    8989  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;
    9191
    9292  BGW::NodeMap<int> dbyj(bgw);

  • src/work/marci/experiment/edmonds_karp.h

    r921 r986  
    4141      //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
    4242      Number free() const {
    43         if (resG->G.aNode(sym)==resG->G.tail(sym)) {
     43        if (resG->G.aNode(sym)==resG->G.source(sym)) {
    4444          return (resG->capacity.get(sym)-resG->flow.get(sym));
    4545        } else {
    … …  
    4949      bool valid() const { return sym.valid(); }
    5050      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)) {
    5252          resG->flow.set(sym, resG->flow.get(sym)+a);
    5353          //resG->flow[sym]+=a;
    … …  
    9797    }
    9898
    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); }
    101101
    102102    Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    … …  
    224224    }
    225225
    226     Node tail(Edge e) const {
     226    Node source(Edge e) const {
    227227      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 {
    229229      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    230230
    … …  
    288288        ResGWOutEdgeIt e=bfs;
    289289        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);
    292292          pred.set(w, e);
    293293          if (res_graph.valid(pred.get(v))) {
    … …  
    296296            free.set(w, res_graph.resCap(e));
    297297          }
    298           if (res_graph.head(e)==t) { _augment=true; break; }
     298          if (res_graph.target(e)==t) { _augment=true; break; }
    299299        }
    300300       
    … …  
    308308          ResGWEdge e=pred.get(n);
    309309          res_graph.augment(e, augment_value);
    310           n=res_graph.tail(e);
     310          n=res_graph.source(e);
    311311        }
    312312      }
    … …  
    325325      int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
    326326      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)));
    328328      }
    329329    };
    … …  
    344344        ResGWOutEdgeIt e=bfs;
    345345        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);
    347347        }
    348348        ++bfs;
    … …  
    370370        typename FilterResGW::EdgeIt e;
    371371        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)));
    374374          original_edge.update();
    375375          original_edge.set(f, e);
    … …  
    424424            typename MG::Edge e=pred.get(n);
    425425            res_graph.augment(original_edge.get(e), augment_value);
    426             n=F.tail(e);
     426            n=F.source(e);
    427427            if (residual_capacity.get(e)==augment_value)
    428428              F.erase(e);
    … …  
    469469        if (res_graph.valid(e)) {
    470470          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)));
    473473            original_edge.update();
    474474            original_edge.set(f, e);
    … …  
    476476            residual_capacity.set(f, res_graph.resCap(e));
    477477          } 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)));
    480480              original_edge.update();
    481481              original_edge.set(f, e);
    … …  
    532532            typename MG::Edge e=pred.get(n);
    533533            res_graph.augment(original_edge.get(e), augment_value);
    534             n=F.tail(e);
     534            n=F.source(e);
    535535            if (residual_capacity.get(e)==augment_value)
    536536              F.erase(e);
    … …  
    558558        ResGWOutEdgeIt e=bfs;
    559559        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);
    561561        }
    562562        ++bfs;
    … …  
    634634            typename ErasingResGW::OutEdgeIt e=pred.get(n);
    635635            res_graph.augment(e, augment_value);
    636             n=erasing_res_graph.tail(e);
     636            n=erasing_res_graph.source(e);
    637637            if (res_graph.resCap(e)==0)
    638638              erasing_res_graph.erase(e);
    … …  
    669669//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    670670//      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);
    672672//      }
    673673//      ++bfs; 
    … …  
    723723//          EAugEdge e=pred.get(n);
    724724//          res_graph.augment(e, augment_value);
    725 //          n=res_graph.tail(e);
     725//          n=res_graph.source(e);
    726726//          if (res_graph.free(e)==0)
    727727//            res_graph.erase(e);
    … …  
    818818//      AugOutEdgeIt e=bfs;
    819819//      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);
    822822//        pred.set(w, e);
    823823//        if (res_graph.valid(pred.get(v))) {
    … …  
    826826//          free.set(w, res_graph.free(e));
    827827//        }
    828 //        n=res_graph.head(e);
     828//        n=res_graph.target(e);
    829829//        if (T->get(n) && (used.get(n)<1) ) {
    830830//          //Number u=0;
    … …  
    848848//        AugEdge e=pred.get(n);
    849849//        res_graph.augment(e, augment_value);
    850 //        n=res_graph.tail(e);
     850//        n=res_graph.source(e);
    851851//      }
    852852//      used.set(n, 1); //mind2 vegen jav
    … …  
    889889// //   AugOutEdgeIt e=bfs;
    890890// //   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);
    892892// //   }
    893893       
    … …  
    911911// //       //which are in some shortest paths
    912912// //       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)));
    915915// //     original_edge.update();
    916916// //     original_edge.set(f, e);
    … …  
    964964// //       typename MutableGraph::Edge e=pred.get(n);
    965965// //       res_graph.augment(original_edge.get(e), augment_value);
    966 // //       n=F.tail(e);
     966// //       n=F.source(e);
    967967// //       if (residual_capacity.get(e)==augment_value)
    968968// //         F.erase(e);
    … …  
    10151015//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    10161016//      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);
    10181018//      }
    10191019//      ++bfs; 
    … …  
    10921092//          EAugEdge e=pred.get(n);
    10931093//          res_graph.augment(e, augment_value);
    1094 //          n=res_graph.tail(e);
     1094//          n=res_graph.source(e);
    10951095//          if (res_graph.free(e)==0)
    10961096//            res_graph.erase(e);
    … …  
    11851185// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    11861186// //   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);
    11891189// //     pred.set(w, e);
    11901190// //     if (pred.get(v).valid()) {
    … …  
    11931193// //       free.set(w, e.free());
    11941194// //     }
    1195 // //     if (TMap.get(res_graph.head(e))) {
     1195// //     if (TMap.get(res_graph.target(e))) {
    11961196// //       _augment=true;
    1197 // //       reached_t_node=res_graph.head(e);
     1197// //       reached_t_node=res_graph.target(e);
    11981198// //       break;
    11991199// //     }
    … …  
    12091209// //     AugEdge e=pred.get(n);
    12101210// //     e.augment(augment_value);
    1211 // //     n=res_graph.tail(e);
     1211// //     n=res_graph.source(e);
    12121212// //   }
    12131213// //       }

  • src/work/marci/experiment/edmonds_karp_1.h

    r921 r986  
    4242      //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
    4343      Number free() const {
    44         if (resG->G.aNode(sym)==resG->G.tail(sym)) {
     44        if (resG->G.aNode(sym)==resG->G.source(sym)) {
    4545          return (resG->capacity.get(sym)-resG->flow.get(sym));
    4646        } else {
    … …  
    5050      bool valid() const { return sym.valid(); }
    5151      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)) {
    5353          resG->flow.set(sym, resG->flow.get(sym)+a);
    5454          //resG->flow[sym]+=a;
    … …  
    9898    }
    9999
    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); }
    102102
    103103    Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    … …  
    225225    }
    226226
    227     Node tail(Edge e) const {
     227    Node source(Edge e) const {
    228228      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 {
    230230      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    231231
    … …  
    287287        ResGWOutEdgeIt e=bfs;
    288288        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);
    291291          pred.set(w, e);
    292292          if (res_graph.valid(pred.get(v))) {
    … …  
    295295            free.set(w, res_graph.resCap(e));
    296296          }
    297           if (res_graph.head(e)==t) { _augment=true; break; }
     297          if (res_graph.target(e)==t) { _augment=true; break; }
    298298        }
    299299       
    … …  
    307307          ResGWEdge e=pred.get(n);
    308308          res_graph.augment(e, augment_value);
    309           n=res_graph.tail(e);
     309          n=res_graph.source(e);
    310310        }
    311311      }
    … …  
    324324      int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
    325325      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)));
    327327      }
    328328    };
    … …  
    343343        ResGWOutEdgeIt e=bfs;
    344344        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);
    346346        }
    347347        ++bfs;
    … …  
    369369        typename FilterResGW::EdgeIt e;
    370370        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)));
    373373          original_edge.update();
    374374          original_edge.set(f, e);
    … …  
    423423            typename MG::Edge e=pred.get(n);
    424424            res_graph.augment(original_edge.get(e), augment_value);
    425             n=F.tail(e);
     425            n=F.source(e);
    426426            if (residual_capacity.get(e)==augment_value)
    427427              F.erase(e);
    … …  
    468468        if (res_graph.valid(e)) {
    469469          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)));
    472472            original_edge.update();
    473473            original_edge.set(f, e);
    … …  
    475475            residual_capacity.set(f, res_graph.resCap(e));
    476476          } 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)));
    479479              original_edge.update();
    480480              original_edge.set(f, e);
    … …  
    531531            typename MG::Edge e=pred.get(n);
    532532            res_graph.augment(original_edge.get(e), augment_value);
    533             n=F.tail(e);
     533            n=F.source(e);
    534534            if (residual_capacity.get(e)==augment_value)
    535535              F.erase(e);
    … …  
    557557        ResGWOutEdgeIt e=bfs;
    558558        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);
    560560        }
    561561        ++bfs;
    … …  
    633633            typename ErasingResGW::OutEdgeIt e=pred.get(n);
    634634            res_graph.augment(e, augment_value);
    635             n=erasing_res_graph.tail(e);
     635            n=erasing_res_graph.source(e);
    636636            if (res_graph.resCap(e)==0)
    637637              erasing_res_graph.erase(e);
    … …  
    728728//      AugOutEdgeIt e=bfs;
    729729//      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);
    732732//        pred.set(w, e);
    733733//        if (res_graph.valid(pred.get(v))) {
    … …  
    736736//          free.set(w, res_graph.free(e));
    737737//        }
    738 //        n=res_graph.head(e);
     738//        n=res_graph.target(e);
    739739//        if (T->get(n) && (used.get(n)<1) ) {
    740740//          //Number u=0;
    … …  
    758758//        AugEdge e=pred.get(n);
    759759//        res_graph.augment(e, augment_value);
    760 //        n=res_graph.tail(e);
     760//        n=res_graph.source(e);
    761761//      }
    762762//      used.set(n, 1); //mind2 vegen jav
    … …  
    799799// //   AugOutEdgeIt e=bfs;
    800800// //   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);
    802802// //   }
    803803       
    … …  
    821821// //       //which are in some shortest paths
    822822// //       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)));
    825825// //     original_edge.update();
    826826// //     original_edge.set(f, e);
    … …  
    874874// //       typename MutableGraph::Edge e=pred.get(n);
    875875// //       res_graph.augment(original_edge.get(e), augment_value);
    876 // //       n=F.tail(e);
     876// //       n=F.source(e);
    877877// //       if (residual_capacity.get(e)==augment_value)
    878878// //         F.erase(e);
    … …  
    925925//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    926926//      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);
    928928//      }
    929929//      ++bfs; 
    … …  
    10021002//          EAugEdge e=pred.get(n);
    10031003//          res_graph.augment(e, augment_value);
    1004 //          n=res_graph.tail(e);
     1004//          n=res_graph.source(e);
    10051005//          if (res_graph.free(e)==0)
    10061006//            res_graph.erase(e);
    … …  
    10951095// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    10961096// //   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);
    10991099// //     pred.set(w, e);
    11001100// //     if (pred.get(v).valid()) {
    … …  
    11031103// //       free.set(w, e.free());
    11041104// //     }
    1105 // //     if (TMap.get(res_graph.head(e))) {
     1105// //     if (TMap.get(res_graph.target(e))) {
    11061106// //       _augment=true;
    1107 // //       reached_t_node=res_graph.head(e);
     1107// //       reached_t_node=res_graph.target(e);
    11081108// //       break;
    11091109// //     }
    … …  
    11191119// //     AugEdge e=pred.get(n);
    11201120// //     e.augment(augment_value);
    1121 // //     n=res_graph.tail(e);
     1121// //     n=res_graph.source(e);
    11221122// //   }
    11231123// //       }

  • src/work/marci/experiment/edmonds_karp_demo.cc

    r921 r986  
    105105    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
    106106//     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)<<") ";
    116116//   }
    117117//   std::cout<<std::endl;
    … …  
    136136    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    137137//     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)<<") ";
    147147//   }
    148148//   std::cout<<std::endl;
    … …  
    167167    while (max_flow_test.augmentOnBlockingFlow2()) {
    168168//     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)<<") ";
    178178//   }
    179179//   std::cout<<std::endl;
    … …  
    198198    while (max_flow_test.augmentOnShortestPath()) {
    199199//     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)<<") ";
    209209//   }
    210210//   std::cout<<std::endl;

  • src/work/marci/experiment/edmonds_karp_demo_1.cc

    r921 r986  
    105105    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
    106106//     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)<<") ";
    116116//   }
    117117//   std::cout<<std::endl;
    … …  
    136136    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    137137//     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)<<") ";
    147147//   }
    148148//   std::cout<<std::endl;
    … …  
    167167    while (max_flow_test.augmentOnBlockingFlow2()) {
    168168//     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)<<") ";
    178178//   }
    179179//   std::cout<<std::endl;
    … …  
    198198    while (max_flow_test.augmentOnShortestPath()) {
    199199//     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)<<") ";
    209209//   }
    210210//   std::cout<<std::endl;

  • src/work/marci/experiment/graph_wrapper.h

    r921 r986  
    9797      It e; first(e, v); return e; }
    9898
    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); }
    101101
    102102    template<typename I> bool valid(const I& i) const
    … …  
    115115 
    116116    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); }
    119119 
    120120    template<typename I> void erase(const I& i) const { graph->erase(i); }
    … …  
    246246      It e; this->first(e, v); return e; }
    247247
    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); }
    250250
    251251    template<typename I> bool valid(const I& i) const { return gw.valid(i); }
    … …  
    261261 
    262262    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); }
    265265 
    266266    template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    323323//       It e; first(e, v); return e; }
    324324
    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); }
    327327 
    328328//     template<typename I> bool valid(const I& i) const
    … …  
    338338
    339339//     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); }
    342342 
    343343//     int nodeNum() const { return graph->nodeNum(); }
    … …  
    404404//     //  It e; first(e, v); return e; }
    405405
    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); }
    408408 
    409409//     //template<typename I> bool valid(const I& i) const
    … …  
    419419
    420420//     //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); }
    423423 
    424424//     //int nodeNum() const { return graph->nodeNum(); }
    … …  
    468468      GraphWrapper<GraphWrapper>(_gw) { } 
    469469
    470     Node head(const Edge& e) const
    471       { return GraphWrapper<GraphWrapper>::tail(e); }
    472     Node tail(const Edge& e) const
    473       { 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); }
    474474  };
    475475
    … …  
    600600//     OutEdgeIt& next(OutEdgeIt& e) const {
    601601//       if (e.out_or_in) {
    602 //      Node n=gw.tail(e.out);
     602//      Node n=gw.source(e.out);
    603603//      gw.next(e.out);
    604604//      if (!gw.valid(e.out)) {
    … …  
    613613
    614614//     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); }
    616616//     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); }
    618618
    619619//     typedef OutEdgeIt InEdgeIt;
    … …  
    633633//       It e; first(e, v); return e; }
    634634
    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); }
    637637
    638638//     template<typename I> bool valid(const I& i) const
    … …  
    652652//     Node addNode() const { return gw.addNode(); }
    653653// // 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); }
    656656 
    657657//     template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    799799    OutEdgeIt& next(OutEdgeIt& e) const {
    800800      if (e.out_or_in) {
    801         Node n=gw.tail(e.out);
     801        Node n=gw.source(e.out);
    802802        gw.next(e.out);
    803803        if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
    … …  
    809809
    810810    EdgeIt& next(EdgeIt& e) const {
    811       //NodeIt v=tail(e);
     811      //NodeIt v=source(e);
    812812      gw.next(e.out);
    813813      while (valid(e.v) && !gw.valid(e.out)) {
    … …  
    827827      It e; first(e, v); return e; }
    828828
    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); }
    831831
    832832//    template<typename I> bool valid(const I& i) const
    … …  
    842842
    843843    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); }
    845845    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); }
    847847 
    848848//    Node addNode() const { return gw.addNode(); }
    849849
    850850// 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); }
    853853 
    854854//    template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    914914//       It e; first(e, v); return e; }
    915915
    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); }
    918918 
    919919//     template<typename I> Node aNode(const I& e) const {
    … …  
    929929 
    930930//     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); }
    933933 
    934934//     template<typename I> void erase(const I& i) { graph->erase(i); }
    … …  
    11811181    }
    11821182
    1183     Node tail(Edge e) const {
     1183    Node source(Edge e) const {
    11841184      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 {
    11861186      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
    11871187
    … …  
    13121312      OutEdgeIt f=e;
    13131313      this->next(f);
    1314       first_out_edges->set(this->tail(e), f);
     1314      first_out_edges->set(this->source(e), f);
    13151315    }
    13161316  };
    … …  
    13821382//       It e; first(e, v); return e; }
    13831383
    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); }
    13861386
    13871387//     //template<typename I> bool valid(const I& i) const
    … …  
    13971397 
    13981398//     //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); }
    14011401 
    14021402//     //void erase(const OutEdgeIt& e) {
    1403 //     //  first_out_edge(this->tail(e))=e;
     1403//     //  first_out_edge(this->source(e))=e;
    14041404//     //}
    14051405//     void erase(const Edge& e) {
    14061406//       OutEdgeIt f(e);
    14071407//       next(f);
    1408 //       first_out_edges.set(this->tail(e), f);
     1408//       first_out_edges.set(this->source(e), f);
    14091409//     }
    14101410//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    14601460//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    14611461//       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))))
    14631463//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    14641464//       return e;
    … …  
    14711471//     OutEdgeIt& next(OutEdgeIt& e) const {
    14721472//       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))))
    14741474//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    14751475//       return e;
    … …  
    14831483//       OutEdgeIt f(e);
    14841484//       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))))
    14861486//      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);
    14881488//     }
    14891489
    … …  
    15081508//       It e; first(e, v); return e; }
    15091509
    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); }
    15121512
    15131513//     //template<typename I> bool valid(const I& i) const
    … …  
    15261526 
    15271527//     //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); }
    15301530 
    15311531//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    16701670//       It e; first(e, v); return e; }
    16711671
    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); }
    16741674 
    16751675//     template<typename I> Node aNode(const I& e) const {
    … …  
    16851685 
    16861686//     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); }
    16891689 
    16901690//     template<typename I> void erase(const I& i) { gw.erase(i); }

  • src/work/marci/experiment/graph_wrapper_1.h

    r921 r986  
    9191      It e; this->first(e, v); return e; }
    9292
    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); }
    9595
    9696    template<typename I> bool valid(const I& i) const {
    … …  
    109109 
    110110    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); }
    113113 
    114114    template<typename I> void erase(const I& i) const { graph->erase(i); }
    … …  
    236236      It e; this->first(e, v); return e; }
    237237
    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); }
    240240
    241241    template<typename I> bool valid(const I& i) const {
    … …  
    254254 
    255255    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); }
    258258 
    259259    template<typename I> void erase(const I& i) const { graph->erase(i); }
    … …  
    317317//       It e; first(e, v); return e; }
    318318
    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); }
    321321 
    322322//     template<typename I> bool valid(const I& i) const
    … …  
    332332
    333333//     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); }
    336336 
    337337//     int nodeNum() const { return graph->nodeNum(); }
    … …  
    379379    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
    380380
    381     Node head(const Edge& e) const
    382       { return GraphWrapper<Graph>::tail(e); }
    383     Node tail(const Edge& e) const
    384       { 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); }
    385385  };
    386386
    … …  
    512512//     OutEdgeIt& next(OutEdgeIt& e) const {
    513513//       if (e.out_or_in) {
    514 //      Node n=gw.tail(e.out);
     514//      Node n=gw.source(e.out);
    515515//      gw.next(e.out);
    516516//      if (!gw.valid(e.out)) {
    … …  
    525525
    526526//     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); }
    528528//     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); }
    530530
    531531//     typedef OutEdgeIt InEdgeIt;
    … …  
    545545//       It e; first(e, v); return e; }
    546546
    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); }
    549549
    550550//     template<typename I> bool valid(const I& i) const
    … …  
    564564//     Node addNode() const { return gw.addNode(); }
    565565// // 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); }
    568568 
    569569//     template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    693693    OutEdgeIt& next(OutEdgeIt& e) const {
    694694      if (e.out_or_in) {
    695         Node n=graph->tail(e.out);
     695        Node n=graph->source(e.out);
    696696        graph->next(e.out);
    697697        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
    … …  
    703703
    704704    EdgeIt& next(EdgeIt& e) const {
    705       //NodeIt v=tail(e);
     705      //NodeIt v=source(e);
    706706      graph->next(e.out);
    707707      while (valid(e.v) && !graph->valid(e.out)) {
    … …  
    721721      It e; this->first(e, v); return e; }
    722722
    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); }
    725725
    726726//    template<typename I> bool valid(const I& i) const
    … …  
    736736
    737737    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); }
    739739    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); }
    741741 
    742742//    Node addNode() const { return gw.addNode(); }
    743743
    744744// 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); }
    747747 
    748748//    template<typename I> void erase(const I& i) const { gw.erase(i); }
    … …  
    808808//       It e; first(e, v); return e; }
    809809
    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); }
    812812 
    813813//     template<typename I> Node aNode(const I& e) const {
    … …  
    823823 
    824824//     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); }
    827827 
    828828//     template<typename I> void erase(const I& i) { graph->erase(i); }
    … …  
    10641064    }
    10651065
    1066     Node tail(Edge e) const {
     1066    Node source(Edge e) const {
    10671067      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 {
    10691069      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
    10701070
    … …  
    11931193      OutEdgeIt f=e;
    11941194      this->next(f);
    1195       first_out_edges->set(this->tail(e), f);
     1195      first_out_edges->set(this->source(e), f);
    11961196    }
    11971197  };
    … …  
    13111311//       It e; first(e, v); return e; }
    13121312
    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); }
    13151315 
    13161316//     template<typename I> Node aNode(const I& e) const {
    … …  
    13261326 
    13271327//     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); }
    13301330 
    13311331//     template<typename I> void erase(const I& i) { gw.erase(i); }

  • src/work/marci/experiment/graph_wrapper_st_ostream_op.h

    r921 r986  
    167167    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    168168
    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))); }
    173173
    174174    bool valid(const Node& n) const {
    … …  
    186186 
    187187    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)); }
    190190
    191191    void erase(const Node& i) const { graph->erase(i); }
    … …  
    273273      return Node(this->graph->bNode(e.e)); }
    274274
    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); }
    279279
    280280  };
    … …  
    490490    OutEdgeIt& next(OutEdgeIt& e) const {
    491491      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);
    493493        this->graph->next(e.out);
    494494        if (!this->graph->valid(e.out)) {
    … …  
    507507
    508508    Node aNode(const OutEdgeIt& e) const {
    509       if (e.out_or_in) return this->graph->tail(e); else
    510         return this->graph->head(e); }
     509      if (e.out_or_in) return this->graph->source(e); else
     510        return this->graph->target(e); }
    511511    Node bNode(const OutEdgeIt& e) const {
    512       if (e.out_or_in) return this->graph->head(e); else
    513         return this->graph->tail(e); }
     512      if (e.out_or_in) return this->graph->target(e); else
     513        return this->graph->source(e); }
    514514  };
    515515 
    … …  
    725725    }
    726726
    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)); }
    731731
    732732    Node aNode(OutEdgeIt e) const {
    … …  
    914914      OutEdgeIt f=e;
    915915      this->next(f);
    916       first_out_edges->set(this->tail(e), f.e);
     916      first_out_edges->set(this->source(e), f.e);
    917917    }
    918918  };
    … …  
    10421042    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    10431043
    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));
    10471047      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));
    10531053      else