lemon/list_graph.h
author deba
Mon, 06 Mar 2006 17:32:35 +0000
changeset 2000 ebcc93ead7da
parent 1995 c1fc2c14a3ae
child 2031 080d51024ac5
permissions -rw-r--r--
Checking missing section reader
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\brief ListGraph, ListUGraph classes.
    25 
    26 #include <lemon/bits/base_extender.h>
    27 #include <lemon/bits/graph_extender.h>
    28 
    29 #include <lemon/error.h>
    30 
    31 #include <vector>
    32 #include <list>
    33 
    34 namespace lemon {
    35 
    36   class ListGraphBase {
    37 
    38   protected:
    39     struct NodeT {
    40       int first_in, first_out;
    41       int prev, next;
    42     };
    43  
    44     struct EdgeT {
    45       int target, source;
    46       int prev_in, prev_out;
    47       int next_in, next_out;
    48     };
    49 
    50     std::vector<NodeT> nodes;
    51 
    52     int first_node;
    53 
    54     int first_free_node;
    55 
    56     std::vector<EdgeT> edges;
    57 
    58     int first_free_edge;
    59     
    60   public:
    61     
    62     typedef ListGraphBase Graph;
    63     
    64     class Node {
    65       friend class ListGraphBase;
    66     protected:
    67 
    68       int id;
    69       Node(int pid) { id = pid;}
    70 
    71     public:
    72       Node() {}
    73       Node (Invalid) { id = -1; }
    74       bool operator==(const Node& node) const {return id == node.id;}
    75       bool operator!=(const Node& node) const {return id != node.id;}
    76       bool operator<(const Node& node) const {return id < node.id;}
    77     };
    78 
    79     class Edge {
    80       friend class ListGraphBase;
    81     protected:
    82 
    83       int id;
    84       Edge(int pid) { id = pid;}
    85 
    86     public:
    87       Edge() {}
    88       Edge (Invalid) { id = -1; }
    89       bool operator==(const Edge& edge) const {return id == edge.id;}
    90       bool operator!=(const Edge& edge) const {return id != edge.id;}
    91       bool operator<(const Edge& edge) const {return id < edge.id;}
    92     };
    93 
    94 
    95 
    96     ListGraphBase()
    97       : nodes(), first_node(-1),
    98 	first_free_node(-1), edges(), first_free_edge(-1) {}
    99 
   100     
   101     /// Maximum node ID.
   102     
   103     /// Maximum node ID.
   104     ///\sa id(Node)
   105     int maxNodeId() const { return nodes.size()-1; } 
   106 
   107     /// Maximum edge ID.
   108     
   109     /// Maximum edge ID.
   110     ///\sa id(Edge)
   111     int maxEdgeId() const { return edges.size()-1; }
   112 
   113     Node source(Edge e) const { return edges[e.id].source; }
   114     Node target(Edge e) const { return edges[e.id].target; }
   115 
   116 
   117     void first(Node& node) const { 
   118       node.id = first_node;
   119     }
   120 
   121     void next(Node& node) const {
   122       node.id = nodes[node.id].next;
   123     }
   124 
   125 
   126     void first(Edge& e) const { 
   127       int n;
   128       for(n = first_node; 
   129 	  n!=-1 && nodes[n].first_in == -1; 
   130 	  n = nodes[n].next);
   131       e.id = (n == -1) ? -1 : nodes[n].first_in;
   132     }
   133 
   134     void next(Edge& edge) const {
   135       if (edges[edge.id].next_in != -1) {
   136 	edge.id = edges[edge.id].next_in;
   137       } else {
   138 	int n;
   139 	for(n = nodes[edges[edge.id].target].next;
   140 	  n!=-1 && nodes[n].first_in == -1; 
   141 	  n = nodes[n].next);
   142 	edge.id = (n == -1) ? -1 : nodes[n].first_in;
   143       }      
   144     }
   145 
   146     void firstOut(Edge &e, const Node& v) const {
   147       e.id = nodes[v.id].first_out;
   148     }
   149     void nextOut(Edge &e) const {
   150       e.id=edges[e.id].next_out;
   151     }
   152 
   153     void firstIn(Edge &e, const Node& v) const {
   154       e.id = nodes[v.id].first_in;
   155     }
   156     void nextIn(Edge &e) const {
   157       e.id=edges[e.id].next_in;
   158     }
   159 
   160     
   161     static int id(Node v) { return v.id; }
   162     static int id(Edge e) { return e.id; }
   163 
   164     static Node nodeFromId(int id) { return Node(id);}
   165     static Edge edgeFromId(int id) { return Edge(id);}
   166 
   167     /// Adds a new node to the graph.
   168 
   169     /// \warning It adds the new node to the front of the list.
   170     /// (i.e. the lastly added node becomes the first.)
   171     Node addNode() {     
   172       int n;
   173       
   174       if(first_free_node==-1) {
   175 	n = nodes.size();
   176 	nodes.push_back(NodeT());
   177       } else {
   178 	n = first_free_node;
   179 	first_free_node = nodes[n].next;
   180       }
   181       
   182       nodes[n].next = first_node;
   183       if(first_node != -1) nodes[first_node].prev = n;
   184       first_node = n;
   185       nodes[n].prev = -1;
   186       
   187       nodes[n].first_in = nodes[n].first_out = -1;
   188       
   189       return Node(n);
   190     }
   191     
   192     Edge addEdge(Node u, Node v) {
   193       int n;      
   194 
   195       if (first_free_edge == -1) {
   196 	n = edges.size();
   197 	edges.push_back(EdgeT());
   198       } else {
   199 	n = first_free_edge;
   200 	first_free_edge = edges[n].next_in;
   201       }
   202       
   203       edges[n].source = u.id; 
   204       edges[n].target = v.id;
   205 
   206       edges[n].next_out = nodes[u.id].first_out;
   207       if(nodes[u.id].first_out != -1) {
   208 	edges[nodes[u.id].first_out].prev_out = n;
   209       }
   210       
   211       edges[n].next_in = nodes[v.id].first_in;
   212       if(nodes[v.id].first_in != -1) {
   213 	edges[nodes[v.id].first_in].prev_in = n;
   214       }
   215       
   216       edges[n].prev_in = edges[n].prev_out = -1;
   217 	
   218       nodes[u.id].first_out = nodes[v.id].first_in = n;
   219 
   220       return Edge(n);
   221     }
   222     
   223     void erase(const Node& node) {
   224       int n = node.id;
   225       
   226       if(nodes[n].next != -1) {
   227 	nodes[nodes[n].next].prev = nodes[n].prev;
   228       }
   229       
   230       if(nodes[n].prev != -1) {
   231 	nodes[nodes[n].prev].next = nodes[n].next;
   232       } else {
   233 	first_node = nodes[n].next;
   234       }
   235       
   236       nodes[n].next = first_free_node;
   237       first_free_node = n;
   238 
   239     }
   240     
   241     void erase(const Edge& edge) {
   242       int n = edge.id;
   243       
   244       if(edges[n].next_in!=-1) {
   245 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
   246       }
   247 
   248       if(edges[n].prev_in!=-1) {
   249 	edges[edges[n].prev_in].next_in = edges[n].next_in;
   250       } else {
   251 	nodes[edges[n].target].first_in = edges[n].next_in;
   252       }
   253 
   254       
   255       if(edges[n].next_out!=-1) {
   256 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
   257       } 
   258 
   259       if(edges[n].prev_out!=-1) {
   260 	edges[edges[n].prev_out].next_out = edges[n].next_out;
   261       } else {
   262 	nodes[edges[n].source].first_out = edges[n].next_out;
   263       }
   264       
   265       edges[n].next_in = first_free_edge;
   266       first_free_edge = n;      
   267 
   268     }
   269 
   270     void clear() {
   271       edges.clear();
   272       nodes.clear();
   273       first_node = first_free_node = first_free_edge = -1;
   274     }
   275 
   276   protected:
   277     void _changeTarget(Edge e, Node n) 
   278     {
   279       if(edges[e.id].next_in != -1)
   280 	edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
   281       if(edges[e.id].prev_in != -1)
   282 	edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
   283       else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
   284       if (nodes[n.id].first_in != -1) {
   285 	edges[nodes[n.id].first_in].prev_in = e.id;
   286       }
   287       edges[e.id].target = n.id;
   288       edges[e.id].prev_in = -1;
   289       edges[e.id].next_in = nodes[n.id].first_in;
   290       nodes[n.id].first_in = e.id;
   291     }
   292     void _changeSource(Edge e, Node n) 
   293     {
   294       if(edges[e.id].next_out != -1)
   295 	edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
   296       if(edges[e.id].prev_out != -1)
   297 	edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
   298       else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
   299       if (nodes[n.id].first_out != -1) {
   300 	edges[nodes[n.id].first_out].prev_out = e.id;
   301       }
   302       edges[e.id].source = n.id;
   303       edges[e.id].prev_out = -1;
   304       edges[e.id].next_out = nodes[n.id].first_out;
   305       nodes[n.id].first_out = e.id;
   306     }
   307 
   308   };
   309 
   310   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
   311 
   312   /// \addtogroup graphs
   313   /// @{
   314 
   315   ///A list graph class.
   316 
   317   ///This is a simple and fast erasable graph implementation.
   318   ///
   319   ///It addition that it conforms to the
   320   ///\ref concept::ErasableGraph "ErasableGraph" concept,
   321   ///it also provides several additional useful extra functionalities.
   322   ///\sa concept::ErasableGraph.
   323 
   324   class ListGraph : public ExtendedListGraphBase {
   325   public:
   326 
   327     typedef ExtendedListGraphBase Parent;
   328 
   329     /// Changes the target of \c e to \c n
   330 
   331     /// Changes the target of \c e to \c n
   332     ///
   333     ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
   334     ///referencing the changed edge remain
   335     ///valid. However <tt>InEdge</tt>'s are invalidated.
   336     void changeTarget(Edge e, Node n) { 
   337       _changeTarget(e,n); 
   338     }
   339     /// Changes the source of \c e to \c n
   340 
   341     /// Changes the source of \c e to \c n
   342     ///
   343     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
   344     ///referencing the changed edge remain
   345     ///valid. However <tt>OutEdge</tt>'s are invalidated.
   346     void changeSource(Edge e, Node n) { 
   347       _changeSource(e,n);
   348     }
   349 
   350     /// Invert the direction of an edge.
   351 
   352     ///\note The <tt>Edge</tt>'s
   353     ///referencing the changed edge remain
   354     ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
   355     void reverseEdge(Edge e) {
   356       Node t=target(e);
   357       _changeTarget(e,source(e));
   358       _changeSource(e,t);
   359     }
   360 
   361     ///Using this it possible to avoid the superfluous memory allocation.
   362 
   363     ///Using this it possible to avoid the superfluous memory allocation.
   364     ///\todo more docs...
   365     void reserveEdge(int n) { edges.reserve(n); };
   366 
   367     ///Contract two nodes.
   368 
   369     ///This function contracts two nodes.
   370     ///
   371     ///Node \p b will be removed but instead of deleting
   372     ///its neighboring edges, they will be joined to \p a.
   373     ///The last parameter \p r controls whether to remove loops. \c true
   374     ///means that loops will be removed.
   375     ///
   376     ///\note The <tt>Edge</tt>s
   377     ///referencing a moved edge remain
   378     ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
   379     ///may be invalidated.
   380     void contract(Node a, Node b, bool r = true) 
   381     {
   382       for(OutEdgeIt e(*this,b);e!=INVALID;) {
   383 	OutEdgeIt f=e;
   384 	++f;
   385 	if(r && target(e)==a) erase(e);
   386 	else changeSource(e,a);
   387 	e=f;
   388       }
   389       for(InEdgeIt e(*this,b);e!=INVALID;) {
   390 	InEdgeIt f=e;
   391 	++f;
   392 	if(r && source(e)==a) erase(e);
   393 	else changeTarget(e,a);
   394 	e=f;
   395       }
   396       erase(b);
   397     }
   398 
   399     ///Split a node.
   400 
   401     ///This function splits a node. First a new node is added to the graph,
   402     ///then the source of each outgoing edge of \c n is moved to this new node.
   403     ///If \c connect is \c true (this is the default value), then a new edge
   404     ///from \c n to the newly created node is also added.
   405     ///\return The newly created node.
   406     ///
   407     ///\note The <tt>Edge</tt>s
   408     ///referencing a moved edge remain
   409     ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
   410     ///may be invalidated.
   411     ///\warning This functionality cannot be used together with the Snapshot
   412     ///feature.
   413     ///\todo It could be implemented in a bit faster way.
   414     Node split(Node n, bool connect = true) 
   415     {
   416       Node b = addNode();
   417       for(OutEdgeIt e(*this,n);e!=INVALID;) {
   418  	OutEdgeIt f=e;
   419 	++f;
   420 	changeSource(e,b);
   421 	e=f;
   422       }
   423       if(connect) addEdge(n,b);
   424       return b;
   425     }
   426       
   427     ///Split an edge.
   428 
   429     ///This function splits an edge. First a new node \c b is added to the graph,
   430     ///then the original edge is re-targetes to \c b. Finally an edge
   431     ///from \c b to the original target is added.
   432     ///\return The newly created node.
   433     ///\warning This functionality cannot be used together with the Snapshot
   434     ///feature.
   435     Node split(Edge e) 
   436     {
   437       Node b = addNode();
   438       addEdge(b,target(e));
   439       changeTarget(e,b);
   440       return b;
   441     }
   442       
   443     ///Class to make a snapshot of the graph and to restrore to it later.
   444 
   445     ///Class to make a snapshot of the graph and to restrore to it later.
   446     ///
   447     ///The newly added nodes and edges can be removed using the
   448     ///restore() function.
   449     ///
   450     ///\warning Edge and node deletions cannot be restored.
   451     ///\warning Snapshots cannot be nested.
   452     class Snapshot : protected Parent::NodeNotifier::ObserverBase,
   453 		     protected Parent::EdgeNotifier::ObserverBase
   454     {
   455     public:
   456       
   457       class UnsupportedOperation : public LogicError {
   458       public:
   459 	virtual const char* exceptionName() const {
   460 	  return "lemon::ListGraph::Snapshot::UnsupportedOperation";
   461 	}
   462       };
   463             
   464 
   465     protected:
   466       
   467       ListGraph *g;
   468       std::list<Node> added_nodes;
   469       std::list<Edge> added_edges;
   470       
   471       bool active;
   472       virtual void add(const Node& n) {
   473 	added_nodes.push_back(n);
   474       };
   475       virtual void erase(const Node&) 
   476       {
   477 	throw UnsupportedOperation();
   478       }
   479       virtual void add(const Edge& n) {
   480 	added_edges.push_back(n);
   481       };
   482       virtual void erase(const Edge&) 
   483       {
   484 	throw UnsupportedOperation();
   485       }
   486 
   487       ///\bug What is this used for?
   488       ///
   489       virtual void build() {}
   490       ///\bug What is this used for?
   491       ///
   492       virtual void clear() {}
   493 
   494       void regist(ListGraph &_g) {
   495 	g=&_g;
   496 	Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
   497 	Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
   498       }
   499             
   500       void deregist() {
   501 	Parent::NodeNotifier::ObserverBase::detach();
   502 	Parent::EdgeNotifier::ObserverBase::detach();
   503 	g=0;
   504       }
   505 
   506     public:
   507       ///Default constructur.
   508       
   509       ///Default constructur.
   510       ///To actually make a snapshot you must call save().
   511       ///
   512       Snapshot() : g(0) {}
   513       ///Constructor that immediately makes a snapshot.
   514       
   515       ///This constructor immediately makes a snapshot of the graph.
   516       ///\param _g The graph we make a snapshot of.
   517       Snapshot(ListGraph &_g) {
   518 	regist(_g);
   519       }
   520       ///\bug Is it necessary?
   521       ///
   522       ~Snapshot() 
   523       {
   524 	if(g) deregist();
   525       }
   526       
   527       ///Make a snapshot.
   528 
   529       ///Make a snapshot of the graph.
   530       ///
   531       ///This function can be called more than once. In case of a repeated
   532       ///call, the previous snapshot gets lost.
   533       ///\param _g The graph we make the snapshot of.
   534       void save(ListGraph &_g) 
   535       {
   536 	if(g!=&_g) {
   537 	  if(g) deregist();
   538 	  regist(_g);
   539 	}
   540 	added_nodes.clear();
   541 	added_edges.clear();
   542       }
   543       
   544     ///Undo the changes until the last snapshot.
   545 
   546     ///Undo the changes until last snapshot created by save().
   547     ///
   548     ///\todo This function might be called undo().
   549       void restore() {
   550 	ListGraph &old_g=*g;
   551 	deregist();
   552 	while(!added_edges.empty()) {
   553 	  old_g.erase(added_edges.front());
   554 	  added_edges.pop_front();
   555 	}
   556  	while(!added_nodes.empty()) {
   557 	  old_g.erase(added_nodes.front());
   558 	  added_nodes.pop_front();
   559 	}
   560       }
   561     };
   562     
   563   };
   564 
   565   ///@}
   566 
   567   /**************** Undirected List Graph ****************/
   568 
   569   typedef UGraphExtender<UGraphBaseExtender<
   570     ListGraphBase> > ExtendedListUGraphBase;
   571 
   572   /// \addtogroup graphs
   573   /// @{
   574 
   575   ///An undirected list graph class.
   576 
   577   ///This is a simple and fast erasable undirected graph implementation.
   578   ///
   579   ///It conforms to the
   580   ///\ref concept::UGraph "UGraph" concept.
   581   ///
   582   ///\sa concept::UGraph.
   583   ///
   584   ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
   585   ///haven't been implemented yet.
   586   ///
   587   class ListUGraph : public ExtendedListUGraphBase {
   588   public:
   589     typedef ExtendedListUGraphBase Parent;
   590     /// \brief Changes the target of \c e to \c n
   591     ///
   592     /// Changes the target of \c e to \c n
   593     ///
   594     /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
   595     /// referencing the changed edge remain
   596     /// valid. However <tt>InEdge</tt>'s are invalidated.
   597     void changeTarget(UEdge e, Node n) { 
   598       _changeTarget(e,n); 
   599     }
   600     /// Changes the source of \c e to \c n
   601     ///
   602     /// Changes the source of \c e to \c n
   603     ///
   604     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
   605     ///referencing the changed edge remain
   606     ///valid. However <tt>OutEdge</tt>'s are invalidated.
   607     void changeSource(UEdge e, Node n) { 
   608       _changeSource(e,n); 
   609     }
   610     /// \brief Contract two nodes.
   611     ///
   612     /// This function contracts two nodes.
   613     ///
   614     /// Node \p b will be removed but instead of deleting
   615     /// its neighboring edges, they will be joined to \p a.
   616     /// The last parameter \p r controls whether to remove loops. \c true
   617     /// means that loops will be removed.
   618     ///
   619     /// \note The <tt>Edge</tt>s
   620     /// referencing a moved edge remain
   621     /// valid.
   622     void contract(Node a, Node b, bool r = true) {
   623       for(IncEdgeIt e(*this, b); e!=INVALID;) {
   624 	IncEdgeIt f = e; ++f;
   625 	if (r && runningNode(e) == a) {
   626 	  erase(e);
   627 	} else if (source(e) == b) {
   628 	  changeSource(e, a);
   629 	} else {
   630 	  changeTarget(e, a);
   631 	}
   632 	e = f;
   633       }
   634       erase(b);
   635     }
   636   };
   637 
   638 
   639   class ListBpUGraphBase {
   640   public:
   641 
   642     class NodeSetError : public LogicError {
   643       virtual const char* exceptionName() const { 
   644 	return "lemon::ListBpUGraph::NodeSetError";
   645       }
   646     };
   647 
   648   protected:
   649 
   650     struct NodeT {
   651       int first_edge, next_node;
   652     };
   653 
   654     struct EdgeT {
   655       int aNode, prev_out, next_out;
   656       int bNode, prev_in, next_in;
   657     };
   658 
   659     std::vector<NodeT> aNodes;
   660     std::vector<NodeT> bNodes;
   661 
   662     std::vector<EdgeT> edges;
   663 
   664     int first_anode;
   665     int first_free_anode;
   666 
   667     int first_bnode;
   668     int first_free_bnode;
   669 
   670     int first_free_edge;
   671 
   672   public:
   673   
   674     class Node {
   675       friend class ListBpUGraphBase;
   676     protected:
   677       int id;
   678 
   679       Node(int _id) : id(_id) {}
   680     public:
   681       Node() {}
   682       Node(Invalid) { id = -1; }
   683       bool operator==(const Node i) const {return id==i.id;}
   684       bool operator!=(const Node i) const {return id!=i.id;}
   685       bool operator<(const Node i) const {return id<i.id;}
   686     };
   687 
   688     class Edge {
   689       friend class ListBpUGraphBase;
   690     protected:
   691       int id;
   692 
   693       Edge(int _id) { id = _id;}
   694     public:
   695       Edge() {}
   696       Edge (Invalid) { id = -1; }
   697       bool operator==(const Edge i) const {return id==i.id;}
   698       bool operator!=(const Edge i) const {return id!=i.id;}
   699       bool operator<(const Edge i) const {return id<i.id;}
   700     };
   701 
   702     ListBpUGraphBase()
   703       : first_anode(-1), first_free_anode(-1),
   704         first_bnode(-1), first_free_bnode(-1),
   705         first_free_edge(-1) {}
   706 
   707     void firstANode(Node& node) const {
   708       node.id = first_anode != -1 ? (first_anode << 1) : -1;
   709     }
   710     void nextANode(Node& node) const {
   711       node.id = aNodes[node.id >> 1].next_node;
   712     }
   713 
   714     void firstBNode(Node& node) const {
   715       node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
   716     }
   717     void nextBNode(Node& node) const {
   718       node.id = bNodes[node.id >> 1].next_node;
   719     }
   720 
   721     void first(Node& node) const {
   722       if (first_anode != -1) {
   723         node.id = (first_anode << 1);
   724       } else if (first_bnode != -1) {
   725         node.id = (first_bnode << 1) + 1;
   726       } else {
   727         node.id = -1;
   728       }
   729     }
   730     void next(Node& node) const {
   731       if (aNode(node)) {
   732         node.id = aNodes[node.id >> 1].next_node;
   733         if (node.id == -1) {
   734           if (first_bnode != -1) {
   735             node.id = (first_bnode << 1) + 1;
   736           }
   737         }
   738       } else {
   739         node.id = bNodes[node.id >> 1].next_node;
   740       }
   741     }
   742   
   743     void first(Edge& edge) const {
   744       int aNodeId = first_anode;
   745       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
   746         aNodeId = aNodes[aNodeId].next_node != -1 ? 
   747           aNodes[aNodeId].next_node >> 1 : -1;
   748       }
   749       if (aNodeId != -1) {
   750         edge.id = aNodes[aNodeId].first_edge;
   751       } else {
   752         edge.id = -1;
   753       }
   754     }
   755     void next(Edge& edge) const {
   756       int aNodeId = edges[edge.id].aNode >> 1;
   757       edge.id = edges[edge.id].next_out;
   758       if (edge.id == -1) {
   759         aNodeId = aNodes[aNodeId].next_node != -1 ? 
   760           aNodes[aNodeId].next_node >> 1 : -1;
   761         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
   762           aNodeId = aNodes[aNodeId].next_node != -1 ? 
   763           aNodes[aNodeId].next_node >> 1 : -1;
   764         }
   765         if (aNodeId != -1) {
   766           edge.id = aNodes[aNodeId].first_edge;
   767         } else {
   768           edge.id = -1;
   769         }
   770       }
   771     }
   772 
   773     void firstOut(Edge& edge, const Node& node) const {
   774       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
   775       edge.id = aNodes[node.id >> 1].first_edge;
   776     }
   777     void nextOut(Edge& edge) const {
   778       edge.id = edges[edge.id].next_out;
   779     }
   780 
   781     void firstIn(Edge& edge, const Node& node) const {
   782       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
   783       edge.id = bNodes[node.id >> 1].first_edge;
   784     }
   785     void nextIn(Edge& edge) const {
   786       edge.id = edges[edge.id].next_in;
   787     }
   788 
   789     static int id(const Node& node) {
   790       return node.id;
   791     }
   792     static Node nodeFromId(int id) {
   793       return Node(id);
   794     }
   795     int maxNodeId() const {
   796       return aNodes.size() > bNodes.size() ?
   797 	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
   798     }
   799   
   800     static int id(const Edge& edge) {
   801       return edge.id;
   802     }
   803     static Edge edgeFromId(int id) {
   804       return Edge(id);
   805     }
   806     int maxEdgeId() const {
   807       return edges.size();
   808     }
   809   
   810     static int aNodeId(const Node& node) {
   811       return node.id >> 1;
   812     }
   813     static Node fromANodeId(int id) {
   814       return Node(id << 1);
   815     }
   816     int maxANodeId() const {
   817       return aNodes.size();
   818     }
   819 
   820     static int bNodeId(const Node& node) {
   821       return node.id >> 1;
   822     }
   823     static Node fromBNodeId(int id) {
   824       return Node((id << 1) + 1);
   825     }
   826     int maxBNodeId() const {
   827       return bNodes.size();
   828     }
   829 
   830     Node aNode(const Edge& edge) const {
   831       return Node(edges[edge.id].aNode);
   832     }
   833     Node bNode(const Edge& edge) const {
   834       return Node(edges[edge.id].bNode);
   835     }
   836 
   837     static bool aNode(const Node& node) {
   838       return (node.id & 1) == 0;
   839     }
   840 
   841     static bool bNode(const Node& node) {
   842       return (node.id & 1) == 1;
   843     }
   844 
   845     Node addANode() {
   846       int aNodeId;
   847       if (first_free_anode == -1) {
   848         aNodeId = aNodes.size();
   849         aNodes.push_back(NodeT());
   850       } else {
   851         aNodeId = first_free_anode;
   852         first_free_anode = aNodes[first_free_anode].next_node;
   853       }
   854       aNodes[aNodeId].next_node = 
   855         first_anode != -1 ? (first_anode << 1) : -1;
   856       first_anode = aNodeId;
   857       aNodes[aNodeId].first_edge = -1;
   858       return Node(aNodeId << 1);
   859     }
   860 
   861     Node addBNode() {
   862       int bNodeId;
   863       if (first_free_bnode == -1) {
   864         bNodeId = bNodes.size();
   865         bNodes.push_back(NodeT());
   866       } else {
   867         bNodeId = first_free_bnode;
   868         first_free_bnode = bNodes[first_free_bnode].next_node;
   869       }
   870       bNodes[bNodeId].next_node = 
   871         first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
   872       first_bnode = bNodeId;
   873       bNodes[bNodeId].first_edge = -1;
   874       return Node((bNodeId << 1) + 1);
   875     }
   876 
   877     Edge addEdge(const Node& source, const Node& target) {
   878       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
   879       int edgeId;
   880       if (first_free_edge != -1) {
   881         edgeId = first_free_edge;
   882         first_free_edge = edges[edgeId].next_out;
   883       } else {
   884         edgeId = edges.size();
   885         edges.push_back(EdgeT());
   886       }
   887       if ((source.id & 1) == 0) {
   888 	edges[edgeId].aNode = source.id;
   889 	edges[edgeId].bNode = target.id;
   890       } else {
   891 	edges[edgeId].aNode = target.id;
   892 	edges[edgeId].bNode = source.id;
   893       }
   894       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
   895       edges[edgeId].prev_out = -1;
   896       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
   897         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
   898       }
   899       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
   900       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
   901       edges[edgeId].prev_in = -1;
   902       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
   903         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
   904       }
   905       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
   906       return Edge(edgeId);
   907     }
   908 
   909     void erase(const Node& node) {
   910       if (aNode(node)) {
   911         int aNodeId = node.id >> 1;
   912         aNodes[aNodeId].next_node = first_free_anode;
   913         first_free_anode = aNodeId;
   914       } else {
   915         int bNodeId = node.id >> 1;
   916         bNodes[bNodeId].next_node = first_free_bnode;
   917         first_free_bnode = bNodeId;
   918       }
   919     }
   920 
   921     void erase(const Edge& edge) {
   922       if (edges[edge.id].prev_out != -1) {
   923         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
   924       } else {
   925         aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
   926       }
   927       if (edges[edge.id].next_out != -1) {
   928         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
   929       }
   930       if (edges[edge.id].prev_in != -1) {
   931         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
   932       } else {
   933         bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
   934       }
   935       if (edges[edge.id].next_in != -1) {
   936         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
   937       }
   938       edges[edge.id].next_out = first_free_edge;
   939       first_free_edge = edge.id;
   940     }
   941 
   942     void clear() {
   943       aNodes.clear();
   944       bNodes.clear();
   945       edges.clear();
   946       first_anode = -1;
   947       first_free_anode = -1;
   948       first_bnode = -1;
   949       first_free_bnode = -1;
   950       first_free_edge = -1;
   951     }
   952 
   953   };
   954 
   955 
   956   typedef BpUGraphExtender< BpUGraphBaseExtender<
   957     ListBpUGraphBase> > ExtendedListBpUGraphBase;
   958 
   959   /// \ingroup graphs
   960   ///
   961   /// \brief A smart bipartite undirected graph class.
   962   ///
   963   /// This is a bipartite undirected graph implementation.
   964   /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 
   965   /// concept.
   966   /// \sa concept::BpUGraph.
   967   ///
   968   class ListBpUGraph : public ExtendedListBpUGraphBase {};
   969 
   970   
   971   /// @}  
   972 } //namespace lemon
   973   
   974 
   975 #endif