test: epoc32/include/stdapis/boost/graph/adjacency_list

     1 //=======================================================================

     2 // Copyright 2001 Universite Joseph Fourier, Grenoble.

     3 // Author: François 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

    12 #include <iostream>

    13 #include <vector>

    14 #include <boost/graph/adjacency_list.hpp>

    15 #include <cctype>

    17 // Method read to parse an adjacency list from an input stream. Examples:

    18 // cin >> read( G );

    19 // cin >> read( G, NodePropertySubset(), EdgepropertySubset() );

    20 //

    21 // Method write to print an adjacency list to an output stream. Examples:

    22 // cout << write( G );

    23 // cout << write( G, NodePropertySubset(), EdgepropertySubset() );

    25 namespace boost {

    27 /* outline

    28         - basic property input

    29         - get property subset

    30         - graph parser

    31         - property printer

    32         - graph printer

    33         - user methods

    34 */

    36 //===========================================================================

    37 // basic property input

    39 template<class Tag, class Value, class Next>

    40 std::istream& operator >> ( std::istream& in, property<Tag,Value,Next>& p )

    41 {

    42         in >> p.m_value >> *(static_cast<Next*>(&p)); // houpla !!

    43         return in;

    44 }

    46 template<class Tag, class Value>

    47 std::istream& operator >> ( std::istream& in, property<Tag,Value,no_property>& p )

    48 {

    49         in >> p.m_value;

    50         return in;

    51 }

    53 inline std::istream& operator >> ( std::istream& in, no_property& )

    54 {

    55         return in;

    56 }

    58 // basic property input

    59 //===========================================================================

    60 // get property subsets

    62 // get a single property tagged Stag

    63 template<class Tag, class Value, class Next, class V, class Stag>

    64 void get

    65 ( property<Tag,Value,Next>& p, const V& v, Stag s )

    66 {

    67         get( *(static_cast<Next*>(&p)),v,s );

    68 }

    70 template<class Value, class Next, class V, class Stag>

    71 void get

    72 ( property<Stag,Value,Next>& p, const V& v, Stag )

    73 {

    74         p.m_value = v;

    75 }

    77 // get a subset of properties tagged Stag

    78 template<class Tag, class Value, class Next,

    79         class Stag, class Svalue, class Snext>

    80 void getSubset

    81 ( property<Tag,Value,Next>& p, const property<Stag,Svalue,Snext>& s )

    82 {

    83         get( p, s.m_value, Stag() );

    84         getSubset( p, Snext(s) );

    85 }

    87 template<class Tag, class Value, class Next,

    88         class Stag, class Svalue>

    89 void getSubset

    90 ( property<Tag,Value,Next>& p, const property<Stag,Svalue,no_property>& s)

    91 {

    92         get( p, s.m_value, Stag() );

    93 }

    95 inline void getSubset

    96 ( no_property& p, const no_property& s )

    97 {

    98 }

   100 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)

   101 template<typename T, typename U>

   102 void getSubset(T& p, const U& s)

   103 {

   104   p = s;

   105 }

   107 template<typename T>

   108 void getSubset(T&, const no_property&)

   109 {

   110 }

   113 #endif

   115 //  get property subset

   116 //===========================================================================

   117 // graph parser

   118 typedef enum{ PARSE_NUM_NODES, PARSE_VERTEX, PARSE_EDGE } GraphParserState;

   120 template<class Graph_t, class VertexProperty, class EdgeProperty, class VertexPropertySubset,

   121 class EdgePropertySubset>

   122 struct GraphParser

   123 {

   125         typedef Graph_t Graph;

   127         GraphParser( Graph* g ): graph(g)

   128         {}

   130         GraphParser& operator () ( std::istream& in )

   131         {

   132                 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

   133                 std::vector<Vertex> nodes;

   135                 GraphParserState state = PARSE_VERTEX;

   137                 unsigned int numLine = 1;

   138                 char c;

   139                 while ( in.get(c) )

   140                 {

   141                         if( c== '#' ) skip(in);

   142                         else if( c== 'n' ) state = PARSE_NUM_NODES;

   143                         else if( c== 'v' ) state = PARSE_VERTEX;

   144                         else if( c== 'e' ) state = PARSE_EDGE;

   145                         else if( c== '\n' ) numLine++;

   146                         else if( !std::isspace(c) ){

   147                                 in.putback(c);

   148                                 if( state == PARSE_VERTEX ){

   149                                         VertexPropertySubset readProp;

   150                                         if( in >> readProp )

   151                                         {

   152                                                 VertexProperty vp;

   153                                                 getSubset( vp, readProp );

   154                                                 nodes.push_back( add_vertex(vp, *graph) );

   155                                         }

   156                                         else

   157                                                 std::cerr<<"read vertex, parse error at line"<<numLine<<std::endl;

   158                                 }

   159                                 else if( state == PARSE_EDGE ) {

   160                                         int source, target;

   161                                         EdgePropertySubset readProp;

   162                                         in >> source >> target;

   163                                         if( in >> readProp )

   164                                         {

   165                                                 EdgeProperty ep;

   166                                                 getSubset( ep, readProp );

   167                                                 add_edge(nodes[source], nodes[target], ep, *graph);

   168                                         }

   169                                         else

   170                                                 std::cerr<<"read edge, parse error at line"<<numLine<<std::endl;

   171                                 }

   172                                 else { // state == PARSE_NUM_NODES

   173                                         int n;

   174                                         if( in >> n ){

   175                                                 for( int i=0; i<n; ++i )

   176                                                         nodes.push_back( add_vertex( *graph ));

   177                                         }

   178                                         else

   179                                                 std::cerr<<"read num_nodes, parse error at line "<< numLine << std::endl;

   180                                 }

   181                         }

   182                 }

   183         return (*this);

   184         }

   187 protected:

   189         Graph* graph;

   191         void skip( std::istream& in )

   192         {

   193                 char c = 0;

   194                 while( c!='\n' && !in.eof() )

   195                        in.get(c);

   196                 in.putback(c);

   197         }

   198 };

   200 // parser

   201 //=======================================================================

   202 // property printer

   204 #if defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)

   205 template<class Graph, class Property>

   206 struct PropertyPrinter

   207 {

   208         typedef typename Property::value_type Value;

   209         typedef typename Property::tag_type Tag;

   210         typedef typename Property::next_type Next;

   212         PropertyPrinter( const Graph& g ):graph(&g){}

   214         template<class Iterator>

   215         PropertyPrinter& operator () ( std::ostream& out, Iterator it )

   216         {

   217                 typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);

   218                 out << ps[ *it ] <<" ";

   219                 PropertyPrinter<Graph,Next> print(*graph);

   220                 print(out, it);

   221                 return (*this);

   222         }

   223 private:

   224         const Graph* graph;

   225 };

   226 #else

   227 template<class Graph, typename Property>

   228 struct PropertyPrinter

   229 {

   230         PropertyPrinter( const Graph& g ):graph(&g){}

   232         template<class Iterator>

   233         PropertyPrinter& operator () ( std::ostream& out, Iterator it )

   234         {

   235                 out << (*graph)[ *it ] <<" ";

   236                 return (*this);

   237         }

   238 private:

   239         const Graph* graph;

   240 };

   242 template<class Graph, typename Tag, typename Value, typename Next>

   243 struct PropertyPrinter<Graph, property<Tag, Value, Next> >

   244 {

   245         PropertyPrinter( const Graph& g ):graph(&g){}

   247         template<class Iterator>

   248         PropertyPrinter& operator () ( std::ostream& out, Iterator it )

   249         {

   250                 typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);

   251                 out << ps[ *it ] <<" ";

   252                 PropertyPrinter<Graph,Next> print(*graph);

   253                 print(out, it);

   254                 return (*this);

   255         }

   256 private:

   257         const Graph* graph;

   258 };

   259 #endif

   261 template<class Graph>

   262 struct PropertyPrinter<Graph, no_property>

   263 {

   264         PropertyPrinter( const Graph& ){}

   266         template<class Iterator>

   267         PropertyPrinter& operator () ( std::ostream&, Iterator it ){ return *this; }

   268 };

   270 // property printer

   271 //=========================================================================

   272 // graph printer

   274 template<class Graph_t, class EdgeProperty>

   275 struct EdgePrinter

   276 {

   278         typedef Graph_t Graph;

   279         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

   281         EdgePrinter( const Graph& g )

   282                 : graph(g)

   283         {}

   285         const EdgePrinter& operator () ( std::ostream& out ) const

   286         {

   287                 // assign indices to vertices

   288                 std::map<Vertex,int> indices;

   289                 int num = 0;

   290                 typename graph_traits<Graph>::vertex_iterator vi;

   291                 for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){

   292                         indices[*vi] = num++;

   293                 }

   295                 // write edges

   296                 PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);

   297                 out << "e" << std::endl;

   298                 typename graph_traits<Graph>::edge_iterator ei;

   299                 for (ei = edges(graph).first; ei != edges(graph).second; ++ei){

   300                         out << indices[source(*ei,graph)] <<  " " << indices[target(*ei,graph)] << "  ";

   301                         print_Edge(out,ei);

   302                         out << std::endl;

   303                 }

   304                 out << std::endl;

   305                 return (*this);

   306         }

   308 protected:

   310         const Graph& graph;

   312 };

   314 template<class Graph, class V, class E>

   315 struct GraphPrinter: public EdgePrinter<Graph,E>

   316 {

   317         GraphPrinter( const Graph& g )

   318           : EdgePrinter<Graph,E>(g)

   319         {}

   321         const GraphPrinter& operator () ( std::ostream& out ) const

   322         {

   323                 PropertyPrinter<Graph, V> printNode(this->graph);

   324                 out << "v"<<std::endl;

   325                 typename graph_traits<Graph>::vertex_iterator vi;

   326                 for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){

   327                         printNode(out,vi);

   328                         out << std::endl;

   329                 }

   331                 EdgePrinter<Graph,E>::operator ()( out );

   332                 return (*this);

   333         }

   334 };

   336 template<class Graph, class E>

   337 struct GraphPrinter<Graph,no_property,E>

   338   : public EdgePrinter<Graph,E>

   339 {

   340         GraphPrinter( const Graph& g )

   341           : EdgePrinter<Graph,E>(g)

   342         {}

   344         const GraphPrinter& operator () ( std::ostream& out ) const

   345         {

   346                 out << "n "<< num_vertices(this->graph) << std::endl;

   347                 EdgePrinter<Graph,E>::operator ()( out );

   348                 return (*this);

   349         }

   350 };

   352 // graph printer

   353 //=========================================================================

   354 // user methods

   356 /// input stream for reading a graph

   357 template<class Graph, class VP, class EP, class VPS, class EPS>

   358 std::istream& operator >> ( std::istream& in, GraphParser<Graph,VP,EP,VPS,EPS> gp )

   359 {

   360         gp(in);

   361         return in;

   362 }

   364 /// graph parser for given subsets of internal vertex and edge properties

   365 template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>

   366 GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>

   367 read( adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS vps, EPS eps )

   368 {

   369         return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>(&g);

   370 }

   372 /// graph parser for all internal vertex and edge properties

   373 template<class EL, class VL, class D, class VP, class EP, class GP>

   374 GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>

   375 read( adjacency_list<EL,VL,D,VP,EP,GP>& g )

   376 {

   377         return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>(&g);

   378 }

   381 /// output stream for writing a graph

   382 template<class Graph, class VP, class EP>

   383 std::ostream& operator << ( std::ostream& out, const GraphPrinter<Graph,VP,EP>& gp )

   384 {

   385         gp(out);

   386         return out;

   387 }

   389 /// write the graph with given property subsets

   390 template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>

   391 GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>

   392 write( const adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS, EPS )

   393 {

   394         return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>(g);

   395 }

   397 /// write the graph with all internal vertex and edge properties

   398 template<class EL, class VL, class D, class VP, class EP, class GP>

   399 GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>

   400 write( const adjacency_list<EL,VL,D,VP,EP,GP>& g )

   401 {

   402         return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>(g);

   403 }

   405 // user methods

   406 //=========================================================================

   407 }// boost

   408 #endif

author	William Roberts <williamr@symbian.org>
	Tue, 16 Mar 2010 16:12:26 +0000
branch	Symbian2
changeset 2	2fe1408b6811
permissions	-rw-r--r--