source: NonGTP/Boost/boost/graph/adjacency_list_io.hpp @ 857

Revision 857, 12.9 KB checked in by igarcia, 19 years ago (diff)
Line 
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
43namespace 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
57template<class Tag, class Value, class Next>
58std::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
64template<class Tag, class Value>
65std::istream& operator >> ( std::istream& in, property<Tag,Value,no_property>& p )
66{
67        in >> p.m_value;
68        return in;
69}
70
71inline 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
81template<class Tag, class Value, class Next, class V, class Stag>
82void get
83( property<Tag,Value,Next>& p, const V& v, Stag s )
84{
85        get( *(static_cast<Next*>(&p)),v,s );
86}
87
88template<class Value, class Next, class V, class Stag>
89void 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
96template<class Tag, class Value, class Next,
97        class Stag, class Svalue, class Snext>
98void 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
105template<class Tag, class Value, class Next,
106        class Stag, class Svalue>
107void getSubset
108( property<Tag,Value,Next>& p, const property<Stag,Svalue,no_property>& s )
109{
110        get( p, s.m_value, Stag() );
111}
112
113inline void getSubset
114( no_property& p, const no_property& s )
115{
116}
117
118//  get property subset
119//===========================================================================
120// graph parser
121
122template<class Graph_t, class VertexProperty, class EdgeProperty, class VertexPropertySubset,
123class EdgePropertySubset>
124struct 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       
190protected:
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
207template<class Graph, class Property>
208struct 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        }
225private:
226        Graph* graph;
227};
228template<class Graph>
229struct 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
241template<class Graph_t, class EdgeProperty>
242struct 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       
275protected:
276
277        Graph& graph;
278       
279};
280
281template<class Graph, class V, class E>
282struct 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
303template<class Graph, class E>
304struct 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
324template<class Graph, class VP, class EP, class VPS, class EPS>
325std::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
332template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
333GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>
334read( 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
340template<class EL, class VL, class D, class VP, class EP, class GP>
341GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>
342read( 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
349template<class Graph, class VP, class EP>
350std::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
357template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
358GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>
359write( 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
365template<class EL, class VL, class D, class VP, class EP, class GP>
366GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>
367write( 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
Note: See TracBrowser for help on using the repository browser.