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
|
/**
** \file misc/graph.hh
** \brief Undirected/oriented graph definition.
*/
#pragma once
#include <iosfwd>
#include <set>
#include <string>
#include <vector>
#include <boost/functional/hash.hpp> // Required by boost/graph/detail/edge.hpp.
/* Forward declarations to help the compiler not to mix up the
namespace `target' with `boost::target'. This happens in the
instantiation of graph concepts in boost/graph/graph_concepts.hpp
if this forward declaration is omitted. */
#include <boost/graph/detail/edge.hpp>
namespace boost
{
template <class OutEdgeListS,
class VertexListS,
class DirectedS,
class VertexProperty,
class EdgeProperty,
class GraphProperty,
class EdgeListS>
class adjacency_list;
template <class Directed,
class Vertex,
class OutEdgeListS,
class VertexListS,
class DirectedS,
class VertexProperty,
class EdgeProperty,
class GraphProperty,
class EdgeListS>
inline Vertex target(const detail::edge_base<Directed, Vertex>& e,
const adjacency_list<OutEdgeListS,
VertexListS,
DirectedS,
VertexProperty,
EdgeProperty,
GraphProperty,
EdgeListS>&);
} // namespace boost
#include <boost/graph/adjacency_list.hpp>
#include <misc/set.hh>
/// Handling of generic, oriented or undirected, graph.
namespace misc
{
/*--------.
| Graph. |
`--------*/
/// Graph property: name.
using name_prop_type = boost::property<boost::graph_name_t, std::string>;
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
class graph
: public boost::adjacency_list<boost::setS,
boost::vecS,
Orientation,
VertexLabel,
EdgeLabel,
name_prop_type>
{
public:
virtual ~graph() = default;
public:
using self_type = graph<Orientation, VertexLabel, EdgeLabel>;
using super_type = boost::adjacency_list<boost::setS,
boost::vecS,
Orientation,
VertexLabel,
EdgeLabel,
name_prop_type>;
using vertex_descriptor = typename super_type::vertex_descriptor;
/// Iterators.
public:
/// \{
/// Iterator on the vertices of a graph.
using vertex_iter_type =
typename boost::graph_traits<self_type>::vertex_iterator;
/// Iterator on the edges of a graph.
using edge_iter_type =
typename boost::graph_traits<self_type>::edge_iterator;
/// \}
/// Graph manipulation.
/// \{
public:
/// \brief Add a vertex to the graph.
///
/// Just a wrapper around boost::add_vertex.
vertex_descriptor vertex_add(const VertexLabel& l);
/// Add an edge between two vertices.
virtual void edge_add(const vertex_descriptor& v1,
const vertex_descriptor& v2) = 0;
/// \}
/// Graph pretty printing.
/// \{
public:
virtual std::ostream& print(std::ostream& ostr) const;
virtual std::ostream& epilogue_print(std::ostream& ostr) const;
virtual void print(std::string file) const;
private:
/// Print the label of vertex of a graph.
virtual std::ostream& vertex_print(vertex_descriptor v,
std::ostream& ostr) const = 0;
/// \}
/// Graph name.
/// \{
public:
const std::string& name_get() const;
void name_set(const std::string& name);
/// \}
};
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
std::ostream& operator<<(std::ostream& ostr,
const graph<Orientation, VertexLabel, EdgeLabel>& g);
// An helper class when we do not want any data attached to vertex
// or an edge.
struct empty
{};
inline std::ostream& operator<<(std::ostream& ostr, empty);
/*----------------------------------------------------.
| Specialization for directed (bidirectional) graph. |
`----------------------------------------------------*/
/* Note that boost::bidirectionalS is like boost::directedS, except
that it provides access to both in-edges and out-edges, whereas
boost::directedS gives us only out-edges. The consequence is
that a bidirectional graph is twice as large as its directed
version. */
template <typename VertexLabel = empty, typename EdgeLabel = empty>
class directed_graph
: public graph<boost::bidirectionalS, VertexLabel, EdgeLabel>
{
public:
using self_type = directed_graph<VertexLabel, EdgeLabel>;
using super_type = graph<boost::bidirectionalS, VertexLabel, EdgeLabel>;
using vertex_descriptor = typename super_type::vertex_descriptor;
public:
/// Iterator on the vertices of a directed_graph.
using vertex_iter_type =
typename boost::graph_traits<self_type>::vertex_iterator;
/// Iterator on the neighbors of the vertex of a directed_graph.
using neighb_iter_type =
typename boost::graph_traits<self_type>::adjacency_iterator;
/// Iterators.
/// \{
public:
/// \brief Add an edge between two vertices.
///
/// This is just a wrapper around boost::add_edge.
void edge_add(const vertex_descriptor& v1,
const vertex_descriptor& v2) override;
/// \}
/// \brief Topological sort.
///
/// This version (algorithm 17.5 in Modern Compiler Implementation
/// in ML, p. 390) is not the same as boost::topological_sort since
/// the former works on directed acyclic graphs (DAGs) and the latter
/// doesn't.
///
/// \{
public:
std::vector<vertex_descriptor> topological_sort() const;
/// \}
};
/*--------------------------------------.
| Specialization for undirected graph. |
`--------------------------------------*/
template <typename VertexLabel = empty, typename EdgeLabel = empty>
class undirected_graph
: public graph<boost::undirectedS, VertexLabel, EdgeLabel>
{
public:
using super_type = graph<boost::undirectedS, VertexLabel, EdgeLabel>;
using vertex_descriptor = typename super_type::vertex_descriptor;
public:
/// \brief Add an edge between two vertices.
///
/// Use this method instead of boost::add_edge directly to keep
/// the order between the ends of an edge.
void edge_add(const vertex_descriptor& v1,
const vertex_descriptor& v2) override;
};
} // namespace misc
#include <misc/graph.hxx>
|
