COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 164:970b265696b0 in lemon-0.x for src/work


Ignore:
Timestamp:
03/10/04 18:47:54 (21 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@231
Message:

New graph interface

Location:
src/work/alpar
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/alpar/smart_graph.h

    r157 r164  
    77#include <limits.h>
    88
    9 struct _Invalid {} Invalid;
     9#include <invalid.h>
    1010
    1111namespace hugo {
    … …  
    4747    template <typename T> class DynEdgeMap;
    4848
     49    class Node;
     50    class Edge;
     51
     52  protected:
     53    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
     54    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
     55   
     56  public:
     57
    4958    class NodeIt;
    5059    class EdgeIt;
    51 
    52   protected:
    53     mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
    54     mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
    55    
    56   public:
    57 
    58     class EachNodeIt;
    59     class EachEdgeIt;
    6060    class OutEdgeIt;
    6161    class InEdgeIt;
    6262   
    63     //     class NodeIt { int n; };
    64     //     class EachNodeIt : public NodeIt { };
    65     //     class EdgeIt { int n; };
    66     //     class EachEdgeIt : public EdgeIt {};
    67     //     class OutEdgeIt : public EdgeIt {};
    68     //     class InEdgeIt : public EdgeIt {};
    69     //     class SymEdgeIt;
     63    //     class Node { int n; };
     64    //     class NodeIt : public Node { };
     65    //     class Edge { int n; };
     66    //     class EdgeIt : public Edge {};
     67    //     class OutEdgeIt : public Edge {};
     68    //     class InEdgeIt : public Edge {};
     69    //     class SymEdge;
    7070   
    7171    template <typename T> class NodeMap;
    … …  
    8181    ~SmartGraph()
    8282    {
    83       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
     83      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    8484          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    85       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
     85      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    8686          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    8787    }
    … …  
    9494
    9595   
    96     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
    97     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
    98 
    99 //     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
    100 //     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
    101 //     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
    102 
    103 //     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
    104 //     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
    105 //     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
    106 
    107     EachNodeIt& getFirst(EachNodeIt& v) const {
    108       v=EachNodeIt(*this); return v; }
    109     EachEdgeIt& getFirst(EachEdgeIt& e) const {
    110       e=EachEdgeIt(*this); return e; }
    111     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {
     96    Node tail(Edge e) const { return edges[e.n].tail; }
     97    Node head(Edge e) const { return edges[e.n].head; }
     98
     99//     Node aNode(const OutEdgeIt& e) const { return tail(e); }
     100//     Node aNode(const InEdgeIt& e) const { return head(e); }
     101//     //Node aNode(const SymEdge& e) const { return e.aNode(); }
     102
     103//     Node bNode(const OutEdgeIt& e) const { return head(e); }
     104//     Node bNode(const InEdgeIt& e) const { return tail(e); }
     105//     //Node bNode(const SymEdge& e) const { return e.bNode(); }
     106
     107    NodeIt& first(NodeIt& v) const {
     108      v=NodeIt(*this); return v; }
     109    EdgeIt& first(EdgeIt& e) const {
     110      e=EdgeIt(*this); return e; }
     111    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    112112      e=OutEdgeIt(*this,v); return e; }
    113     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {
     113    InEdgeIt& first(InEdgeIt& e, const Node v) const {
    114114      e=InEdgeIt(*this,v); return e; }
    115115
    … …  
    122122
    123123    template< typename It >
    124     It first(NodeIt v) const {
     124    It first(Node v) const {
    125125      It e;
    126126      getFirst(e, v);
    … …  
    128128    }
    129129
    130     bool valid(EdgeIt e) const { return e.n!=-1; }
    131     //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
    132     bool valid(NodeIt n) const { return n.n!=-1; }
    133    
    134     void setInvalid(EdgeIt &e) { e.n=-1; }
    135     void setInvalid(NodeIt &n) { n.n=-1; }
     130    bool valid(Edge e) const { return e.n!=-1; }
     131    //    bool valid(EdgeIt e) const { return e.n<int(edges.size()); }
     132    bool valid(Node n) const { return n.n!=-1; }
     133   
     134    void setInvalid(Edge &e) { e.n=-1; }
     135    void setInvalid(Node &n) { n.n=-1; }
    136136   
    137137    template <typename It> It getNext(It it) const
    … …  
    139139    //{ It tmp; tmp.n=it.n+1; return tmp; }
    140140
    141     NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
     141    Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
    142142    OutEdgeIt& next(OutEdgeIt& it) const
    143143    { it.n=edges[it.n].next_out; return it; }
    144144    InEdgeIt& next(InEdgeIt& it) const
    145145    { it.n=edges[it.n].next_in; return it; }
    146     EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
    147 
    148     int id(NodeIt v) const { return v.n; }
    149     int id(EdgeIt e) const { return e.n; }
    150 
    151     NodeIt addNode() {
    152       NodeIt n; n.n=nodes.size();
     146    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
     147
     148    int id(Node v) const { return v.n; }
     149    int id(Edge e) const { return e.n; }
     150
     151    Node addNode() {
     152      Node n; n.n=nodes.size();
    153153      nodes.push_back(NodeT()); //FIXME: Hmmm...
    154154
    155       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
     155      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    156156          i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
    157157
    … …  
    159159    }
    160160   
    161     EdgeIt addEdge(NodeIt u, NodeIt v) {
    162       EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
     161    Edge addEdge(Node u, Node v) {
     162      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
    163163      edges[e.n].tail=u.n; edges[e.n].head=v.n;
    164164      edges[e.n].next_out=nodes[u.n].first_out;
    … …  
    166166      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    167167
    168       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
     168      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    169169          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
    170170
    … …  
    174174    void clear() {nodes.clear();edges.clear();}
    175175
    176     class NodeIt {
     176    class Node {
    177177      friend class SmartGraph;
    178178      template <typename T> friend class NodeMap;
    179179      template <typename T> friend class DynNodeMap;
    180180     
    181       friend class EdgeIt;
     181      friend class Edge;
    182182      friend class OutEdgeIt;
    183183      friend class InEdgeIt;
    184       friend class SymEdgeIt;
     184      friend class SymEdge;
    185185
    186186    protected:
    187187      int n;
    188       friend int SmartGraph::id(NodeIt v) const;
    189       NodeIt(int nn) {n=nn;}
    190     public:
    191       NodeIt() {}
    192       NodeIt (_Invalid i) { n=-1; }
    193       bool operator==(const NodeIt i) const {return n==i.n;}
    194       bool operator!=(const NodeIt i) const {return n!=i.n;}
    195       bool operator<(const NodeIt i) const {return n<i.n;}
    196     };
    197    
    198     class EachNodeIt : public NodeIt {
    199       friend class SmartGraph;
    200     public:
    201       EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
    202       EachNodeIt() : NodeIt() { }
    203     };
    204 
    205     class EdgeIt {
     188      friend int SmartGraph::id(Node v) const;
     189      Node(int nn) {n=nn;}
     190    public:
     191      Node() {}
     192      Node (Invalid i) { n=-1; }
     193      bool operator==(const Node i) const {return n==i.n;}
     194      bool operator!=(const Node i) const {return n!=i.n;}
     195      bool operator<(const Node i) const {return n<i.n;}
     196    };
     197   
     198    class NodeIt : public Node {
     199      friend class SmartGraph;
     200    public:
     201      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
     202      NodeIt() : Node() { }
     203    };
     204
     205    class Edge {
    206206      friend class SmartGraph;
    207207      template <typename T> friend class EdgeMap;
    208208      template <typename T> friend class DynEdgeMap;
    209209     
     210      friend class Node;
    210211      friend class NodeIt;
    211       friend class EachNodeIt;
    212212    protected:
    213213      int n;
    214       friend int SmartGraph::id(EdgeIt e) const;
    215 
    216       EdgeIt(int nn) {n=nn;}
    217     public:
    218       EdgeIt() { }
    219       EdgeIt (_Invalid i) { n=-1; }
    220       bool operator==(const EdgeIt i) const {return n==i.n;}
    221       bool operator!=(const EdgeIt i) const {return n!=i.n;}
    222       bool operator<(const EdgeIt i) const {return n<i.n;}
    223     };
    224    
    225     class EachEdgeIt : public EdgeIt {
    226       friend class SmartGraph;
    227     public:
    228       EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
    229       EachEdgeIt (_Invalid i) : EdgeIt(i) { }
    230       EachEdgeIt() : EdgeIt() { }
    231     };
    232    
    233     class OutEdgeIt : public EdgeIt {
     214      friend int SmartGraph::id(Edge e) const;
     215
     216      Edge(int nn) {n=nn;}
     217    public:
     218      Edge() { }
     219      Edge (Invalid i) { n=-1; }
     220      bool operator==(const Edge i) const {return n==i.n;}
     221      bool operator!=(const Edge i) const {return n!=i.n;}
     222      bool operator<(const Edge i) const {return n<i.n;}
     223    };
     224   
     225    class EdgeIt : public Edge {
     226      friend class SmartGraph;
     227    public:
     228      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
     229      EdgeIt (Invalid i) : Edge(i) { }
     230      EdgeIt() : Edge() { }
     231    };
     232   
     233    class OutEdgeIt : public Edge {
    234234      friend class SmartGraph;
    235235    public:
    236       OutEdgeIt() : EdgeIt() { }
    237       OutEdgeIt (_Invalid i) : EdgeIt(i) { }
    238 
    239       OutEdgeIt(const SmartGraph& G,const NodeIt v)
    240         : EdgeIt(G.nodes[v.n].first_out) {}
    241     };
    242    
    243     class InEdgeIt : public EdgeIt {
     236      OutEdgeIt() : Edge() { }
     237      OutEdgeIt (Invalid i) : Edge(i) { }
     238
     239      OutEdgeIt(const SmartGraph& G,const Node v)
     240        : Edge(G.nodes[v.n].first_out) {}
     241    };
     242   
     243    class InEdgeIt : public Edge {
    244244      friend class SmartGraph;
    245245    public:
    246       InEdgeIt() : EdgeIt() { }
    247       InEdgeIt (_Invalid i) : EdgeIt(i) { }
    248       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
     246      InEdgeIt() : Edge() { }
     247      InEdgeIt (Invalid i) : Edge(i) { }
     248      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
    249249    };
    250250
    … …  
    257257    public:
    258258      typedef T ValueType;
    259       typedef NodeIt KeyType;
     259      typedef Node KeyType;
    260260      NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
    261261      NodeMap(const SmartGraph& _G, T a) :
    262262        G(_G), container(G.maxNodeId(), a) { }
    263       void set(NodeIt n, T a) { container[n.n]=a; }
    264       T get(NodeIt n) const { return container[n.n]; }
    265       T& operator[](NodeIt n) { return container[n.n]; }
    266       const T& operator[](NodeIt n) const { return container[n.n]; }
     263      void set(Node n, T a) { container[n.n]=a; }
     264      T get(Node n) const { return container[n.n]; }
     265      T& operator[](Node n) { return container[n.n]; }
     266      const T& operator[](Node n) const { return container[n.n]; }
    267267      void update() { container.resize(G.maxNodeId()); }
    268268      void update(T a) { container.resize(G.maxNodeId(), a); }
    … …  
    275275    public:
    276276      typedef T ValueType;
    277       typedef EdgeIt KeyType;
     277      typedef Edge KeyType;
    278278      EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
    279279      EdgeMap(const SmartGraph& _G, T a) :
    280280        G(_G), container(G.maxEdgeId(), a) { }
    281       void set(EdgeIt e, T a) { container[e.n]=a; }
    282       T get(EdgeIt e) const { return container[e.n]; }
    283       T& operator[](EdgeIt e) { return container[e.n]; }
    284       const T& operator[](EdgeIt e) const { return container[e.n]; }
     281      void set(Edge e, T a) { container[e.n]=a; }
     282      T get(Edge e) const { return container[e.n]; }
     283      T& operator[](Edge e) { return container[e.n]; }
     284      const T& operator[](Edge e) const { return container[e.n]; }
    285285      void update() { container.resize(G.maxEdgeId()); }
    286286      void update(T a) { container.resize(G.maxEdgeId(), a); }
    287287    };
    288288
    289     template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
     289    template <typename T> class DynNodeMap : public DynMapBase<Node>
    290290    {
    291291      std::vector<T> container;
    … …  
    293293    public:
    294294      typedef T ValueType;
    295       typedef NodeIt KeyType;
     295      typedef Node KeyType;
    296296
    297297      DynNodeMap(const SmartGraph &_G) :
    298         DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
     298        DynMapBase<Node>(_G), container(_G.maxNodeId())
    299299      {
    300300        //FIXME: What if there are empty Id's?
    … …  
    305305      {
    306306        if(G) {
    307           std::vector<DynMapBase<NodeIt>* >::iterator i;
     307          std::vector<DynMapBase<Node>* >::iterator i;
    308308          for(i=G->dyn_node_maps.begin();
    309309              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
    … …  
    317317      }
    318318
    319       void add(const NodeIt k)
     319      void add(const Node k)
    320320      {
    321321        if(k.n>=container.size()) container.resize(k.n+1);
    322322      }
    323 //       void erase(const NodeIt k)
     323//       void erase(const Node k)
    324324//       {
    325325//      //FIXME: Please implement me.
    326326//       }
    327 //       void erase(const EdgeIt k)
     327//       void erase(const Edge k)
    328328//       {
    329329//      //FIXME: Please implement me.
    330330//       }
    331331     
    332       void set(NodeIt n, T a) { container[n.n]=a; }
    333       T get(NodeIt n) const { return container[n.n]; }
    334       T& operator[](NodeIt n) { return container[n.n]; }
    335       const T& operator[](NodeIt n) const { return container[n.n]; }
     332      void set(Node n, T a) { container[n.n]=a; }
     333      T get(Node n) const { return container[n.n]; }
     334      T& operator[](Node n) { return container[n.n]; }
     335      const T& operator[](Node n) const { return container[n.n]; }
    336336
    337337      void update() {}    //Useless for DynMaps
    … …  
    339339    };
    340340   
    341     template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
     341    template <typename T> class DynEdgeMap : public DynMapBase<Edge>
    342342    {
    343343      std::vector<T> container;
    … …  
    345345    public:
    346346      typedef T ValueType;
    347       typedef EdgeIt KeyType;
     347      typedef Edge KeyType;
    348348
    349349      DynEdgeMap(const SmartGraph &_G) :
    350         DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
     350        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    351351      {
    352352        //FIXME: What if there are empty Id's?
    … …  
    357357      {
    358358        if(G) {
    359           std::vector<DynMapBase<EdgeIt>* >::iterator i;
     359          std::vector<DynMapBase<Edge>* >::iterator i;
    360360          for(i=G->dyn_edge_maps.begin();
    361361              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
    … …  
    369369      }
    370370     
    371       void add(const EdgeIt k)
     371      void add(const Edge k)
    372372      {
    373373        if(k.n>=int(container.size())) container.resize(k.n+1);
    374374      }
    375       void erase(const EdgeIt k)
     375      void erase(const Edge k)
    376376      {
    377377        //FIXME: Please implement me.
    378378      }
    379379     
    380       void set(EdgeIt n, T a) { container[n.n]=a; }
    381       T get(EdgeIt n) const { return container[n.n]; }
    382       T& operator[](EdgeIt n) { return container[n.n]; }
    383       const T& operator[](EdgeIt n) const { return container[n.n]; }
     380      void set(Edge n, T a) { container[n.n]=a; }
     381      T get(Edge n) const { return container[n.n]; }
     382      T& operator[](Edge n) { return container[n.n]; }
     383      const T& operator[](Edge n) const { return container[n.n]; }
    384384
    385385      void update() {}    //Useless for DynMaps

  • src/work/alpar/smart_graph_demo.cc

    r157 r164  
    11#include<smart_graph.h>
     2#include<emptygraph.h>
    23
    34#include <iostream>
     5#include <vector>
    46
    57using namespace hugo;
    68
    7 SmartGraph::OutEdgeIt safeFirstOut(const SmartGraph &G, SmartGraph::NodeIt n)
     9//typedef SmartGraph Graph;
     10typedef EmptyGraph Graph;
     11
     12
     13Graph::OutEdgeIt safeFirstOut(const Graph &G, Graph::Node n)
    814{
    9   return G.valid(n) ? SmartGraph::OutEdgeIt(G,n):Invalid;
     15  return G.valid(n) ? Graph::OutEdgeIt(G,n):INVALID;
    1016}
    1117
    … …  
    1319{
    1420
    15   typedef SmartGraph::EdgeIt EdgeIt;
    16   typedef SmartGraph::InEdgeIt InEdgeIt;
    17   typedef SmartGraph::OutEdgeIt OutEdgeIt;
    18   typedef SmartGraph::EachEdgeIt EachEdgeIt;
    19   typedef SmartGraph::NodeIt NodeIt;
    20   typedef SmartGraph::EachNodeIt EachNodeIt;
     21  typedef Graph::Edge Edge;
     22  typedef Graph::InEdgeIt InEdgeIt;
     23  typedef Graph::OutEdgeIt OutEdgeIt;
     24  typedef Graph::EdgeIt EdgeIt;
     25  typedef Graph::Node Node;
     26  typedef Graph::NodeIt NodeIt;
    2127 
    22   SmartGraph G;
    23   EachNodeIt n;
     28  Graph G;
     29  NodeIt n;
    2430
    2531
    26   //  std::cout.form("%s: %d\n","Sztring",15);
    27 
    2832  for(int i=0;i<10;i++) G.addNode();
    29   for(G.getFirst(n);G.valid(n);G.next(n))
    30     for(EachNodeIt m(G);m!=Invalid;G.next(m))
     33  for(G.first(n);G.valid(n);G.next(n))
     34    for(NodeIt m(G);m!=INVALID;G.next(m))
    3135      if(n!=m) G.addEdge(n,m);
    3236
    3337  OutEdgeIt e = safeFirstOut(G,n);
    34   OutEdgeIt f = safeFirstOut(G,EachNodeIt(G));
     38  OutEdgeIt f = safeFirstOut(G,NodeIt(G));
     39 
     40
     41  InEdgeIt i(INVALID), j;
     42  InEdgeIt ii(i);
     43  ii=G.first(i,n);
     44  ii=G.next(i);
     45 
     46  OutEdgeIt o(INVALID), oo;
     47  OutEdgeIt ooo(oo);
     48  oo=G.first(o,n);
     49  oo=G.next(o);
     50 
     51  EdgeIt ei(INVALID), eie;
     52  EdgeIt eiee(ei);
     53  eie=G.first(ei);
     54  eie=G.next(ei);
     55
     56  Edge eee(i);
     57  eee=o;
     58  eee=eie;
     59 
     60 
     61  bool tm;
     62  tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei);
     63
     64  std::vector<InEdgeIt> v(10);
     65  std::vector<InEdgeIt> w(10,INVALID);
    3566 
    3667}
Note: See TracChangeset for help on using the changeset viewer.