1 //=======================================================================
2 // Copyright 2001 Universite Joseph Fourier, Grenoble.
3 // Author: Francois Faure
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 #ifndef BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
10 #define BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
11
12 #include <iostream>
13 #include <vector>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/iteration_macros.hpp>
16 #include <cctype>
17
18 // Method read to parse an adjacency list from an input stream. Examples:
19 // cin >> read( G );
20 // cin >> read( G, NodePropertySubset(), EdgepropertySubset() );
21 //
22 // Method write to print an adjacency list to an output stream. Examples:
23 // cout << write( G );
24 // cout << write( G, NodePropertySubset(), EdgepropertySubset() );
25
26 namespace boost
27 {
28
29 /* outline
30 - basic property input
31 - get property subset
32 - graph parser
33 - property printer
34 - graph printer
35 - user methods
36 */
37
38 //===========================================================================
39 // basic property input
40
41 template < class Tag, class Value, class Next >
operator >>(std::istream & in,property<Tag,Value,Next> & p)42 std::istream& operator>>(std::istream& in, property< Tag, Value, Next >& p)
43 {
44 in >> p.m_value >> p.m_base; // houpla !!
45 return in;
46 }
47
48 template < class Tag, class Value >
operator >>(std::istream & in,property<Tag,Value,no_property> & p)49 std::istream& operator>>(
50 std::istream& in, property< Tag, Value, no_property >& p)
51 {
52 in >> p.m_value;
53 return in;
54 }
55
operator >>(std::istream & in,no_property &)56 inline std::istream& operator>>(std::istream& in, no_property&) { return in; }
57
58 // basic property input
59 //===========================================================================
60 // get property subsets
61
62 // get a single property tagged Stag
63 template < class Tag, class Value, class Next, class V, class Stag >
get(property<Tag,Value,Next> & p,const V & v,Stag s)64 void get(property< Tag, Value, Next >& p, const V& v, Stag s)
65 {
66 get(p.m_base, v, s);
67 }
68
69 template < class Value, class Next, class V, class Stag >
get(property<Stag,Value,Next> & p,const V & v,Stag)70 void get(property< Stag, Value, Next >& p, const V& v, Stag)
71 {
72 p.m_value = v;
73 }
74
75 // get a subset of properties tagged Stag
76 template < class Tag, class Value, class Next, class Stag, class Svalue,
77 class Snext >
getSubset(property<Tag,Value,Next> & p,const property<Stag,Svalue,Snext> & s)78 void getSubset(
79 property< Tag, Value, Next >& p, const property< Stag, Svalue, Snext >& s)
80 {
81 get(p, s.m_value, Stag());
82 getSubset(p, s.m_base);
83 }
84
85 template < class Tag, class Value, class Next, class Stag, class Svalue >
getSubset(property<Tag,Value,Next> & p,const property<Stag,Svalue,no_property> & s)86 void getSubset(property< Tag, Value, Next >& p,
87 const property< Stag, Svalue, no_property >& s)
88 {
89 get(p, s.m_value, Stag());
90 }
91
getSubset(no_property &,const no_property &)92 inline void getSubset(no_property&, const no_property&) {}
93
94 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
getSubset(T & p,const U & s)95 template < typename T, typename U > void getSubset(T& p, const U& s) { p = s; }
96
getSubset(T &,const no_property &)97 template < typename T > void getSubset(T&, const no_property&) {}
98
99 #endif
100
101 // get property subset
102 //===========================================================================
103 // graph parser
104 typedef enum
105 {
106 PARSE_NUM_NODES,
107 PARSE_VERTEX,
108 PARSE_EDGE
109 } GraphParserState;
110
111 template < class Graph_t, class VertexProperty, class EdgeProperty,
112 class VertexPropertySubset, class EdgePropertySubset >
113 struct GraphParser
114 {
115
116 typedef Graph_t Graph;
117
GraphParserboost::GraphParser118 GraphParser(Graph* g) : graph(g) {}
119
operator ()boost::GraphParser120 GraphParser& operator()(std::istream& in)
121 {
122 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
123 std::vector< Vertex > nodes;
124
125 GraphParserState state = PARSE_VERTEX;
126
127 unsigned int numLine = 1;
128 char c;
129 while (in.get(c))
130 {
131 if (c == '#')
132 skip(in);
133 else if (c == 'n')
134 state = PARSE_NUM_NODES;
135 else if (c == 'v')
136 state = PARSE_VERTEX;
137 else if (c == 'e')
138 state = PARSE_EDGE;
139 else if (c == '\n')
140 numLine++;
141 else if (!std::isspace(c))
142 {
143 in.putback(c);
144 if (state == PARSE_VERTEX)
145 {
146 VertexPropertySubset readProp;
147 if (in >> readProp)
148 {
149 VertexProperty vp;
150 getSubset(vp, readProp);
151 nodes.push_back(add_vertex(vp, *graph));
152 }
153 else
154 std::cerr << "read vertex, parse error at line"
155 << numLine << std::endl;
156 }
157 else if (state == PARSE_EDGE)
158 {
159 int source, target;
160 EdgePropertySubset readProp;
161 in >> source >> target;
162 if (in >> readProp)
163 {
164 EdgeProperty ep;
165 getSubset(ep, readProp);
166 add_edge(nodes[source], nodes[target], ep, *graph);
167 }
168 else
169 std::cerr << "read edge, parse error at line" << numLine
170 << std::endl;
171 }
172 else
173 { // state == PARSE_NUM_NODES
174 int n;
175 if (in >> n)
176 {
177 for (int i = 0; i < n; ++i)
178 nodes.push_back(add_vertex(*graph));
179 }
180 else
181 std::cerr << "read num_nodes, parse error at line "
182 << numLine << std::endl;
183 }
184 }
185 }
186 return (*this);
187 }
188
189 protected:
190 Graph* graph;
191
skipboost::GraphParser192 void skip(std::istream& in)
193 {
194 char c = 0;
195 while (c != '\n' && !in.eof())
196 in.get(c);
197 in.putback(c);
198 }
199 };
200
201 // parser
202 //=======================================================================
203 // property printer
204
205 #if defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
206 template < class Graph, class Property > struct PropertyPrinter
207 {
208 typedef typename Property::value_type Value;
209 typedef typename Property::tag_type Tag;
210 typedef typename Property::next_type Next;
211
PropertyPrinterboost::PropertyPrinter212 PropertyPrinter(const Graph& g) : graph(&g) {}
213
214 template < class Val >
operator ()boost::PropertyPrinter215 PropertyPrinter& operator()(std::ostream& out, const Val& v)
216 {
217 typename property_map< Graph, Tag >::const_type ps = get(Tag(), *graph);
218 out << ps[v] << " ";
219 PropertyPrinter< Graph, Next > print(*graph);
220 print(out, v);
221 return (*this);
222 }
223
224 private:
225 const Graph* graph;
226 };
227 #else
228 template < class Graph, typename Property > struct PropertyPrinter
229 {
PropertyPrinterboost::PropertyPrinter230 PropertyPrinter(const Graph& g) : graph(&g) {}
231
232 template < class Val >
operator ()boost::PropertyPrinter233 PropertyPrinter& operator()(std::ostream& out, const Val& v)
234 {
235 out << (*graph)[v] << " ";
236 return (*this);
237 }
238
239 private:
240 const Graph* graph;
241 };
242
243 template < class Graph, typename Tag, typename Value, typename Next >
244 struct PropertyPrinter< Graph, property< Tag, Value, Next > >
245 {
PropertyPrinterboost::PropertyPrinter246 PropertyPrinter(const Graph& g) : graph(&g) {}
247
248 template < class Val >
operator ()boost::PropertyPrinter249 PropertyPrinter& operator()(std::ostream& out, const Val& v)
250 {
251 typename property_map< Graph, Tag >::const_type ps = get(Tag(), *graph);
252 out << ps[v] << " ";
253 PropertyPrinter< Graph, Next > print(*graph);
254 print(out, v);
255 return (*this);
256 }
257
258 private:
259 const Graph* graph;
260 };
261 #endif
262
263 template < class Graph > struct PropertyPrinter< Graph, no_property >
264 {
PropertyPrinterboost::PropertyPrinter265 PropertyPrinter(const Graph&) {}
266
267 template < class Val >
operator ()boost::PropertyPrinter268 PropertyPrinter& operator()(std::ostream&, const Val&)
269 {
270 return *this;
271 }
272 };
273
274 // property printer
275 //=========================================================================
276 // graph printer
277
278 template < class Graph_t, class EdgeProperty > struct EdgePrinter
279 {
280
281 typedef Graph_t Graph;
282 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
283
EdgePrinterboost::EdgePrinter284 EdgePrinter(const Graph& g) : graph(g) {}
285
operator ()boost::EdgePrinter286 const EdgePrinter& operator()(std::ostream& out) const
287 {
288 // assign indices to vertices
289 std::map< Vertex, int > indices;
290 int num = 0;
291 BGL_FORALL_VERTICES_T(v, graph, Graph) { indices[v] = num++; }
292
293 // write edges
294 PropertyPrinter< Graph, EdgeProperty > print_Edge(graph);
295 out << "e" << std::endl;
296 BGL_FORALL_EDGES_T(e, graph, Graph)
297 {
298 out << indices[source(e, graph)] << " " << indices[target(e, graph)]
299 << " ";
300 print_Edge(out, e);
301 out << std::endl;
302 }
303 out << std::endl;
304 return (*this);
305 }
306
307 protected:
308 const Graph& graph;
309 };
310
311 template < class Graph, class V, class E >
312 struct GraphPrinter : public EdgePrinter< Graph, E >
313 {
GraphPrinterboost::GraphPrinter314 GraphPrinter(const Graph& g) : EdgePrinter< Graph, E >(g) {}
315
operator ()boost::GraphPrinter316 const GraphPrinter& operator()(std::ostream& out) const
317 {
318 PropertyPrinter< Graph, V > printNode(this->graph);
319 out << "v" << std::endl;
320 BGL_FORALL_VERTICES_T(v, this->graph, Graph)
321 {
322 printNode(out, v);
323 out << std::endl;
324 }
325
326 EdgePrinter< Graph, E >::operator()(out);
327 return (*this);
328 }
329 };
330
331 template < class Graph, class E >
332 struct GraphPrinter< Graph, no_property, E > : public EdgePrinter< Graph, E >
333 {
GraphPrinterboost::GraphPrinter334 GraphPrinter(const Graph& g) : EdgePrinter< Graph, E >(g) {}
335
operator ()boost::GraphPrinter336 const GraphPrinter& operator()(std::ostream& out) const
337 {
338 out << "n " << num_vertices(this->graph) << std::endl;
339 EdgePrinter< Graph, E >::operator()(out);
340 return (*this);
341 }
342 };
343
344 // graph printer
345 //=========================================================================
346 // user methods
347
348 /// input stream for reading a graph
349 template < class Graph, class VP, class EP, class VPS, class EPS >
operator >>(std::istream & in,GraphParser<Graph,VP,EP,VPS,EPS> gp)350 std::istream& operator>>(
351 std::istream& in, GraphParser< Graph, VP, EP, VPS, EPS > gp)
352 {
353 gp(in);
354 return in;
355 }
356
357 /// graph parser for given subsets of internal vertex and edge properties
358 template < class EL, class VL, class D, class VP, class EP, class GP, class VPS,
359 class EPS >
read(adjacency_list<EL,VL,D,VP,EP,GP> & g,VPS vps,EPS eps)360 GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VPS, EPS > read(
361 adjacency_list< EL, VL, D, VP, EP, GP >& g, VPS vps, EPS eps)
362 {
363 return GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VPS,
364 EPS >(&g);
365 }
366
367 /// graph parser for all internal vertex and edge properties
368 template < class EL, class VL, class D, class VP, class EP, class GP >
read(adjacency_list<EL,VL,D,VP,EP,GP> & g)369 GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VP, EP > read(
370 adjacency_list< EL, VL, D, VP, EP, GP >& g)
371 {
372 return GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VP,
373 EP >(&g);
374 }
375
376 /// output stream for writing a graph
377 template < class Graph, class VP, class EP >
operator <<(std::ostream & out,const GraphPrinter<Graph,VP,EP> & gp)378 std::ostream& operator<<(
379 std::ostream& out, const GraphPrinter< Graph, VP, EP >& gp)
380 {
381 gp(out);
382 return out;
383 }
384
385 /// write the graph with given property subsets
386 template < class EL, class VL, class D, class VP, class EP, class GP, class VPS,
387 class EPS >
write(const adjacency_list<EL,VL,D,VP,EP,GP> & g,VPS,EPS)388 GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VPS, EPS > write(
389 const adjacency_list< EL, VL, D, VP, EP, GP >& g, VPS, EPS)
390 {
391 return GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VPS, EPS >(g);
392 }
393
394 /// write the graph with all internal vertex and edge properties
395 template < class EL, class VL, class D, class VP, class EP, class GP >
write(const adjacency_list<EL,VL,D,VP,EP,GP> & g)396 GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP > write(
397 const adjacency_list< EL, VL, D, VP, EP, GP >& g)
398 {
399 return GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP >(g);
400 }
401
402 // user methods
403 //=========================================================================
404 } // boost
405 #endif
406