Changeset 2498:290e43cddc1a in lemon-0.x

Timestamp:

10/19/07 17:21:07 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3337

Message:

Bug fix in undirected graphs (adding loops)
Bug fix in undirected edgesets (alteration notifying)

Redesigned undirected edgesets (like the smart or ugraph)

Location:

lemon

Files:

• bits/edge_set_extender.h (modified) (2 diffs)
• edge_set.h (modified) (5 diffs)
• list_graph.h (modified) (1 diff)
• smart_graph.h (modified) (2 diffs)

lemon/bits/edge_set_extender.h

@@ -591 +591 @@
       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;
     }
@@ -603 +605 @@
 
     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);

lemon/edge_set.h

@@ -242 +242 @@
   /// "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> > {
@@ -321 +319 @@
   };
 
+  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
   ///
@@ -337 +644 @@
   /// \ref concepts::UGraph "UGraph" concept.
   template <typename _Graph>
-  class ListUEdgeSet 
-    : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
-
-  public:
-
-    typedef UEdgeSetExtender<UndirGraphExtender<
-      ListEdgeSetBase<_Graph> > > Parent;
+  class ListUEdgeSet : public UEdgeSetExtender<ListUEdgeSetBase<_Graph> > {
+
+  public:
+
+    typedef UEdgeSetExtender<ListUEdgeSetBase<_Graph> > Parent;
     
     typedef typename Parent::Node Node;
@@ -662 +967 @@
   };
 
+
+  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
   ///
@@ -678 +1197 @@
   /// \ref concepts::UGraph "UGraph" concept.
   template <typename _Graph>
-  class SmartUEdgeSet 
-    : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
-
-  public:
-
-    typedef UEdgeSetExtender<UndirGraphExtender<
-      SmartEdgeSetBase<_Graph> > > Parent;
+  class SmartUEdgeSet : public UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > {
+
+  public:
+
+    typedef UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > Parent;
     
     typedef typename Parent::Node Node;

lemon/list_graph.h

@@ -978 +978 @@
 
       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);
 

lemon/smart_graph.h

@@ -186 +186 @@
   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
@@ -572 +572 @@
 
       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);