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>
12 #include <algorithm>
13 #include <boost/graph/adjacency_list.hpp>
14
15 using namespace std;
16 using namespace boost;
17
18 /*
19 Vertex Basics
20
21 This example demonstrates the GGCL Vertex interface.
22
23 Sample output:
24
25 vertices(g) = 0 1 2 3 4
26 vertex id: 0
27 out-edges: (0,1) (0,2) (0,3) (0,4)
28 in-edges: (2,0) (3,0) (4,0)
29 adjacent vertices: 1 2 3 4
30
31 vertex id: 1
32 out-edges:
33 in-edges: (0,1) (3,1) (4,1)
34 adjacent vertices:
35
36 vertex id: 2
37 out-edges: (2,0) (2,4)
38 in-edges: (0,2)
39 adjacent vertices: 0 4
40
41 vertex id: 3
42 out-edges: (3,0) (3,1) (3,4)
43 in-edges: (0,3)
44 adjacent vertices: 0 1 4
45
46 vertex id: 4
47 out-edges: (4,0) (4,1)
48 in-edges: (0,4) (2,4) (3,4)
49 adjacent vertices: 0 1
50
51
52 */
53
54 /* some helper functors for output */
55
56 template < class Graph > struct print_edge
57 {
print_edgeprint_edge58 print_edge(Graph& g) : G(g) {}
59
60 typedef typename boost::graph_traits< Graph >::edge_descriptor Edge;
61 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
operator ()print_edge62 void operator()(Edge e) const
63 {
64 typename boost::property_map< Graph, vertex_index_t >::type id
65 = get(vertex_index, G);
66
67 Vertex src = source(e, G);
68 Vertex targ = target(e, G);
69
70 cout << "(" << id[src] << "," << id[targ] << ") ";
71 }
72
73 Graph& G;
74 };
75
76 template < class Graph > struct print_index
77 {
print_indexprint_index78 print_index(Graph& g) : G(g) {}
79
80 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
operator ()print_index81 void operator()(Vertex c) const
82 {
83 typename boost::property_map< Graph, vertex_index_t >::type id
84 = get(vertex_index, G);
85 cout << id[c] << " ";
86 }
87
88 Graph& G;
89 };
90
91 template < class Graph > struct exercise_vertex
92 {
93 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
94
exercise_vertexexercise_vertex95 exercise_vertex(Graph& _g) : g(_g) {}
96
operator ()exercise_vertex97 void operator()(Vertex v) const
98 {
99 typename boost::property_map< Graph, vertex_index_t >::type id
100 = get(vertex_index, g);
101
102 cout << "vertex id: " << id[v] << endl;
103
104 cout << "out-edges: ";
105 for_each(out_edges(v, g).first, out_edges(v, g).second,
106 print_edge< Graph >(g));
107
108 cout << endl;
109
110 cout << "in-edges: ";
111 for_each(in_edges(v, g).first, in_edges(v, g).second,
112 print_edge< Graph >(g));
113
114 cout << endl;
115
116 cout << "adjacent vertices: ";
117 for_each(adjacent_vertices(v, g).first, adjacent_vertices(v, g).second,
118 print_index< Graph >(g));
119 cout << endl << endl;
120 }
121
122 Graph& g;
123 };
124
main()125 int main()
126 {
127 typedef adjacency_list< vecS, vecS, bidirectionalS > MyGraphType;
128
129 typedef pair< int, int > Pair;
130 Pair edge_array[11] = { Pair(0, 1), Pair(0, 2), Pair(0, 3), Pair(0, 4),
131 Pair(2, 0), Pair(3, 0), Pair(2, 4), Pair(3, 1), Pair(3, 4), Pair(4, 0),
132 Pair(4, 1) };
133
134 /* Construct a graph using the edge_array*/
135 MyGraphType g(5);
136 for (int i = 0; i < 11; ++i)
137 add_edge(edge_array[i].first, edge_array[i].second, g);
138
139 boost::property_map< MyGraphType, vertex_index_t >::type id
140 = get(vertex_index, g);
141
142 cout << "vertices(g) = ";
143 boost::graph_traits< MyGraphType >::vertex_iterator vi;
144 for (vi = vertices(g).first; vi != vertices(g).second; ++vi)
145 std::cout << id[*vi] << " ";
146 std::cout << std::endl;
147
148 /* Use the STL for_each algorithm to "exercise" all
149 of the vertices in the graph */
150 for_each(vertices(g).first, vertices(g).second,
151 exercise_vertex< MyGraphType >(g));
152
153 return 0;
154 }
155