# HG changeset patch
# User deba
# Date 1192807267 0
# Node ID 290e43cddc1ab11d20b99ab30d7eecc9dddd9f4a
# Parent  ea96c0acefc42fa6b8fbeb3142618c51597adc49
Bug fix in undirected graphs (adding loops)
Bug fix in undirected edgesets (alteration notifying)

Redesigned undirected edgesets (like the smart or ugraph)

diff -r ea96c0acefc4 -r 290e43cddc1a lemon/bits/edge_set_extender.h
--- a/lemon/bits/edge_set_extender.h	Fri Oct 19 13:50:13 2007 +0000
+++ b/lemon/bits/edge_set_extender.h	Fri Oct 19 15:21:07 2007 +0000
@@ -590,8 +590,10 @@
     UEdge addEdge(const Node& from, const Node& to) {
       UEdge uedge = Parent::addEdge(from, to);
       notifier(UEdge()).add(uedge);
-      notifier(Edge()).add(Parent::direct(uedge, true));
-      notifier(Edge()).add(Parent::direct(uedge, false));
+      std::vector<Edge> edges;
+      edges.push_back(Parent::direct(uedge, true));
+      edges.push_back(Parent::direct(uedge, false));
+      notifier(Edge()).add(edges);
       return uedge;
     }
     
@@ -602,8 +604,10 @@
     }
 
     void erase(const UEdge& uedge) {
-      notifier(Edge()).erase(Parent::direct(uedge, true));
-      notifier(Edge()).erase(Parent::direct(uedge, false));
+      std::vector<Edge> edges;
+      edges.push_back(Parent::direct(uedge, true));
+      edges.push_back(Parent::direct(uedge, false));
+      notifier(Edge()).erase(edges);
       notifier(UEdge()).erase(uedge);
       Parent::erase(uedge);
     }
diff -r ea96c0acefc4 -r 290e43cddc1a lemon/edge_set.h
--- a/lemon/edge_set.h	Fri Oct 19 13:50:13 2007 +0000
+++ b/lemon/edge_set.h	Fri Oct 19 15:21:07 2007 +0000
@@ -241,8 +241,6 @@
   /// this class. Its interface must conform to the \ref concepts::Graph
   /// "Graph" concept.
   ///
-  /// In the edge extension and removing it conforms to the 
-  /// \ref concepts::Graph "Graph" concept.
   template <typename _Graph>
   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
 
@@ -320,6 +318,315 @@
     
   };
 
+  template <typename _Graph>
+  class ListUEdgeSetBase {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+
+  protected:
+
+    struct NodeT {
+      int first_out;
+      NodeT() : first_out(-1) {}
+    };
+
+    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
+
+    NodesImplBase* nodes;
+
+    struct EdgeT {
+      Node target;
+      int prev_out, next_out;
+      EdgeT() : prev_out(-1), next_out(-1) {}
+    };
+
+    std::vector<EdgeT> edges;
+
+    int first_edge;
+    int first_free_edge;
+
+    const Graph* graph;
+
+    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
+      graph = &_graph;
+      nodes = &_nodes;
+    }
+    
+  public:
+
+    class UEdge {
+      friend class ListUEdgeSetBase;
+    protected:
+
+      int id;
+      explicit UEdge(int _id) { id = _id;}
+
+    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 ListUEdgeSetBase;
+    protected:
+      Edge(int _id) : id(_id) {}
+      int id;
+    public:
+      operator UEdge() const { return uEdgeFromId(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; }
+    };
+
+    ListUEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} 
+
+    UEdge addEdge(const Node& u, const 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;
+      edges[n | 1].target = v;
+
+      edges[n].next_out = (*nodes)[v].first_out;
+      if ((*nodes)[v].first_out != -1) {
+	edges[(*nodes)[v].first_out].prev_out = n;
+      }
+      (*nodes)[v].first_out = n;
+      edges[n].prev_out = -1;
+      
+      if ((*nodes)[u].first_out != -1) {
+	edges[(*nodes)[u].first_out].prev_out = (n | 1);
+      }
+      edges[n | 1].next_out = (*nodes)[u].first_out;
+      (*nodes)[u].first_out = (n | 1);
+      edges[n | 1].prev_out = -1;
+
+      return UEdge(n / 2);
+    }
+
+    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() {
+      Node node;
+      for (first(node); node != INVALID; next(node)) {
+        (*nodes)[node].first_out = -1;
+      }
+      edges.clear();
+      first_edge = -1;
+      first_free_edge = -1;
+    }
+
+    void first(Node& node) const {
+      graph->first(node);
+    }
+
+    void next(Node& node) const {
+      graph->next(node);
+    }
+
+    void first(Edge& edge) const {
+      Node node;
+      first(node);
+      while (node != INVALID && (*nodes)[node].first_out == -1) {
+        next(node);
+      }
+      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
+    }
+
+    void next(Edge& edge) const {
+      if (edges[edge.id].next_out != -1) {
+	edge.id = edges[edge.id].next_out;
+      } else {
+	Node node = edges[edge.id ^ 1].target;
+	next(node);
+        while(node != INVALID && (*nodes)[node].first_out == -1) {
+          next(node);
+        }
+	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
+      }      
+    }
+
+    void first(UEdge& uedge) const {
+      Node node;
+      first(node);
+      while (node != INVALID) {
+        uedge.id = (*nodes)[node].first_out;
+        while ((uedge.id & 1) != 1) {
+          uedge.id = edges[uedge.id].next_out;
+        }
+        if (uedge.id != -1) {
+          uedge.id /= 2;
+          return;
+        } 
+        next(node);
+      }
+      uedge.id = -1;
+    }
+
+    void next(UEdge& uedge) const {
+      Node node = edges[uedge.id * 2].target;
+      uedge.id = edges[(uedge.id * 2) | 1].next_out;
+      while ((uedge.id & 1) != 1) {
+        uedge.id = edges[uedge.id].next_out;
+      }
+      if (uedge.id != -1) {
+        uedge.id /= 2;
+        return;
+      } 
+      next(node);
+      while (node != INVALID) {
+        uedge.id = (*nodes)[node].first_out;
+        while ((uedge.id & 1) != 1) {
+          uedge.id = edges[uedge.id].next_out;
+        }
+        if (uedge.id != -1) {
+          uedge.id /= 2;
+          return;
+        } 
+	next(node);
+      }
+      uedge.id = -1;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge.id = (*nodes)[node].first_out;
+    }
+    
+    void nextOut(Edge& edge) const {
+      edge.id = edges[edge.id].next_out;        
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.id = (((*nodes)[node].first_out) ^ 1);
+      if (edge.id == -2) edge.id = -1;
+    }
+
+    void nextIn(Edge& edge) const {
+      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
+      if (edge.id == -2) edge.id = -1;
+    }
+
+    void firstInc(UEdge &edge, bool& dir, const Node& node) const {
+      int de = (*nodes)[node].first_out;
+      if (de != -1 ) {
+        edge.id = de / 2;
+        dir = ((de & 1) == 1);
+      } else {
+        edge.id = -1;
+        dir = true;
+      }
+    }
+    void nextInc(UEdge &edge, bool& dir) const {
+      int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
+      if (de != -1 ) {
+        edge.id = de / 2;
+        dir = ((de & 1) == 1);
+      } else {
+        edge.id = -1;
+        dir = true;
+      }
+    }
+
+    static bool direction(Edge edge) {
+      return (edge.id & 1) == 1;
+    }
+
+    static Edge direct(UEdge uedge, bool dir) {
+      return Edge(uedge.id * 2 + (dir ? 1 : 0));
+    }
+
+    int id(const Node& node) const { return graph->id(node); }
+    static int id(Edge e) { return e.id; }
+    static int id(UEdge e) { return e.id; }
+
+    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
+    static Edge edgeFromId(int id) { return Edge(id);}
+    static UEdge uEdgeFromId(int id) { return UEdge(id);}
+
+    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxUEdgeId() const { return edges.size() / 2 - 1; }
+    int maxEdgeId() const { return edges.size()-1; }
+
+    Node source(Edge e) const { return edges[e.id ^ 1].target; }
+    Node target(Edge e) const { return edges[e.id].target; }
+
+    Node source(UEdge e) const { return edges[2 * e.id].target; }
+    Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
+
+    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+
+    NodeNotifier& notifier(Node) const {
+      return graph->notifier(Node());
+    } 
+
+    template <typename _Value>
+    class NodeMap : public Graph::template NodeMap<_Value> {
+    public:
+
+      typedef typename _Graph::template NodeMap<_Value> Parent;
+
+      explicit NodeMap(const ListUEdgeSetBase<Graph>& edgeset) 
+	: Parent(*edgeset.graph) {}
+
+      NodeMap(const ListUEdgeSetBase<Graph>& edgeset, const _Value& value)
+	: Parent(*edgeset.graph, value) {}
+
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+
+      template <typename CMap>
+      NodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+
+  };
+
   /// \ingroup semi_adaptors
   ///
   /// \brief Graph using a node set of another graph and an
@@ -336,13 +643,11 @@
   /// In the edge extension and removing it conforms to the 
   /// \ref concepts::UGraph "UGraph" concept.
   template <typename _Graph>
-  class ListUEdgeSet 
-    : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
+  class ListUEdgeSet : public UEdgeSetExtender<ListUEdgeSetBase<_Graph> > {
 
   public:
 
-    typedef UEdgeSetExtender<UndirGraphExtender<
-      ListEdgeSetBase<_Graph> > > Parent;
+    typedef UEdgeSetExtender<ListUEdgeSetBase<_Graph> > Parent;
     
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
@@ -661,6 +966,220 @@
     
   };
 
+
+  template <typename _Graph>
+  class SmartUEdgeSetBase {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+
+  protected:
+
+    struct NodeT {
+      int first_out;
+      NodeT() : first_out(-1) {}
+    };
+
+    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
+
+    NodesImplBase* nodes;
+
+    struct EdgeT {
+      Node target;
+      int next_out;
+      EdgeT() {}
+    };
+
+    std::vector<EdgeT> edges;
+
+    const Graph* graph;
+
+    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
+      graph = &_graph;
+      nodes = &_nodes;
+    }
+    
+  public:
+
+    class UEdge {
+      friend class SmartUEdgeSetBase;
+    protected:
+
+      int id;
+      explicit UEdge(int _id) { id = _id;}
+
+    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 SmartUEdgeSetBase;
+    protected:
+      Edge(int _id) : id(_id) {}
+      int id;
+    public:
+      operator UEdge() const { return uEdgeFromId(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; }
+    };
+
+    SmartUEdgeSetBase() {} 
+
+    UEdge addEdge(const Node& u, const Node& v) {
+      int n = edges.size();
+      edges.push_back(EdgeT());
+      edges.push_back(EdgeT());
+      
+      edges[n].target = u;
+      edges[n | 1].target = v;
+
+      edges[n].next_out = (*nodes)[v].first_out;
+      (*nodes)[v].first_out = n;
+
+      edges[n | 1].next_out = (*nodes)[u].first_out;	
+      (*nodes)[u].first_out = (n | 1);
+
+      return UEdge(n / 2);
+    }
+
+    void clear() {
+      Node node;
+      for (first(node); node != INVALID; next(node)) {
+        (*nodes)[node].first_out = -1;
+      }
+      edges.clear();
+    }
+
+    void first(Node& node) const {
+      graph->first(node);
+    }
+
+    void next(Node& node) const {
+      graph->next(node);
+    }
+
+    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& node) const {
+      edge.id = (*nodes)[node].first_out;    
+    }
+    
+    void nextOut(Edge& edge) const {
+      edge.id = edges[edge.id].next_out;        
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.id = (((*nodes)[node].first_out) ^ 1);
+      if (edge.id == -2) edge.id = -1;
+    }
+
+    void nextIn(Edge& edge) const {
+      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
+      if (edge.id == -2) edge.id = -1;
+    }
+
+    void firstInc(UEdge &edge, bool& dir, const Node& node) const {
+      int de = (*nodes)[node].first_out;
+      if (de != -1 ) {
+        edge.id = de / 2;
+        dir = ((de & 1) == 1);
+      } else {
+        edge.id = -1;
+        dir = true;
+      }
+    }
+    void nextInc(UEdge &edge, bool& dir) const {
+      int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
+      if (de != -1 ) {
+        edge.id = de / 2;
+        dir = ((de & 1) == 1);
+      } else {
+        edge.id = -1;
+        dir = true;
+      }
+    }
+
+    static bool direction(Edge edge) {
+      return (edge.id & 1) == 1;
+    }
+
+    static Edge direct(UEdge uedge, bool dir) {
+      return Edge(uedge.id * 2 + (dir ? 1 : 0));
+    }
+
+    int id(Node node) const { return graph->id(node); }
+    static int id(Edge edge) { return edge.id; }
+    static int id(UEdge edge) { return edge.id; }
+
+    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
+    static Edge edgeFromId(int id) { return Edge(id); }
+    static UEdge uEdgeFromId(int id) { return UEdge(id);}
+
+    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxEdgeId() const { return edges.size() - 1; }
+    int maxUEdgeId() const { return edges.size() / 2 - 1; }
+
+    Node source(Edge e) const { return edges[e.id ^ 1].target; }
+    Node target(Edge e) const { return edges[e.id].target; }
+
+    Node source(UEdge e) const { return edges[2 * e.id].target; }
+    Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
+
+    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+
+    NodeNotifier& notifier(Node) const {
+      return graph->notifier(Node());
+    } 
+
+    template <typename _Value>
+    class NodeMap : public Graph::template NodeMap<_Value> {
+    public:
+
+      typedef typename _Graph::template NodeMap<_Value> Parent;
+
+      explicit NodeMap(const SmartUEdgeSetBase<Graph>& edgeset) 
+	: Parent(*edgeset.graph) { }
+
+      NodeMap(const SmartUEdgeSetBase<Graph>& edgeset, const _Value& value)
+	: Parent(*edgeset.graph, value) { }
+
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+
+      template <typename CMap>
+      NodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+
+  };
+
   /// \ingroup semi_adaptors
   ///
   /// \brief Graph using a node set of another graph and an
@@ -677,13 +1196,11 @@
   /// In the edge extension and removing it conforms to the 
   /// \ref concepts::UGraph "UGraph" concept.
   template <typename _Graph>
-  class SmartUEdgeSet 
-    : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
+  class SmartUEdgeSet : public UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > {
 
   public:
 
-    typedef UEdgeSetExtender<UndirGraphExtender<
-      SmartEdgeSetBase<_Graph> > > Parent;
+    typedef UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > Parent;
     
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
diff -r ea96c0acefc4 -r 290e43cddc1a lemon/list_graph.h
--- a/lemon/list_graph.h	Fri Oct 19 13:50:13 2007 +0000
+++ b/lemon/list_graph.h	Fri Oct 19 15:21:07 2007 +0000
@@ -977,17 +977,17 @@
       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;
-      }
+      }      
+      edges[n].prev_out = -1;
+      nodes[v.id].first_out = n;
+      
+      edges[n | 1].next_out = nodes[u.id].first_out;
       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;
+      edges[n | 1].prev_out = -1;      
       nodes[u.id].first_out = (n | 1);
 
       return UEdge(n / 2);
diff -r ea96c0acefc4 -r 290e43cddc1a lemon/smart_graph.h
--- a/lemon/smart_graph.h	Fri Oct 19 13:50:13 2007 +0000
+++ b/lemon/smart_graph.h	Fri Oct 19 15:21:07 2007 +0000
@@ -185,10 +185,10 @@
 
   typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
 
-  /// \ingroup graphs
-
-  ///A smart graph class.
-
+  ///\ingroup graphs
+  ///
+  ///\brief A smart graph class.
+  ///
   ///This is a simple and fast graph implementation.
   ///It is also quite memory efficient, but at the price
   ///that <b> it does support only limited (only stack-like)
@@ -571,9 +571,9 @@
       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;
+
+      edges[n | 1].next_out = nodes[u.id].first_out;	
       nodes[u.id].first_out = (n | 1);
 
       return UEdge(n / 2);