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

Timestamp:

01/11/07 22:06:47 (17 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:

• lemon/smart_graph.h (modified) (6 diffs)

lemon/smart_graph.h

@@ -367 +367 @@
 
 
-  /**************** Undirected List Graph ****************/
-
-  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
-  ExtendedSmartUGraphBase;
+  class SmartUGraphBase {
+
+  protected:
+
+    struct NodeT {
+      int first_out;
+    };
+ 
+    struct EdgeT {
+      int target;
+      int next_out;
+    };
+
+    std::vector<NodeT> nodes;
+    std::vector<EdgeT> edges;
+
+    int first_free_edge;
+    
+  public:
+    
+    typedef SmartUGraphBase Graph;
+    
+    class Node {
+      friend class SmartUGraphBase;
+    protected:
+
+      int id;
+      explicit Node(int pid) { id = pid;}
+
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node& node) const {return id == node.id;}
+      bool operator!=(const Node& node) const {return id != node.id;}
+      bool operator<(const Node& node) const {return id < node.id;}
+    };
+
+    class UEdge {
+      friend class SmartUGraphBase;
+    protected:
+
+      int id;
+      explicit UEdge(int pid) { id = pid;}
+
+    public:
+      UEdge() {}
+      UEdge (Invalid) { id = -1; }
+      bool operator==(const UEdge& edge) const {return id == edge.id;}
+      bool operator!=(const UEdge& edge) const {return id != edge.id;}
+      bool operator<(const UEdge& edge) const {return id < edge.id;}
+    };
+
+    class Edge {
+      friend class SmartUGraphBase;
+    protected:
+
+      int id;
+      explicit Edge(int pid) { id = pid;}
+
+    public:
+      operator UEdge() const { return UEdge(id / 2); }
+
+      Edge() {}
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge& edge) const {return id == edge.id;}
+      bool operator!=(const Edge& edge) const {return id != edge.id;}
+      bool operator<(const Edge& edge) const {return id < edge.id;}
+    };
+
+
+
+    SmartUGraphBase()
+      : nodes(), edges() {}
+
+    
+    int maxNodeId() const { return nodes.size()-1; } 
+    int maxUEdgeId() const { return edges.size() / 2 - 1; }
+    int maxEdgeId() const { return edges.size()-1; }
+
+    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
+    Node target(Edge e) const { return Node(edges[e.id].target); }
+
+    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
+    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
+
+    static bool direction(Edge e) {
+      return (e.id & 1) == 1;
+    }
+
+    static Edge direct(UEdge e, bool d) {
+      return Edge(e.id * 2 + (d ? 1 : 0));
+    }
+
+    void first(Node& node) const { 
+      node.id = nodes.size() - 1;
+    }
+
+    void next(Node& node) const {
+      --node.id;
+    }
+
+    void first(Edge& edge) const { 
+      edge.id = edges.size() - 1;
+    }
+
+    void next(Edge& edge) const {
+      --edge.id;
+    }
+
+    void first(UEdge& edge) const { 
+      edge.id = edges.size() / 2 - 1;
+    }
+
+    void next(UEdge& edge) const {
+      --edge.id;
+    }
+
+    void firstOut(Edge &edge, const Node& v) const {
+      edge.id = nodes[v.id].first_out;
+    }
+    void nextOut(Edge &edge) const {
+      edge.id = edges[edge.id].next_out;
+    }
+
+    void firstIn(Edge &edge, const Node& v) const {
+      edge.id = ((nodes[v.id].first_out) ^ 1);
+      if (e.id == -2) e.id = -1;
+    }
+    void nextIn(Edge &edge) const {
+      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
+      if (e.id == -2) e.id = -1;
+    }
+
+    void firstInc(UEdge &edge, bool& d, const Node& v) const {
+      int de = nodes[v.id].first_out;
+      edge.id = de / 2;
+      d = ((de & 1) == 1);
+    }
+    void nextInc(UEdge &edge, bool& d) const {
+      int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
+      edge.id = de / 2;
+      d = ((de & 1) == 1);
+    }
+    
+    static int id(Node v) { return v.id; }
+    static int id(Edge e) { return e.id; }
+    static int id(UEdge e) { return e.id; }
+
+    static Node nodeFromId(int id) { return Node(id);}
+    static Edge edgeFromId(int id) { return Edge(id);}
+    static UEdge uEdgeFromId(int id) { return UEdge(id);}
+
+    Node addNode() {     
+      int n = nodes.size();
+      nodes.push_back(NodeT());
+      nodes[n].first_out = -1;
+      
+      return Node(n);
+    }
+    
+    UEdge addEdge(Node u, Node v) {
+      int n = edges.size();
+      edges.push_back(EdgeT());
+      edges.push_back(EdgeT());
+      
+      edges[n].target = u.id;
+      edges[n | 1].target = v.id;
+
+      edges[n].next_out = nodes[v.id].first_out;
+      edges[n | 1].next_out = nodes[u.id].first_out;
+        
+      nodes[v.id].first_out = n;
+      nodes[u.id].first_out = (n | 1);
+
+      return UEdge(n / 2);
+    }
+    
+    void clear() {
+      edges.clear();
+      nodes.clear();
+    }
+
+  };
+
+  typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
 
   /// \ingroup graphs
@@ -408 +589 @@
 
     typedef ExtendedSmartUGraphBase Parent;
+    typedef Parent::OutEdgeIt IncEdgeIt;
 
     /// Constructor
@@ -444 +626 @@
   protected:
 
+    void saveSnapshot(Snapshot &s)
+    {
+      s.g = this;
+      s.node_num = nodes.size();
+      s.edge_num = edges.size();
+    }
 
     void restoreSnapshot(const Snapshot &s)
     {
       while(s.edge_num<edges.size()) {
-        UEdge edge = uEdgeFromId(edges.size()-1);
+        int n=edges.size()-1;
+        UEdge edge=uEdgeFromId(n/2);
         Parent::getNotifier(UEdge()).erase(edge);
         std::vector<Edge> dir;
-        dir.push_back(Parent::direct(edge, true));
-        dir.push_back(Parent::direct(edge, false));
+        dir.push_back(edgeFromId(n));
+        dir.push_back(edgeFromId(n-1));
         Parent::getNotifier(Edge()).erase(dir);
-        nodes[edges.back().source].first_out=edges.back().next_out;
-        nodes[edges.back().target].first_in=edges.back().next_in;
+        nodes[edges[n].target].first_out=edges[n].next_out;
+        nodes[edges[n-1].target].first_out=edges[n-1].next_out;
         edges.pop_back();
+        edges.pop_back();
       }
       while(s.node_num<nodes.size()) {
-        Node node = nodeFromId(nodes.size()-1);
+        int n=nodes.size()-1;
+        Node node = nodeFromId(n);
         Parent::getNotifier(Node()).erase(node);
         nodes.pop_back();
@@ -500 +691 @@
       ///This constructor immediately makes a snapshot of the graph.
       ///\param _g The graph we make a snapshot of.
-      Snapshot(SmartUGraph &_g) :g(&_g) {
-        node_num=g->nodes.size();
-        edge_num=g->edges.size();
+      Snapshot(SmartUGraph &g) {
+        g.saveSnapshot(*this);
       }
 
@@ -512 +702 @@
       ///call, the previous snapshot gets lost.
       ///\param _g The graph we make the snapshot of.
-      void save(SmartUGraph &_g) 
+      void save(SmartUGraph &g) 
       {
-        g=&_g;
-        node_num=g->nodes.size();
-        edge_num=g->edges.size();
+        g.saveSnapshot(*this);
       }
 
@@ -528 +716 @@
       void restore()
       {
-        g->restoreSnapshot(*this);
+        g->restoreSnapshot(*this);
       }
     };