Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:42:49 

0001 //=======================================================================
0002 // Copyright 2001 Universite Joseph Fourier, Grenoble.
0003 // Author: Francois Faure
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 #ifndef BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
0010 #define BOOST_GRAPH_ADJACENCY_LIST_IO_HPP
0011 
0012 #include <iostream>
0013 #include <vector>
0014 #include <boost/graph/adjacency_list.hpp>
0015 #include <boost/graph/iteration_macros.hpp>
0016 #include <cctype>
0017 
0018 // Method read to parse an adjacency list from an input stream. Examples:
0019 // cin >> read( G );
0020 // cin >> read( G, NodePropertySubset(), EdgepropertySubset() );
0021 //
0022 // Method write to print an adjacency list to an output stream. Examples:
0023 // cout << write( G );
0024 // cout << write( G, NodePropertySubset(), EdgepropertySubset() );
0025 
0026 namespace boost
0027 {
0028 
0029 /* outline
0030         - basic property input
0031         - get property subset
0032         - graph parser
0033         - property printer
0034         - graph printer
0035         - user methods
0036 */
0037 
0038 //===========================================================================
0039 // basic property input
0040 
0041 template < class Tag, class Value, class Next >
0042 std::istream& operator>>(std::istream& in, property< Tag, Value, Next >& p)
0043 {
0044     in >> p.m_value >> p.m_base; // houpla !!
0045     return in;
0046 }
0047 
0048 template < class Tag, class Value >
0049 std::istream& operator>>(
0050     std::istream& in, property< Tag, Value, no_property >& p)
0051 {
0052     in >> p.m_value;
0053     return in;
0054 }
0055 
0056 inline std::istream& operator>>(std::istream& in, no_property&) { return in; }
0057 
0058 // basic property input
0059 //===========================================================================
0060 // get property subsets
0061 
0062 // get a single property tagged Stag
0063 template < class Tag, class Value, class Next, class V, class Stag >
0064 void get(property< Tag, Value, Next >& p, const V& v, Stag s)
0065 {
0066     get(p.m_base, v, s);
0067 }
0068 
0069 template < class Value, class Next, class V, class Stag >
0070 void get(property< Stag, Value, Next >& p, const V& v, Stag)
0071 {
0072     p.m_value = v;
0073 }
0074 
0075 // get a subset of properties tagged Stag
0076 template < class Tag, class Value, class Next, class Stag, class Svalue,
0077     class Snext >
0078 void getSubset(
0079     property< Tag, Value, Next >& p, const property< Stag, Svalue, Snext >& s)
0080 {
0081     get(p, s.m_value, Stag());
0082     getSubset(p, s.m_base);
0083 }
0084 
0085 template < class Tag, class Value, class Next, class Stag, class Svalue >
0086 void getSubset(property< Tag, Value, Next >& p,
0087     const property< Stag, Svalue, no_property >& s)
0088 {
0089     get(p, s.m_value, Stag());
0090 }
0091 
0092 inline void getSubset(no_property&, const no_property&) {}
0093 
0094 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
0095 template < typename T, typename U > void getSubset(T& p, const U& s) { p = s; }
0096 
0097 template < typename T > void getSubset(T&, const no_property&) {}
0098 
0099 #endif
0100 
0101 //  get property subset
0102 //===========================================================================
0103 // graph parser
0104 typedef enum
0105 {
0106     PARSE_NUM_NODES,
0107     PARSE_VERTEX,
0108     PARSE_EDGE
0109 } GraphParserState;
0110 
0111 template < class Graph_t, class VertexProperty, class EdgeProperty,
0112     class VertexPropertySubset, class EdgePropertySubset >
0113 struct GraphParser
0114 {
0115 
0116     typedef Graph_t Graph;
0117 
0118     GraphParser(Graph* g) : graph(g) {}
0119 
0120     GraphParser& operator()(std::istream& in)
0121     {
0122         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0123         std::vector< Vertex > nodes;
0124 
0125         GraphParserState state = PARSE_VERTEX;
0126 
0127         unsigned int numLine = 1;
0128         char c;
0129         while (in.get(c))
0130         {
0131             if (c == '#')
0132                 skip(in);
0133             else if (c == 'n')
0134                 state = PARSE_NUM_NODES;
0135             else if (c == 'v')
0136                 state = PARSE_VERTEX;
0137             else if (c == 'e')
0138                 state = PARSE_EDGE;
0139             else if (c == '\n')
0140                 numLine++;
0141             else if (!std::isspace(c))
0142             {
0143                 in.putback(c);
0144                 if (state == PARSE_VERTEX)
0145                 {
0146                     VertexPropertySubset readProp;
0147                     if (in >> readProp)
0148                     {
0149                         VertexProperty vp;
0150                         getSubset(vp, readProp);
0151                         nodes.push_back(add_vertex(vp, *graph));
0152                     }
0153                     else
0154                         std::cerr << "read vertex, parse error at line"
0155                                   << numLine << std::endl;
0156                 }
0157                 else if (state == PARSE_EDGE)
0158                 {
0159                     int source, target;
0160                     EdgePropertySubset readProp;
0161                     in >> source >> target;
0162                     if (in >> readProp)
0163                     {
0164                         EdgeProperty ep;
0165                         getSubset(ep, readProp);
0166                         add_edge(nodes[source], nodes[target], ep, *graph);
0167                     }
0168                     else
0169                         std::cerr << "read edge, parse error at line" << numLine
0170                                   << std::endl;
0171                 }
0172                 else
0173                 { // state == PARSE_NUM_NODES
0174                     int n;
0175                     if (in >> n)
0176                     {
0177                         for (int i = 0; i < n; ++i)
0178                             nodes.push_back(add_vertex(*graph));
0179                     }
0180                     else
0181                         std::cerr << "read num_nodes, parse error at line "
0182                                   << numLine << std::endl;
0183                 }
0184             }
0185         }
0186         return (*this);
0187     }
0188 
0189 protected:
0190     Graph* graph;
0191 
0192     void skip(std::istream& in)
0193     {
0194         char c = 0;
0195         while (c != '\n' && !in.eof())
0196             in.get(c);
0197         in.putback(c);
0198     }
0199 };
0200 
0201 // parser
0202 //=======================================================================
0203 // property printer
0204 
0205 #if defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
0206 template < class Graph, class Property > struct PropertyPrinter
0207 {
0208     typedef typename Property::value_type Value;
0209     typedef typename Property::tag_type Tag;
0210     typedef typename Property::next_type Next;
0211 
0212     PropertyPrinter(const Graph& g) : graph(&g) {}
0213 
0214     template < class Val >
0215     PropertyPrinter& operator()(std::ostream& out, const Val& v)
0216     {
0217         typename property_map< Graph, Tag >::const_type ps = get(Tag(), *graph);
0218         out << ps[v] << " ";
0219         PropertyPrinter< Graph, Next > print(*graph);
0220         print(out, v);
0221         return (*this);
0222     }
0223 
0224 private:
0225     const Graph* graph;
0226 };
0227 #else
0228 template < class Graph, typename Property > struct PropertyPrinter
0229 {
0230     PropertyPrinter(const Graph& g) : graph(&g) {}
0231 
0232     template < class Val >
0233     PropertyPrinter& operator()(std::ostream& out, const Val& v)
0234     {
0235         out << (*graph)[v] << " ";
0236         return (*this);
0237     }
0238 
0239 private:
0240     const Graph* graph;
0241 };
0242 
0243 template < class Graph, typename Tag, typename Value, typename Next >
0244 struct PropertyPrinter< Graph, property< Tag, Value, Next > >
0245 {
0246     PropertyPrinter(const Graph& g) : graph(&g) {}
0247 
0248     template < class Val >
0249     PropertyPrinter& operator()(std::ostream& out, const Val& v)
0250     {
0251         typename property_map< Graph, Tag >::const_type ps = get(Tag(), *graph);
0252         out << ps[v] << " ";
0253         PropertyPrinter< Graph, Next > print(*graph);
0254         print(out, v);
0255         return (*this);
0256     }
0257 
0258 private:
0259     const Graph* graph;
0260 };
0261 #endif
0262 
0263 template < class Graph > struct PropertyPrinter< Graph, no_property >
0264 {
0265     PropertyPrinter(const Graph&) {}
0266 
0267     template < class Val >
0268     PropertyPrinter& operator()(std::ostream&, const Val&)
0269     {
0270         return *this;
0271     }
0272 };
0273 
0274 // property printer
0275 //=========================================================================
0276 // graph printer
0277 
0278 template < class Graph_t, class EdgeProperty > struct EdgePrinter
0279 {
0280 
0281     typedef Graph_t Graph;
0282     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0283 
0284     EdgePrinter(const Graph& g) : graph(g) {}
0285 
0286     const EdgePrinter& operator()(std::ostream& out) const
0287     {
0288         // assign indices to vertices
0289         std::map< Vertex, int > indices;
0290         int num = 0;
0291         BGL_FORALL_VERTICES_T(v, graph, Graph) { indices[v] = num++; }
0292 
0293         // write edges
0294         PropertyPrinter< Graph, EdgeProperty > print_Edge(graph);
0295         out << "e" << std::endl;
0296         BGL_FORALL_EDGES_T(e, graph, Graph)
0297         {
0298             out << indices[source(e, graph)] << " " << indices[target(e, graph)]
0299                 << "  ";
0300             print_Edge(out, e);
0301             out << std::endl;
0302         }
0303         out << std::endl;
0304         return (*this);
0305     }
0306 
0307 protected:
0308     const Graph& graph;
0309 };
0310 
0311 template < class Graph, class V, class E >
0312 struct GraphPrinter : public EdgePrinter< Graph, E >
0313 {
0314     GraphPrinter(const Graph& g) : EdgePrinter< Graph, E >(g) {}
0315 
0316     const GraphPrinter& operator()(std::ostream& out) const
0317     {
0318         PropertyPrinter< Graph, V > printNode(this->graph);
0319         out << "v" << std::endl;
0320         BGL_FORALL_VERTICES_T(v, this->graph, Graph)
0321         {
0322             printNode(out, v);
0323             out << std::endl;
0324         }
0325 
0326         EdgePrinter< Graph, E >::operator()(out);
0327         return (*this);
0328     }
0329 };
0330 
0331 template < class Graph, class E >
0332 struct GraphPrinter< Graph, no_property, E > : public EdgePrinter< Graph, E >
0333 {
0334     GraphPrinter(const Graph& g) : EdgePrinter< Graph, E >(g) {}
0335 
0336     const GraphPrinter& operator()(std::ostream& out) const
0337     {
0338         out << "n " << num_vertices(this->graph) << std::endl;
0339         EdgePrinter< Graph, E >::operator()(out);
0340         return (*this);
0341     }
0342 };
0343 
0344 // graph printer
0345 //=========================================================================
0346 // user methods
0347 
0348 /// input stream for reading a graph
0349 template < class Graph, class VP, class EP, class VPS, class EPS >
0350 std::istream& operator>>(
0351     std::istream& in, GraphParser< Graph, VP, EP, VPS, EPS > gp)
0352 {
0353     gp(in);
0354     return in;
0355 }
0356 
0357 /// graph parser for given subsets of internal vertex and edge properties
0358 template < class EL, class VL, class D, class VP, class EP, class GP, class VPS,
0359     class EPS >
0360 GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VPS, EPS > read(
0361     adjacency_list< EL, VL, D, VP, EP, GP >& g, VPS vps, EPS eps)
0362 {
0363     return GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VPS,
0364         EPS >(&g);
0365 }
0366 
0367 /// graph parser for all internal vertex and edge properties
0368 template < class EL, class VL, class D, class VP, class EP, class GP >
0369 GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VP, EP > read(
0370     adjacency_list< EL, VL, D, VP, EP, GP >& g)
0371 {
0372     return GraphParser< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP, VP,
0373         EP >(&g);
0374 }
0375 
0376 /// output stream for writing a graph
0377 template < class Graph, class VP, class EP >
0378 std::ostream& operator<<(
0379     std::ostream& out, const GraphPrinter< Graph, VP, EP >& gp)
0380 {
0381     gp(out);
0382     return out;
0383 }
0384 
0385 /// write the graph with given property subsets
0386 template < class EL, class VL, class D, class VP, class EP, class GP, class VPS,
0387     class EPS >
0388 GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VPS, EPS > write(
0389     const adjacency_list< EL, VL, D, VP, EP, GP >& g, VPS, EPS)
0390 {
0391     return GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VPS, EPS >(g);
0392 }
0393 
0394 /// write the graph with all internal vertex and edge properties
0395 template < class EL, class VL, class D, class VP, class EP, class GP >
0396 GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP > write(
0397     const adjacency_list< EL, VL, D, VP, EP, GP >& g)
0398 {
0399     return GraphPrinter< adjacency_list< EL, VL, D, VP, EP, GP >, VP, EP >(g);
0400 }
0401 
0402 // user methods
0403 //=========================================================================
0404 } // boost
0405 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!