COIN-OR::LEMON - Graph Library

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


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
Location:
src/lemon
Files:
21 edited

Legend:

Unmodified
Added
Removed
  • 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        }
Note: See TracChangeset for help on using the changeset viewer.