ceph/src/boost/libs/graph/include/boost/graph/adjacency_list_io.hpp

   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 /* 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
  40 template<class Tag, class Value, class Next>
  41 std::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
  47 template<class Tag, class Value>
  48 std::istream& operator >> ( std::istream& in, property<Tag,Value,no_property>& p )
  49 {
  50         in >> p.m_value;
  51         return in;
  52 }
  53
  54 inline 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
  64 template<class Tag, class Value, class Next, class V, class Stag>
  65 void get
  66 ( property<Tag,Value,Next>& p, const V& v, Stag s )
  67 {
  68         get( p.m_base,v,s );
  69 }
  70
  71 template<class Value, class Next, class V, class Stag>
  72 void 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
  79 template<class Tag, class Value, class Next,
  80         class Stag, class Svalue, class Snext>
  81 void 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
  88 template<class Tag, class Value, class Next,
  89         class Stag, class Svalue>
  90 void getSubset
  91 ( property<Tag,Value,Next>& p, const property<Stag,Svalue,no_property>& s)
  92 {
  93         get( p, s.m_value, Stag() );
  94 }
  95
  96 inline void getSubset
  97 ( no_property&, const no_property& )
  98 {
  99 }
 100
 101 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
 102 template<typename T, typename U>
 103 void getSubset(T& p, const U& s)
 104 {
 105   p = s;
 106 }
 107
 108 template<typename T>
 109 void getSubset(T&, const no_property&)
 110 {
 111 }
 112
 113
 114 #endif
 115
 116 //  get property subset
 117 //===========================================================================
 118 // graph parser
 119 typedef enum{ PARSE_NUM_NODES, PARSE_VERTEX, PARSE_EDGE } GraphParserState;
 120
 121 template<class Graph_t, class VertexProperty, class EdgeProperty, class VertexPropertySubset,
 122 class EdgePropertySubset>
 123 struct 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) )
 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);
 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
 188 protected:
 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);
 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>
 207 struct 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         }
 224 private:
 225         const Graph* graph;
 226 };
 227 #else
 228 template<class Graph, typename Property>
 229 struct 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         }
 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 {
 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         }
 257 private:
 258         const Graph* graph;
 259 };
 260 #endif
 261
 262 template<class Graph>
 263 struct 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
 275 template<class Graph_t, class EdgeProperty>
 276 struct 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
 307 protected:
 308
 309         const Graph& graph;
 310
 311 };
 312
 313 template<class Graph, class V, class E>
 314 struct 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
 334 template<class Graph, class E>
 335 struct 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
 355 template<class Graph, class VP, class EP, class VPS, class EPS>
 356 std::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
 363 template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
 364 GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>
 365 read( 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
 371 template<class EL, class VL, class D, class VP, class EP, class GP>
 372 GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>
 373 read( 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
 380 template<class Graph, class VP, class EP>
 381 std::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
 388 template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
 389 GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>
 390 write( 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
 396 template<class EL, class VL, class D, class VP, class EP, class GP>
 397 GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>
 398 write( 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