1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #include <boost/config.hpp>
11 #include <iostream> // for std::cout
12 #include <utility> // for std::pair
13 #include <algorithm> // for std::for_each
14 #include <boost/utility.hpp> // for boost::tie
15 #include <boost/graph/adjacency_list.hpp>
16 #include <boost/graph/graphviz.hpp>
17
18 using namespace boost;
19
20 template < class Graph > struct exercise_vertex
21 {
exercise_vertexexercise_vertex22 exercise_vertex(Graph& g_, const char name_[]) : g(g_), name(name_) {}
23 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
operator ()exercise_vertex24 void operator()(const Vertex& v) const
25 {
26 using namespace boost;
27 typename property_map< Graph, vertex_index_t >::type vertex_id
28 = get(vertex_index, g);
29 std::cout << "vertex: " << name[get(vertex_id, v)] << std::endl;
30
31 // Write out the outgoing edges
32 std::cout << "\tout-edges: ";
33 typename graph_traits< Graph >::out_edge_iterator out_i, out_end;
34 typename graph_traits< Graph >::edge_descriptor e;
35 for (boost::tie(out_i, out_end) = out_edges(v, g); out_i != out_end;
36 ++out_i)
37 {
38 e = *out_i;
39 Vertex src = source(e, g), targ = target(e, g);
40 std::cout << "(" << name[get(vertex_id, src)] << ","
41 << name[get(vertex_id, targ)] << ") ";
42 }
43 std::cout << std::endl;
44
45 // Write out the incoming edges
46 std::cout << "\tin-edges: ";
47 typename graph_traits< Graph >::in_edge_iterator in_i, in_end;
48 for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
49 {
50 e = *in_i;
51 Vertex src = source(e, g), targ = target(e, g);
52 std::cout << "(" << name[get(vertex_id, src)] << ","
53 << name[get(vertex_id, targ)] << ") ";
54 }
55 std::cout << std::endl;
56
57 // Write out all adjacent vertices
58 std::cout << "\tadjacent vertices: ";
59 typename graph_traits< Graph >::adjacency_iterator ai, ai_end;
60 for (boost::tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end;
61 ++ai)
62 std::cout << name[get(vertex_id, *ai)] << " ";
63 std::cout << std::endl;
64 }
65 Graph& g;
66 const char* name;
67 };
68
main(int,char * [])69 int main(int, char*[])
70 {
71 // create a typedef for the Graph type
72 typedef adjacency_list< vecS, vecS, bidirectionalS, no_property,
73 property< edge_weight_t, float > >
74 Graph;
75
76 // Make convenient labels for the vertices
77 enum
78 {
79 A,
80 B,
81 C,
82 D,
83 E,
84 N
85 };
86 const int num_vertices = N;
87 const char name[] = "ABCDE";
88
89 // writing out the edges in the graph
90 typedef std::pair< int, int > Edge;
91 Edge edge_array[] = {
92 Edge(A, B),
93 Edge(A, D),
94 Edge(C, A),
95 Edge(D, C),
96 Edge(C, E),
97 Edge(B, D),
98 Edge(D, E),
99 };
100 const int num_edges = sizeof(edge_array) / sizeof(edge_array[0]);
101
102 // average transmission delay (in milliseconds) for each connection
103 float transmission_delay[] = { 1.2, 4.5, 2.6, 0.4, 5.2, 1.8, 3.3, 9.1 };
104
105 // declare a graph object, adding the edges and edge properties
106 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
107 // VC++ can't handle the iterator constructor
108 Graph g(num_vertices);
109 property_map< Graph, edge_weight_t >::type weightmap = get(edge_weight, g);
110 for (std::size_t j = 0; j < num_edges; ++j)
111 {
112 graph_traits< Graph >::edge_descriptor e;
113 bool inserted;
114 boost::tie(e, inserted)
115 = add_edge(edge_array[j].first, edge_array[j].second, g);
116 weightmap[e] = transmission_delay[j];
117 }
118 #else
119 Graph g(
120 edge_array, edge_array + num_edges, transmission_delay, num_vertices);
121 #endif
122
123 boost::property_map< Graph, vertex_index_t >::type vertex_id
124 = get(vertex_index, g);
125 boost::property_map< Graph, edge_weight_t >::type trans_delay
126 = get(edge_weight, g);
127
128 std::cout << "vertices(g) = ";
129 typedef graph_traits< Graph >::vertex_iterator vertex_iter;
130 std::pair< vertex_iter, vertex_iter > vp;
131 for (vp = vertices(g); vp.first != vp.second; ++vp.first)
132 std::cout << name[get(vertex_id, *vp.first)] << " ";
133 std::cout << std::endl;
134
135 std::cout << "edges(g) = ";
136 graph_traits< Graph >::edge_iterator ei, ei_end;
137 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
138 std::cout << "(" << name[get(vertex_id, source(*ei, g))] << ","
139 << name[get(vertex_id, target(*ei, g))] << ") ";
140 std::cout << std::endl;
141
142 std::for_each(vertices(g).first, vertices(g).second,
143 exercise_vertex< Graph >(g, name));
144
145 std::map< std::string, std::string > graph_attr, vertex_attr, edge_attr;
146 graph_attr["size"] = "3,3";
147 graph_attr["rankdir"] = "LR";
148 graph_attr["ratio"] = "fill";
149 vertex_attr["shape"] = "circle";
150
151 boost::write_graphviz(std::cout, g, make_label_writer(name),
152 make_label_writer(trans_delay),
153 make_graph_attributes_writer(graph_attr, vertex_attr, edge_attr));
154
155 return 0;
156 }
157