//=======================================================================
// Copyright 2001 Universite Joseph Fourier, Grenoble.
// Author: François 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 <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 >> *(static_cast<Next*>(&p)); // 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( *(static_cast<Next*>(&p)),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, Snext(s) );
}
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& p, const no_property& s )
{
}
#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 Iterator>
PropertyPrinter& operator () ( std::ostream& out, Iterator it )
{
typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
out << ps[ *it ] <<" ";
PropertyPrinter<Graph,Next> print(*graph);
print(out, it);
return (*this);
}
private:
const Graph* graph;
};
#else
template<class Graph, typename Property>
struct PropertyPrinter
{
PropertyPrinter( const Graph& g ):graph(&g){}
template<class Iterator>
PropertyPrinter& operator () ( std::ostream& out, Iterator it )
{
out << (*graph)[ *it ] <<" ";
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 Iterator>
PropertyPrinter& operator () ( std::ostream& out, Iterator it )
{
typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
out << ps[ *it ] <<" ";
PropertyPrinter<Graph,Next> print(*graph);
print(out, it);
return (*this);
}
private:
const Graph* graph;
};
#endif
template<class Graph>
struct PropertyPrinter<Graph, no_property>
{
PropertyPrinter( const Graph& ){}
template<class Iterator>
PropertyPrinter& operator () ( std::ostream&, Iterator it ){ 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;
typename graph_traits<Graph>::vertex_iterator vi;
for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){
indices[*vi] = num++;
}
// write edges
PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);
out << "e" << std::endl;
typename graph_traits<Graph>::edge_iterator ei;
for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
out << indices[source(*ei,graph)] << " " << indices[target(*ei,graph)] << " ";
print_Edge(out,ei);
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;
typename graph_traits<Graph>::vertex_iterator vi;
for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){
printNode(out,vi);
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