LEMON/LEMON-main Changeset - r149:2f7ae34e1333

Repositories » LEMON » LEMON-main

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

Changeset - r149:2f7ae34e1333

« 148:4e2581

154:f4e4db »

r149:2f7ae34e1333

Thu, 24 Apr 2008 14:53:09

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Item validity checking for ListGraph and SmartGraph

0 3 0

default

3 files changed with 211 insertions and 46 deletions:

lemon/list_graph.h

lemon/smart_graph.h

test/graph_test.cc

↑ Collapse diff ↑

lemon/list_graph.h

Show inline comments

@@ -143,24 +143,34 @@
+		    }
 		    void nextIn(Arc &e) const {
 		      e.id=arcs[e.id].next_in;
+		    }
 		    static int id(Node v) { return v.id; }
 		    static int id(Arc e) { return e.id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    bool valid(Node n) const {
 		      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
 			nodes[n.id].prev != -2;
+		    }
 		    bool valid(Arc a) const {
 		      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
 			arcs[a.id].prev_in != -2;
+		    }
 		    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;
@@ -210,24 +220,25 @@
 		      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;
 		      nodes[n].prev = -2;
+		    }
 		    void erase(const Arc& arc) {
 		      int n = arc.id;
 		      if(arcs[n].next_in!=-1) {
 			arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+		      }
 		      if(arcs[n].prev_in!=-1) {
 			arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
@@ -239,25 +250,25 @@
 		      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].source].first_out = arcs[n].next_out;
+		      }
 		      arcs[n].next_in = first_free_arc;
 		      first_free_arc = n;
+		      arcs[n].prev_in = -2;
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
 		      first_node = first_free_node = first_free_arc = -1;
+		    }
 		  protected:
 		    void changeTarget(Arc e, Node n)
+		    {
 		      if(arcs[e.id].next_in != -1)
@@ -341,24 +352,44 @@
 		    ///\return the new node.
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new arc to the digraph.
 		    ///Add a new arc to the digraph with source node \c s
 		    ///and target node \c t.
 		    ///\return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    /// Node validity check
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Change the target of \c e to \c n
 		    /// Change the target of \c e to \c n
 		    ///
 		    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
 		    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeTarget(Arc e, Node n) {
 		      Parent::changeTarget(e,n);
@@ -936,24 +967,39 @@
 		        d = true;
+		      }
+		    }
 		    static int id(Node v) { return v.id; }
 		    static int id(Arc e) { return e.id; }
 		    static int id(Edge e) { return e.id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    bool valid(Node n) const {
 		      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
 			nodes[n.id].prev != -2;
+		    }
 		    bool valid(Arc a) const {
 		      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
 			arcs[a.id].prev_out != -2;
+		    }
 		    bool valid(Edge e) const {
 		      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
 			arcs[2 * e.id].prev_out != -2;
+		    }
 		    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;
@@ -1004,25 +1050,25 @@
 		      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;
+		      nodes[n].prev = -2;
+		    }
 		    void erase(const Edge& edge) {
 		      int n = edge.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 {
@@ -1032,24 +1078,26 @@
 		      if (arcs[n | 1].next_out != -1) {
 			arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
+		      }
 		      if (arcs[n | 1].prev_out != -1) {
 			arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
 		      } else {
 			nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
+		      }
 		      arcs[n].next_out = first_free_arc;
 		      first_free_arc = n;
 		      arcs[n].prev_out = -2;
 		      arcs[n | 1].prev_out = -2;
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
 		      first_node = first_free_node = first_free_arc = -1;
+		    }
 		  protected:
 		    void changeTarget(Edge e, Node n) {
@@ -1148,24 +1196,51 @@
 		    /// Add a new node to the graph.
 		    /// \return the new node.
 		    Node addNode() { return Parent::addNode(); }
 		    /// \brief Add a new edge to the graph.
 		    ///
 		    /// Add a new edge to the graph with source node \c s
 		    /// and target node \c t.
 		    /// \return the new edge.
 		    Edge addEdge(const Node& s, const Node& t) {
 		      return Parent::addEdge(s, t);
+		    }
 		    /// Node validity check
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new edges are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Edge validity check
 		    /// This function gives back true if the given edge is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning A Edge pointing to a removed item
 		    /// could become valid again later if new edges are
 		    /// added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    /// \brief Change the source of \c e to \c n
 		    ///
 		    /// This function changes the source of \c e to \c n.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
 		    ///referencing the changed arc remain
 		    ///valid. However <tt>OutArcIt</tt>s are invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void changeSource(Edge e, Node n) {
 		      Parent::changeSource(e,n);

lemon/smart_graph.h

Show inline comments

@@ -106,24 +106,31 @@
 		      nodes.clear();
+		    }
 		    Node source(Arc a) const { return Node(arcs[a._id].source); }
 		    Node target(Arc a) const { return Node(arcs[a._id].target); }
 		    static int id(Node v) { return v._id; }
 		    static int id(Arc a) { return a._id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    bool valid(Node n) const {
 		      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
+		    }
 		    bool valid(Arc a) const {
 		      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+		    }
 		    class Node {
 		      friend class SmartDigraphBase;
 		      friend class SmartDigraph;
 		    protected:
 		      int _id;
 		      explicit Node(int id) : _id(id) {}
 		    public:
 		      Node() {}
 		      Node (Invalid) : _id(-1) {}
 		      bool operator==(const Node i) const {return _id == i._id;}
 		      bool operator!=(const Node i) const {return _id != i._id;}
@@ -252,24 +259,42 @@
 		    /// \brief Using this it is possible to avoid the superfluous memory
 		    /// allocation.
 		    /// Using this it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveNode
 		    void reserveArc(int m) { arcs.reserve(m); };
 		    /// \brief Node validity check
 		    ///
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A removed node (using Snapshot) could become valid again
 		    /// when new nodes are added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// \brief Arc validity check
 		    ///
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning A removed arc (using Snapshot) could become valid again
 		    /// when new arcs are added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    ///Clear the digraph.
 		    ///Erase all the nodes and arcs from the digraph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		    ///Split a node.
 		    ///This function splits a node. First a new node is added to the digraph,
 		    ///then the source of each outgoing arc of \c n is moved to this new node.
@@ -541,24 +566,34 @@
 		        d = true;
+		      }
+		    }
 		    static int id(Node v) { return v._id; }
 		    static int id(Arc e) { return e._id; }
 		    static int id(Edge e) { return e._id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    bool valid(Node n) const {
 		      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
+		    }
 		    bool valid(Arc a) const {
 		      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+		    }
 		    bool valid(Edge e) const {
 		      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
+		    }
 		    Node addNode() {
 		      int n = nodes.size();
 		      nodes.push_back(NodeT());
 		      nodes[n].first_out = -1;
 		      return Node(n);
+		    }
 		    Edge addEdge(Node u, Node v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs.push_back(ArcT());
@@ -633,24 +668,51 @@
 		    ///
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new edge to the graph.
 		    ///Add a new edge to the graph with node \c s
 		    ///and \c t.
 		    ///\return the new edge.
 		    Edge addEdge(const Node& s, const Node& t) {
 		      return Parent::addEdge(s, t);
+		    }
 		    /// \brief Node validity check
 		    ///
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A removed node (using Snapshot) could become valid again
 		    /// when new nodes are added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// \brief Arc validity check
 		    ///
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning A removed arc (using Snapshot) could become valid again
 		    /// when new edges are added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// \brief Edge validity check
 		    ///
 		    /// This function gives back true if the given edge is valid,
 		    /// ie. it is a real edge of the graph.
 		    ///
 		    /// \warning A removed edge (using Snapshot) could become valid again
 		    /// when new edges are added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    ///Clear the graph.
 		    ///Erase all the nodes and edges from the graph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		  public:
 		    class Snapshot;

test/graph_test.cc

Show inline comments

@@ -13,25 +13,25 @@
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <lemon/concepts/graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/smart_graph.h>
 		// #include <lemon/full_graph.h>
 		// #include <lemon/grid_graph.h>
-		//#include <lemon/graph_utils.h>
 		#include <lemon/graph_utils.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		void check_concepts() {
 		  { // checking digraph components
 		    checkConcept<BaseGraphComponent, BaseGraphComponent >();
@@ -73,82 +73,107 @@
 		  //  check(countArcs(g) == 2*e, "Wrong arc number.");
 		  int uee = 0;
 		  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
 		    ++uee;
+		  }
 		  check(uee == e, "Wrong edge number.");
 		  //  check(countEdges(g) == e, "Wrong edge number.");
+		}
 		template <typename Graph>
-		void print_items(Graph &g) {
+		void check_graph_counts() {
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::EdgeIt EdgeIt;
 		  typedef typename Graph::ArcIt ArcIt;
 		  std::cout << "Nodes" << std::endl;
 		  int i=0;
 		  for(NodeIt it(g); it!=INVALID; ++it, ++i) {
 		    std::cout << "  " << i << ": " << g.id(it) << std::endl;
+		  }
 		  std::cout << "Edge" << std::endl;
 		  i=0;
 		  for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
 		    std::cout << "  " << i << ": " << g.id(it)
 			 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
 			 << ")" << std::endl;
+		  }
 		  std::cout << "Arc" << std::endl;
 		  i=0;
 		  for(ArcIt it(g); it!=INVALID; ++it, ++i) {
 		    std::cout << "  " << i << ": " << g.id(it)
 			 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
 			 << ")" << std::endl;
+		  }
+		}
 		template <typename Graph>
 		void check_graph() {
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::Edge Edge;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::EdgeIt EdgeIt;
 		  typedef typename Graph::ArcIt ArcIt;
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  check_item_counts(g,0,0);
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Edge
 		    e1 = g.addEdge(n1, n2),
 		    e2 = g.addEdge(n2, n3);
 		  // print_items(g);
 		  check_item_counts(g,3,2);
+		}
 		template <typename Graph>
 		void check_graph_validity() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  check_item_counts(g,0,0);
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Edge
 		    e1 = g.addEdge(n1, n2),
 		    e2 = g.addEdge(n2, n3);
 		  check(g.valid(n1), "Validity check");
 		  check(g.valid(e1), "Validity check");
 		  check(g.valid(g.direct(e1, true)), "Validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Validity check");
 		  check(!g.valid(g.edgeFromId(-1)), "Validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Validity check");
+		}
 		template <typename Graph>
 		void check_graph_validity_erase() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  check_item_counts(g,0,0);
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Edge
 		    e1 = g.addEdge(n1, n2),
 		    e2 = g.addEdge(n2, n3);
 		  check(g.valid(n1), "Validity check");
 		  check(g.valid(e1), "Validity check");
 		  check(g.valid(g.direct(e1, true)), "Validity check");
 		  g.erase(n1);
 		  check(!g.valid(n1), "Validity check");
 		  check(g.valid(n2), "Validity check");
 		  check(g.valid(n3), "Validity check");
 		  check(!g.valid(e1), "Validity check");
 		  check(g.valid(e2), "Validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Validity check");
 		  check(!g.valid(g.edgeFromId(-1)), "Validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Validity check");
+		}
 		// void checkGridGraph(const GridGraph& g, int w, int h) {
 		//   check(g.width() == w, "Wrong width");
 		//   check(g.height() == h, "Wrong height");
 		//   for (int i = 0; i < w; ++i) {
 		//     for (int j = 0; j < h; ++j) {
 		//       check(g.col(g(i, j)) == i, "Wrong col");
 		//       check(g.row(g(i, j)) == j, "Wrong row");
 		//     }
 		//   }
 		//   for (int i = 0; i < w; ++i) {
@@ -178,26 +203,29 @@
 		//   for (int j = 0; j < h; ++j) {
 		//     for (int i = 1; i < w; ++i) {
 		//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
 		//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
 		//     }
 		//     check(g.left(g(0, j)) == INVALID, "Wrong left");
 		//   }
 		// }
 		int main() {
 		  check_concepts();
 		  check_graph<ListGraph>();
 		  check_graph<SmartGraph>();
 		  check_graph_counts<ListGraph>();
 		  check_graph_counts<SmartGraph>();
 		  check_graph_validity_erase<ListGraph>();
 		  check_graph_validity<SmartGraph>();
 		//   {
 		//     FullGraph g(5);
 		//     check_item_counts(g, 5, 10);
 		//   }
 		//   {
 		//     GridGraph g(5, 6);
 		//     check_item_counts(g, 30, 49);
 		//     checkGridGraph(g, 5, 6);
 		//   }

0 comments (0 inline)

RhodeCode

Login to your account