1.1 --- a/lemon/list_graph.h Thu Apr 24 11:56:44 2008 +0200
1.2 +++ b/lemon/list_graph.h Thu Apr 24 13:53:09 2008 +0100
1.3 @@ -152,6 +152,16 @@
1.4 static Node nodeFromId(int id) { return Node(id);}
1.5 static Arc arcFromId(int id) { return Arc(id);}
1.6
1.7 + bool valid(Node n) const {
1.8 + return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.9 + nodes[n.id].prev != -2;
1.10 + }
1.11 +
1.12 + bool valid(Arc a) const {
1.13 + return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.14 + arcs[a.id].prev_in != -2;
1.15 + }
1.16 +
1.17 Node addNode() {
1.18 int n;
1.19
1.20 @@ -219,6 +229,7 @@
1.21
1.22 nodes[n].next = first_free_node;
1.23 first_free_node = n;
1.24 + nodes[n].prev = -2;
1.25
1.26 }
1.27
1.28 @@ -247,8 +258,8 @@
1.29 }
1.30
1.31 arcs[n].next_in = first_free_arc;
1.32 - first_free_arc = n;
1.33 -
1.34 + first_free_arc = n;
1.35 + arcs[n].prev_in = -2;
1.36 }
1.37
1.38 void clear() {
1.39 @@ -350,6 +361,26 @@
1.40 return Parent::addArc(s, t);
1.41 }
1.42
1.43 + /// Node validity check
1.44 +
1.45 + /// This function gives back true if the given node is valid,
1.46 + /// ie. it is a real node of the graph.
1.47 + ///
1.48 + /// \warning A Node pointing to a removed item
1.49 + /// could become valid again later if new nodes are
1.50 + /// added to the graph.
1.51 + bool valid(Node n) const { return Parent::valid(n); }
1.52 +
1.53 + /// Arc validity check
1.54 +
1.55 + /// This function gives back true if the given arc is valid,
1.56 + /// ie. it is a real arc of the graph.
1.57 + ///
1.58 + /// \warning An Arc pointing to a removed item
1.59 + /// could become valid again later if new nodes are
1.60 + /// added to the graph.
1.61 + bool valid(Arc a) const { return Parent::valid(a); }
1.62 +
1.63 /// Change the target of \c e to \c n
1.64
1.65 /// Change the target of \c e to \c n
1.66 @@ -945,6 +976,21 @@
1.67 static Arc arcFromId(int id) { return Arc(id);}
1.68 static Edge edgeFromId(int id) { return Edge(id);}
1.69
1.70 + bool valid(Node n) const {
1.71 + return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.72 + nodes[n.id].prev != -2;
1.73 + }
1.74 +
1.75 + bool valid(Arc a) const {
1.76 + return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.77 + arcs[a.id].prev_out != -2;
1.78 + }
1.79 +
1.80 + bool valid(Edge e) const {
1.81 + return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.82 + arcs[2 * e.id].prev_out != -2;
1.83 + }
1.84 +
1.85 Node addNode() {
1.86 int n;
1.87
1.88 @@ -1013,7 +1059,7 @@
1.89
1.90 nodes[n].next = first_free_node;
1.91 first_free_node = n;
1.92 -
1.93 + nodes[n].prev = -2;
1.94 }
1.95
1.96 void erase(const Edge& edge) {
1.97 @@ -1041,6 +1087,8 @@
1.98
1.99 arcs[n].next_out = first_free_arc;
1.100 first_free_arc = n;
1.101 + arcs[n].prev_out = -2;
1.102 + arcs[n | 1].prev_out = -2;
1.103
1.104 }
1.105
1.106 @@ -1157,6 +1205,33 @@
1.107 Edge addEdge(const Node& s, const Node& t) {
1.108 return Parent::addEdge(s, t);
1.109 }
1.110 + /// Node validity check
1.111 +
1.112 + /// This function gives back true if the given node is valid,
1.113 + /// ie. it is a real node of the graph.
1.114 + ///
1.115 + /// \warning A Node pointing to a removed item
1.116 + /// could become valid again later if new nodes are
1.117 + /// added to the graph.
1.118 + bool valid(Node n) const { return Parent::valid(n); }
1.119 + /// Arc validity check
1.120 +
1.121 + /// This function gives back true if the given arc is valid,
1.122 + /// ie. it is a real arc of the graph.
1.123 + ///
1.124 + /// \warning An Arc pointing to a removed item
1.125 + /// could become valid again later if new edges are
1.126 + /// added to the graph.
1.127 + bool valid(Arc a) const { return Parent::valid(a); }
1.128 + /// Edge validity check
1.129 +
1.130 + /// This function gives back true if the given edge is valid,
1.131 + /// ie. it is a real arc of the graph.
1.132 + ///
1.133 + /// \warning A Edge pointing to a removed item
1.134 + /// could become valid again later if new edges are
1.135 + /// added to the graph.
1.136 + bool valid(Edge e) const { return Parent::valid(e); }
1.137 /// \brief Change the source of \c e to \c n
1.138 ///
1.139 /// This function changes the source of \c e to \c n.
2.1 --- a/lemon/smart_graph.h Thu Apr 24 11:56:44 2008 +0200
2.2 +++ b/lemon/smart_graph.h Thu Apr 24 13:53:09 2008 +0100
2.3 @@ -115,6 +115,13 @@
2.4 static Node nodeFromId(int id) { return Node(id);}
2.5 static Arc arcFromId(int id) { return Arc(id);}
2.6
2.7 + bool valid(Node n) const {
2.8 + return n._id >= 0 && n._id < static_cast<int>(nodes.size());
2.9 + }
2.10 + bool valid(Arc a) const {
2.11 + return a._id >= 0 && a._id < static_cast<int>(arcs.size());
2.12 + }
2.13 +
2.14 class Node {
2.15 friend class SmartDigraphBase;
2.16 friend class SmartDigraph;
2.17 @@ -261,6 +268,24 @@
2.18 /// \sa reserveNode
2.19 void reserveArc(int m) { arcs.reserve(m); };
2.20
2.21 + /// \brief Node validity check
2.22 + ///
2.23 + /// This function gives back true if the given node is valid,
2.24 + /// ie. it is a real node of the graph.
2.25 + ///
2.26 + /// \warning A removed node (using Snapshot) could become valid again
2.27 + /// when new nodes are added to the graph.
2.28 + bool valid(Node n) const { return Parent::valid(n); }
2.29 +
2.30 + /// \brief Arc validity check
2.31 + ///
2.32 + /// This function gives back true if the given arc is valid,
2.33 + /// ie. it is a real arc of the graph.
2.34 + ///
2.35 + /// \warning A removed arc (using Snapshot) could become valid again
2.36 + /// when new arcs are added to the graph.
2.37 + bool valid(Arc a) const { return Parent::valid(a); }
2.38 +
2.39 ///Clear the digraph.
2.40
2.41 ///Erase all the nodes and arcs from the digraph.
2.42 @@ -550,6 +575,16 @@
2.43 static Arc arcFromId(int id) { return Arc(id);}
2.44 static Edge edgeFromId(int id) { return Edge(id);}
2.45
2.46 + bool valid(Node n) const {
2.47 + return n._id >= 0 && n._id < static_cast<int>(nodes.size());
2.48 + }
2.49 + bool valid(Arc a) const {
2.50 + return a._id >= 0 && a._id < static_cast<int>(arcs.size());
2.51 + }
2.52 + bool valid(Edge e) const {
2.53 + return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
2.54 + }
2.55 +
2.56 Node addNode() {
2.57 int n = nodes.size();
2.58 nodes.push_back(NodeT());
2.59 @@ -642,6 +677,33 @@
2.60 return Parent::addEdge(s, t);
2.61 }
2.62
2.63 + /// \brief Node validity check
2.64 + ///
2.65 + /// This function gives back true if the given node is valid,
2.66 + /// ie. it is a real node of the graph.
2.67 + ///
2.68 + /// \warning A removed node (using Snapshot) could become valid again
2.69 + /// when new nodes are added to the graph.
2.70 + bool valid(Node n) const { return Parent::valid(n); }
2.71 +
2.72 + /// \brief Arc validity check
2.73 + ///
2.74 + /// This function gives back true if the given arc is valid,
2.75 + /// ie. it is a real arc of the graph.
2.76 + ///
2.77 + /// \warning A removed arc (using Snapshot) could become valid again
2.78 + /// when new edges are added to the graph.
2.79 + bool valid(Arc a) const { return Parent::valid(a); }
2.80 +
2.81 + /// \brief Edge validity check
2.82 + ///
2.83 + /// This function gives back true if the given edge is valid,
2.84 + /// ie. it is a real edge of the graph.
2.85 + ///
2.86 + /// \warning A removed edge (using Snapshot) could become valid again
2.87 + /// when new edges are added to the graph.
2.88 + bool valid(Edge e) const { return Parent::valid(e); }
2.89 +
2.90 ///Clear the graph.
2.91
2.92 ///Erase all the nodes and edges from the graph.
3.1 --- a/test/graph_test.cc Thu Apr 24 11:56:44 2008 +0200
3.2 +++ b/test/graph_test.cc Thu Apr 24 13:53:09 2008 +0100
3.3 @@ -22,7 +22,7 @@
3.4 // #include <lemon/full_graph.h>
3.5 // #include <lemon/grid_graph.h>
3.6
3.7 -//#include <lemon/graph_utils.h>
3.8 +#include <lemon/graph_utils.h>
3.9
3.10 #include "test_tools.h"
3.11
3.12 @@ -82,46 +82,9 @@
3.13 }
3.14
3.15 template <typename Graph>
3.16 -void print_items(Graph &g) {
3.17 +void check_graph_counts() {
3.18
3.19 - typedef typename Graph::NodeIt NodeIt;
3.20 - typedef typename Graph::EdgeIt EdgeIt;
3.21 - typedef typename Graph::ArcIt ArcIt;
3.22 -
3.23 - std::cout << "Nodes" << std::endl;
3.24 - int i=0;
3.25 - for(NodeIt it(g); it!=INVALID; ++it, ++i) {
3.26 - std::cout << " " << i << ": " << g.id(it) << std::endl;
3.27 - }
3.28 -
3.29 - std::cout << "Edge" << std::endl;
3.30 - i=0;
3.31 - for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
3.32 - std::cout << " " << i << ": " << g.id(it)
3.33 - << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
3.34 - << ")" << std::endl;
3.35 - }
3.36 -
3.37 - std::cout << "Arc" << std::endl;
3.38 - i=0;
3.39 - for(ArcIt it(g); it!=INVALID; ++it, ++i) {
3.40 - std::cout << " " << i << ": " << g.id(it)
3.41 - << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
3.42 - << ")" << std::endl;
3.43 - }
3.44 -
3.45 -}
3.46 -
3.47 -template <typename Graph>
3.48 -void check_graph() {
3.49 -
3.50 - typedef typename Graph::Node Node;
3.51 - typedef typename Graph::Edge Edge;
3.52 - typedef typename Graph::Arc Arc;
3.53 - typedef typename Graph::NodeIt NodeIt;
3.54 - typedef typename Graph::EdgeIt EdgeIt;
3.55 - typedef typename Graph::ArcIt ArcIt;
3.56 -
3.57 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
3.58 Graph g;
3.59
3.60 check_item_counts(g,0,0);
3.61 @@ -135,11 +98,73 @@
3.62 e1 = g.addEdge(n1, n2),
3.63 e2 = g.addEdge(n2, n3);
3.64
3.65 - // print_items(g);
3.66 -
3.67 check_item_counts(g,3,2);
3.68 }
3.69
3.70 +template <typename Graph>
3.71 +void check_graph_validity() {
3.72 +
3.73 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
3.74 + Graph g;
3.75 +
3.76 + check_item_counts(g,0,0);
3.77 +
3.78 + Node
3.79 + n1 = g.addNode(),
3.80 + n2 = g.addNode(),
3.81 + n3 = g.addNode();
3.82 +
3.83 + Edge
3.84 + e1 = g.addEdge(n1, n2),
3.85 + e2 = g.addEdge(n2, n3);
3.86 +
3.87 + check(g.valid(n1), "Validity check");
3.88 + check(g.valid(e1), "Validity check");
3.89 + check(g.valid(g.direct(e1, true)), "Validity check");
3.90 +
3.91 + check(!g.valid(g.nodeFromId(-1)), "Validity check");
3.92 + check(!g.valid(g.edgeFromId(-1)), "Validity check");
3.93 + check(!g.valid(g.arcFromId(-1)), "Validity check");
3.94 +
3.95 +}
3.96 +
3.97 +template <typename Graph>
3.98 +void check_graph_validity_erase() {
3.99 +
3.100 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
3.101 + Graph g;
3.102 +
3.103 + check_item_counts(g,0,0);
3.104 +
3.105 + Node
3.106 + n1 = g.addNode(),
3.107 + n2 = g.addNode(),
3.108 + n3 = g.addNode();
3.109 +
3.110 + Edge
3.111 + e1 = g.addEdge(n1, n2),
3.112 + e2 = g.addEdge(n2, n3);
3.113 +
3.114 + check(g.valid(n1), "Validity check");
3.115 + check(g.valid(e1), "Validity check");
3.116 + check(g.valid(g.direct(e1, true)), "Validity check");
3.117 +
3.118 + g.erase(n1);
3.119 +
3.120 + check(!g.valid(n1), "Validity check");
3.121 + check(g.valid(n2), "Validity check");
3.122 + check(g.valid(n3), "Validity check");
3.123 + check(!g.valid(e1), "Validity check");
3.124 + check(g.valid(e2), "Validity check");
3.125 +
3.126 + check(!g.valid(g.nodeFromId(-1)), "Validity check");
3.127 + check(!g.valid(g.edgeFromId(-1)), "Validity check");
3.128 + check(!g.valid(g.arcFromId(-1)), "Validity check");
3.129 +
3.130 +}
3.131 +
3.132 +
3.133 +
3.134 // void checkGridGraph(const GridGraph& g, int w, int h) {
3.135 // check(g.width() == w, "Wrong width");
3.136 // check(g.height() == h, "Wrong height");
3.137 @@ -187,8 +212,11 @@
3.138 int main() {
3.139 check_concepts();
3.140
3.141 - check_graph<ListGraph>();
3.142 - check_graph<SmartGraph>();
3.143 + check_graph_counts<ListGraph>();
3.144 + check_graph_counts<SmartGraph>();
3.145 +
3.146 + check_graph_validity_erase<ListGraph>();
3.147 + check_graph_validity<SmartGraph>();
3.148
3.149 // {
3.150 // FullGraph g(5);