COIN-OR::LEMON - Graph Library

Changeset 1982:f0eb6b79dcdf in lemon-0.x for lemon


Ignore:
Timestamp:
02/23/06 16:10:45 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2575
Message:

ListBpUGraph

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r1979 r1982  
    637637  };
    638638
     639
     640  class ListBpUGraphBase {
     641  public:
     642
     643    class NodeSetError : public LogicError {
     644      virtual const char* exceptionName() const {
     645        return "lemon::ListBpUGraph::NodeSetError";
     646      }
     647    };
     648
     649  protected:
     650
     651    struct NodeT {
     652      int first_edge, next_node;
     653    };
     654
     655    struct EdgeT {
     656      int aNode, prev_out, next_out;
     657      int bNode, prev_in, next_in;
     658    };
     659
     660    std::vector<NodeT> aNodes;
     661    std::vector<NodeT> bNodes;
     662
     663    std::vector<EdgeT> edges;
     664
     665    int first_anode;
     666    int first_free_anode;
     667
     668    int first_bnode;
     669    int first_free_bnode;
     670
     671    int first_free_edge;
     672
     673  public:
     674 
     675    class Node {
     676      friend class ListBpUGraphBase;
     677    protected:
     678      int id;
     679
     680      Node(int _id) : id(_id) {}
     681    public:
     682      Node() {}
     683      Node(Invalid) { id = -1; }
     684      bool operator==(const Node i) const {return id==i.id;}
     685      bool operator!=(const Node i) const {return id!=i.id;}
     686      bool operator<(const Node i) const {return id<i.id;}
     687    };
     688
     689    class Edge {
     690      friend class ListBpUGraphBase;
     691    protected:
     692      int id;
     693
     694      Edge(int _id) { id = _id;}
     695    public:
     696      Edge() {}
     697      Edge (Invalid) { id = -1; }
     698      bool operator==(const Edge i) const {return id==i.id;}
     699      bool operator!=(const Edge i) const {return id!=i.id;}
     700      bool operator<(const Edge i) const {return id<i.id;}
     701    };
     702
     703    ListBpUGraphBase()
     704      : first_anode(-1), first_free_anode(-1),
     705        first_bnode(-1), first_free_bnode(-1),
     706        first_free_edge(-1) {}
     707
     708    void firstANode(Node& node) const {
     709      node.id = first_anode != -1 ? (first_anode << 1) : -1;
     710    }
     711    void nextANode(Node& node) const {
     712      node.id = aNodes[node.id >> 1].next_node;
     713    }
     714
     715    void firstBNode(Node& node) const {
     716      node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
     717    }
     718    void nextBNode(Node& node) const {
     719      node.id = aNodes[node.id >> 1].next_node;
     720    }
     721
     722    void first(Node& node) const {
     723      if (first_anode != -1) {
     724        node.id = (first_anode << 1);
     725      } else if (first_bnode != -1) {
     726        node.id = (first_bnode << 1) + 1;
     727      } else {
     728        node.id = -1;
     729      }
     730    }
     731    void next(Node& node) const {
     732      if (aNode(node)) {
     733        node.id = aNodes[node.id >> 1].next_node;
     734        if (node.id == -1) {
     735          if (first_bnode != -1) {
     736            node.id = (first_bnode << 1) + 1;
     737          }
     738        }
     739      } else {
     740        node.id = bNodes[node.id >> 1].next_node;
     741      }
     742    }
     743 
     744    void first(Edge& edge) const {
     745      int aNodeId = first_anode;
     746      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
     747        aNodeId = aNodes[aNodeId].next_node != -1 ?
     748          aNodes[aNodeId].next_node >> 1 : -1;
     749      }
     750      if (aNodeId != -1) {
     751        edge.id = aNodes[aNodeId].first_edge;
     752      } else {
     753        edge.id = -1;
     754      }
     755    }
     756    void next(Edge& edge) const {
     757      int aNodeId = edges[edge.id].aNode >> 1;
     758      edge.id = edges[edge.id].next_out;
     759      if (edge.id == -1) {
     760        aNodeId = aNodes[aNodeId].next_node != -1 ?
     761          aNodes[aNodeId].next_node >> 1 : -1;
     762        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
     763          aNodeId = aNodes[aNodeId].next_node != -1 ?
     764          aNodes[aNodeId].next_node >> 1 : -1;
     765        }
     766        if (aNodeId != -1) {
     767          edge.id = aNodes[aNodeId].first_edge;
     768        } else {
     769          edge.id = -1;
     770        }
     771      }
     772    }
     773
     774    void firstOut(Edge& edge, const Node& node) const {
     775      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     776      edge.id = aNodes[node.id >> 1].first_edge;
     777    }
     778    void nextOut(Edge& edge) const {
     779      edge.id = edges[edge.id].next_out;
     780    }
     781
     782    void firstIn(Edge& edge, const Node& node) const {
     783      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     784      edge.id = bNodes[node.id >> 1].first_edge;
     785    }
     786    void nextIn(Edge& edge) const {
     787      edge.id = edges[edge.id].next_in;
     788    }
     789
     790    static int id(const Node& node) {
     791      return node.id;
     792    }
     793    static Node nodeFromId(int id) {
     794      return Node(id);
     795    }
     796    int maxNodeId() const {
     797      return aNodes.size() > bNodes.size() ?
     798        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
     799    }
     800 
     801    static int id(const Edge& edge) {
     802      return edge.id;
     803    }
     804    static Edge edgeFromId(int id) {
     805      return Edge(id);
     806    }
     807    int maxEdgeId() const {
     808      return edges.size();
     809    }
     810 
     811    static int aNodeId(const Node& node) {
     812      return node.id >> 1;
     813    }
     814    static Node fromANodeId(int id, Node) {
     815      return Node(id << 1);
     816    }
     817    int maxANodeId() const {
     818      return aNodes.size();
     819    }
     820
     821    static int bNodeId(const Node& node) {
     822      return node.id >> 1;
     823    }
     824    static Node fromBNodeId(int id) {
     825      return Node((id << 1) + 1);
     826    }
     827    int maxBNodeId() const {
     828      return bNodes.size();
     829    }
     830
     831    Node aNode(const Edge& edge) const {
     832      return Node(edges[edge.id].aNode);
     833    }
     834    Node bNode(const Edge& edge) const {
     835      return Node(edges[edge.id].bNode);
     836    }
     837
     838    static bool aNode(const Node& node) {
     839      return (node.id & 1) == 0;
     840    }
     841
     842    static bool bNode(const Node& node) {
     843      return (node.id & 1) == 1;
     844    }
     845
     846    Node addANode() {
     847      int aNodeId;
     848      if (first_free_anode == -1) {
     849        aNodeId = aNodes.size();
     850        aNodes.push_back(NodeT());
     851      } else {
     852        aNodeId = first_free_anode;
     853        first_free_anode = aNodes[first_free_anode].next_node;
     854      }
     855      aNodes[aNodeId].next_node =
     856        first_anode != -1 ? (first_anode << 1) : -1;
     857      first_anode = aNodeId;
     858      aNodes[aNodeId].first_edge = -1;
     859      return Node(aNodeId << 1);
     860    }
     861
     862    Node addBNode() {
     863      int bNodeId;
     864      if (first_free_anode == -1) {
     865        bNodeId = bNodes.size();
     866        bNodes.push_back(NodeT());
     867      } else {
     868        bNodeId = first_free_bnode;
     869        first_free_bnode = bNodes[first_free_bnode].next_node;
     870      }
     871      bNodes[bNodeId].next_node =
     872        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
     873      first_bnode = bNodeId;
     874      bNodes[bNodeId].first_edge = -1;
     875      return Node((bNodeId << 1) + 1);
     876    }
     877
     878    Edge addEdge(const Node& source, const Node& target) {
     879      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
     880      int edgeId;
     881      if (first_free_edge != -1) {
     882        edgeId = first_free_edge;
     883        first_free_edge = edges[edgeId].next_out;
     884      } else {
     885        edgeId = edges.size();
     886        edges.push_back(EdgeT());
     887      }
     888      if ((source.id & 1) == 0) {
     889        edges[edgeId].aNode = source.id;
     890        edges[edgeId].bNode = target.id;
     891      } else {
     892        edges[edgeId].aNode = target.id;
     893        edges[edgeId].bNode = source.id;
     894      }
     895      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
     896      edges[edgeId].prev_out = -1;
     897      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
     898        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
     899      }
     900      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
     901      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
     902      edges[edgeId].prev_in = -1;
     903      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
     904        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
     905      }
     906      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
     907      return Edge(edgeId);
     908    }
     909
     910    void erase(const Node& node) {
     911      if (aNode(node)) {
     912        int aNodeId = node.id >> 1;
     913        aNodes[aNodeId].next_node = first_free_anode;
     914        first_free_anode = aNodeId;
     915      } else {
     916        int bNodeId = node.id >> 1;
     917        bNodes[bNodeId].next_node = first_free_bnode;
     918        first_free_bnode = bNodeId;
     919      }
     920    }
     921
     922    void erase(const Edge& edge) {
     923      if (edges[edge.id].prev_out != -1) {
     924        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
     925      } else {
     926        aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
     927      }
     928      if (edges[edge.id].next_out != -1) {
     929        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
     930      }
     931      if (edges[edge.id].prev_in != -1) {
     932        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
     933      } else {
     934        bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
     935      }
     936      if (edges[edge.id].next_in != -1) {
     937        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
     938      }
     939      edges[edge.id].next_out = first_free_edge;
     940      first_free_edge = edge.id;
     941    }
     942
     943    void clear() {
     944      aNodes.clear();
     945      bNodes.clear();
     946      edges.clear();
     947      first_anode = -1;
     948      first_free_anode = -1;
     949      first_bnode = -1;
     950      first_free_bnode = -1;
     951      first_free_edge = -1;
     952    }
     953
     954  };
     955
     956
     957  typedef BpUGraphExtender< BpUGraphBaseExtender<
     958    ListBpUGraphBase> > ExtendedListBpUGraphBase;
     959
     960  /// \ingroup graphs
     961  ///
     962  /// \brief A smart bipartite undirected graph class.
     963  ///
     964  /// This is a bipartite undirected graph implementation.
     965  /// Except from this it conforms to
     966  /// the \ref concept::BpUGraph "BpUGraph" concept.
     967  /// \sa concept::BpUGraph.
     968  ///
     969  class ListBpUGraph : public ExtendedListBpUGraphBase {};
     970
    639971 
    640972  /// @} 
Note: See TracChangeset for help on using the changeset viewer.