Imported Upstream version 1.49.0upstream/1.49.0

1 files changed, 406 insertions, 0 deletions

diff --git a/boost/graph/adjacency_list_io.hpp b/boost/graph/adjacency_list_io.hpp
new file mode 100644
index 0000000000..91b0b465d7
--- /dev/null
+++ b/boost/graph/adjacency_list_io.hpp
@@ -0,0 +1,406 @@
+//=======================================================================
+// 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 >> *(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&, 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>::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>::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