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.