1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
/* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file has been adapted by Nicolas Bonneel (2013),
* from full_graph.h from LEMON, a generic C++ optimization library,
* to implement a lightweight fully connected bipartite graph. A previous
* version of this file is used as part of the Displacement Interpolation
* project,
* Web: http://www.cs.ubc.ca/labs/imager/tr/2011/DisplacementInterpolation/
*
*
**** Original file Copyright Notice :
* Copyright (C) 2003-2010
* 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_FULL_BIPARTITE_GRAPH_H
#define LEMON_FULL_BIPARTITE_GRAPH_H
#include "core.h"
///\ingroup graphs
///\file
///\brief FullBipartiteDigraph and FullBipartiteGraph classes.
namespace lemon {
class FullBipartiteDigraphBase {
public:
typedef FullBipartiteDigraphBase Digraph;
//class Node;
typedef int Node;
//class Arc;
typedef long long Arc;
protected:
int _node_num;
long long _arc_num;
FullBipartiteDigraphBase() {}
void construct(int n1, int n2) { _node_num = n1+n2; _arc_num = n1 * n2; _n1=n1; _n2=n2;}
public:
int _n1, _n2;
Node operator()(int ix) const { return Node(ix); }
static int index(const Node& node) { return node; }
Arc arc(const Node& s, const Node& t) const {
if (s<_n1 && t>=_n1)
return Arc(s * _n2 + (t-_n1) );
else
return Arc(-1);
}
int nodeNum() const { return _node_num; }
long long arcNum() const { return _arc_num; }
int maxNodeId() const { return _node_num - 1; }
long long maxArcId() const { return _arc_num - 1; }
Node source(Arc arc) const { return arc / _n2; }
Node target(Arc arc) const { return (arc % _n2) + _n1; }
static int id(Node node) { return node; }
static long long id(Arc arc) { return arc; }
static Node nodeFromId(int id) { return Node(id);}
static Arc arcFromId(int id) { return Arc(id);}
Arc findArc(Node s, Node t, Arc prev = -1) const {
return prev == -1 ? arc(s, t) : -1;
}
void first(Node& node) const {
node = _node_num - 1;
}
static void next(Node& node) {
--node;
}
void first(Arc& arc) const {
arc = _arc_num - 1;
}
static void next(Arc& arc) {
--arc;
}
void firstOut(Arc& arc, const Node& node) const {
if (node>=_n1)
arc = -1;
else
arc = (node + 1) * _n2 - 1;
}
void nextOut(Arc& arc) const {
if (arc % _n2 == 0) arc = 0;
--arc;
}
void firstIn(Arc& arc, const Node& node) const {
if (node<_n1)
arc = -1;
else
arc = _arc_num + node - _node_num;
}
void nextIn(Arc& arc) const {
arc -= _n2;
if (arc < 0) arc = -1;
}
};
/// \ingroup graphs
///
/// \brief A directed full graph class.
///
/// FullBipartiteDigraph is a simple and fast implmenetation of directed full
/// (complete) graphs. It contains an arc from each node to each node
/// (including a loop for each node), therefore the number of arcs
/// is the square of the number of nodes.
/// This class is completely static and it needs constant memory space.
/// Thus you can neither add nor delete nodes or arcs, however
/// the structure can be resized using resize().
///
/// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
/// Most of its member functions and nested classes are documented
/// only in the concept class.
///
/// This class provides constant time counting for nodes and arcs.
///
/// \note FullBipartiteDigraph and FullBipartiteGraph classes are very similar,
/// but there are two differences. While this class conforms only
/// to the \ref concepts::Digraph "Digraph" concept, FullBipartiteGraph
/// conforms to the \ref concepts::Graph "Graph" concept,
/// moreover FullBipartiteGraph does not contain a loop for each
/// node as this class does.
///
/// \sa FullBipartiteGraph
class FullBipartiteDigraph : public FullBipartiteDigraphBase {
typedef FullBipartiteDigraphBase Parent;
public:
/// \brief Default constructor.
///
/// Default constructor. The number of nodes and arcs will be zero.
FullBipartiteDigraph() { construct(0,0); }
/// \brief Constructor
///
/// Constructor.
/// \param n The number of the nodes.
FullBipartiteDigraph(int n1, int n2) { construct(n1, n2); }
/// \brief Returns the node with the given index.
///
/// Returns the node with the given index. Since this structure is
/// completely static, the nodes can be indexed with integers from
/// the range <tt>[0..nodeNum()-1]</tt>.
/// The index of a node is the same as its ID.
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
/// \brief Returns the index of the given node.
///
/// Returns the index of the given node. Since this structure is
/// completely static, the nodes can be indexed with integers from
/// the range <tt>[0..nodeNum()-1]</tt>.
/// The index of a node is the same as its ID.
/// \sa operator()()
static int index(const Node& node) { return Parent::index(node); }
/// \brief Returns the arc connecting the given nodes.
///
/// Returns the arc connecting the given nodes.
/*Arc arc(Node u, Node v) const {
return Parent::arc(u, v);
}*/
/// \brief Number of nodes.
int nodeNum() const { return Parent::nodeNum(); }
/// \brief Number of arcs.
long long arcNum() const { return Parent::arcNum(); }
};
} //namespace lemon
#endif //LEMON_FULL_GRAPH_H
|
