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