lemon/list_graph.h
 changeset 149 2f7ae34e1333 parent 73 c56b7389dc78 child 184 716b220697a0
```     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.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.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.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.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.
```