COIN-OR::LEMON - Graph Library

Changeset 2338:359f0b71919b in lemon-0.x for lemon/smart_graph.h


Ignore:
Timestamp:
01/11/07 22:06:47 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3130
Message:

Changing implementation of undirected graphs
slightly faster, 10% speed-up

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r2261 r2338  
    367367
    368368
    369   /**************** Undirected List Graph ****************/
    370 
    371   typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
    372   ExtendedSmartUGraphBase;
     369  class SmartUGraphBase {
     370
     371  protected:
     372
     373    struct NodeT {
     374      int first_out;
     375    };
     376 
     377    struct EdgeT {
     378      int target;
     379      int next_out;
     380    };
     381
     382    std::vector<NodeT> nodes;
     383    std::vector<EdgeT> edges;
     384
     385    int first_free_edge;
     386   
     387  public:
     388   
     389    typedef SmartUGraphBase Graph;
     390   
     391    class Node {
     392      friend class SmartUGraphBase;
     393    protected:
     394
     395      int id;
     396      explicit Node(int pid) { id = pid;}
     397
     398    public:
     399      Node() {}
     400      Node (Invalid) { id = -1; }
     401      bool operator==(const Node& node) const {return id == node.id;}
     402      bool operator!=(const Node& node) const {return id != node.id;}
     403      bool operator<(const Node& node) const {return id < node.id;}
     404    };
     405
     406    class UEdge {
     407      friend class SmartUGraphBase;
     408    protected:
     409
     410      int id;
     411      explicit UEdge(int pid) { id = pid;}
     412
     413    public:
     414      UEdge() {}
     415      UEdge (Invalid) { id = -1; }
     416      bool operator==(const UEdge& edge) const {return id == edge.id;}
     417      bool operator!=(const UEdge& edge) const {return id != edge.id;}
     418      bool operator<(const UEdge& edge) const {return id < edge.id;}
     419    };
     420
     421    class Edge {
     422      friend class SmartUGraphBase;
     423    protected:
     424
     425      int id;
     426      explicit Edge(int pid) { id = pid;}
     427
     428    public:
     429      operator UEdge() const { return UEdge(id / 2); }
     430
     431      Edge() {}
     432      Edge (Invalid) { id = -1; }
     433      bool operator==(const Edge& edge) const {return id == edge.id;}
     434      bool operator!=(const Edge& edge) const {return id != edge.id;}
     435      bool operator<(const Edge& edge) const {return id < edge.id;}
     436    };
     437
     438
     439
     440    SmartUGraphBase()
     441      : nodes(), edges() {}
     442
     443   
     444    int maxNodeId() const { return nodes.size()-1; }
     445    int maxUEdgeId() const { return edges.size() / 2 - 1; }
     446    int maxEdgeId() const { return edges.size()-1; }
     447
     448    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
     449    Node target(Edge e) const { return Node(edges[e.id].target); }
     450
     451    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
     452    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
     453
     454    static bool direction(Edge e) {
     455      return (e.id & 1) == 1;
     456    }
     457
     458    static Edge direct(UEdge e, bool d) {
     459      return Edge(e.id * 2 + (d ? 1 : 0));
     460    }
     461
     462    void first(Node& node) const {
     463      node.id = nodes.size() - 1;
     464    }
     465
     466    void next(Node& node) const {
     467      --node.id;
     468    }
     469
     470    void first(Edge& edge) const {
     471      edge.id = edges.size() - 1;
     472    }
     473
     474    void next(Edge& edge) const {
     475      --edge.id;
     476    }
     477
     478    void first(UEdge& edge) const {
     479      edge.id = edges.size() / 2 - 1;
     480    }
     481
     482    void next(UEdge& edge) const {
     483      --edge.id;
     484    }
     485
     486    void firstOut(Edge &edge, const Node& v) const {
     487      edge.id = nodes[v.id].first_out;
     488    }
     489    void nextOut(Edge &edge) const {
     490      edge.id = edges[edge.id].next_out;
     491    }
     492
     493    void firstIn(Edge &edge, const Node& v) const {
     494      edge.id = ((nodes[v.id].first_out) ^ 1);
     495      if (e.id == -2) e.id = -1;
     496    }
     497    void nextIn(Edge &edge) const {
     498      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
     499      if (e.id == -2) e.id = -1;
     500    }
     501
     502    void firstInc(UEdge &edge, bool& d, const Node& v) const {
     503      int de = nodes[v.id].first_out;
     504      edge.id = de / 2;
     505      d = ((de & 1) == 1);
     506    }
     507    void nextInc(UEdge &edge, bool& d) const {
     508      int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
     509      edge.id = de / 2;
     510      d = ((de & 1) == 1);
     511    }
     512   
     513    static int id(Node v) { return v.id; }
     514    static int id(Edge e) { return e.id; }
     515    static int id(UEdge e) { return e.id; }
     516
     517    static Node nodeFromId(int id) { return Node(id);}
     518    static Edge edgeFromId(int id) { return Edge(id);}
     519    static UEdge uEdgeFromId(int id) { return UEdge(id);}
     520
     521    Node addNode() {     
     522      int n = nodes.size();
     523      nodes.push_back(NodeT());
     524      nodes[n].first_out = -1;
     525     
     526      return Node(n);
     527    }
     528   
     529    UEdge addEdge(Node u, Node v) {
     530      int n = edges.size();
     531      edges.push_back(EdgeT());
     532      edges.push_back(EdgeT());
     533     
     534      edges[n].target = u.id;
     535      edges[n | 1].target = v.id;
     536
     537      edges[n].next_out = nodes[v.id].first_out;
     538      edges[n | 1].next_out = nodes[u.id].first_out;
     539       
     540      nodes[v.id].first_out = n;
     541      nodes[u.id].first_out = (n | 1);
     542
     543      return UEdge(n / 2);
     544    }
     545   
     546    void clear() {
     547      edges.clear();
     548      nodes.clear();
     549    }
     550
     551  };
     552
     553  typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
    373554
    374555  /// \ingroup graphs
     
    408589
    409590    typedef ExtendedSmartUGraphBase Parent;
     591    typedef Parent::OutEdgeIt IncEdgeIt;
    410592
    411593    /// Constructor
     
    444626  protected:
    445627
     628    void saveSnapshot(Snapshot &s)
     629    {
     630      s.g = this;
     631      s.node_num = nodes.size();
     632      s.edge_num = edges.size();
     633    }
    446634
    447635    void restoreSnapshot(const Snapshot &s)
    448636    {
    449637      while(s.edge_num<edges.size()) {
    450         UEdge edge = uEdgeFromId(edges.size()-1);
     638        int n=edges.size()-1;
     639        UEdge edge=uEdgeFromId(n/2);
    451640        Parent::getNotifier(UEdge()).erase(edge);
    452641        std::vector<Edge> dir;
    453         dir.push_back(Parent::direct(edge, true));
    454         dir.push_back(Parent::direct(edge, false));
     642        dir.push_back(edgeFromId(n));
     643        dir.push_back(edgeFromId(n-1));
    455644        Parent::getNotifier(Edge()).erase(dir);
    456         nodes[edges.back().source].first_out=edges.back().next_out;
    457         nodes[edges.back().target].first_in=edges.back().next_in;
     645        nodes[edges[n].target].first_out=edges[n].next_out;
     646        nodes[edges[n-1].target].first_out=edges[n-1].next_out;
    458647        edges.pop_back();
     648        edges.pop_back();
    459649      }
    460650      while(s.node_num<nodes.size()) {
    461         Node node = nodeFromId(nodes.size()-1);
     651        int n=nodes.size()-1;
     652        Node node = nodeFromId(n);
    462653        Parent::getNotifier(Node()).erase(node);
    463654        nodes.pop_back();
     
    500691      ///This constructor immediately makes a snapshot of the graph.
    501692      ///\param _g The graph we make a snapshot of.
    502       Snapshot(SmartUGraph &_g) :g(&_g) {
    503         node_num=g->nodes.size();
    504         edge_num=g->edges.size();
     693      Snapshot(SmartUGraph &g) {
     694        g.saveSnapshot(*this);
    505695      }
    506696
     
    512702      ///call, the previous snapshot gets lost.
    513703      ///\param _g The graph we make the snapshot of.
    514       void save(SmartUGraph &_g)
     704      void save(SmartUGraph &g)
    515705      {
    516         g=&_g;
    517         node_num=g->nodes.size();
    518         edge_num=g->edges.size();
     706        g.saveSnapshot(*this);
    519707      }
    520708
     
    528716      void restore()
    529717      {
    530         g->restoreSnapshot(*this);
     718        g->restoreSnapshot(*this);
    531719      }
    532720    };
Note: See TracChangeset for help on using the changeset viewer.