COIN-OR::LEMON - Graph Library

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

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 18 years ago

Splitted graph files

File size: 6.5 KB
Line 
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_SMART_BPUGRAPH_H
20#define LEMON_SMART_BPUGRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief SmartBpUGraph class.
25
26#include <vector>
27
28#include <lemon/bits/invalid.h>
29
30#include <lemon/bits/bpugraph_extender.h>
31
32#include <lemon/bits/utility.h>
33#include <lemon/error.h>
34
35#include <lemon/bits/graph_extender.h>
36
37namespace lemon {
38
39  class SmartBpUGraphBase {
40  public:
41
42    class NodeSetError : public LogicError {
43      virtual const char* exceptionName() const {
44        return "lemon::SmartBpUGraph::NodeSetError";
45      }
46    };
47
48  protected:
49
50    struct NodeT {
51      int first;
52      NodeT() {}
53      NodeT(int _first) : first(_first) {}
54    };
55
56    struct UEdgeT {
57      int aNode, next_out;
58      int bNode, next_in;
59    };
60
61    std::vector<NodeT> aNodes;
62    std::vector<NodeT> bNodes;
63
64    std::vector<UEdgeT> edges;
65
66  public:
67 
68    class Node {
69      friend class SmartBpUGraphBase;
70    protected:
71      int id;
72
73      Node(int _id) : id(_id) {}
74    public:
75      Node() {}
76      Node(Invalid) { id = -1; }
77      bool operator==(const Node i) const {return id==i.id;}
78      bool operator!=(const Node i) const {return id!=i.id;}
79      bool operator<(const Node i) const {return id<i.id;}
80    };
81
82    class UEdge {
83      friend class SmartBpUGraphBase;
84    protected:
85      int id;
86
87      UEdge(int _id) { id = _id;}
88    public:
89      UEdge() {}
90      UEdge (Invalid) { id = -1; }
91      bool operator==(const UEdge i) const {return id==i.id;}
92      bool operator!=(const UEdge i) const {return id!=i.id;}
93      bool operator<(const UEdge i) const {return id<i.id;}
94    };
95
96    void firstANode(Node& node) const {
97      node.id = 2 * aNodes.size() - 2;
98      if (node.id < 0) node.id = -1;
99    }
100    void nextANode(Node& node) const {
101      node.id -= 2;
102      if (node.id < 0) node.id = -1;
103    }
104
105    void firstBNode(Node& node) const {
106      node.id = 2 * bNodes.size() - 1;
107    }
108    void nextBNode(Node& node) const {
109      node.id -= 2;
110    }
111
112    void first(Node& node) const {
113      if (aNodes.size() > 0) {
114        node.id = 2 * aNodes.size() - 2;
115      } else {
116        node.id = 2 * bNodes.size() - 1;
117      }
118    }
119    void next(Node& node) const {
120      node.id -= 2;
121      if (node.id == -2) {
122        node.id = 2 * bNodes.size() - 1;
123      }
124    }
125 
126    void first(UEdge& edge) const {
127      edge.id = edges.size() - 1;
128    }
129    void next(UEdge& edge) const {
130      --edge.id;
131    }
132
133    void firstFromANode(UEdge& edge, const Node& node) const {
134      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
135      edge.id = aNodes[node.id >> 1].first;
136    }
137    void nextFromANode(UEdge& edge) const {
138      edge.id = edges[edge.id].next_out;
139    }
140
141    void firstFromBNode(UEdge& edge, const Node& node) const {
142      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
143      edge.id = bNodes[node.id >> 1].first;
144    }
145    void nextFromBNode(UEdge& edge) const {
146      edge.id = edges[edge.id].next_in;
147    }
148
149    static int id(const Node& node) {
150      return node.id;
151    }
152    static Node nodeFromId(int id) {
153      return Node(id);
154    }
155    int maxNodeId() const {
156      return aNodes.size() > bNodes.size() ?
157        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
158    }
159 
160    static int id(const UEdge& edge) {
161      return edge.id;
162    }
163    static UEdge uEdgeFromId(int id) {
164      return UEdge(id);
165    }
166    int maxUEdgeId() const {
167      return edges.size();
168    }
169 
170    static int aNodeId(const Node& node) {
171      return node.id >> 1;
172    }
173    static Node fromANodeId(int id) {
174      return Node(id << 1);
175    }
176    int maxANodeId() const {
177      return aNodes.size();
178    }
179
180    static int bNodeId(const Node& node) {
181      return node.id >> 1;
182    }
183    static Node fromBNodeId(int id) {
184      return Node((id << 1) + 1);
185    }
186    int maxBNodeId() const {
187      return bNodes.size();
188    }
189
190    Node aNode(const UEdge& edge) const {
191      return Node(edges[edge.id].aNode);
192    }
193    Node bNode(const UEdge& edge) const {
194      return Node(edges[edge.id].bNode);
195    }
196
197    static bool aNode(const Node& node) {
198      return (node.id & 1) == 0;
199    }
200
201    static bool bNode(const Node& node) {
202      return (node.id & 1) == 1;
203    }
204
205    Node addANode() {
206      NodeT nodeT;
207      nodeT.first = -1;
208      aNodes.push_back(nodeT);
209      return Node(aNodes.size() * 2 - 2);
210    }
211
212    Node addBNode() {
213      NodeT nodeT;
214      nodeT.first = -1;
215      bNodes.push_back(nodeT);
216      return Node(bNodes.size() * 2 - 1);
217    }
218
219    UEdge addEdge(const Node& source, const Node& target) {
220      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
221      UEdgeT edgeT;
222      if ((source.id & 1) == 0) {
223        edgeT.aNode = source.id;
224        edgeT.bNode = target.id;
225      } else {
226        edgeT.aNode = target.id;
227        edgeT.bNode = source.id;
228      }
229      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
230      aNodes[edgeT.aNode >> 1].first = edges.size();
231      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
232      bNodes[edgeT.bNode >> 1].first = edges.size();
233      edges.push_back(edgeT);
234      return UEdge(edges.size() - 1);
235    }
236
237    void clear() {
238      aNodes.clear();
239      bNodes.clear();
240      edges.clear();
241    }
242
243    typedef True NodeNumTag;
244    int nodeNum() const { return aNodes.size() + bNodes.size(); }
245    int aNodeNum() const { return aNodes.size(); }
246    int bNodeNum() const { return bNodes.size(); }
247
248    typedef True EdgeNumTag;
249    int uEdgeNum() const { return edges.size(); }
250
251  };
252
253
254  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
255
256  /// \ingroup graphs
257  ///
258  /// \brief A smart bipartite undirected graph class.
259  ///
260  /// This is a simple and fast bipartite undirected graph implementation.
261  /// It is also quite memory efficient, but at the price
262  /// that <b> it does not support node and edge deletions</b>.
263  /// Except from this it conforms to
264  /// the \ref concept::BpUGraph "BpUGraph" concept.
265  /// \sa concept::BpUGraph.
266  ///
267  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
268
269 
270} //namespace lemon
271
272
273#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.