COIN-OR::LEMON - Graph Library

Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/list_graph.h


Ignore:
Timestamp:
06/30/06 14:15:45 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
Message:

Revert splitted files

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r2115 r2116  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph class.
    25 
     24///\brief ListGraph, ListUGraph classes.
     25
     26#include <lemon/bits/base_extender.h>
    2627#include <lemon/bits/graph_extender.h>
     28
     29#include <lemon/error.h>
    2730
    2831#include <vector>
     
    307310  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    308311
    309   /// \ingroup graphs
     312  /// \addtogroup graphs
     313  /// @{
    310314
    311315  ///A list graph class.
     
    702706  };
    703707
     708  ///@}
     709
     710  /**************** Undirected List Graph ****************/
     711
     712  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
     713  ExtendedListUGraphBase;
     714
     715  /// \addtogroup graphs
     716  /// @{
     717
     718  ///An undirected list graph class.
     719
     720  ///This is a simple and fast erasable undirected graph implementation.
     721  ///
     722  ///It conforms to the
     723  ///\ref concept::UGraph "UGraph" concept.
     724  ///
     725  ///\sa concept::UGraph.
     726  ///
     727  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
     728  ///haven't been implemented yet.
     729  ///
     730  class ListUGraph : public ExtendedListUGraphBase {
     731  public:
     732    typedef ExtendedListUGraphBase Parent;
     733    /// \brief Add a new node to the graph.
     734    ///
     735    /// \return the new node.
     736    ///
     737    Node addNode() { return Parent::addNode(); }
     738
     739    /// \brief Add a new edge to the graph.
     740    ///
     741    /// Add a new edge to the graph with source node \c s
     742    /// and target node \c t.
     743    /// \return the new undirected edge.
     744    UEdge addEdge(const Node& s, const Node& t) {
     745      return Parent::addEdge(s, t);
     746    }
     747    /// \brief Changes the target of \c e to \c n
     748    ///
     749    /// Changes the target of \c e to \c n
     750    ///
     751    /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
     752    /// referencing the changed edge remain
     753    /// valid. However <tt>InEdge</tt>'s are invalidated.
     754    void changeTarget(UEdge e, Node n) {
     755      Parent::changeTarget(e,n);
     756    }
     757    /// Changes the source of \c e to \c n
     758    ///
     759    /// Changes the source of \c e to \c n
     760    ///
     761    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
     762    ///referencing the changed edge remain
     763    ///valid. However <tt>OutEdge</tt>'s are invalidated.
     764    void changeSource(UEdge e, Node n) {
     765      Parent::changeSource(e,n);
     766    }
     767    /// \brief Contract two nodes.
     768    ///
     769    /// This function contracts two nodes.
     770    ///
     771    /// Node \p b will be removed but instead of deleting
     772    /// its neighboring edges, they will be joined to \p a.
     773    /// The last parameter \p r controls whether to remove loops. \c true
     774    /// means that loops will be removed.
     775    ///
     776    /// \note The <tt>Edge</tt>s
     777    /// referencing a moved edge remain
     778    /// valid.
     779    void contract(Node a, Node b, bool r = true) {
     780      for(IncEdgeIt e(*this, b); e!=INVALID;) {
     781        IncEdgeIt f = e; ++f;
     782        if (r && runningNode(e) == a) {
     783          erase(e);
     784        } else if (source(e) == b) {
     785          changeSource(e, a);
     786        } else {
     787          changeTarget(e, a);
     788        }
     789        e = f;
     790      }
     791      erase(b);
     792    }
     793  };
     794
     795
     796  class ListBpUGraphBase {
     797  public:
     798
     799    class NodeSetError : public LogicError {
     800      virtual const char* exceptionName() const {
     801        return "lemon::ListBpUGraph::NodeSetError";
     802      }
     803    };
     804
     805  protected:
     806
     807    struct NodeT {
     808      int first_edge, prev, next;
     809    };
     810
     811    struct UEdgeT {
     812      int aNode, prev_out, next_out;
     813      int bNode, prev_in, next_in;
     814    };
     815
     816    std::vector<NodeT> aNodes;
     817    std::vector<NodeT> bNodes;
     818
     819    std::vector<UEdgeT> edges;
     820
     821    int first_anode;
     822    int first_free_anode;
     823
     824    int first_bnode;
     825    int first_free_bnode;
     826
     827    int first_free_edge;
     828
     829  public:
     830 
     831    class Node {
     832      friend class ListBpUGraphBase;
     833    protected:
     834      int id;
     835
     836      explicit Node(int _id) : id(_id) {}
     837    public:
     838      Node() {}
     839      Node(Invalid) { id = -1; }
     840      bool operator==(const Node i) const {return id==i.id;}
     841      bool operator!=(const Node i) const {return id!=i.id;}
     842      bool operator<(const Node i) const {return id<i.id;}
     843    };
     844
     845    class UEdge {
     846      friend class ListBpUGraphBase;
     847    protected:
     848      int id;
     849
     850      explicit UEdge(int _id) { id = _id;}
     851    public:
     852      UEdge() {}
     853      UEdge (Invalid) { id = -1; }
     854      bool operator==(const UEdge i) const {return id==i.id;}
     855      bool operator!=(const UEdge i) const {return id!=i.id;}
     856      bool operator<(const UEdge i) const {return id<i.id;}
     857    };
     858
     859    ListBpUGraphBase()
     860      : first_anode(-1), first_free_anode(-1),
     861        first_bnode(-1), first_free_bnode(-1),
     862        first_free_edge(-1) {}
     863
     864    void firstANode(Node& node) const {
     865      node.id = first_anode != -1 ? (first_anode << 1) : -1;
     866    }
     867    void nextANode(Node& node) const {
     868      node.id = aNodes[node.id >> 1].next;
     869    }
     870
     871    void firstBNode(Node& node) const {
     872      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
     873    }
     874    void nextBNode(Node& node) const {
     875      node.id = bNodes[node.id >> 1].next;
     876    }
     877
     878    void first(Node& node) const {
     879      if (first_anode != -1) {
     880        node.id = (first_anode << 1);
     881      } else if (first_bnode != -1) {
     882        node.id = (first_bnode << 1) + 1;
     883      } else {
     884        node.id = -1;
     885      }
     886    }
     887    void next(Node& node) const {
     888      if (aNode(node)) {
     889        node.id = aNodes[node.id >> 1].next;
     890        if (node.id == -1) {
     891          if (first_bnode != -1) {
     892            node.id = (first_bnode << 1) + 1;
     893          }
     894        }
     895      } else {
     896        node.id = bNodes[node.id >> 1].next;
     897      }
     898    }
     899 
     900    void first(UEdge& edge) const {
     901      int aNodeId = first_anode;
     902      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
     903        aNodeId = aNodes[aNodeId].next != -1 ?
     904          aNodes[aNodeId].next >> 1 : -1;
     905      }
     906      if (aNodeId != -1) {
     907        edge.id = aNodes[aNodeId].first_edge;
     908      } else {
     909        edge.id = -1;
     910      }
     911    }
     912    void next(UEdge& edge) const {
     913      int aNodeId = edges[edge.id].aNode >> 1;
     914      edge.id = edges[edge.id].next_out;
     915      if (edge.id == -1) {
     916        aNodeId = aNodes[aNodeId].next != -1 ?
     917          aNodes[aNodeId].next >> 1 : -1;
     918        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
     919          aNodeId = aNodes[aNodeId].next != -1 ?
     920          aNodes[aNodeId].next >> 1 : -1;
     921        }
     922        if (aNodeId != -1) {
     923          edge.id = aNodes[aNodeId].first_edge;
     924        } else {
     925          edge.id = -1;
     926        }
     927      }
     928    }
     929
     930    void firstFromANode(UEdge& edge, const Node& node) const {
     931      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     932      edge.id = aNodes[node.id >> 1].first_edge;
     933    }
     934    void nextFromANode(UEdge& edge) const {
     935      edge.id = edges[edge.id].next_out;
     936    }
     937
     938    void firstFromBNode(UEdge& edge, const Node& node) const {
     939      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     940      edge.id = bNodes[node.id >> 1].first_edge;
     941    }
     942    void nextFromBNode(UEdge& edge) const {
     943      edge.id = edges[edge.id].next_in;
     944    }
     945
     946    static int id(const Node& node) {
     947      return node.id;
     948    }
     949    static Node nodeFromId(int id) {
     950      return Node(id);
     951    }
     952    int maxNodeId() const {
     953      return aNodes.size() > bNodes.size() ?
     954        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
     955    }
     956 
     957    static int id(const UEdge& edge) {
     958      return edge.id;
     959    }
     960    static UEdge uEdgeFromId(int id) {
     961      return UEdge(id);
     962    }
     963    int maxUEdgeId() const {
     964      return edges.size();
     965    }
     966 
     967    static int aNodeId(const Node& node) {
     968      return node.id >> 1;
     969    }
     970    static Node fromANodeId(int id) {
     971      return Node(id << 1);
     972    }
     973    int maxANodeId() const {
     974      return aNodes.size();
     975    }
     976
     977    static int bNodeId(const Node& node) {
     978      return node.id >> 1;
     979    }
     980    static Node fromBNodeId(int id) {
     981      return Node((id << 1) + 1);
     982    }
     983    int maxBNodeId() const {
     984      return bNodes.size();
     985    }
     986
     987    Node aNode(const UEdge& edge) const {
     988      return Node(edges[edge.id].aNode);
     989    }
     990    Node bNode(const UEdge& edge) const {
     991      return Node(edges[edge.id].bNode);
     992    }
     993
     994    static bool aNode(const Node& node) {
     995      return (node.id & 1) == 0;
     996    }
     997
     998    static bool bNode(const Node& node) {
     999      return (node.id & 1) == 1;
     1000    }
     1001
     1002    Node addANode() {
     1003      int aNodeId;
     1004      if (first_free_anode == -1) {
     1005        aNodeId = aNodes.size();
     1006        aNodes.push_back(NodeT());
     1007      } else {
     1008        aNodeId = first_free_anode;
     1009        first_free_anode = aNodes[first_free_anode].next;
     1010      }
     1011      if (first_anode != -1) {
     1012        aNodes[aNodeId].next = first_anode << 1;
     1013        aNodes[first_anode].prev = aNodeId << 1;
     1014      } else {
     1015        aNodes[aNodeId].next = -1;
     1016      }
     1017      aNodes[aNodeId].prev = -1;
     1018      first_anode = aNodeId;
     1019      aNodes[aNodeId].first_edge = -1;
     1020      return Node(aNodeId << 1);
     1021    }
     1022
     1023    Node addBNode() {
     1024      int bNodeId;
     1025      if (first_free_bnode == -1) {
     1026        bNodeId = bNodes.size();
     1027        bNodes.push_back(NodeT());
     1028      } else {
     1029        bNodeId = first_free_bnode;
     1030        first_free_bnode = bNodes[first_free_bnode].next;
     1031      }
     1032      if (first_bnode != -1) {
     1033        bNodes[bNodeId].next = (first_bnode << 1) + 1;
     1034        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
     1035      } else {
     1036        bNodes[bNodeId].next = -1;
     1037      }
     1038      first_bnode = bNodeId;
     1039      bNodes[bNodeId].first_edge = -1;
     1040      return Node((bNodeId << 1) + 1);
     1041    }
     1042
     1043    UEdge addEdge(const Node& source, const Node& target) {
     1044      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
     1045      int edgeId;
     1046      if (first_free_edge != -1) {
     1047        edgeId = first_free_edge;
     1048        first_free_edge = edges[edgeId].next_out;
     1049      } else {
     1050        edgeId = edges.size();
     1051        edges.push_back(UEdgeT());
     1052      }
     1053      if ((source.id & 1) == 0) {
     1054        edges[edgeId].aNode = source.id;
     1055        edges[edgeId].bNode = target.id;
     1056      } else {
     1057        edges[edgeId].aNode = target.id;
     1058        edges[edgeId].bNode = source.id;
     1059      }
     1060      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
     1061      edges[edgeId].prev_out = -1;
     1062      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
     1063        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
     1064      }
     1065      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
     1066      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
     1067      edges[edgeId].prev_in = -1;
     1068      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
     1069        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
     1070      }
     1071      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
     1072      return UEdge(edgeId);
     1073    }
     1074
     1075    void erase(const Node& node) {
     1076      if (aNode(node)) {
     1077        int aNodeId = node.id >> 1;
     1078        if (aNodes[aNodeId].prev != -1) {
     1079          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
     1080        } else {
     1081          first_anode = aNodes[aNodeId].next >> 1;
     1082        }
     1083        if (aNodes[aNodeId].next != -1) {
     1084          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
     1085        }
     1086        aNodes[aNodeId].next = first_free_anode;
     1087        first_free_anode = aNodeId;
     1088      } else {
     1089        int bNodeId = node.id >> 1;
     1090        if (bNodes[bNodeId].prev != -1) {
     1091          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
     1092        } else {
     1093          first_bnode = bNodes[bNodeId].next >> 1;
     1094        }
     1095        if (bNodes[bNodeId].next != -1) {
     1096          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
     1097        }
     1098        bNodes[bNodeId].next = first_free_bnode;
     1099        first_free_bnode = bNodeId;
     1100      }
     1101    }
     1102
     1103    void erase(const UEdge& edge) {
     1104
     1105      if (edges[edge.id].prev_out != -1) {
     1106        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
     1107      } else {
     1108        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
     1109      }
     1110      if (edges[edge.id].next_out != -1) {
     1111        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
     1112      }
     1113
     1114      if (edges[edge.id].prev_in != -1) {
     1115        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
     1116      } else {
     1117        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
     1118      }
     1119      if (edges[edge.id].next_in != -1) {
     1120        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
     1121      }
     1122
     1123      edges[edge.id].next_out = first_free_edge;
     1124      first_free_edge = edge.id;
     1125    }
     1126
     1127    void clear() {
     1128      aNodes.clear();
     1129      bNodes.clear();
     1130      edges.clear();
     1131      first_anode = -1;
     1132      first_free_anode = -1;
     1133      first_bnode = -1;
     1134      first_free_bnode = -1;
     1135      first_free_edge = -1;
     1136    }
     1137
     1138  };
     1139
     1140
     1141  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
     1142
     1143  /// \ingroup graphs
     1144  ///
     1145  /// \brief A smart bipartite undirected graph class.
     1146  ///
     1147  /// This is a bipartite undirected graph implementation.
     1148  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
     1149  /// concept.
     1150  /// \sa concept::BpUGraph.
     1151  ///
     1152  class ListBpUGraph : public ExtendedListBpUGraphBase {};
     1153
     1154 
     1155  /// @} 
    7041156} //namespace lemon
    7051157 
Note: See TracChangeset for help on using the changeset viewer.