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.