LEMON/LEMON-main Changeset - r670:926c47568a56

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r670:926c47568a56

« 669:4faca8

671:da70af »

r670:926c47568a56

Wed, 13 May 2009 10:42:26

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Add artificial addNode() function to the arc/edge set classes

0 1 0

default

1 file changed with 24 insertions and 0 deletions:

lemon/edge_set.h

↑ Collapse diff ↑

lemon/edge_set.h

Show inline comments

@@ -39,96 +39,102 @@
 		  protected:
 		    struct NodeT {
 		      int first_out, first_in;
 		      NodeT() : first_out(-1), first_in(-1) {}
 		    };
 		    typedef typename ItemSetTraits<GR, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* _nodes;
 		    struct ArcT {
 		      Node source, target;
 		      int next_out, next_in;
 		      int prev_out, prev_in;
 		      ArcT() : prev_out(-1), prev_in(-1) {}
 		    };
 		    std::vector<ArcT> arcs;
 		    int first_arc;
 		    int first_free_arc;
 		    const GR* _graph;
 		    void initalize(const GR& graph, NodesImplBase& nodes) {
 		      _graph = &graph;
 		      _nodes = &nodes;
+		    }
 		  public:
 		    class Arc {
 		      friend class ListArcSetBase<GR>;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
 		    Node addNode() {
 		      LEMON_ASSERT(false,
 		        "This graph structure does not support node insertion");
 		      return INVALID; // avoid warning
+		    }
 		    Arc addArc(const Node& u, const Node& v) {
 		      int n;
 		      if (first_free_arc == -1) {
 		        n = arcs.size();
 		        arcs.push_back(ArcT());
 		      } else {
 		        n = first_free_arc;
 		        first_free_arc = arcs[first_free_arc].next_in;
+		      }
 		      arcs[n].next_in = (*_nodes)[v].first_in;
 		      if ((*_nodes)[v].first_in != -1) {
 		        arcs[(*_nodes)[v].first_in].prev_in = n;
+		      }
 		      (*_nodes)[v].first_in = n;
 		      arcs[n].next_out = (*_nodes)[u].first_out;
 		      if ((*_nodes)[u].first_out != -1) {
 		        arcs[(*_nodes)[u].first_out].prev_out = n;
+		      }
 		      (*_nodes)[u].first_out = n;
 		      arcs[n].source = u;
 		      arcs[n].target = v;
 		      return Arc(n);
+		    }
 		    void erase(const Arc& arc) {
 		      int n = arc.id;
 		      if (arcs[n].prev_in != -1) {
 		        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 		      } else {
 		        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
+		      }
 		      if (arcs[n].next_in != -1) {
 		        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+		      }
 		      if (arcs[n].prev_out != -1) {
 		        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 		        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
+		      }
 		      if (arcs[n].next_out != -1) {
 		        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
+		    }
 		    void clear() {
 		      Node node;
@@ -371,96 +377,102 @@
 		    };
 		    std::vector<ArcT> arcs;
 		    int first_arc;
 		    int first_free_arc;
 		    const GR* _graph;
 		    void initalize(const GR& graph, NodesImplBase& nodes) {
 		      _graph = &graph;
 		      _nodes = &nodes;
+		    }
 		  public:
 		    class Edge {
 		      friend class ListEdgeSetBase;
 		    protected:
 		      int id;
 		      explicit Edge(int _id) { id = _id;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { id = -1; }
 		      bool operator==(const Edge& arc) const {return id == arc.id;}
 		      bool operator!=(const Edge& arc) const {return id != arc.id;}
 		      bool operator<(const Edge& arc) const {return id < arc.id;}
 		    };
 		    class Arc {
 		      friend class ListEdgeSetBase;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      operator Edge() const { return edgeFromId(id / 2); }
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
 		    Node addNode() {
 		      LEMON_ASSERT(false,
 		        "This graph structure does not support node insertion");
 		      return INVALID; // avoid warning
+		    }
 		    Edge addEdge(const Node& u, const Node& v) {
 		      int n;
 		      if (first_free_arc == -1) {
 		        n = arcs.size();
 		        arcs.push_back(ArcT());
 		        arcs.push_back(ArcT());
 		      } else {
 		        n = first_free_arc;
 		        first_free_arc = arcs[n].next_out;
+		      }
 		      arcs[n].target = u;
 		      arcs[n | 1].target = v;
 		      arcs[n].next_out = (*_nodes)[v].first_out;
 		      if ((*_nodes)[v].first_out != -1) {
 		        arcs[(*_nodes)[v].first_out].prev_out = n;
+		      }
 		      (*_nodes)[v].first_out = n;
 		      arcs[n].prev_out = -1;
 		      if ((*_nodes)[u].first_out != -1) {
 		        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
+		      }
 		      arcs[n | 1].next_out = (*_nodes)[u].first_out;
 		      (*_nodes)[u].first_out = (n | 1);
 		      arcs[n | 1].prev_out = -1;
 		      return Edge(n / 2);
+		    }
 		    void erase(const Edge& arc) {
 		      int n = arc.id * 2;
 		      if (arcs[n].next_out != -1) {
 		        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
 		      if (arcs[n].prev_out != -1) {
 		        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 		        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
+		      }
 		      if (arcs[n | 1].next_out != -1) {
 		        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
+		      }
@@ -771,96 +783,102 @@
 		    typedef typename GR::Node Node;
 		    typedef typename GR::NodeIt NodeIt;
 		  protected:
 		    struct NodeT {
 		      int first_out, first_in;
 		      NodeT() : first_out(-1), first_in(-1) {}
 		    };
 		    typedef typename ItemSetTraits<GR, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* _nodes;
 		    struct ArcT {
 		      Node source, target;
 		      int next_out, next_in;
 		      ArcT() {}
 		    };
 		    std::vector<ArcT> arcs;
 		    const GR* _graph;
 		    void initalize(const GR& graph, NodesImplBase& nodes) {
 		      _graph = &graph;
 		      _nodes = &nodes;
+		    }
 		  public:
 		    class Arc {
 		      friend class SmartArcSetBase<GR>;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    SmartArcSetBase() {}
 		    Node addNode() {
 		      LEMON_ASSERT(false,
 		        "This graph structure does not support node insertion");
 		      return INVALID; // avoid warning
+		    }
 		    Arc addArc(const Node& u, const Node& v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs[n].next_in = (*_nodes)[v].first_in;
 		      (*_nodes)[v].first_in = n;
 		      arcs[n].next_out = (*_nodes)[u].first_out;
 		      (*_nodes)[u].first_out = n;
 		      arcs[n].source = u;
 		      arcs[n].target = v;
 		      return Arc(n);
+		    }
 		    void clear() {
 		      Node node;
 		      for (first(node); node != INVALID; next(node)) {
 		        (*_nodes)[node].first_in = -1;
 		        (*_nodes)[node].first_out = -1;
+		      }
 		      arcs.clear();
+		    }
 		    void first(Node& node) const {
 		      _graph->first(node);
+		    }
 		    void next(Node& node) const {
 		      _graph->next(node);
+		    }
 		    void first(Arc& arc) const {
 		      arc.id = arcs.size() - 1;
+		    }
 		    void next(Arc& arc) const {
 		      --arc.id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc.id = (*_nodes)[node].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc.id = (*_nodes)[node].first_in;
+		    }
@@ -1067,96 +1085,102 @@
 		      Node target;
 		      int next_out;
 		      ArcT() {}
 		    };
 		    std::vector<ArcT> arcs;
 		    const GR* _graph;
 		    void initalize(const GR& graph, NodesImplBase& nodes) {
 		      _graph = &graph;
 		      _nodes = &nodes;
+		    }
 		  public:
 		    class Edge {
 		      friend class SmartEdgeSetBase;
 		    protected:
 		      int id;
 		      explicit Edge(int _id) { id = _id;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { id = -1; }
 		      bool operator==(const Edge& arc) const {return id == arc.id;}
 		      bool operator!=(const Edge& arc) const {return id != arc.id;}
 		      bool operator<(const Edge& arc) const {return id < arc.id;}
 		    };
 		    class Arc {
 		      friend class SmartEdgeSetBase;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      operator Edge() const { return edgeFromId(id / 2); }
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    SmartEdgeSetBase() {}
 		    Node addNode() {
 		      LEMON_ASSERT(false,
 		        "This graph structure does not support node insertion");
 		      return INVALID; // avoid warning
+		    }
 		    Edge addEdge(const Node& u, const Node& v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs.push_back(ArcT());
 		      arcs[n].target = u;
 		      arcs[n | 1].target = v;
 		      arcs[n].next_out = (*_nodes)[v].first_out;
 		      (*_nodes)[v].first_out = n;
 		      arcs[n | 1].next_out = (*_nodes)[u].first_out;
 		      (*_nodes)[u].first_out = (n | 1);
 		      return Edge(n / 2);
+		    }
 		    void clear() {
 		      Node node;
 		      for (first(node); node != INVALID; next(node)) {
 		        (*_nodes)[node].first_out = -1;
+		      }
 		      arcs.clear();
+		    }
 		    void first(Node& node) const {
 		      _graph->first(node);
+		    }
 		    void next(Node& node) const {
 		      _graph->next(node);
+		    }
 		    void first(Arc& arc) const {
 		      arc.id = arcs.size() - 1;
+		    }
 		    void next(Arc& arc) const {
 		      --arc.id;
+		    }
 		    void first(Edge& arc) const {
 		      arc.id = arcs.size() / 2 - 1;
+		    }
 		    void next(Edge& arc) const {
 		      --arc.id;
+		    }

0 comments (0 inline)

RhodeCode

Login to your account