[857] | 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
|
---|