COIN-OR::LEMON - Graph Library

Changeset 397:b4d7b19b6740 in lemon-0.x for src/work


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

I hope it works. The 'erase' functions hasn't been tested yet.

Location:
src/work/alpar
Files:
1 added
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/list_graph.h

    r396 r397  
    55
    66///\file
    7 ///\brief SmartGraph and SymSmartGraph classes.
     7///\brief ListGraph and SymListGraph classes.
    88
    99#include <vector>
     
    1414namespace hugo {
    1515
    16   class SymSmartGraph;
     16  class SymListGraph;
    1717
    1818  ///A smart graph class.
    1919
    20   ///This is a simple and fast graph implementation.
    21   ///It is also quite memory efficient, but at the price
    22   ///that <b> it does not support node and edge deletion</b>.
     20  ///This is a simple and fast erasable graph implementation.
     21  ///
    2322  ///It conforms to the graph interface documented under
    2423  ///the description of \ref GraphSkeleton.
    2524  ///\sa \ref GraphSkeleton.
    26   class SmartGraph {
    27 
     25  class ListGraph {
     26
     27    //Nodes are double linked.
     28    //The free nodes are only single linked using the "next" field.
    2829    struct NodeT
    2930    {
    30       int first_in,first_out;     
    31       NodeT() : first_in(-1), first_out(-1) {}
    32     };
     31      int first_in,first_out;
     32      int prev, next;
     33      //      NodeT() {}
     34    };
     35    //Edges are double linked.
     36    //The free edges are only single linked using the "next_in" field.
    3337    struct EdgeT
    3438    {
    35       int head, tail, next_in, next_out;     
     39      int head, tail;
     40      int prev_in, prev_out;
     41      int next_in, next_out;
    3642      //FIXME: is this necessary?
    37       EdgeT() : next_in(-1), next_out(-1) {} 
     43      //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {} 
    3844    };
    3945
    4046    std::vector<NodeT> nodes;
    41 
     47    //The first node
     48    int first_node;
     49    //The first free node
     50    int first_free_node;
    4251    std::vector<EdgeT> edges;
    43    
     52    //The first free edge
     53    int first_free_edge;
     54   
     55  protected:
     56   
     57    template <typename Key> class DynMapBase
     58    {
    4459    protected:
    45    
    46     template <typename Key> class DynMapBase
    47     {
    48     protected:
    49       const SmartGraph* G;
     60      const ListGraph* G;
    5061    public:
    5162      virtual void add(const Key k) = NULL;
    5263      virtual void erase(const Key k) = NULL;
    53       DynMapBase(const SmartGraph &_G) : G(&_G) {}
     64      DynMapBase(const ListGraph &_G) : G(&_G) {}
    5465      virtual ~DynMapBase() {}
    55       friend class SmartGraph;
     66      friend class ListGraph;
    5667    };
    5768   
     
    5970    template <typename T> class EdgeMap;
    6071    template <typename T> class EdgeMap;
    61 
     72   
    6273    class Node;
    6374    class Edge;
     
    8596  public:
    8697
    87     SmartGraph() : nodes(), edges() { }
    88     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
    89    
    90     ~SmartGraph()
     98    ListGraph() : nodes(), first_node(-1),
     99                  first_free_node(-1), edges(), first_free_edge(-1) {}
     100    ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
     101                                     first_free_node(_g.first_free_node),
     102                                     edges(_g.edges),
     103                                     first_free_edge(_g.first_free_edge) {}
     104   
     105    ~ListGraph()
    91106    {
    92107      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
     
    140155
    141156    NodeIt& next(NodeIt& it) const {
    142       it.n=(it.n+2)%(nodes.size()+1)-1;
     157      it.n=nodes[it.n].next;
    143158      return it;
    144159    }
     
    147162    InEdgeIt& next(InEdgeIt& it) const
    148163    { it.n=edges[it.n].next_in; return it; }
    149     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
     164    EdgeIt& next(EdgeIt& it) const {
     165      if(edges[it.n].next_in!=-1) {
     166        it.n=edges[it.n].next_in;
     167      }
     168      else {
     169        int n;
     170        for(n=nodes[edges[it.n].head].next;
     171            n!=-1 && nodes[n].first_in == -1;
     172            n = nodes[n].next) ;
     173        it.n = (n==-1)?-1:nodes[n].first_in;
     174      }
     175      return it;
     176    }
    150177
    151178    int id(Node v) const { return v.n; }
    152179    int id(Edge e) const { return e.n; }
    153180
     181    /// Adds a new node to the graph.
     182
     183    /// \todo It adds the nodes in a reversed order.
     184    /// (i.e. the lastly added node becomes the first.)
    154185    Node addNode() {
    155       Node n; n.n=nodes.size();
    156       nodes.push_back(NodeT()); //FIXME: Hmmm...
    157 
     186      int n;
     187     
     188      if(first_free_node==-1)
     189        {
     190          n = nodes.size();
     191          nodes.push_back(NodeT());
     192        }
     193      else {
     194        n = first_free_node;
     195        first_free_node = nodes[n].next;
     196      }
     197     
     198      nodes[n].next = first_node;
     199      if(first_node != -1) nodes[first_node].prev = n;
     200      first_node = n;
     201      nodes[n].prev = -1;
     202     
     203      nodes[n].first_in = nodes[n].first_out = -1;
     204     
     205      Node nn; nn.n=n;
     206
     207      //Update dynamic maps
    158208      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    159           i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
    160 
    161       return n;
     209          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
     210
     211      return nn;
    162212    }
    163213   
    164214    Edge addEdge(Node u, Node v) {
    165       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
    166       edges[e.n].tail=u.n; edges[e.n].head=v.n;
    167       edges[e.n].next_out=nodes[u.n].first_out;
    168       edges[e.n].next_in=nodes[v.n].first_in;
    169       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    170 
     215      int n;
     216     
     217      if(first_free_edge==-1)
     218        {
     219          n = edges.size();
     220          edges.push_back(EdgeT());
     221        }
     222      else {
     223        n = first_free_edge;
     224        first_free_edge = edges[n].next_in;
     225      }
     226     
     227      edges[n].tail = u.n; edges[n].head = v.n;
     228
     229      edges[n].next_out = nodes[u.n].first_out;
     230      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
     231      edges[n].next_in = nodes[v.n].first_in;
     232      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
     233      edges[n].prev_in = edges[n].prev_out = -1;
     234       
     235      nodes[u.n].first_out = nodes[v.n].first_in = n;
     236
     237      Edge e; e.n=n;
     238
     239      //Update dynamic maps
    171240      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    172241          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
     
    175244    }
    176245
    177     void clear() {nodes.clear();edges.clear();}
     246  private:
     247    void eraseEdge(int n) {
     248     
     249      if(edges[n].next_in!=-1)
     250        edges[edges[n].next_in].prev_in = edges[n].prev_in;
     251      if(edges[n].prev_in!=-1)
     252        edges[edges[n].prev_in].next_in = edges[n].next_in;
     253      else nodes[edges[n].head].first_in = edges[n].next_in;
     254     
     255      if(edges[n].next_out!=-1)
     256        edges[edges[n].next_out].prev_out = edges[n].prev_out;
     257      if(edges[n].prev_out!=-1)
     258        edges[edges[n].prev_out].next_out = edges[n].next_out;
     259      else nodes[edges[n].tail].first_out = edges[n].next_out;
     260     
     261      edges[n].next_in = first_free_edge;
     262      first_free_edge = -1;     
     263
     264      //Update dynamic maps
     265      Edge e; e.n=n;
     266      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
     267          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
     268    }
     269     
     270  public:
     271
     272    void erase(Node nn) {
     273      int n=nn.n;
     274     
     275      int m;
     276      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
     277      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
     278
     279      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
     280      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
     281      else first_node = nodes[n].next;
     282     
     283      nodes[n].next = first_free_node;
     284      first_free_node = n;
     285
     286      //Update dynamic maps
     287      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
     288          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
     289    }
     290   
     291    void erase(Edge e) { eraseEdge(e.n); }
     292
     293    ///\bug Dynamic maps must be updated!
     294    ///
     295    void clear() {
     296      nodes.clear();edges.clear();
     297      first_node=first_free_node=first_free_edge=-1;
     298    }
    178299
    179300    class Node {
    180       friend class SmartGraph;
     301      friend class ListGraph;
    181302      template <typename T> friend class NodeMap;
    182303     
     
    188309    protected:
    189310      int n;
    190       friend int SmartGraph::id(Node v) const;
     311      friend int ListGraph::id(Node v) const;
    191312      Node(int nn) {n=nn;}
    192313    public:
     
    199320   
    200321    class NodeIt : public Node {
    201       friend class SmartGraph;
     322      friend class ListGraph;
    202323    public:
    203       NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
     324      NodeIt(const ListGraph& G) : Node(G.first_node) { }
    204325      NodeIt() : Node() { }
    205326    };
    206327
    207328    class Edge {
    208       friend class SmartGraph;
     329      friend class ListGraph;
    209330      template <typename T> friend class EdgeMap;
    210331
    211       //template <typename T> friend class SymSmartGraph::SymEdgeMap;     
    212       //friend Edge SymSmartGraph::opposite(Edge) const;
     332      //template <typename T> friend class SymListGraph::SymEdgeMap;     
     333      //friend Edge SymListGraph::opposite(Edge) const;
    213334     
    214335      friend class Node;
     
    216337    protected:
    217338      int n;
    218       friend int SmartGraph::id(Edge e) const;
     339      friend int ListGraph::id(Edge e) const;
    219340
    220341      Edge(int nn) {n=nn;}
     
    226347      bool operator<(const Edge i) const {return n<i.n;}
    227348      ///\bug This is a workaround until somebody tells me how to
    228       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
     349      ///make class \c SymListGraph::SymEdgeMap friend of Edge
    229350      int &idref() {return n;}
    230351      const int &idref() const {return n;}
     
    232353   
    233354    class EdgeIt : public Edge {
    234       friend class SmartGraph;
     355      friend class ListGraph;
    235356    public:
    236       EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
     357      EdgeIt(const ListGraph& G) : Edge() {
     358        int m;
     359        for(m=G.first_node;
     360            m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
     361        n = (m==-1)?-1:G.nodes[m].first_in;
     362      }
    237363      EdgeIt (Invalid i) : Edge(i) { }
    238364      EdgeIt() : Edge() { }
    239365      ///\bug This is a workaround until somebody tells me how to
    240       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
     366      ///make class \c SymListGraph::SymEdgeMap friend of Edge
    241367      int &idref() {return n;}
    242368    };
    243369   
    244370    class OutEdgeIt : public Edge {
    245       friend class SmartGraph;
     371      friend class ListGraph;
    246372    public:
    247373      OutEdgeIt() : Edge() { }
    248374      OutEdgeIt (Invalid i) : Edge(i) { }
    249375
    250       OutEdgeIt(const SmartGraph& G,const Node v)
     376      OutEdgeIt(const ListGraph& G,const Node v)
    251377        : Edge(G.nodes[v.n].first_out) {}
    252378    };
    253379   
    254380    class InEdgeIt : public Edge {
    255       friend class SmartGraph;
     381      friend class ListGraph;
    256382    public:
    257383      InEdgeIt() : Edge() { }
    258384      InEdgeIt (Invalid i) : Edge(i) { }
    259       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
     385      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
    260386    };
    261387
     
    268394      typedef Node KeyType;
    269395
    270       NodeMap(const SmartGraph &_G) :
     396      NodeMap(const ListGraph &_G) :
    271397        DynMapBase<Node>(_G), container(_G.maxNodeId())
    272398      {
    273399        G->dyn_node_maps.push_back(this);
    274400      }
    275       NodeMap(const SmartGraph &_G,const T &t) :
     401      NodeMap(const ListGraph &_G,const T &t) :
    276402        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
    277403      {
     
    358484      typedef Edge KeyType;
    359485
    360       EdgeMap(const SmartGraph &_G) :
     486      EdgeMap(const ListGraph &_G) :
    361487        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    362488      {
     
    365491        G->dyn_edge_maps.push_back(this);
    366492      }
    367       EdgeMap(const SmartGraph &_G,const T &t) :
     493      EdgeMap(const ListGraph &_G,const T &t) :
    368494        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    369495      {
     
    447573  ///of oppositely directed edges.
    448574  ///There is a new edge map type called
    449   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
     575  ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
    450576  ///that complements this
    451577  ///feature by
     
    457583  ///The oppositely directed edge can also be obtained easily
    458584  ///using \ref opposite.
    459   ///\warning It shares the similarity with \ref SmartGraph that
    460   ///it is not possible to delete edges or nodes from the graph.
    461   //\sa \ref SmartGraph.
    462 
    463   class SymSmartGraph : public SmartGraph
     585  ///
     586  ///Here erase(Edge) deletes a pair of edges.
     587  ///
     588  ///\todo this date structure need some reconsiderations. Maybe it
     589  ///should be implemented independently from ListGraph.
     590
     591  class SymListGraph : public ListGraph
    464592  {
    465593  public:
     
    467595    template<typename T> friend class SymEdgeMap;
    468596
    469     SymSmartGraph() : SmartGraph() { }
    470     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
     597    SymListGraph() : ListGraph() { }
     598    SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
     599    ///Adds a pair of oppositely directed edges to the graph.
    471600    Edge addEdge(Node u, Node v)
    472601    {
    473       Edge e = SmartGraph::addEdge(u,v);
    474       SmartGraph::addEdge(v,u);
     602      Edge e = ListGraph::addEdge(u,v);
     603      ListGraph::addEdge(v,u);
    475604      return e;
    476605    }
    477606
     607    void erase(Node n) { ListGraph::erase(n); }
    478608    ///The oppositely directed edge.
    479609
     
    487617    }
    488618   
     619    ///Removes a pair of oppositely directed edges to the graph.
     620    void erase(Edge e) {
     621      ListGraph::erase(opposite(e));
     622      ListGraph::erase(e);
     623    }
     624   
    489625    ///Common data storage for the edge pairs.
    490626
     
    499635      typedef Edge KeyType;
    500636
    501       SymEdgeMap(const SymSmartGraph &_G) :
     637      SymEdgeMap(const SymListGraph &_G) :
    502638        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
    503639      {
    504         static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
    505       }
    506       SymEdgeMap(const SymSmartGraph &_G,const T &t) :
     640        static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
     641      }
     642      SymEdgeMap(const SymListGraph &_G,const T &t) :
    507643        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
    508644      {
     
    536672        if(G) {
    537673          std::vector<DynMapBase<Edge>* >::iterator i;
    538           for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
    539               i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
     674          for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
     675              i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
    540676                && *i!=this; ++i) ;
    541677          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    542678          //A better way to do that: (Is this really important?)
    543679          if(*i==this) {
    544             *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
    545             static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
     680            *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
     681            static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
    546682          }
    547683        }
Note: See TracChangeset for help on using the changeset viewer.