COIN-OR::LEMON - Graph Library

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


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/work/alpar
Files:
10 edited

Legend:

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