source: lemon-0.x/lemon/list_bpugraph.h @ 2115:4cd528a30ec1

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_LIST_BPUGRAPH_H
#define LEMON_LIST_BPUGRAPH_H

///\ingroup graphs
///\file
///\brief ListBpUGraph classes.

#include <lemon/bits/bpugraph_extender.h>

#include <lemon/error.h>

#include <vector>
#include <list>

namespace lemon {

  class ListBpUGraphBase {
  public:

    class NodeSetError : public LogicError {
      virtual const char* exceptionName() const { 
        return "lemon::ListBpUGraph::NodeSetError";
      }
    };

  protected:

    struct NodeT {
      int first_edge, prev, next;
    };

    struct UEdgeT {
      int aNode, prev_out, next_out;
      int bNode, prev_in, next_in;
    };

    std::vector<NodeT> aNodes;
    std::vector<NodeT> bNodes;

    std::vector<UEdgeT> edges;

    int first_anode;
    int first_free_anode;

    int first_bnode;
    int first_free_bnode;

    int first_free_edge;

  public:
  
    class Node {
      friend class ListBpUGraphBase;
    protected:
      int id;

      explicit Node(int _id) : id(_id) {}
    public:
      Node() {}
      Node(Invalid) { id = -1; }
      bool operator==(const Node i) const {return id==i.id;}
      bool operator!=(const Node i) const {return id!=i.id;}
      bool operator<(const Node i) const {return id<i.id;}
    };

    class UEdge {
      friend class ListBpUGraphBase;
    protected:
      int id;

      explicit UEdge(int _id) { id = _id;}
    public:
      UEdge() {}
      UEdge (Invalid) { id = -1; }
      bool operator==(const UEdge i) const {return id==i.id;}
      bool operator!=(const UEdge i) const {return id!=i.id;}
      bool operator<(const UEdge i) const {return id<i.id;}
    };

    ListBpUGraphBase()
      : first_anode(-1), first_free_anode(-1),
        first_bnode(-1), first_free_bnode(-1),
        first_free_edge(-1) {}

    void firstANode(Node& node) const {
      node.id = first_anode != -1 ? (first_anode << 1) : -1;
    }
    void nextANode(Node& node) const {
      node.id = aNodes[node.id >> 1].next;
    }

    void firstBNode(Node& node) const {
      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    }
    void nextBNode(Node& node) const {
      node.id = bNodes[node.id >> 1].next;
    }

    void first(Node& node) const {
      if (first_anode != -1) {
        node.id = (first_anode << 1);
      } else if (first_bnode != -1) {
        node.id = (first_bnode << 1) + 1;
      } else {
        node.id = -1;
      }
    }
    void next(Node& node) const {
      if (aNode(node)) {
        node.id = aNodes[node.id >> 1].next;
        if (node.id == -1) {
          if (first_bnode != -1) {
            node.id = (first_bnode << 1) + 1;
          }
        }
      } else {
        node.id = bNodes[node.id >> 1].next;
      }
    }
  
    void first(UEdge& edge) const {
      int aNodeId = first_anode;
      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
        aNodeId = aNodes[aNodeId].next != -1 ? 
          aNodes[aNodeId].next >> 1 : -1;
      }
      if (aNodeId != -1) {
        edge.id = aNodes[aNodeId].first_edge;
      } else {
        edge.id = -1;
      }
    }
    void next(UEdge& edge) const {
      int aNodeId = edges[edge.id].aNode >> 1;
      edge.id = edges[edge.id].next_out;
      if (edge.id == -1) {
        aNodeId = aNodes[aNodeId].next != -1 ? 
          aNodes[aNodeId].next >> 1 : -1;
        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
          aNodeId = aNodes[aNodeId].next != -1 ? 
          aNodes[aNodeId].next >> 1 : -1;
        }
        if (aNodeId != -1) {
          edge.id = aNodes[aNodeId].first_edge;
        } else {
          edge.id = -1;
        }
      }
    }

    void firstFromANode(UEdge& edge, const Node& node) const {
      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
      edge.id = aNodes[node.id >> 1].first_edge;
    }
    void nextFromANode(UEdge& edge) const {
      edge.id = edges[edge.id].next_out;
    }

    void firstFromBNode(UEdge& edge, const Node& node) const {
      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
      edge.id = bNodes[node.id >> 1].first_edge;
    }
    void nextFromBNode(UEdge& edge) const {
      edge.id = edges[edge.id].next_in;
    }

    static int id(const Node& node) {
      return node.id;
    }
    static Node nodeFromId(int id) {
      return Node(id);
    }
    int maxNodeId() const {
      return aNodes.size() > bNodes.size() ?
        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    }
  
    static int id(const UEdge& edge) {
      return edge.id;
    }
    static UEdge uEdgeFromId(int id) {
      return UEdge(id);
    }
    int maxUEdgeId() const {
      return edges.size();
    }
  
    static int aNodeId(const Node& node) {
      return node.id >> 1;
    }
    static Node fromANodeId(int id) {
      return Node(id << 1);
    }
    int maxANodeId() const {
      return aNodes.size();
    }

    static int bNodeId(const Node& node) {
      return node.id >> 1;
    }
    static Node fromBNodeId(int id) {
      return Node((id << 1) + 1);
    }
    int maxBNodeId() const {
      return bNodes.size();
    }

    Node aNode(const UEdge& edge) const {
      return Node(edges[edge.id].aNode);
    }
    Node bNode(const UEdge& edge) const {
      return Node(edges[edge.id].bNode);
    }

    static bool aNode(const Node& node) {
      return (node.id & 1) == 0;
    }

    static bool bNode(const Node& node) {
      return (node.id & 1) == 1;
    }

    Node addANode() {
      int aNodeId;
      if (first_free_anode == -1) {
        aNodeId = aNodes.size();
        aNodes.push_back(NodeT());
      } else {
        aNodeId = first_free_anode;
        first_free_anode = aNodes[first_free_anode].next;
      }
      if (first_anode != -1) {
        aNodes[aNodeId].next = first_anode << 1;
        aNodes[first_anode].prev = aNodeId << 1;
      } else {
        aNodes[aNodeId].next = -1;
      }
      aNodes[aNodeId].prev = -1;
      first_anode = aNodeId;
      aNodes[aNodeId].first_edge = -1;
      return Node(aNodeId << 1);
    }

    Node addBNode() {
      int bNodeId;
      if (first_free_bnode == -1) {
        bNodeId = bNodes.size();
        bNodes.push_back(NodeT());
      } else {
        bNodeId = first_free_bnode;
        first_free_bnode = bNodes[first_free_bnode].next;
      }
      if (first_bnode != -1) {
        bNodes[bNodeId].next = (first_bnode << 1) + 1;
        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
      } else {
        bNodes[bNodeId].next = -1;
      }
      first_bnode = bNodeId;
      bNodes[bNodeId].first_edge = -1;
      return Node((bNodeId << 1) + 1);
    }

    UEdge addEdge(const Node& source, const Node& target) {
      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
      int edgeId;
      if (first_free_edge != -1) {
        edgeId = first_free_edge;
        first_free_edge = edges[edgeId].next_out;
      } else {
        edgeId = edges.size();
        edges.push_back(UEdgeT());
      }
      if ((source.id & 1) == 0) {
        edges[edgeId].aNode = source.id;
        edges[edgeId].bNode = target.id;
      } else {
        edges[edgeId].aNode = target.id;
        edges[edgeId].bNode = source.id;
      }
      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
      edges[edgeId].prev_out = -1;
      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
      }
      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
      edges[edgeId].prev_in = -1;
      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
      }
      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
      return UEdge(edgeId);
    }

    void erase(const Node& node) {
      if (aNode(node)) {
        int aNodeId = node.id >> 1;
        if (aNodes[aNodeId].prev != -1) {
          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
        } else {
          first_anode = aNodes[aNodeId].next >> 1;
        }
        if (aNodes[aNodeId].next != -1) {
          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
        }
        aNodes[aNodeId].next = first_free_anode;
        first_free_anode = aNodeId;
      } else {
        int bNodeId = node.id >> 1;
        if (bNodes[bNodeId].prev != -1) {
          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
        } else {
          first_bnode = bNodes[bNodeId].next >> 1;
        }
        if (bNodes[bNodeId].next != -1) {
          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
        }
        bNodes[bNodeId].next = first_free_bnode;
        first_free_bnode = bNodeId;
      }
    }

    void erase(const UEdge& edge) {

      if (edges[edge.id].prev_out != -1) {
        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
      } else {
        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
      }
      if (edges[edge.id].next_out != -1) {
        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
      }

      if (edges[edge.id].prev_in != -1) {
        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
      } else {
        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
      }
      if (edges[edge.id].next_in != -1) {
        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
      }

      edges[edge.id].next_out = first_free_edge;
      first_free_edge = edge.id;
    }

    void clear() {
      aNodes.clear();
      bNodes.clear();
      edges.clear();
      first_anode = -1;
      first_free_anode = -1;
      first_bnode = -1;
      first_free_bnode = -1;
      first_free_edge = -1;
    }

  };


  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;

  /// \ingroup graphs
  ///
  /// \brief A smart bipartite undirected graph class.
  ///
  /// This is a bipartite undirected graph implementation.
  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 
  /// concept.
  /// \sa concept::BpUGraph.
  ///
  class ListBpUGraph : public ExtendedListBpUGraphBase {};

  
  /// @}  
} //namespace lemon
  

#endif