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

source code of boost/boost/graph/adjacency_list_io.hpp