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


Ignore:
Timestamp:
11/13/04 13:53:28 (19 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
Files:
104 edited

Legend:

Unmodified
Added
Removed

  • doc/graphs.dox

    r959 r986  
    126126  std::cout << "Edges:";
    127127  for (EdgeIt i(g); i!=INVALID; ++i)
    128     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
     128    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
    129129  std::cout << std::endl;
    130130\endcode
    … …  
    134134\endcode
    135135
    136 We can also iterate through all edges of the graph very similarly. The head and
    137 tail member functions can be used to access the endpoints of an edge.
     136We can also iterate through all edges of the graph very similarly. The target and
     137source member functions can be used to access the endpoints of an edge.
    138138
    139139\code
    … …  
    142142  std::cout << "Out-edges of node " << g.id(first_node) << ":";
    143143  for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
    144     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
     144    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
    145145  std::cout << std::endl;
    146146
    147147  std::cout << "In-edges of node " << g.id(first_node) << ":";
    148148  for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
    149     std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")";
     149    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
    150150  std::cout << std::endl;
    151151\endcode
    … …  
    167167  std::cout << "Id Edge  Value" << std::endl;
    168168  for (EdgeIt e(g); e!=INVALID; ++e)
    169     std::cout << g.id(e) << "  (" << g.id(g.tail(e)) << "," << g.id(g.head(e))
     169    std::cout << g.id(e) << "  (" << g.id(g.source(e)) << "," << g.id(g.target(e))
    170170      << ") " << m[e] << std::endl;
    171171\endcode

  • doc/maps.dox

    r927 r986  
    113113public:
    114114  ValueType operator[](KeyType e) const {
    115     return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
     115    return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));
    116116  }
    117117 

  • 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)) {