COIN-OR::LEMON - Graph Library

Changeset 149:2f7ae34e1333 in lemon


Ignore:
Timestamp:
04/24/08 14:53:09 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Item validity checking for ListGraph? and SmartGraph?

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r73 r149  
    153153    static Arc arcFromId(int id) { return Arc(id);}
    154154
     155    bool valid(Node n) const {
     156      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
     157        nodes[n.id].prev != -2;
     158    }
     159
     160    bool valid(Arc a) const {
     161      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
     162        arcs[a.id].prev_in != -2;
     163    }
     164
    155165    Node addNode() {     
    156166      int n;
     
    220230      nodes[n].next = first_free_node;
    221231      first_free_node = n;
     232      nodes[n].prev = -2;
    222233
    223234    }
     
    248259     
    249260      arcs[n].next_in = first_free_arc;
    250       first_free_arc = n;     
    251 
     261      first_free_arc = n;
     262      arcs[n].prev_in = -2;
    252263    }
    253264
     
    350361      return Parent::addArc(s, t);
    351362    }
     363
     364    /// Node validity check
     365
     366    /// This function gives back true if the given node is valid,
     367    /// ie. it is a real node of the graph. 
     368    ///
     369    /// \warning A Node pointing to a removed item
     370    /// could become valid again later if new nodes are
     371    /// added to the graph.
     372    bool valid(Node n) const { return Parent::valid(n); }
     373
     374    /// Arc validity check
     375
     376    /// This function gives back true if the given arc is valid,
     377    /// ie. it is a real arc of the graph. 
     378    ///
     379    /// \warning An Arc pointing to a removed item
     380    /// could become valid again later if new nodes are
     381    /// added to the graph.
     382    bool valid(Arc a) const { return Parent::valid(a); }
    352383
    353384    /// Change the target of \c e to \c n
     
    946977    static Edge edgeFromId(int id) { return Edge(id);}
    947978
     979    bool valid(Node n) const {
     980      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
     981        nodes[n.id].prev != -2;
     982    }
     983
     984    bool valid(Arc a) const {
     985      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
     986        arcs[a.id].prev_out != -2;
     987    }
     988
     989    bool valid(Edge e) const {
     990      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
     991        arcs[2 * e.id].prev_out != -2;
     992    }
     993
    948994    Node addNode() {     
    949995      int n;
     
    10141060      nodes[n].next = first_free_node;
    10151061      first_free_node = n;
    1016 
     1062      nodes[n].prev = -2;
    10171063    }
    10181064   
     
    10421088      arcs[n].next_out = first_free_arc;
    10431089      first_free_arc = n;     
     1090      arcs[n].prev_out = -2;
     1091      arcs[n | 1].prev_out = -2;
    10441092
    10451093    }
     
    11581206      return Parent::addEdge(s, t);
    11591207    }
     1208    /// Node validity check
     1209
     1210    /// This function gives back true if the given node is valid,
     1211    /// ie. it is a real node of the graph. 
     1212    ///
     1213    /// \warning A Node pointing to a removed item
     1214    /// could become valid again later if new nodes are
     1215    /// added to the graph.
     1216    bool valid(Node n) const { return Parent::valid(n); }
     1217    /// Arc validity check
     1218
     1219    /// This function gives back true if the given arc is valid,
     1220    /// ie. it is a real arc of the graph. 
     1221    ///
     1222    /// \warning An Arc pointing to a removed item
     1223    /// could become valid again later if new edges are
     1224    /// added to the graph.
     1225    bool valid(Arc a) const { return Parent::valid(a); }
     1226    /// Edge validity check
     1227
     1228    /// This function gives back true if the given edge is valid,
     1229    /// ie. it is a real arc of the graph. 
     1230    ///
     1231    /// \warning A Edge pointing to a removed item
     1232    /// could become valid again later if new edges are
     1233    /// added to the graph.
     1234    bool valid(Edge e) const { return Parent::valid(e); }
    11601235    /// \brief Change the source of \c e to \c n
    11611236    ///
  • lemon/smart_graph.h

    r139 r149  
    116116    static Arc arcFromId(int id) { return Arc(id);}
    117117
     118    bool valid(Node n) const {
     119      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     120    }
     121    bool valid(Arc a) const {
     122      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     123    }
     124
    118125    class Node {
    119126      friend class SmartDigraphBase;
     
    261268    /// \sa reserveNode
    262269    void reserveArc(int m) { arcs.reserve(m); };
     270
     271    /// \brief Node validity check
     272    ///
     273    /// This function gives back true if the given node is valid,
     274    /// ie. it is a real node of the graph. 
     275    ///
     276    /// \warning A removed node (using Snapshot) could become valid again
     277    /// when new nodes are added to the graph.
     278    bool valid(Node n) const { return Parent::valid(n); }
     279
     280    /// \brief Arc validity check
     281    ///
     282    /// This function gives back true if the given arc is valid,
     283    /// ie. it is a real arc of the graph. 
     284    ///
     285    /// \warning A removed arc (using Snapshot) could become valid again
     286    /// when new arcs are added to the graph.
     287    bool valid(Arc a) const { return Parent::valid(a); }
    263288
    264289    ///Clear the digraph.
     
    551576    static Edge edgeFromId(int id) { return Edge(id);}
    552577
     578    bool valid(Node n) const {
     579      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     580    }
     581    bool valid(Arc a) const {
     582      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     583    }
     584    bool valid(Edge e) const {
     585      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
     586    }
     587
    553588    Node addNode() {     
    554589      int n = nodes.size();
     
    642677      return Parent::addEdge(s, t);
    643678    }
     679
     680    /// \brief Node validity check
     681    ///
     682    /// This function gives back true if the given node is valid,
     683    /// ie. it is a real node of the graph. 
     684    ///
     685    /// \warning A removed node (using Snapshot) could become valid again
     686    /// when new nodes are added to the graph.
     687    bool valid(Node n) const { return Parent::valid(n); }
     688
     689    /// \brief Arc validity check
     690    ///
     691    /// This function gives back true if the given arc is valid,
     692    /// ie. it is a real arc of the graph. 
     693    ///
     694    /// \warning A removed arc (using Snapshot) could become valid again
     695    /// when new edges are added to the graph.
     696    bool valid(Arc a) const { return Parent::valid(a); }
     697
     698    /// \brief Edge validity check
     699    ///
     700    /// This function gives back true if the given edge is valid,
     701    /// ie. it is a real edge of the graph. 
     702    ///
     703    /// \warning A removed edge (using Snapshot) could become valid again
     704    /// when new edges are added to the graph.
     705    bool valid(Edge e) const { return Parent::valid(e); }
    644706
    645707    ///Clear the graph.
  • test/graph_test.cc

    r109 r149  
    2323// #include <lemon/grid_graph.h>
    2424
    25 //#include <lemon/graph_utils.h>
     25#include <lemon/graph_utils.h>
    2626
    2727#include "test_tools.h"
     
    8383
    8484template <typename Graph>
    85 void print_items(Graph &g) {
    86 
    87   typedef typename Graph::NodeIt NodeIt;
    88   typedef typename Graph::EdgeIt EdgeIt;
    89   typedef typename Graph::ArcIt ArcIt;
    90 
    91   std::cout << "Nodes" << std::endl;
    92   int i=0;
    93   for(NodeIt it(g); it!=INVALID; ++it, ++i) {
    94     std::cout << "  " << i << ": " << g.id(it) << std::endl;
    95   }
    96 
    97   std::cout << "Edge" << std::endl;
    98   i=0;
    99   for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
    100     std::cout << "  " << i << ": " << g.id(it)
    101          << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
    102          << ")" << std::endl;
    103   }
    104 
    105   std::cout << "Arc" << std::endl;
    106   i=0;
    107   for(ArcIt it(g); it!=INVALID; ++it, ++i) {
    108     std::cout << "  " << i << ": " << g.id(it)
    109          << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
    110          << ")" << std::endl;
    111   }
    112 
    113 }
    114 
    115 template <typename Graph>
    116 void check_graph() {
    117 
    118   typedef typename Graph::Node Node;
    119   typedef typename Graph::Edge Edge;
    120   typedef typename Graph::Arc Arc;
    121   typedef typename Graph::NodeIt NodeIt;
    122   typedef typename Graph::EdgeIt EdgeIt;
    123   typedef typename Graph::ArcIt ArcIt;
    124 
     85void check_graph_counts() {
     86
     87  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    12588  Graph g;
    12689
     
    13699    e2 = g.addEdge(n2, n3);
    137100
    138   // print_items(g);
    139 
    140101  check_item_counts(g,3,2);
    141102}
     103
     104template <typename Graph>
     105void check_graph_validity() {
     106
     107  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     108  Graph g;
     109
     110  check_item_counts(g,0,0);
     111
     112  Node
     113    n1 = g.addNode(),
     114    n2 = g.addNode(),
     115    n3 = g.addNode();
     116
     117  Edge
     118    e1 = g.addEdge(n1, n2),
     119    e2 = g.addEdge(n2, n3);
     120
     121  check(g.valid(n1), "Validity check");
     122  check(g.valid(e1), "Validity check");
     123  check(g.valid(g.direct(e1, true)), "Validity check");
     124
     125  check(!g.valid(g.nodeFromId(-1)), "Validity check");
     126  check(!g.valid(g.edgeFromId(-1)), "Validity check");
     127  check(!g.valid(g.arcFromId(-1)), "Validity check");
     128   
     129}
     130
     131template <typename Graph>
     132void check_graph_validity_erase() {
     133
     134  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     135  Graph g;
     136
     137  check_item_counts(g,0,0);
     138
     139  Node
     140    n1 = g.addNode(),
     141    n2 = g.addNode(),
     142    n3 = g.addNode();
     143
     144  Edge
     145    e1 = g.addEdge(n1, n2),
     146    e2 = g.addEdge(n2, n3);
     147
     148  check(g.valid(n1), "Validity check");
     149  check(g.valid(e1), "Validity check");
     150  check(g.valid(g.direct(e1, true)), "Validity check");
     151
     152  g.erase(n1);
     153
     154  check(!g.valid(n1), "Validity check");
     155  check(g.valid(n2), "Validity check");
     156  check(g.valid(n3), "Validity check");
     157  check(!g.valid(e1), "Validity check");
     158  check(g.valid(e2), "Validity check");
     159
     160  check(!g.valid(g.nodeFromId(-1)), "Validity check");
     161  check(!g.valid(g.edgeFromId(-1)), "Validity check");
     162  check(!g.valid(g.arcFromId(-1)), "Validity check");
     163   
     164}
     165
     166
    142167
    143168// void checkGridGraph(const GridGraph& g, int w, int h) {
     
    188213  check_concepts();
    189214
    190   check_graph<ListGraph>();
    191   check_graph<SmartGraph>();
     215  check_graph_counts<ListGraph>();
     216  check_graph_counts<SmartGraph>();
     217
     218  check_graph_validity_erase<ListGraph>();
     219  check_graph_validity<SmartGraph>();
    192220
    193221//   {
Note: See TracChangeset for help on using the changeset viewer.