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 >
add_named_vertex(Graph & g,NameMap nm,const std::string & name,VertexMap & vm)18 typename boost::graph_traits< Graph >::vertex_descriptor add_named_vertex(
19 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 {
30 // The name was unique so we need to add a vertex to the graph
31 v = add_vertex(g);
32 iter->second = v;
33 put(nm, v, name); // store the name in the name map
34 }
35 else
36 {
37 // We had alread inserted this name so we can return the
38 // associated vertex.
39 v = iter->second;
40 }
41 return v;
42 }
43
44 template < typename Graph, typename NameMap, typename InputStream >
45 inline std::map< std::string,
46 typename boost::graph_traits< Graph >::vertex_descriptor >
read_graph(Graph & g,NameMap nm,InputStream & is)47 read_graph(Graph& g, NameMap nm, InputStream& is)
48 {
49 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
50 std::map< std::string, Vertex > verts;
51 for (std::string line; std::getline(is, line);)
52 {
53 if (line.empty())
54 continue;
55 std::size_t index = line.find_first_of(',');
56 std::string first(line, 0, index);
57 std::string second(line, index + 1);
58
59 Vertex u = add_named_vertex(g, nm, first, verts);
60 Vertex v = add_named_vertex(g, nm, second, verts);
61 add_edge(u, v, g);
62 }
63 return verts;
64 }
65
66 template < typename Graph, typename InputStream >
67 inline std::map< std::string,
68 typename boost::graph_traits< Graph >::vertex_descriptor >
read_graph(Graph & g,InputStream & is)69 read_graph(Graph& g, InputStream& is)
70 {
71 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
72 typedef boost::null_property_map< Vertex, std::string > NameMap;
73 return read_graph(g, NameMap(), is);
74 }
75
76 template < typename Graph, typename NameMap, typename WeightMap,
77 typename InputStream >
78 inline std::map< std::string,
79 typename boost::graph_traits< Graph >::vertex_descriptor >
read_weighted_graph(Graph & g,NameMap nm,WeightMap wm,InputStream & is)80 read_weighted_graph(Graph& g, NameMap nm, WeightMap wm, InputStream& is)
81 {
82 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
83 typedef typename boost::graph_traits< Graph >::edge_descriptor Edge;
84 std::map< std::string, Vertex > verts;
85 for (std::string line; std::getline(is, line);)
86 {
87 if (line.empty())
88 continue;
89 std::size_t i = line.find_first_of(',');
90 std::size_t j = line.find_first_of(',', i + 1);
91 std::string first(line, 0, i);
92 std::string second(line, i + 1, j - i - 1);
93 std::string prob(line, j + 1);
94
95 // convert the probability to a float
96 std::stringstream ss(prob);
97 float p;
98 ss >> p;
99
100 // add the vertices to the graph
101 Vertex u = add_named_vertex(g, nm, first, verts);
102 Vertex v = add_named_vertex(g, nm, second, verts);
103
104 // add the edge and set the weight
105 Edge e = add_edge(u, v, g).first;
106 put(wm, e, p);
107 }
108 return verts;
109 }
110
111 template < typename Graph, typename WeightMap, typename InputStream >
112 inline std::map< std::string,
113 typename boost::graph_traits< Graph >::vertex_descriptor >
read_weighted_graph(Graph & g,WeightMap wm,InputStream & is)114 read_weighted_graph(Graph& g, WeightMap wm, InputStream& is)
115 {
116 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
117 typedef boost::null_property_map< Vertex, std::string > NameMap;
118
119 return read_weighted_graph(g, NameMap(), wm, is);
120 }
121
122 #endif
123