ceph/src/boost/libs/graph/example/helper.hpp

   1 // (C) Copyright Andrew Sutton 2007
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_EXAMPLE_HELPER_HPP
   8 #define BOOST_GRAPH_EXAMPLE_HELPER_HPP
   9
  10 #include <string>
  11 #include <sstream>
  12 #include <map>
  13 #include <algorithm>
  14
  15 #include <boost/graph/properties.hpp>
  16
  17 template <typename Graph, typename NameMap, typename VertexMap>
  18 typename boost::graph_traits<Graph>::vertex_descriptor
  19 add_named_vertex(Graph& g, NameMap nm, const std::string& name, VertexMap& vm)
  20 {
  21     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  22     typedef typename VertexMap::iterator Iterator;
  23
  24     Vertex v;
  25     Iterator iter;
  26     bool inserted;
  27     boost::tie(iter, inserted) = vm.insert(make_pair(name, Vertex()));
  28     if(inserted) {
  29         // The name was unique so we need to add a vertex to the graph
  30         v = add_vertex(g);
  31         iter->second = v;
  32         put(nm, v, name);      // store the name in the name map
  33     }
  34     else {
  35         // We had alread inserted this name so we can return the
  36         // associated vertex.
  37         v = iter->second;
  38     }
  39     return v;
  40 }
  41
  42 template <typename Graph, typename NameMap, typename InputStream>
  43 inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
  44 read_graph(Graph& g, NameMap nm, InputStream& is)
  45 {
  46     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  47     std::map<std::string, Vertex> verts;
  48     for(std::string line; std::getline(is, line); ) {
  49         if(line.empty()) continue;
  50         std::size_t index = line.find_first_of(',');
  51         std::string first(line, 0, index);
  52         std::string second(line, index + 1);
  53
  54         Vertex u = add_named_vertex(g, nm, first, verts);
  55         Vertex v = add_named_vertex(g, nm, second, verts);
  56         add_edge(u, v, g);
  57     }
  58     return verts;
  59 }
  60
  61 template <typename Graph, typename InputStream>
  62 inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
  63 read_graph(Graph& g, InputStream& is)
  64 {
  65     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  66     typedef boost::null_property_map<Vertex, std::string> NameMap;
  67     return read_graph(g, NameMap(), is);
  68 }
  69
  70 template <typename Graph, typename NameMap, typename WeightMap, typename InputStream>
  71 inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
  72 read_weighted_graph(Graph& g, NameMap nm, WeightMap wm, InputStream& is)
  73 {
  74     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  75     typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
  76     std::map<std::string, Vertex> verts;
  77     for(std::string line; std::getline(is, line); ) {
  78         if(line.empty()) continue;
  79         std::size_t i = line.find_first_of(',');
  80         std::size_t j = line.find_first_of(',', i + 1);
  81         std::string first(line, 0, i);
  82         std::string second(line, i + 1, j - i - 1);
  83         std::string prob(line, j + 1);
  84
  85         // convert the probability to a float
  86         std::stringstream ss(prob);
  87         float p;
  88         ss >> p;
  89
  90         // add the vertices to the graph
  91         Vertex u = add_named_vertex(g, nm, first, verts);
  92         Vertex v = add_named_vertex(g, nm, second, verts);
  93
  94         // add the edge and set the weight
  95         Edge e = add_edge(u, v, g).first;
  96         put(wm, e, p);
  97     }
  98     return verts;
  99 }
 100
 101
 102 template <typename Graph, typename WeightMap, typename InputStream>
 103 inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
 104 read_weighted_graph(Graph& g, WeightMap wm, InputStream& is)
 105 {
 106     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
 107     typedef boost::null_property_map<Vertex, std::string> NameMap;
 108
 109     return read_weighted_graph(g, NameMap(), wm, is);
 110 }
 111
 112
 113 #endif