Chris@16: //=======================================================================
Chris@16: // Copyright 2001 Universite Joseph Fourier, Grenoble.
Chris@16: // Author: Francois Faure
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: #ifndef BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
Chris@16: #define BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
Chris@16: 
Chris@16: #include <iostream>
Chris@16: #include <vector>
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <cctype>
Chris@16: 
Chris@16: // Method read to parse an adjacency list from an input stream. Examples:
Chris@16: // cin >> read( G );
Chris@16: // cin >> read( G, NodePropertySubset(), EdgepropertySubset() );
Chris@16: //
Chris@16: // Method write to print an adjacency list to an output stream. Examples:
Chris@16: // cout << write( G );
Chris@16: // cout << write( G, NodePropertySubset(), EdgepropertySubset() );
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: /* outline
Chris@16:         - basic property input
Chris@16:         - get property subset
Chris@16:         - graph parser
Chris@16:         - property printer
Chris@16:         - graph printer
Chris@16:         - user methods
Chris@16: */
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // basic property input
Chris@16: 
Chris@16: template<class Tag, class Value, class Next>
Chris@16: std::istream& operator >> ( std::istream& in, property<Tag,Value,Next>& p )
Chris@16: {
Chris@16:         in >> p.m_value >> p.m_base; // houpla !!
Chris@16:         return in;
Chris@16: }
Chris@16: 
Chris@16: template<class Tag, class Value>
Chris@16: std::istream& operator >> ( std::istream& in, property<Tag,Value,no_property>& p )
Chris@16: {
Chris@16:         in >> p.m_value;
Chris@16:         return in;
Chris@16: }
Chris@16: 
Chris@16: inline std::istream& operator >> ( std::istream& in, no_property& )
Chris@16: {
Chris@16:         return in;
Chris@16: }
Chris@16: 
Chris@16: // basic property input
Chris@16: //===========================================================================
Chris@16: // get property subsets
Chris@16: 
Chris@16: // get a single property tagged Stag
Chris@16: template<class Tag, class Value, class Next, class V, class Stag>
Chris@16: void get
Chris@16: ( property<Tag,Value,Next>& p, const V& v, Stag s )
Chris@16: {
Chris@16:         get( p.m_base,v,s );
Chris@16: }
Chris@16: 
Chris@16: template<class Value, class Next, class V, class Stag>
Chris@16: void get
Chris@16: ( property<Stag,Value,Next>& p, const V& v, Stag )
Chris@16: {
Chris@16:         p.m_value = v;
Chris@16: }
Chris@16: 
Chris@16: // get a subset of properties tagged Stag
Chris@16: template<class Tag, class Value, class Next, 
Chris@16:         class Stag, class Svalue, class Snext>
Chris@16: void getSubset
Chris@16: ( property<Tag,Value,Next>& p, const property<Stag,Svalue,Snext>& s )
Chris@16: {
Chris@16:         get( p, s.m_value, Stag() );
Chris@16:         getSubset( p, s.m_base );
Chris@16: }
Chris@16: 
Chris@16: template<class Tag, class Value, class Next, 
Chris@16:         class Stag, class Svalue>
Chris@16: void getSubset
Chris@16: ( property<Tag,Value,Next>& p, const property<Stag,Svalue,no_property>& s)
Chris@16: {
Chris@16:         get( p, s.m_value, Stag() );
Chris@16: }
Chris@16: 
Chris@16: inline void getSubset
Chris@16: ( no_property&, const no_property& )
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
Chris@16: template<typename T, typename U>
Chris@16: void getSubset(T& p, const U& s)
Chris@16: {
Chris@16:   p = s;
Chris@16: }
Chris@16: 
Chris@16: template<typename T>
Chris@16: void getSubset(T&, const no_property&)
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: //  get property subset
Chris@16: //===========================================================================
Chris@16: // graph parser
Chris@16: typedef enum{ PARSE_NUM_NODES, PARSE_VERTEX, PARSE_EDGE } GraphParserState;
Chris@16: 
Chris@16: template<class Graph_t, class VertexProperty, class EdgeProperty, class VertexPropertySubset,
Chris@16: class EdgePropertySubset>
Chris@16: struct GraphParser
Chris@16: {
Chris@16: 
Chris@16:         typedef Graph_t Graph;
Chris@16:         
Chris@16:         GraphParser( Graph* g ): graph(g)
Chris@16:         {}      
Chris@16:         
Chris@16:         GraphParser& operator () ( std::istream& in )
Chris@16:         {
Chris@16:                 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:                 std::vector<Vertex> nodes;
Chris@16: 
Chris@16:                 GraphParserState state = PARSE_VERTEX;
Chris@16: 
Chris@16:                 unsigned int numLine = 1;
Chris@16:                 char c;
Chris@16:                 while ( in.get(c) )
Chris@16:                 {
Chris@16:                         if( c== '#' ) skip(in);
Chris@16:                         else if( c== 'n' ) state = PARSE_NUM_NODES;
Chris@16:                         else if( c== 'v' ) state = PARSE_VERTEX;
Chris@16:                         else if( c== 'e' ) state = PARSE_EDGE;
Chris@16:                         else if( c== '\n' ) numLine++;
Chris@16:                         else if( !std::isspace(c) ){
Chris@16:                                 in.putback(c);
Chris@16:                                 if( state == PARSE_VERTEX ){
Chris@16:                                         VertexPropertySubset readProp;
Chris@16:                                         if( in >> readProp )
Chris@16:                                         {
Chris@16:                                                 VertexProperty vp;
Chris@16:                                                 getSubset( vp, readProp );
Chris@16:                                                 nodes.push_back( add_vertex(vp, *graph) );
Chris@16:                                         }
Chris@16:                                         else
Chris@16:                                                 std::cerr<<"read vertex, parse error at line"<<numLine<<std::endl;
Chris@16:                                 }
Chris@16:                                 else if( state == PARSE_EDGE ) {
Chris@16:                                         int source, target;
Chris@16:                                         EdgePropertySubset readProp;
Chris@16:                                         in >> source >> target;
Chris@16:                                         if( in >> readProp ) 
Chris@16:                                         {
Chris@16:                                                 EdgeProperty ep;
Chris@16:                                                 getSubset( ep, readProp );
Chris@16:                                                 add_edge(nodes[source], nodes[target], ep, *graph);
Chris@16:                                         }
Chris@16:                                         else
Chris@16:                                                 std::cerr<<"read edge, parse error at line"<<numLine<<std::endl;
Chris@16:                                 }
Chris@16:                                 else { // state == PARSE_NUM_NODES
Chris@16:                                         int n;
Chris@16:                                         if( in >> n ){
Chris@16:                                                 for( int i=0; i<n; ++i )
Chris@16:                                                         nodes.push_back( add_vertex( *graph ));
Chris@16:                                         }
Chris@16:                                         else 
Chris@16:                                                 std::cerr<<"read num_nodes, parse error at line "<< numLine << std::endl;
Chris@16:                                 }
Chris@16:                         }
Chris@16:                 }
Chris@16:         return (*this);
Chris@16:         }
Chris@16:         
Chris@16:         
Chris@16: protected:
Chris@16: 
Chris@16:         Graph* graph;
Chris@16:         
Chris@16:         void skip( std::istream& in )
Chris@16:         {
Chris@16:                 char c = 0;
Chris@16:                 while( c!='\n' && !in.eof() ) 
Chris@16:                        in.get(c);
Chris@16:                 in.putback(c);
Chris@16:         }
Chris@16: };
Chris@16: 
Chris@16: // parser
Chris@16: //=======================================================================
Chris@16: // property printer
Chris@16: 
Chris@16: #if defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
Chris@16: template<class Graph, class Property>
Chris@16: struct PropertyPrinter
Chris@16: {
Chris@16:         typedef typename Property::value_type Value;
Chris@16:         typedef typename Property::tag_type Tag;
Chris@16:         typedef typename Property::next_type Next;
Chris@16:         
Chris@16:         PropertyPrinter( const Graph& g ):graph(&g){}
Chris@16:         
Chris@16:         template<class Val>
Chris@16:         PropertyPrinter& operator () ( std::ostream& out, const Val& v )
Chris@16:         {
Chris@16:                 typename property_map<Graph,Tag>::const_type ps = get(Tag(), *graph);
Chris@16:                 out << ps[ v ] <<" ";
Chris@16:                 PropertyPrinter<Graph,Next> print(*graph);
Chris@16:                 print(out, v);
Chris@16:                 return (*this);
Chris@16:         }
Chris@16: private:
Chris@16:         const Graph* graph;
Chris@16: };
Chris@16: #else
Chris@16: template<class Graph, typename Property>
Chris@16: struct PropertyPrinter
Chris@16: {
Chris@16:         PropertyPrinter( const Graph& g ):graph(&g){}
Chris@16:         
Chris@16:         template<class Val>
Chris@16:         PropertyPrinter& operator () ( std::ostream& out, const Val& v )
Chris@16:         {
Chris@16:                 out << (*graph)[ v ] <<" ";
Chris@16:                 return (*this);
Chris@16:         }
Chris@16: private:
Chris@16:         const Graph* graph;
Chris@16: };
Chris@16: 
Chris@16: template<class Graph, typename Tag, typename Value, typename Next>
Chris@16: struct PropertyPrinter<Graph, property<Tag, Value, Next> >
Chris@16: {
Chris@16:         PropertyPrinter( const Graph& g ):graph(&g){}
Chris@16:         
Chris@16:         template<class Val>
Chris@16:         PropertyPrinter& operator () ( std::ostream& out, const Val& v )
Chris@16:         {
Chris@16:                 typename property_map<Graph,Tag>::const_type ps = get(Tag(), *graph);
Chris@16:                 out << ps[ v ] <<" ";
Chris@16:                 PropertyPrinter<Graph,Next> print(*graph);
Chris@16:                 print(out, v);
Chris@16:                 return (*this);
Chris@16:         }
Chris@16: private:
Chris@16:         const Graph* graph;
Chris@16: };
Chris@16: #endif
Chris@16: 
Chris@16: template<class Graph>
Chris@16: struct PropertyPrinter<Graph, no_property>
Chris@16: {
Chris@16:         PropertyPrinter( const Graph& ){}
Chris@16: 
Chris@16:         template<class Val>
Chris@16:         PropertyPrinter& operator () ( std::ostream&, const Val& ){ return *this; }
Chris@16: };
Chris@16: 
Chris@16: // property printer
Chris@16: //=========================================================================
Chris@16: // graph printer
Chris@16: 
Chris@16: template<class Graph_t, class EdgeProperty>
Chris@16: struct EdgePrinter
Chris@16: {
Chris@16: 
Chris@16:         typedef Graph_t Graph;
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:         
Chris@16:         EdgePrinter( const Graph& g )
Chris@16:                 : graph(g)
Chris@16:         {}      
Chris@16:         
Chris@16:         const EdgePrinter& operator () ( std::ostream& out ) const
Chris@16:         {
Chris@16:                 // assign indices to vertices
Chris@16:                 std::map<Vertex,int> indices;
Chris@16:                 int num = 0;
Chris@16:                 BGL_FORALL_VERTICES_T(v, graph, Graph) {
Chris@16:                         indices[v] = num++;
Chris@16:                 }
Chris@16: 
Chris@16:                 // write edges
Chris@16:                 PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);
Chris@16:                 out << "e" << std::endl;
Chris@16:                 BGL_FORALL_EDGES_T(e, graph, Graph) {
Chris@16:                         out << indices[source(e,graph)] <<  " " << indices[target(e,graph)] << "  "; 
Chris@16:                         print_Edge(out,e); 
Chris@16:                         out << std::endl;
Chris@16:                 }
Chris@16:                 out << std::endl;            
Chris@16:                 return (*this);
Chris@16:         }
Chris@16:         
Chris@16: protected:
Chris@16: 
Chris@16:         const Graph& graph;
Chris@16:         
Chris@16: };
Chris@16: 
Chris@16: template<class Graph, class V, class E>
Chris@16: struct GraphPrinter: public EdgePrinter<Graph,E>
Chris@16: {
Chris@16:         GraphPrinter( const Graph& g )
Chris@16:           : EdgePrinter<Graph,E>(g)
Chris@16:         {}
Chris@16:         
Chris@16:         const GraphPrinter& operator () ( std::ostream& out ) const
Chris@16:         {
Chris@16:                 PropertyPrinter<Graph, V> printNode(this->graph);
Chris@16:                 out << "v"<<std::endl;
Chris@16:                 BGL_FORALL_VERTICES_T(v, this->graph, Graph) {
Chris@16:                         printNode(out,v); 
Chris@16:                         out << std::endl;
Chris@16:                 }
Chris@16:                 
Chris@16:                 EdgePrinter<Graph,E>::operator ()( out );
Chris@16:                 return (*this);
Chris@16:         }
Chris@16: };
Chris@16: 
Chris@16: template<class Graph, class E>
Chris@16: struct GraphPrinter<Graph,no_property,E> 
Chris@16:   : public EdgePrinter<Graph,E>
Chris@16: {
Chris@16:         GraphPrinter( const Graph& g )
Chris@16:           : EdgePrinter<Graph,E>(g)
Chris@16:         {}
Chris@16:         
Chris@16:         const GraphPrinter& operator () ( std::ostream& out ) const
Chris@16:         {
Chris@16:                 out << "n "<< num_vertices(this->graph) << std::endl;
Chris@16:                 EdgePrinter<Graph,E>::operator ()( out );
Chris@16:                 return (*this);
Chris@16:         }
Chris@16: };
Chris@16: 
Chris@16: // graph printer
Chris@16: //=========================================================================
Chris@16: // user methods
Chris@16: 
Chris@16: /// input stream for reading a graph
Chris@16: template<class Graph, class VP, class EP, class VPS, class EPS>
Chris@16: std::istream& operator >> ( std::istream& in, GraphParser<Graph,VP,EP,VPS,EPS> gp ) 
Chris@16: { 
Chris@16:         gp(in); 
Chris@16:         return in; 
Chris@16: }
Chris@16: 
Chris@16: /// graph parser for given subsets of internal vertex and edge properties
Chris@16: template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
Chris@16: GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS> 
Chris@16: read( adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS vps, EPS eps )
Chris@16: {
Chris@16:         return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VPS,EPS>(&g);
Chris@16: }
Chris@16: 
Chris@16: /// graph parser for all internal vertex and edge properties
Chris@16: template<class EL, class VL, class D, class VP, class EP, class GP>
Chris@16: GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP> 
Chris@16: read( adjacency_list<EL,VL,D,VP,EP,GP>& g )
Chris@16: {
Chris@16:         return GraphParser<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP,VP,EP>(&g);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: /// output stream for writing a graph
Chris@16: template<class Graph, class VP, class EP>
Chris@16: std::ostream& operator << ( std::ostream& out, const GraphPrinter<Graph,VP,EP>& gp ) 
Chris@16: { 
Chris@16:         gp(out); 
Chris@16:         return out; 
Chris@16: }
Chris@16: 
Chris@16: /// write the graph with given property subsets
Chris@16: template<class EL, class VL, class D, class VP, class EP, class GP, class VPS, class EPS>
Chris@16: GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS> 
Chris@16: write( const adjacency_list<EL,VL,D,VP,EP,GP>& g, VPS, EPS )
Chris@16: {
Chris@16:         return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VPS,EPS>(g);
Chris@16: }
Chris@16: 
Chris@16: /// write the graph with all internal vertex and edge properties
Chris@16: template<class EL, class VL, class D, class VP, class EP, class GP>
Chris@16: GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP> 
Chris@16: write( const adjacency_list<EL,VL,D,VP,EP,GP>& g )
Chris@16: {
Chris@16:         return GraphPrinter<adjacency_list<EL,VL,D,VP,EP,GP>,VP,EP>(g);
Chris@16: }
Chris@16: 
Chris@16: // user methods
Chris@16: //=========================================================================
Chris@16: }// boost
Chris@16: #endif