1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/adjacency_list_io.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,408 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 Universite Joseph Fourier, Grenoble.
1.6 +// Author: François Faure
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +#ifndef BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
1.13 +#define BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
1.14 +
1.15 +#include <iostream>
1.16 +#include <vector>
1.17 +#include <boost/graph/adjacency_list.hpp>
1.18 +#include <cctype>
1.19 +
1.20 +// Method read to parse an adjacency list from an input stream. Examples:
1.21 +// cin >> read( G );
1.22 +// cin >> read( G, NodePropertySubset(), EdgepropertySubset() );
1.23 +//
1.24 +// Method write to print an adjacency list to an output stream. Examples:
1.25 +// cout << write( G );
1.26 +// cout << write( G, NodePropertySubset(), EdgepropertySubset() );
1.27 +
1.28 +namespace boost {
1.29 +
1.30 +/* outline
1.31 + - basic property input
1.32 + - get property subset
1.33 + - graph parser
1.34 + - property printer
1.35 + - graph printer
1.36 + - user methods
1.37 +*/
1.38 +
1.39 +//===========================================================================
1.40 +// basic property input
1.41 +
1.42 +template<class Tag, class Value, class Next>
1.43 +std::istream& operator >> ( std::istream& in, property<Tag,Value,Next>& p )
1.44 +{
1.45 + in >> p.m_value >> *(static_cast<Next*>(&p)); // houpla !!
1.46 + return in;
1.47 +}
1.48 +
1.49 +template<class Tag, class Value>
1.50 +std::istream& operator >> ( std::istream& in, property<Tag,Value,no_property>& p )
1.51 +{
1.52 + in >> p.m_value;
1.53 + return in;
1.54 +}
1.55 +
1.56 +inline std::istream& operator >> ( std::istream& in, no_property& )
1.57 +{
1.58 + return in;
1.59 +}
1.60 +
1.61 +// basic property input
1.62 +//===========================================================================
1.63 +// get property subsets
1.64 +
1.65 +// get a single property tagged Stag
1.66 +template<class Tag, class Value, class Next, class V, class Stag>
1.67 +void get
1.68 +( property<Tag,Value,Next>& p, const V& v, Stag s )
1.69 +{
1.70 + get( *(static_cast<Next*>(&p)),v,s );
1.71 +}
1.72 +
1.73 +template<class Value, class Next, class V, class Stag>
1.74 +void get
1.75 +( property<Stag,Value,Next>& p, const V& v, Stag )
1.76 +{
1.77 + p.m_value = v;
1.78 +}
1.79 +
1.80 +// get a subset of properties tagged Stag
1.81 +template<class Tag, class Value, class Next,
1.82 + class Stag, class Svalue, class Snext>
1.83 +void getSubset
1.84 +( property<Tag,Value,Next>& p, const property<Stag,Svalue,Snext>& s )
1.85 +{
1.86 + get( p, s.m_value, Stag() );
1.87 + getSubset( p, Snext(s) );
1.88 +}
1.89 +
1.90 +template<class Tag, class Value, class Next,
1.91 + class Stag, class Svalue>
1.92 +void getSubset
1.93 +( property<Tag,Value,Next>& p, const property<Stag,Svalue,no_property>& s)
1.94 +{
1.95 + get( p, s.m_value, Stag() );
1.96 +}
1.97 +
1.98 +inline void getSubset
1.99 +( no_property& p, const no_property& s )
1.100 +{
1.101 +}
1.102 +
1.103 +#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
1.104 +template<typename T, typename U>
1.105 +void getSubset(T& p, const U& s)
1.106 +{
1.107 + p = s;
1.108 +}
1.109 +
1.110 +template<typename T>
1.111 +void getSubset(T&, const no_property&)
1.112 +{
1.113 +}
1.114 +
1.115 +
1.116 +#endif
1.117 +
1.118 +// get property subset
1.119 +//===========================================================================
1.120 +// graph parser
1.121 +typedef enum{ PARSE_NUM_NODES, PARSE_VERTEX, PARSE_EDGE } GraphParserState;
1.122 +
1.123 +template<class Graph_t, class VertexProperty, class EdgeProperty, class VertexPropertySubset,
1.124 +class EdgePropertySubset>
1.125 +struct GraphParser
1.126 +{
1.127 +
1.128 + typedef Graph_t Graph;
1.129 +
1.130 + GraphParser( Graph* g ): graph(g)
1.131 + {}
1.132 +
1.133 + GraphParser& operator () ( std::istream& in )
1.134 + {
1.135 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.136 + std::vector<Vertex> nodes;
1.137 +
1.138 + GraphParserState state = PARSE_VERTEX;
1.139 +
1.140 + unsigned int numLine = 1;
1.141 + char c;
1.142 + while ( in.get(c) )
1.143 + {
1.144 + if( c== '#' ) skip(in);
1.145 + else if( c== 'n' ) state = PARSE_NUM_NODES;
1.146 + else if( c== 'v' ) state = PARSE_VERTEX;
1.147 + else if( c== 'e' ) state = PARSE_EDGE;
1.148 + else if( c== '\n' ) numLine++;
1.149 + else if( !std::isspace(c) ){
1.150 + in.putback(c);
1.151 + if( state == PARSE_VERTEX ){
1.152 + VertexPropertySubset readProp;
1.153 + if( in >> readProp )
1.154 + {
1.155 + VertexProperty vp;
1.156 + getSubset( vp, readProp );
1.157 + nodes.push_back( add_vertex(vp, *graph) );
1.158 + }
1.159 + else
1.160 + std::cerr<<"read vertex, parse error at line"<<numLine<<std::endl;
1.161 + }
1.162 + else if( state == PARSE_EDGE ) {
1.163 + int source, target;
1.164 + EdgePropertySubset readProp;
1.165 + in >> source >> target;
1.166 + if( in >> readProp )
1.167 + {
1.168 + EdgeProperty ep;
1.169 + getSubset( ep, readProp );
1.170 + add_edge(nodes[source], nodes[target], ep, *graph);
1.171 + }
1.172 + else
1.173 + std::cerr<<"read edge, parse error at line"<<numLine<<std::endl;
1.174 + }
1.175 + else { // state == PARSE_NUM_NODES
1.176 + int n;
1.177 + if( in >> n ){
1.178 + for( int i=0; i<n; ++i )
1.179 + nodes.push_back( add_vertex( *graph ));
1.180 + }
1.181 + else
1.182 + std::cerr<<"read num_nodes, parse error at line "<< numLine << std::endl;
1.183 + }
1.184 + }
1.185 + }
1.186 + return (*this);
1.187 + }
1.188 +
1.189 +
1.190 +protected:
1.191 +
1.192 + Graph* graph;
1.193 +
1.194 + void skip( std::istream& in )
1.195 + {
1.196 + char c = 0;
1.197 + while( c!='\n' && !in.eof() )
1.198 + in.get(c);
1.199 + in.putback(c);
1.200 + }
1.201 +};
1.202 +
1.203 +// parser
1.204 +//=======================================================================
1.205 +// property printer
1.206 +
1.207 +#if defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
1.208 +template<class Graph, class Property>
1.209 +struct PropertyPrinter
1.210 +{
1.211 + typedef typename Property::value_type Value;
1.212 + typedef typename Property::tag_type Tag;
1.213 + typedef typename Property::next_type Next;
1.214 +
1.215 + PropertyPrinter( const Graph& g ):graph(&g){}
1.216 +
1.217 + template<class Iterator>
1.218 + PropertyPrinter& operator () ( std::ostream& out, Iterator it )
1.219 + {
1.220 + typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
1.221 + out << ps[ *it ] <<" ";
1.222 + PropertyPrinter<Graph,Next> print(*graph);
1.223 + print(out, it);
1.224 + return (*this);
1.225 + }
1.226 +private:
1.227 + const Graph* graph;
1.228 +};
1.229 +#else
1.230 +template<class Graph, typename Property>
1.231 +struct PropertyPrinter
1.232 +{
1.233 + PropertyPrinter( const Graph& g ):graph(&g){}
1.234 +
1.235 + template<class Iterator>
1.236 + PropertyPrinter& operator () ( std::ostream& out, Iterator it )
1.237 + {
1.238 + out << (*graph)[ *it ] <<" ";
1.239 + return (*this);
1.240 + }
1.241 +private:
1.242 + const Graph* graph;
1.243 +};
1.244 +
1.245 +template<class Graph, typename Tag, typename Value, typename Next>
1.246 +struct PropertyPrinter<Graph, property<Tag, Value, Next> >
1.247 +{
1.248 + PropertyPrinter( const Graph& g ):graph(&g){}
1.249 +
1.250 + template<class Iterator>
1.251 + PropertyPrinter& operator () ( std::ostream& out, Iterator it )
1.252 + {
1.253 + typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
1.254 + out << ps[ *it ] <<" ";
1.255 + PropertyPrinter<Graph,Next> print(*graph);
1.256 + print(out, it);
1.257 + return (*this);
1.258 + }
1.259 +private:
1.260 + const Graph* graph;
1.261 +};
1.262 +#endif
1.263 +
1.264 +template<class Graph>
1.265 +struct PropertyPrinter<Graph, no_property>
1.266 +{
1.267 + PropertyPrinter( const Graph& ){}
1.268 +
1.269 + template<class Iterator>
1.270 + PropertyPrinter& operator () ( std::ostream&, Iterator it ){ return *this; }
1.271 +};
1.272 +
1.273 +// property printer
1.274 +//=========================================================================
1.275 +// graph printer
1.276 +
1.277 +template<class Graph_t, class EdgeProperty>
1.278 +struct EdgePrinter
1.279 +{
1.280 +
1.281 + typedef Graph_t Graph;
1.282 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.283 +
1.284 + EdgePrinter( const Graph& g )
1.285 + : graph(g)
1.286 + {}
1.287 +
1.288 + const EdgePrinter& operator () ( std::ostream& out ) const
1.289 + {
1.290 + // assign indices to vertices
1.291 + std::map<Vertex,int> indices;
1.292 + int num = 0;
1.293 + typename graph_traits<Graph>::vertex_iterator vi;
1.294 + for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){
1.295 + indices[*vi] = num++;
1.296 + }
1.297 +
1.298 + // write edges
1.299 + PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);
1.300 + out << "e" << std::endl;
1.301 + typename graph_traits<Graph>::edge_iterator ei;
1.302 + for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
1.303 + out << indices[source(*ei,graph)] << " " << indices[target(*ei,graph)] << " ";
1.304 + print_Edge(out,ei);
1.305 + out << std::endl;
1.306 + }
1.307 + out << std::endl;
1.308 + return (*this);
1.309 + }
1.310 +
1.311 +protected:
1.312 +
1.313 + const Graph& graph;
1.314 +
1.315 +};
1.316 +
1.317 +template<class Graph, class V, class E>
1.318 +struct GraphPrinter: public EdgePrinter<Graph,E>
1.319 +{
1.320 + GraphPrinter( const Graph& g )
1.321 + : EdgePrinter<Graph,E>(g)
1.322 + {}
1.323 +
1.324 + const GraphPrinter& operator () ( std::ostream& out ) const
1.325 + {
1.326 + PropertyPrinter<Graph, V> printNode(this->graph);
1.327 + out << "v"<<std::endl;
1.328 + typename graph_traits<Graph>::vertex_iterator vi;
1.329 + for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){
1.330 + printNode(out,vi);
1.331 + out << std::endl;
1.332 + }
1.333 +
1.334 + EdgePrinter<Graph,E>::operator ()( out );
1.335 + return (*this);
1.336 + }
1.337 +};
1.338 +
1.339 +template<class Graph, class E>
1.340 +struct GraphPrinter<Graph,no_property,E>
1.341 + : public EdgePrinter<Graph,E>
1.342 +{
1.343 + GraphPrinter( const Graph& g )
1.344 + : EdgePrinter<Graph,E>(g)
1.345 + {}
1.346 +
1.347 + const GraphPrinter& operator () ( std::ostream& out ) const
1.348 + {
1.349 + out << "n "<< num_vertices(this->graph) << std::endl;
1.350 + EdgePrinter<Graph,E>::operator ()( out );
1.351 + return (*this);
1.352 + }
1.353 +};
1.354 +
1.355 +// graph printer
1.356 +//=========================================================================
1.357 +// user methods
1.358 +
1.359 +/// input stream for reading a graph
1.360 +template<class Graph, class VP, class EP, class VPS, class EPS>
1.361 +std::istream& operator >> ( std::istream& in, GraphParser<Graph,VP,EP,VPS,EPS> gp )
1.362 +{
1.363 + gp(in);
1.364 + return in;
1.365 +}
1.366 +
1.367 +/// graph parser for given subsets of internal vertex and edge properties
1.368 +template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
1.369 +GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>
1.370 +read( adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS vps, EPS eps )
1.371 +{
1.372 + return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>(&g);
1.373 +}
1.374 +
1.375 +/// graph parser for all internal vertex and edge properties
1.376 +template<class EL, class VL, class D, class VP, class EP, class GP>
1.377 +GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>
1.378 +read( adjacency_list<EL,VL,D,VP,EP,GP>& g )
1.379 +{
1.380 + return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>(&g);
1.381 +}
1.382 +
1.383 +
1.384 +/// output stream for writing a graph
1.385 +template<class Graph, class VP, class EP>
1.386 +std::ostream& operator << ( std::ostream& out, const GraphPrinter<Graph,VP,EP>& gp )
1.387 +{
1.388 + gp(out);
1.389 + return out;
1.390 +}
1.391 +
1.392 +/// write the graph with given property subsets
1.393 +template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
1.394 +GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>
1.395 +write( const adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS, EPS )
1.396 +{
1.397 + return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>(g);
1.398 +}
1.399 +
1.400 +/// write the graph with all internal vertex and edge properties
1.401 +template<class EL, class VL, class D, class VP, class EP, class GP>
1.402 +GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>
1.403 +write( const adjacency_list<EL,VL,D,VP,EP,GP>& g )
1.404 +{
1.405 + return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>(g);
1.406 +}
1.407 +
1.408 +// user methods
1.409 +//=========================================================================
1.410 +}// boost
1.411 +#endif