Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / adjacency_list_io.hpp
1 //=======================================================================
2 // Copyright 2001 Universite Joseph Fourier, Grenoble.
3 // Author: Fran├žois Faure
4 //
5 // This file is part of the Boost Graph Library
6 //
7 // You should have received a copy of the License Agreement for the
8 // Boost Graph Library along with the software; see the file LICENSE.
9 // If not, contact Office of Research, University of Notre Dame, Notre
10 // Dame, IN 46556.
11 //
12 // Permission to modify the code and to distribute modified code is
13 // granted, provided the text of this NOTICE is retained, a notice that
14 // the code was modified is included with the above COPYRIGHT NOTICE and
15 // with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
16 // file is distributed with the modified code.
17 //
18 // LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
19 // By way of example, but not limitation, Licensor MAKES NO
20 // REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
21 // PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
22 // OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
23 // OR OTHER RIGHTS.
24 //=======================================================================
25
26
27 #ifndef ______adj_list_io_______
28 #define ______adj_list_io_______
29
30 #include <iostream>
31 #include <vector>
32 #include <boost/graph/adjacency_list.hpp>
33 #include <cctype>
34
35 // Method read to parse an adjacency list from an input stream. Examples:
36 // cin >> read( G );
37 // cin >> read( G, NodePropertySubset(), EdgepropertySubset() );
38 //
39 // Method write to print an adjacency list to an output stream. Examples:
40 // cout << write( G );
41 // cout << write( G, NodePropertySubset(), EdgepropertySubset() );
42
43 namespace boost {
44
45 /* outline
46         - basic property input
47         - get property subset
48         - graph parser
49         - property printer
50         - graph printer
51         - user methods
52 */
53
54 //===========================================================================
55 // basic property input
56
57 template<class Tag, class Value, class Next>
58 std::istream& operator >> ( std::istream& in, property<Tag,Value,Next>& p )
59 {
60         in >> p.m_value >> *(static_cast<Next*>(&p)); // houpla !!
61         return in;
62 }
63
64 template<class Tag, class Value>
65 std::istream& operator >> ( std::istream& in, property<Tag,Value,no_property>& p )
66 {
67         in >> p.m_value;
68         return in;
69 }
70
71 inline std::istream& operator >> ( std::istream& in, no_property& )
72 {
73         return in;
74 }
75
76 // basic property input
77 //===========================================================================
78 // get property subsets
79
80 // get a single property tagged Stag
81 template<class Tag, class Value, class Next, class V, class Stag>
82 void get
83 ( property<Tag,Value,Next>& p, const V& v, Stag s )
84 {
85         get( *(static_cast<Next*>(&p)),v,s );
86 }
87
88 template<class Value, class Next, class V, class Stag>
89 void get
90 ( property<Stag,Value,Next>& p, const V& v, Stag )
91 {
92         p.m_value = v;
93 }
94
95 // get a subset of properties tagged Stag
96 template<class Tag, class Value, class Next, 
97         class Stag, class Svalue, class Snext>
98 void getSubset
99 ( property<Tag,Value,Next>& p, const property<Stag,Svalue,Snext>& s )
100 {
101         get( p, s.m_value, Stag() );
102         getSubset( p, Snext(s) );
103 }
104
105 template<class Tag, class Value, class Next, 
106         class Stag, class Svalue>
107 void getSubset
108 ( property<Tag,Value,Next>& p, const property<Stag,Svalue,no_property>& s )
109 {
110         get( p, s.m_value, Stag() );
111 }
112
113 inline void getSubset
114 ( no_property& p, const no_property& s )
115 {
116 }
117
118 //  get property subset
119 //===========================================================================
120 // graph parser
121
122 template<class Graph_t, class VertexProperty, class EdgeProperty, class VertexPropertySubset,
123 class EdgePropertySubset>
124 struct GraphParser
125 {
126
127         typedef Graph_t Graph;
128         
129         GraphParser( Graph* g ): graph(g)
130         {}      
131         
132         GraphParser& operator () ( std::istream& in )
133         {
134                 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
135                 std::vector<Vertex> nodes;
136
137                 typedef enum{ PARSE_NUM_NODES, PARSE_VERTEX, PARSE_EDGE } State;
138                 State state = PARSE_VERTEX;
139
140                 unsigned int numLine = 1;
141                 char c;
142                 while ( in.get(c) )
143                 {
144                         if( c== '#' ) skip(in);
145                         else if( c== 'n' ) state = PARSE_NUM_NODES;
146                         else if( c== 'v' ) state = PARSE_VERTEX;
147                         else if( c== 'e' ) state = PARSE_EDGE;
148                         else if( c== '\n' ) numLine++;
149                         else if( !std::isspace(c) ){
150                                 in.putback(c);
151                                 if( state == PARSE_VERTEX ){
152                                         VertexPropertySubset readProp;
153                                         if( in >> readProp )
154                                         {
155                                                 VertexProperty vp;
156                                                 getSubset( vp, readProp );
157                                                 nodes.push_back( add_vertex(vp, *graph) );
158                                         }
159                                         else
160                                                 std::cerr<<"read vertex, parse error at line"<<numLine<<std::endl;
161                                 }
162                                 else if( state == PARSE_EDGE ) {
163                                         int source, target;
164                                         EdgePropertySubset readProp;
165                                         in >> source >> target;
166                                         if( in >> readProp ) 
167                                         {
168                                                 EdgeProperty ep;
169                                                 getSubset( ep, readProp );
170                                                 add_edge(nodes[source], nodes[target], ep, *graph);
171                                         }
172                                         else
173                                                 std::cerr<<"read edge, parse error at line"<<numLine<<std::endl;
174                                 }
175                                 else { // state == PARSE_NUM_NODES
176                                         int n;
177                                         if( in >> n ){
178                                                 for( int i=0; i<n; ++i )
179                                                         nodes.push_back( add_vertex( *graph ));
180                                         }
181                                         else 
182                                                 std::cerr<<"read num_nodes, parse error at line "<< numLine << std::endl;
183                                 }
184                         }
185                 }
186         return (*this);
187         }
188         
189         
190 protected:
191
192         Graph* graph;
193         
194         void skip( std::istream& in )
195         {
196                 char c = 0;
197                 while( c!='\n' && !in.eof() ) 
198                        in.get(c);
199                 in.putback(c);
200         }
201 };
202
203 // parser
204 //=======================================================================
205 // property printer
206
207 template<class Graph, class Property>
208 struct PropertyPrinter
209 {
210         typedef typename Property::value_type Value;
211         typedef typename Property::tag_type Tag;
212         typedef typename Property::next_type Next;
213         
214         PropertyPrinter( Graph& g ):graph(&g){}
215         
216         template<class Iterator>
217         PropertyPrinter& operator () ( std::ostream& out, Iterator it )
218         {
219                 typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
220                 out << ps[ *it ] <<" ";
221                 PropertyPrinter<Graph,Next> print(*graph);
222                 print(out, it);
223                 return (*this);
224         }
225 private:
226         Graph* graph;
227 };
228 template<class Graph>
229 struct PropertyPrinter<Graph, no_property>
230 {
231         PropertyPrinter( Graph& ){}
232
233         template<class Iterator>
234         PropertyPrinter& operator () ( std::ostream&, Iterator it ){ return *this; }
235 };
236
237 // property printer
238 //=========================================================================
239 // graph printer
240
241 template<class Graph_t, class EdgeProperty>
242 struct EdgePrinter
243 {
244
245         typedef Graph_t Graph;
246         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
247         
248         EdgePrinter( Graph& g )
249                 : graph(g)
250         {}      
251         
252         const EdgePrinter& operator () ( std::ostream& out ) const
253         {
254                 // assign indices to vertices
255                 std::map<Vertex,int> indices;
256                 int num = 0;
257                 typename graph_traits<Graph>::vertex_iterator vi;
258                 for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){
259                         indices[*vi] = num++;
260                 }
261
262                 // write edges
263                 PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);
264                 out << "e" << std::endl;
265                 typename graph_traits<Graph>::edge_iterator ei;
266                 for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
267                         out << indices[source(*ei,graph)] <<  " " << indices[target(*ei,graph)] << "  "; 
268                         print_Edge(out,ei); 
269                         out << std::endl;
270                 }
271                 out << std::endl;            
272                 return (*this);
273         }
274         
275 protected:
276
277         Graph& graph;
278         
279 };
280
281 template<class Graph, class V, class E>
282 struct GraphPrinter: public EdgePrinter<Graph,E>
283 {
284         GraphPrinter( Graph& g )
285           : EdgePrinter<Graph,E>(g)
286         {}
287         
288         const GraphPrinter& operator () ( std::ostream& out ) const
289         {
290                 PropertyPrinter<Graph, V> printNode(this->graph);
291                 out << "v"<<std::endl;
292                 typename graph_traits<Graph>::vertex_iterator vi;
293                 for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){
294                         printNode(out,vi); 
295                         out << std::endl;
296                 }
297                 
298                 EdgePrinter<Graph,E>::operator ()( out );
299                 return (*this);
300         }
301 };
302
303 template<class Graph, class E>
304 struct GraphPrinter<Graph,no_property,E> 
305   : public EdgePrinter<Graph,E>
306 {
307         GraphPrinter( Graph& g )
308           : EdgePrinter<Graph,E>(g)
309         {}
310         
311         const GraphPrinter& operator () ( std::ostream& out ) const
312         {
313                 out << "n "<< num_vertices(this->graph) << std::endl;
314                 EdgePrinter<Graph,E>::operator ()( out );
315                 return (*this);
316         }
317 };
318
319 // graph printer
320 //=========================================================================
321 // user methods
322
323 /// input stream for reading a graph
324 template<class Graph, class VP, class EP, class VPS, class EPS>
325 std::istream& operator >> ( std::istream& in, GraphParser<Graph,VP,EP,VPS,EPS> gp ) 
326
327         gp(in); 
328         return in; 
329 }
330
331 /// graph parser for given subsets of internal vertex and edge properties
332 template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
333 GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS> 
334 read( adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS vps, EPS eps )
335 {
336         return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>(&g);
337 }
338
339 /// graph parser for all internal vertex and edge properties
340 template<class EL, class VL, class D, class VP, class EP, class GP>
341 GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP> 
342 read( adjacency_list<EL,VL,D,VP,EP,GP>& g )
343 {
344         return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>(&g);
345 }
346
347
348 /// output stream for writing a graph
349 template<class Graph, class VP, class EP>
350 std::ostream& operator << ( std::ostream& out, const GraphPrinter<Graph,VP,EP>& gp ) 
351
352         gp(out); 
353         return out; 
354 }
355
356 /// write the graph with given property subsets
357 template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
358 GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS> 
359 write( adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS, EPS )
360 {
361         return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>(g);
362 }
363
364 /// write the graph with all internal vertex and edge properties
365 template<class EL, class VL, class D, class VP, class EP, class GP>
366 GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP> 
367 write( adjacency_list<EL,VL,D,VP,EP,GP>& g )
368 {
369         return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>(g);
370 }
371
372 // user methods
373 //=========================================================================
374 }// boost
375 #endif