# HG changeset patch
# User deba
# Date 1168549607 0
# Node ID 359f0b71919bb03316881147f23bd5734b5eb37d
# Parent  9c3d44ac39fbc30ad9002c0a3a247823ce32c991
Changing implementation of undirected graphs
slightly faster, 10% speed-up

diff -r 9c3d44ac39fb -r 359f0b71919b lemon/list_graph.h
--- a/lemon/list_graph.h	Thu Jan 11 21:05:00 2007 +0000
+++ b/lemon/list_graph.h	Thu Jan 11 21:06:47 2007 +0000
@@ -98,16 +98,7 @@
 	first_free_node(-1), edges(), first_free_edge(-1) {}
 
     
-    /// 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; }
 
     Node source(Edge e) const { return Node(edges[e.id].source); }
@@ -164,12 +155,6 @@
     static Node nodeFromId(int id) { return Node(id);}
     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;
       
@@ -735,10 +720,368 @@
 
   ///@}
 
-  /**************** Undirected List Graph ****************/
+  class ListUGraphBase {
 
-  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
-  ExtendedListUGraphBase;
+  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
   /// @{
@@ -776,6 +1119,9 @@
     ListUGraph() {}
 
     typedef ExtendedListUGraphBase Parent;
+
+    typedef Parent::OutEdgeIt IncEdgeIt;
+
     /// \brief Add a new node to the graph.
     ///
     /// \return the new node.
diff -r 9c3d44ac39fb -r 359f0b71919b lemon/smart_graph.h
--- a/lemon/smart_graph.h	Thu Jan 11 21:05:00 2007 +0000
+++ b/lemon/smart_graph.h	Thu Jan 11 21:06:47 2007 +0000
@@ -366,10 +366,191 @@
   };
 
 
-  /**************** Undirected List Graph ****************/
+  class SmartUGraphBase {
 
-  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
-  ExtendedSmartUGraphBase;
+  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
   ///
@@ -407,6 +588,7 @@
   public:
 
     typedef ExtendedSmartUGraphBase Parent;
+    typedef Parent::OutEdgeIt IncEdgeIt;
 
     /// Constructor
     
@@ -443,22 +625,31 @@
 
   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();
       }
@@ -499,9 +690,8 @@
       
       ///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);
       }
 
       ///Make a snapshot.
@@ -511,11 +701,9 @@
       ///This function can be called more than once. In case of a repeated
       ///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);
       }
 
       ///Undo the changes until a snapshot.
@@ -527,7 +715,7 @@
       ///by restore().
       void restore()
       {
-	g->restoreSnapshot(*this);
+        g->restoreSnapshot(*this);
       }
     };
   };