Changeset 149:2f7ae34e1333 in lemon-1.2

Ignore:
Timestamp:
04/24/08 14:53:09 (12 years ago)
Branch:
default
Phase:
public
Message:

Item validity checking for ListGraph? and SmartGraph?

Files:
3 edited

Unmodified
Added
Removed
• lemon/list_graph.h

 r73 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; nodes[n].next = first_free_node; first_free_node = n; nodes[n].prev = -2; } arcs[n].next_in = first_free_arc; first_free_arc = n; first_free_arc = n; arcs[n].prev_in = -2; } 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 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; nodes[n].next = first_free_node; first_free_node = n; nodes[n].prev = -2; } arcs[n].next_out = first_free_arc; first_free_arc = n; arcs[n].prev_out = -2; arcs[n | 1].prev_out = -2; } 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 ///
• lemon/smart_graph.h

 r139 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; /// \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. 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(); 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.
• test/graph_test.cc

 r109 // #include //#include #include #include "test_tools.h" template void print_items(Graph &g) { 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; void check_graph_counts() { TEMPLATE_GRAPH_TYPEDEFS(Graph); Graph g; 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_concepts(); check_graph(); check_graph(); check_graph_counts(); check_graph_counts(); check_graph_validity_erase(); check_graph_validity(); //   {
Note: See TracChangeset for help on using the changeset viewer.