Changeset 2338:359f0b71919b in lemon-0.x for lemon/list_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/list_graph.h (modified) (4 diffs)

lemon/list_graph.h

@@ -99 +99 @@
 
     
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
     int maxNodeId() const { return nodes.size()-1; } 
-
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
     int maxEdgeId() const { return edges.size()-1; }
 
@@ -165 +156 @@
     static Edge edgeFromId(int id) { return Edge(id);}
 
-    /// Adds a new node to the graph.
-
-    /// Adds a new node to the graph.
-    ///
-    /// \warning It adds the new node to the front of the list.
-    /// (i.e. the lastly added node becomes the first.)
     Node addNode() {     
       int n;
@@ -736 +721 @@
   ///@}
 
-  /**************** Undirected List Graph ****************/
-
-  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
-  ExtendedListUGraphBase;
+  class ListUGraphBase {
+
+  protected:
+
+    struct NodeT {
+      int first_out;
+      int prev, next;
+    };
+ 
+    struct EdgeT {
+      int target;
+      int prev_out, next_out;
+    };
+
+    std::vector<NodeT> nodes;
+
+    int first_node;
+
+    int first_free_node;
+
+    std::vector<EdgeT> edges;
+
+    int first_free_edge;
+    
+  public:
+    
+    typedef ListUGraphBase Graph;
+    
+    class Node {
+      friend class ListUGraphBase;
+    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 ListUGraphBase;
+    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 ListUGraphBase;
+    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;}
+    };
+
+
+
+    ListUGraphBase()
+      : nodes(), first_node(-1),
+        first_free_node(-1), edges(), first_free_edge(-1) {}
+
+    
+    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 = first_node;
+    }
+
+    void next(Node& node) const {
+      node.id = nodes[node.id].next;
+    }
+
+    void first(Edge& e) const { 
+      int n = first_node;
+      while (n != -1 && nodes[n].first_out == -1) {
+        n = nodes[n].next;
+      }
+      e.id = (n == -1) ? -1 : nodes[n].first_out;
+    }
+
+    void next(Edge& e) const {
+      if (edges[e.id].next_out != -1) {
+        e.id = edges[e.id].next_out;
+      } else {
+        int n = nodes[edges[e.id ^ 1].target].next;
+        while(n != -1 && nodes[n].first_out == -1) {
+          n = nodes[n].next;
+        }
+        e.id = (n == -1) ? -1 : nodes[n].first_out;
+      }      
+    }
+
+    void first(UEdge& e) const { 
+      int n = first_node;
+      while (n != -1) {
+        e.id = nodes[n].first_out;
+        while ((e.id & 1) != 1) {
+          e.id = edges[e.id].next_out;
+        }
+        if (e.id != -1) {
+          e.id /= 2;
+          return;
+        } 
+        n = nodes[n].next;
+      }
+      e.id = -1;
+    }
+
+    void next(UEdge& e) const {
+      int n = edges[e.id * 2].target;
+      e.id = edges[(e.id * 2) | 1].next_out;
+      while ((e.id & 1) != 1) {
+        e.id = edges[e.id].next_out;
+      }
+      if (e.id != -1) {
+        e.id /= 2;
+        return;
+      } 
+      n = nodes[n].next;
+      while (n != -1) {
+        e.id = nodes[n].first_out;
+        while ((e.id & 1) != 1) {
+          e.id = edges[e.id].next_out;
+        }
+        if (e.id != -1) {
+          e.id /= 2;
+          return;
+        } 
+        n = nodes[n].next;
+      }
+      e.id = -1;
+    }
+
+    void firstOut(Edge &e, const Node& v) const {
+      e.id = nodes[v.id].first_out;
+    }
+    void nextOut(Edge &e) const {
+      e.id = edges[e.id].next_out;
+    }
+
+    void firstIn(Edge &e, const Node& v) const {
+      e.id = ((nodes[v.id].first_out) ^ 1);
+      if (e.id == -2) e.id = -1;
+    }
+    void nextIn(Edge &e) const {
+      e.id = ((edges[e.id ^ 1].next_out) ^ 1);
+      if (e.id == -2) e.id = -1;
+    }
+
+    void firstInc(UEdge &e, bool& d, const Node& v) const {
+      int de = nodes[v.id].first_out;
+      e.id = de / 2;
+      d = ((de & 1) == 1);
+    }
+    void nextInc(UEdge &e, bool& d) const {
+      int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
+      e.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;
+      
+      if(first_free_node==-1) {
+        n = nodes.size();
+        nodes.push_back(NodeT());
+      } else {
+        n = first_free_node;
+        first_free_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_node;
+      if (first_node != -1) nodes[first_node].prev = n;
+      first_node = n;
+      nodes[n].prev = -1;
+      
+      nodes[n].first_out = -1;
+      
+      return Node(n);
+    }
+    
+    UEdge addEdge(Node u, Node v) {
+      int n;      
+
+      if (first_free_edge == -1) {
+        n = edges.size();
+        edges.push_back(EdgeT());
+        edges.push_back(EdgeT());
+      } else {
+        n = first_free_edge;
+        first_free_edge = edges[n].next_out;
+      }
+      
+      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;
+      if (nodes[v.id].first_out != -1) {
+        edges[nodes[v.id].first_out].prev_out = n;
+      }
+      if (nodes[u.id].first_out != -1) {
+        edges[nodes[u.id].first_out].prev_out = (n | 1);
+      }
+      
+      edges[n].prev_out = edges[n | 1].prev_out = -1;
+        
+      nodes[v.id].first_out = n;
+      nodes[u.id].first_out = (n | 1);
+
+      return UEdge(n / 2);
+    }
+    
+    void erase(const Node& node) {
+      int n = node.id;
+      
+      if(nodes[n].next != -1) {
+        nodes[nodes[n].next].prev = nodes[n].prev;
+      }
+      
+      if(nodes[n].prev != -1) {
+        nodes[nodes[n].prev].next = nodes[n].next;
+      } else {
+        first_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_free_node;
+      first_free_node = n;
+
+    }
+    
+    void erase(const UEdge& edge) {
+      int n = edge.id * 2;
+      
+      if (edges[n].next_out != -1) {
+        edges[edges[n].next_out].prev_out = edges[n].prev_out;
+      } 
+
+      if (edges[n].prev_out != -1) {
+        edges[edges[n].prev_out].next_out = edges[n].next_out;
+      } else {
+        nodes[edges[n | 1].target].first_out = edges[n].next_out;
+      }
+
+      if (edges[n | 1].next_out != -1) {
+        edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
+      } 
+
+      if (edges[n | 1].prev_out != -1) {
+        edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
+      } else {
+        nodes[edges[n].target].first_out = edges[n | 1].next_out;
+      }
+      
+      edges[n].next_out = first_free_edge;
+      first_free_edge = n;      
+
+    }
+
+    void clear() {
+      edges.clear();
+      nodes.clear();
+      first_node = first_free_node = first_free_edge = -1;
+    }
+
+  protected:
+
+    void changeTarget(UEdge e, Node n) {
+      if(edges[2 * e.id].next_out != -1) {
+        edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
+      }
+      if(edges[2 * e.id].prev_out != -1) {
+        edges[edges[2 * e.id].prev_out].next_out = 
+          edges[2 * e.id].next_out;
+      } else {
+        nodes[edges[(2 * e.id) | 1].target].first_out = 
+          edges[2 * e.id].next_out;
+      }
+
+      if (nodes[n.id].first_out != -1) {
+        edges[nodes[n.id].first_out].prev_out = 2 * e.id;
+      }
+      edges[(2 * e.id) | 1].target = n.id;
+      edges[2 * e.id].prev_out = -1;
+      edges[2 * e.id].next_out = nodes[n.id].first_out;
+      nodes[n.id].first_out = 2 * e.id;
+    }
+
+    void changeSource(UEdge e, Node n) {
+      if(edges[(2 * e.id) | 1].next_out != -1) {
+        edges[edges[(2 * e.id) | 1].next_out].prev_out = 
+          edges[(2 * e.id) | 1].prev_out;
+      }
+      if(edges[(2 * e.id) | 1].prev_out != -1) {
+        edges[edges[(2 * e.id) | 1].prev_out].next_out = 
+          edges[(2 * e.id) | 1].next_out;
+      } else {
+        nodes[edges[2 * e.id].target].first_out = 
+          edges[(2 * e.id) | 1].next_out;
+      }
+
+      if (nodes[n.id].first_out != -1) {
+        edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
+      }
+      edges[2 * e.id].target = n.id;
+      edges[(2 * e.id) | 1].prev_out = -1;
+      edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
+      nodes[n.id].first_out = ((2 * e.id) | 1);
+    }
+
+  };
+
+//   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
+//   ExtendedListUGraphBase;
+
+  typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
+
+
 
   /// \addtogroup graphs
@@ -777 +1120 @@
 
     typedef ExtendedListUGraphBase Parent;
+
+    typedef Parent::OutEdgeIt IncEdgeIt;
+
     /// \brief Add a new node to the graph.
     ///