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
|
/**
** \file misc/graph.hxx
** \brief Undirected/oriented graph implementation.
*/
#pragma once
#include <algorithm>
#include <fstream>
#include <sstream>
#include <tuple>
#include <misc/algorithm.hh>
#include <misc/contract.hh>
#include <misc/deref.hh>
namespace misc
{
/*--------.
| Graph. |
`--------*/
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
typename graph<Orientation, VertexLabel, EdgeLabel>::vertex_descriptor
graph<Orientation, VertexLabel, EdgeLabel>::vertex_add(const VertexLabel& l)
{
return boost::add_vertex(l, *this);
}
/*-----------------------------------------------------------------.
| graph::print. |
| |
| For oriented graph, keeping edges bound to the source node looks |
| nicer, while an edge oriented dump is more appropriate for |
| unoriented graphs. In the latter case, be sure not to output |
| each edge twice. |
| |
| FIXME: We do lack something similar to Escape when "deref"ing, |
| for if there are strings in there, they should be escaped for |
| dotty. |
| |
| FIXME: Enforce the order by sorting before outputting. |
`-----------------------------------------------------------------*/
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
std::ostream&
graph<Orientation, VertexLabel, EdgeLabel>::print(std::ostream& ostr) const
{
using misc::deref;
std::string graphtype = boost::is_undirected(*this) ? "graph" : "digraph";
std::string link = boost::is_undirected(*this) ? "--" : "->";
ostr << "/* Graph Visualization */\n";
ostr << graphtype << " \"" << name_get() << "\" {\n"
<< " node [shape=box];\n";
for (auto [vi, vi_end] = boost::vertices(*this); vi != vi_end; ++vi)
{
ostr << " \"" << *vi << "\" "
<< "[label=\"";
vertex_print(*vi, ostr);
ostr << "\"]\n";
}
for (auto [ei, ei_end] = boost::edges(*this); ei != ei_end; ++ei)
{
std::ostringstream label;
label << deref << (*this)[*ei];
ostr << " \"" << boost::source(*ei, *this) << "\" " << link << " \""
<< boost::target(*ei, *this) << "\"";
if (label.str() != "")
ostr << " [label=\"" << label.str() << "\"]";
ostr << '\n';
}
epilogue_print(ostr);
return ostr << "}\n";
}
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
std::ostream& graph<Orientation, VertexLabel, EdgeLabel>::epilogue_print(
std::ostream& ostr) const
{
return ostr;
}
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
void graph<Orientation, VertexLabel, EdgeLabel>::print(std::string file) const
{
std::ofstream ofs;
static unsigned cpt = 0;
if (file.empty())
{
std::stringstream sstr;
sstr << "graph-" << cpt << ".gv";
++cpt;
file = sstr.str();
}
file += ".gv";
ofs.open(file.c_str());
print(ofs);
ofs.close();
}
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
const std::string&
graph<Orientation, VertexLabel, EdgeLabel>::name_get() const
{
// For some reason, the following cast is needed with Boost 1.45.
return boost::get_property(static_cast<const super_type&>(*this),
boost::graph_name);
}
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
void
graph<Orientation, VertexLabel, EdgeLabel>::name_set(const std::string& name)
{
boost::set_property(*this, boost::graph_name, name);
}
template <typename Orientation, typename VertexLabel, typename EdgeLabel>
inline std::ostream&
operator<<(std::ostream& ostr,
const graph<Orientation, VertexLabel, EdgeLabel>& g)
{
return g.print(ostr);
}
inline std::ostream& operator<<(std::ostream& ostr, empty) { return ostr; }
/*----------------.
| DirectedGraph. |
`----------------*/
template <typename VertexLabel, typename EdgeLabel>
void
directed_graph<VertexLabel, EdgeLabel>::edge_add(const vertex_descriptor& v1,
const vertex_descriptor& v2)
{
boost::add_edge(v1, v2, *this);
}
template <typename NodeLabel, typename EdgeLabel>
std::vector<typename directed_graph<NodeLabel, EdgeLabel>::vertex_descriptor>
directed_graph<NodeLabel, EdgeLabel>::topological_sort() const
{
std::vector<vertex_descriptor> res;
misc::set<vertex_descriptor> visited;
return res;
}
/*------------------.
| UndirectedGraph. |
`------------------*/
template <typename VertexLabel, typename EdgeLabel>
void undirected_graph<VertexLabel, EdgeLabel>::edge_add(
const vertex_descriptor& v1,
const vertex_descriptor& v2)
{
if (v1 > v2)
boost::add_edge(v2, v1, *this);
else
boost::add_edge(v1, v2, *this);
}
} // namespace misc
|
