1.1 --- a/lemon/list_graph.h	Thu Feb 23 09:03:18 2006 +0000
     1.2 +++ b/lemon/list_graph.h	Thu Feb 23 15:10:45 2006 +0000
     1.3 @@ -636,6 +636,338 @@
     1.4      }
     1.5    };
     1.6  
     1.7 +
     1.8 +  class ListBpUGraphBase {
     1.9 +  public:
    1.10 +
    1.11 +    class NodeSetError : public LogicError {
    1.12 +      virtual const char* exceptionName() const { 
    1.13 +	return "lemon::ListBpUGraph::NodeSetError";
    1.14 +      }
    1.15 +    };
    1.16 +
    1.17 +  protected:
    1.18 +
    1.19 +    struct NodeT {
    1.20 +      int first_edge, next_node;
    1.21 +    };
    1.22 +
    1.23 +    struct EdgeT {
    1.24 +      int aNode, prev_out, next_out;
    1.25 +      int bNode, prev_in, next_in;
    1.26 +    };
    1.27 +
    1.28 +    std::vector<NodeT> aNodes;
    1.29 +    std::vector<NodeT> bNodes;
    1.30 +
    1.31 +    std::vector<EdgeT> edges;
    1.32 +
    1.33 +    int first_anode;
    1.34 +    int first_free_anode;
    1.35 +
    1.36 +    int first_bnode;
    1.37 +    int first_free_bnode;
    1.38 +
    1.39 +    int first_free_edge;
    1.40 +
    1.41 +  public:
    1.42 +  
    1.43 +    class Node {
    1.44 +      friend class ListBpUGraphBase;
    1.45 +    protected:
    1.46 +      int id;
    1.47 +
    1.48 +      Node(int _id) : id(_id) {}
    1.49 +    public:
    1.50 +      Node() {}
    1.51 +      Node(Invalid) { id = -1; }
    1.52 +      bool operator==(const Node i) const {return id==i.id;}
    1.53 +      bool operator!=(const Node i) const {return id!=i.id;}
    1.54 +      bool operator<(const Node i) const {return id<i.id;}
    1.55 +    };
    1.56 +
    1.57 +    class Edge {
    1.58 +      friend class ListBpUGraphBase;
    1.59 +    protected:
    1.60 +      int id;
    1.61 +
    1.62 +      Edge(int _id) { id = _id;}
    1.63 +    public:
    1.64 +      Edge() {}
    1.65 +      Edge (Invalid) { id = -1; }
    1.66 +      bool operator==(const Edge i) const {return id==i.id;}
    1.67 +      bool operator!=(const Edge i) const {return id!=i.id;}
    1.68 +      bool operator<(const Edge i) const {return id<i.id;}
    1.69 +    };
    1.70 +
    1.71 +    ListBpUGraphBase()
    1.72 +      : first_anode(-1), first_free_anode(-1),
    1.73 +        first_bnode(-1), first_free_bnode(-1),
    1.74 +        first_free_edge(-1) {}
    1.75 +
    1.76 +    void firstANode(Node& node) const {
    1.77 +      node.id = first_anode != -1 ? (first_anode << 1) : -1;
    1.78 +    }
    1.79 +    void nextANode(Node& node) const {
    1.80 +      node.id = aNodes[node.id >> 1].next_node;
    1.81 +    }
    1.82 +
    1.83 +    void firstBNode(Node& node) const {
    1.84 +      node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    1.85 +    }
    1.86 +    void nextBNode(Node& node) const {
    1.87 +      node.id = aNodes[node.id >> 1].next_node;
    1.88 +    }
    1.89 +
    1.90 +    void first(Node& node) const {
    1.91 +      if (first_anode != -1) {
    1.92 +        node.id = (first_anode << 1);
    1.93 +      } else if (first_bnode != -1) {
    1.94 +        node.id = (first_bnode << 1) + 1;
    1.95 +      } else {
    1.96 +        node.id = -1;
    1.97 +      }
    1.98 +    }
    1.99 +    void next(Node& node) const {
   1.100 +      if (aNode(node)) {
   1.101 +        node.id = aNodes[node.id >> 1].next_node;
   1.102 +        if (node.id == -1) {
   1.103 +          if (first_bnode != -1) {
   1.104 +            node.id = (first_bnode << 1) + 1;
   1.105 +          }
   1.106 +        }
   1.107 +      } else {
   1.108 +        node.id = bNodes[node.id >> 1].next_node;
   1.109 +      }
   1.110 +    }
   1.111 +  
   1.112 +    void first(Edge& edge) const {
   1.113 +      int aNodeId = first_anode;
   1.114 +      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
   1.115 +        aNodeId = aNodes[aNodeId].next_node != -1 ? 
   1.116 +          aNodes[aNodeId].next_node >> 1 : -1;
   1.117 +      }
   1.118 +      if (aNodeId != -1) {
   1.119 +        edge.id = aNodes[aNodeId].first_edge;
   1.120 +      } else {
   1.121 +        edge.id = -1;
   1.122 +      }
   1.123 +    }
   1.124 +    void next(Edge& edge) const {
   1.125 +      int aNodeId = edges[edge.id].aNode >> 1;
   1.126 +      edge.id = edges[edge.id].next_out;
   1.127 +      if (edge.id == -1) {
   1.128 +        aNodeId = aNodes[aNodeId].next_node != -1 ? 
   1.129 +          aNodes[aNodeId].next_node >> 1 : -1;
   1.130 +        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
   1.131 +          aNodeId = aNodes[aNodeId].next_node != -1 ? 
   1.132 +          aNodes[aNodeId].next_node >> 1 : -1;
   1.133 +        }
   1.134 +        if (aNodeId != -1) {
   1.135 +          edge.id = aNodes[aNodeId].first_edge;
   1.136 +        } else {
   1.137 +          edge.id = -1;
   1.138 +        }
   1.139 +      }
   1.140 +    }
   1.141 +
   1.142 +    void firstOut(Edge& edge, const Node& node) const {
   1.143 +      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
   1.144 +      edge.id = aNodes[node.id >> 1].first_edge;
   1.145 +    }
   1.146 +    void nextOut(Edge& edge) const {
   1.147 +      edge.id = edges[edge.id].next_out;
   1.148 +    }
   1.149 +
   1.150 +    void firstIn(Edge& edge, const Node& node) const {
   1.151 +      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
   1.152 +      edge.id = bNodes[node.id >> 1].first_edge;
   1.153 +    }
   1.154 +    void nextIn(Edge& edge) const {
   1.155 +      edge.id = edges[edge.id].next_in;
   1.156 +    }
   1.157 +
   1.158 +    static int id(const Node& node) {
   1.159 +      return node.id;
   1.160 +    }
   1.161 +    static Node nodeFromId(int id) {
   1.162 +      return Node(id);
   1.163 +    }
   1.164 +    int maxNodeId() const {
   1.165 +      return aNodes.size() > bNodes.size() ?
   1.166 +	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
   1.167 +    }
   1.168 +  
   1.169 +    static int id(const Edge& edge) {
   1.170 +      return edge.id;
   1.171 +    }
   1.172 +    static Edge edgeFromId(int id) {
   1.173 +      return Edge(id);
   1.174 +    }
   1.175 +    int maxEdgeId() const {
   1.176 +      return edges.size();
   1.177 +    }
   1.178 +  
   1.179 +    static int aNodeId(const Node& node) {
   1.180 +      return node.id >> 1;
   1.181 +    }
   1.182 +    static Node fromANodeId(int id, Node) {
   1.183 +      return Node(id << 1);
   1.184 +    }
   1.185 +    int maxANodeId() const {
   1.186 +      return aNodes.size();
   1.187 +    }
   1.188 +
   1.189 +    static int bNodeId(const Node& node) {
   1.190 +      return node.id >> 1;
   1.191 +    }
   1.192 +    static Node fromBNodeId(int id) {
   1.193 +      return Node((id << 1) + 1);
   1.194 +    }
   1.195 +    int maxBNodeId() const {
   1.196 +      return bNodes.size();
   1.197 +    }
   1.198 +
   1.199 +    Node aNode(const Edge& edge) const {
   1.200 +      return Node(edges[edge.id].aNode);
   1.201 +    }
   1.202 +    Node bNode(const Edge& edge) const {
   1.203 +      return Node(edges[edge.id].bNode);
   1.204 +    }
   1.205 +
   1.206 +    static bool aNode(const Node& node) {
   1.207 +      return (node.id & 1) == 0;
   1.208 +    }
   1.209 +
   1.210 +    static bool bNode(const Node& node) {
   1.211 +      return (node.id & 1) == 1;
   1.212 +    }
   1.213 +
   1.214 +    Node addANode() {
   1.215 +      int aNodeId;
   1.216 +      if (first_free_anode == -1) {
   1.217 +        aNodeId = aNodes.size();
   1.218 +        aNodes.push_back(NodeT());
   1.219 +      } else {
   1.220 +        aNodeId = first_free_anode;
   1.221 +        first_free_anode = aNodes[first_free_anode].next_node;
   1.222 +      }
   1.223 +      aNodes[aNodeId].next_node = 
   1.224 +        first_anode != -1 ? (first_anode << 1) : -1;
   1.225 +      first_anode = aNodeId;
   1.226 +      aNodes[aNodeId].first_edge = -1;
   1.227 +      return Node(aNodeId << 1);
   1.228 +    }
   1.229 +
   1.230 +    Node addBNode() {
   1.231 +      int bNodeId;
   1.232 +      if (first_free_anode == -1) {
   1.233 +        bNodeId = bNodes.size();
   1.234 +        bNodes.push_back(NodeT());
   1.235 +      } else {
   1.236 +        bNodeId = first_free_bnode;
   1.237 +        first_free_bnode = bNodes[first_free_bnode].next_node;
   1.238 +      }
   1.239 +      bNodes[bNodeId].next_node = 
   1.240 +        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
   1.241 +      first_bnode = bNodeId;
   1.242 +      bNodes[bNodeId].first_edge = -1;
   1.243 +      return Node((bNodeId << 1) + 1);
   1.244 +    }
   1.245 +
   1.246 +    Edge addEdge(const Node& source, const Node& target) {
   1.247 +      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
   1.248 +      int edgeId;
   1.249 +      if (first_free_edge != -1) {
   1.250 +        edgeId = first_free_edge;
   1.251 +        first_free_edge = edges[edgeId].next_out;
   1.252 +      } else {
   1.253 +        edgeId = edges.size();
   1.254 +        edges.push_back(EdgeT());
   1.255 +      }
   1.256 +      if ((source.id & 1) == 0) {
   1.257 +	edges[edgeId].aNode = source.id;
   1.258 +	edges[edgeId].bNode = target.id;
   1.259 +      } else {
   1.260 +	edges[edgeId].aNode = target.id;
   1.261 +	edges[edgeId].bNode = source.id;
   1.262 +      }
   1.263 +      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
   1.264 +      edges[edgeId].prev_out = -1;
   1.265 +      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
   1.266 +        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
   1.267 +      }
   1.268 +      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
   1.269 +      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
   1.270 +      edges[edgeId].prev_in = -1;
   1.271 +      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
   1.272 +        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
   1.273 +      }
   1.274 +      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
   1.275 +      return Edge(edgeId);
   1.276 +    }
   1.277 +
   1.278 +    void erase(const Node& node) {
   1.279 +      if (aNode(node)) {
   1.280 +        int aNodeId = node.id >> 1;
   1.281 +        aNodes[aNodeId].next_node = first_free_anode;
   1.282 +        first_free_anode = aNodeId;
   1.283 +      } else {
   1.284 +        int bNodeId = node.id >> 1;
   1.285 +        bNodes[bNodeId].next_node = first_free_bnode;
   1.286 +        first_free_bnode = bNodeId;
   1.287 +      }
   1.288 +    }
   1.289 +
   1.290 +    void erase(const Edge& edge) {
   1.291 +      if (edges[edge.id].prev_out != -1) {
   1.292 +        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
   1.293 +      } else {
   1.294 +        aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
   1.295 +      }
   1.296 +      if (edges[edge.id].next_out != -1) {
   1.297 +        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
   1.298 +      }
   1.299 +      if (edges[edge.id].prev_in != -1) {
   1.300 +        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
   1.301 +      } else {
   1.302 +        bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
   1.303 +      }
   1.304 +      if (edges[edge.id].next_in != -1) {
   1.305 +        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
   1.306 +      }
   1.307 +      edges[edge.id].next_out = first_free_edge;
   1.308 +      first_free_edge = edge.id;
   1.309 +    }
   1.310 +
   1.311 +    void clear() {
   1.312 +      aNodes.clear();
   1.313 +      bNodes.clear();
   1.314 +      edges.clear();
   1.315 +      first_anode = -1;
   1.316 +      first_free_anode = -1;
   1.317 +      first_bnode = -1;
   1.318 +      first_free_bnode = -1;
   1.319 +      first_free_edge = -1;
   1.320 +    }
   1.321 +
   1.322 +  };
   1.323 +
   1.324 +
   1.325 +  typedef BpUGraphExtender< BpUGraphBaseExtender<
   1.326 +    ListBpUGraphBase> > ExtendedListBpUGraphBase;
   1.327 +
   1.328 +  /// \ingroup graphs
   1.329 +  ///
   1.330 +  /// \brief A smart bipartite undirected graph class.
   1.331 +  ///
   1.332 +  /// This is a bipartite undirected graph implementation.
   1.333 +  /// Except from this it conforms to 
   1.334 +  /// the \ref concept::BpUGraph "BpUGraph" concept.
   1.335 +  /// \sa concept::BpUGraph.
   1.336 +  ///
   1.337 +  class ListBpUGraph : public ExtendedListBpUGraphBase {};
   1.338 +
   1.339    
   1.340    /// @}  
   1.341  } //namespace lemon