lemon/list_graph.h
changeset 161 2c999941b871
parent 73 c56b7389dc78
child 184 716b220697a0
equal deleted inserted replaced
3:e51dfcdb46b1 4:f2f995ea1744
   150     static int id(Arc e) { return e.id; }
   150     static int id(Arc e) { return e.id; }
   151 
   151 
   152     static Node nodeFromId(int id) { return Node(id);}
   152     static Node nodeFromId(int id) { return Node(id);}
   153     static Arc arcFromId(int id) { return Arc(id);}
   153     static Arc arcFromId(int id) { return Arc(id);}
   154 
   154 
       
   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 
   155     Node addNode() {     
   165     Node addNode() {     
   156       int n;
   166       int n;
   157       
   167       
   158       if(first_free_node==-1) {
   168       if(first_free_node==-1) {
   159 	n = nodes.size();
   169 	n = nodes.size();
   217 	first_node = nodes[n].next;
   227 	first_node = nodes[n].next;
   218       }
   228       }
   219       
   229       
   220       nodes[n].next = first_free_node;
   230       nodes[n].next = first_free_node;
   221       first_free_node = n;
   231       first_free_node = n;
       
   232       nodes[n].prev = -2;
   222 
   233 
   223     }
   234     }
   224     
   235     
   225     void erase(const Arc& arc) {
   236     void erase(const Arc& arc) {
   226       int n = arc.id;
   237       int n = arc.id;
   245       } else {
   256       } else {
   246 	nodes[arcs[n].source].first_out = arcs[n].next_out;
   257 	nodes[arcs[n].source].first_out = arcs[n].next_out;
   247       }
   258       }
   248       
   259       
   249       arcs[n].next_in = first_free_arc;
   260       arcs[n].next_in = first_free_arc;
   250       first_free_arc = n;      
   261       first_free_arc = n;
   251 
   262       arcs[n].prev_in = -2;
   252     }
   263     }
   253 
   264 
   254     void clear() {
   265     void clear() {
   255       arcs.clear();
   266       arcs.clear();
   256       nodes.clear();
   267       nodes.clear();
   347     ///and target node \c t.
   358     ///and target node \c t.
   348     ///\return the new arc.
   359     ///\return the new arc.
   349     Arc addArc(const Node& s, const Node& t) { 
   360     Arc addArc(const Node& s, const Node& t) { 
   350       return Parent::addArc(s, t); 
   361       return Parent::addArc(s, t); 
   351     }
   362     }
       
   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); }
   352 
   383 
   353     /// Change the target of \c e to \c n
   384     /// Change the target of \c e to \c n
   354 
   385 
   355     /// Change the target of \c e to \c n
   386     /// Change the target of \c e to \c n
   356     ///
   387     ///
   943 
   974 
   944     static Node nodeFromId(int id) { return Node(id);}
   975     static Node nodeFromId(int id) { return Node(id);}
   945     static Arc arcFromId(int id) { return Arc(id);}
   976     static Arc arcFromId(int id) { return Arc(id);}
   946     static Edge edgeFromId(int id) { return Edge(id);}
   977     static Edge edgeFromId(int id) { return Edge(id);}
   947 
   978 
       
   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 
   948     Node addNode() {     
   994     Node addNode() {     
   949       int n;
   995       int n;
   950       
   996       
   951       if(first_free_node==-1) {
   997       if(first_free_node==-1) {
   952 	n = nodes.size();
   998 	n = nodes.size();
  1011 	first_node = nodes[n].next;
  1057 	first_node = nodes[n].next;
  1012       }
  1058       }
  1013       
  1059       
  1014       nodes[n].next = first_free_node;
  1060       nodes[n].next = first_free_node;
  1015       first_free_node = n;
  1061       first_free_node = n;
  1016 
  1062       nodes[n].prev = -2;
  1017     }
  1063     }
  1018     
  1064     
  1019     void erase(const Edge& edge) {
  1065     void erase(const Edge& edge) {
  1020       int n = edge.id * 2;
  1066       int n = edge.id * 2;
  1021       
  1067       
  1039 	nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1085 	nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1040       }
  1086       }
  1041       
  1087       
  1042       arcs[n].next_out = first_free_arc;
  1088       arcs[n].next_out = first_free_arc;
  1043       first_free_arc = n;      
  1089       first_free_arc = n;      
       
  1090       arcs[n].prev_out = -2;
       
  1091       arcs[n | 1].prev_out = -2;
  1044 
  1092 
  1045     }
  1093     }
  1046 
  1094 
  1047     void clear() {
  1095     void clear() {
  1048       arcs.clear();
  1096       arcs.clear();
  1155     /// and target node \c t.
  1203     /// and target node \c t.
  1156     /// \return the new edge.
  1204     /// \return the new edge.
  1157     Edge addEdge(const Node& s, const Node& t) { 
  1205     Edge addEdge(const Node& s, const Node& t) { 
  1158       return Parent::addEdge(s, t); 
  1206       return Parent::addEdge(s, t); 
  1159     }
  1207     }
       
  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); }
  1160     /// \brief Change the source of \c e to \c n
  1235     /// \brief Change the source of \c e to \c n
  1161     ///
  1236     ///
  1162     /// This function changes the source of \c e to \c n.
  1237     /// This function changes the source of \c e to \c n.
  1163     ///
  1238     ///
  1164     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1239     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s