# HG changeset patch # User Balazs Dezso # Date 1209041589 -3600 # Node ID 2f7ae34e133354ce6697d2d62f9637ae684b6b71 # Parent 4e2581021300caee6e11d6f9797e5bce857f0a8c Item validity checking for ListGraph and SmartGraph diff -r 4e2581021300 -r 2f7ae34e1333 lemon/list_graph.h --- a/lemon/list_graph.h Thu Apr 24 11:56:44 2008 +0200 +++ b/lemon/list_graph.h Thu Apr 24 13:53:09 2008 +0100 @@ -152,6 +152,16 @@ 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(nodes.size()) && + nodes[n.id].prev != -2; + } + + bool valid(Arc a) const { + return a.id >= 0 && a.id < static_cast(arcs.size()) && + arcs[a.id].prev_in != -2; + } + Node addNode() { int n; @@ -219,6 +229,7 @@ nodes[n].next = first_free_node; first_free_node = n; + nodes[n].prev = -2; } @@ -247,8 +258,8 @@ } arcs[n].next_in = first_free_arc; - first_free_arc = n; - + first_free_arc = n; + arcs[n].prev_in = -2; } void clear() { @@ -350,6 +361,26 @@ 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 @@ -945,6 +976,21 @@ 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(nodes.size()) && + nodes[n.id].prev != -2; + } + + bool valid(Arc a) const { + return a.id >= 0 && a.id < static_cast(arcs.size()) && + arcs[a.id].prev_out != -2; + } + + bool valid(Edge e) const { + return e.id >= 0 && 2 * e.id < static_cast(arcs.size()) && + arcs[2 * e.id].prev_out != -2; + } + Node addNode() { int n; @@ -1013,7 +1059,7 @@ nodes[n].next = first_free_node; first_free_node = n; - + nodes[n].prev = -2; } void erase(const Edge& edge) { @@ -1041,6 +1087,8 @@ arcs[n].next_out = first_free_arc; first_free_arc = n; + arcs[n].prev_out = -2; + arcs[n | 1].prev_out = -2; } @@ -1157,6 +1205,33 @@ 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. diff -r 4e2581021300 -r 2f7ae34e1333 lemon/smart_graph.h --- a/lemon/smart_graph.h Thu Apr 24 11:56:44 2008 +0200 +++ b/lemon/smart_graph.h Thu Apr 24 13:53:09 2008 +0100 @@ -115,6 +115,13 @@ 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(nodes.size()); + } + bool valid(Arc a) const { + return a._id >= 0 && a._id < static_cast(arcs.size()); + } + class Node { friend class SmartDigraphBase; friend class SmartDigraph; @@ -261,6 +268,24 @@ /// \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. @@ -550,6 +575,16 @@ 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(nodes.size()); + } + bool valid(Arc a) const { + return a._id >= 0 && a._id < static_cast(arcs.size()); + } + bool valid(Edge e) const { + return e._id >= 0 && 2 * e._id < static_cast(arcs.size()); + } + Node addNode() { int n = nodes.size(); nodes.push_back(NodeT()); @@ -642,6 +677,33 @@ 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. diff -r 4e2581021300 -r 2f7ae34e1333 test/graph_test.cc --- a/test/graph_test.cc Thu Apr 24 11:56:44 2008 +0200 +++ b/test/graph_test.cc Thu Apr 24 13:53:09 2008 +0100 @@ -22,7 +22,7 @@ // #include // #include -//#include +#include #include "test_tools.h" @@ -82,46 +82,9 @@ } template -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 -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); @@ -135,11 +98,73 @@ e1 = g.addEdge(n1, n2), e2 = g.addEdge(n2, n3); - // print_items(g); - check_item_counts(g,3,2); } +template +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 +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"); @@ -187,8 +212,11 @@ int main() { check_concepts(); - check_graph(); - check_graph(); + check_graph_counts(); + check_graph_counts(); + + check_graph_validity_erase(); + check_graph_validity(); // { // FullGraph g(5);