1 | // (C) Copyright 2009 Andrew Sutton |
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 | #include <iostream> |
8 | #include <string> |
9 | #include <set> |
10 | |
11 | #include <boost/assert.hpp> |
12 | #include <boost/range.hpp> |
13 | |
14 | #include <boost/graph/undirected_graph.hpp> |
15 | #include <boost/graph/directed_graph.hpp> |
16 | #include <boost/graph/labeled_graph.hpp> |
17 | |
18 | #include "typestr.hpp" |
19 | |
20 | using std::cout; |
21 | using std::string; |
22 | using namespace boost; |
23 | |
24 | void test_norm(); |
25 | void test_temp(); |
26 | void test_bacon(); |
27 | |
28 | int main() |
29 | { |
30 | test_norm(); |
31 | test_temp(); |
32 | test_bacon(); |
33 | } |
34 | |
35 | ////////////////////////////////////// |
36 | // Utility Functions and Types |
37 | ////////////////////////////////////// |
38 | |
39 | struct Actor |
40 | { |
41 | Actor() {} |
42 | Actor(string const& s) : name(s) {} |
43 | string name; |
44 | }; |
45 | |
46 | struct Movie |
47 | { |
48 | Movie() {} |
49 | Movie(string const& s) : name(s) {} |
50 | string name; |
51 | }; |
52 | |
53 | template < typename Graph > void init_graph(Graph& g) |
54 | { |
55 | for (int i = 0; i < 6; ++i) |
56 | { |
57 | add_vertex(i, g); |
58 | } |
59 | } |
60 | |
61 | template < typename Graph > void label_graph(Graph& g) |
62 | { |
63 | typedef typename graph_traits< Graph >::vertex_iterator Iter; |
64 | Iter f, l; |
65 | int x = 0; |
66 | for (boost::tie(f, l) = vertices(g); f != l; ++f, ++x) |
67 | { |
68 | label_vertex(*f, x, g); |
69 | } |
70 | } |
71 | |
72 | template < typename Graph > void build_graph(Graph& g) |
73 | { |
74 | // This is the graph shown on the wikipedia page for Graph Theory. |
75 | add_edge_by_label(5, 3, g); |
76 | add_edge_by_label(3, 4, g); |
77 | add_edge_by_label(3, 2, g); |
78 | add_edge_by_label(4, 1, g); |
79 | add_edge_by_label(4, 0, g); |
80 | add_edge_by_label(2, 1, g); |
81 | add_edge_by_label(1, 0, g); |
82 | BOOST_ASSERT(num_vertices(g) == 6); |
83 | BOOST_ASSERT(num_edges(g) == 7); |
84 | } |
85 | |
86 | ////////////////////////////////////// |
87 | // Temporal Labelings |
88 | ////////////////////////////////////// |
89 | |
90 | void test_norm() |
91 | { |
92 | { |
93 | typedef labeled_graph< undirected_graph<>, unsigned > Graph; |
94 | Graph g; |
95 | init_graph(g); |
96 | build_graph(g); |
97 | } |
98 | |
99 | { |
100 | typedef labeled_graph< directed_graph<>, unsigned > Graph; |
101 | Graph g; |
102 | init_graph(g); |
103 | build_graph(g); |
104 | } |
105 | } |
106 | |
107 | ////////////////////////////////////// |
108 | // Temporal Labelings |
109 | ////////////////////////////////////// |
110 | |
111 | void test_temp() |
112 | { |
113 | typedef undirected_graph<> Graph; |
114 | typedef labeled_graph< Graph*, int > LabGraph; |
115 | Graph g(6); |
116 | LabGraph lg(&g); |
117 | label_graph(g&: lg); |
118 | build_graph(g&: lg); |
119 | } |
120 | |
121 | ////////////////////////////////////// |
122 | // Labeled w/ Properties |
123 | ////////////////////////////////////// |
124 | |
125 | void test_bacon() |
126 | { |
127 | string bacon("Kevin Bacon" ); |
128 | string slater("Christian Slater" ); |
129 | Movie murder("Murder in the First" ); |
130 | { |
131 | |
132 | typedef labeled_graph< undirected_graph< Actor, Movie >, string > Graph; |
133 | Graph g; |
134 | add_vertex(l: bacon, g); |
135 | add_vertex(l: slater, g); |
136 | add_edge_by_label(u: bacon, v: slater, p: murder, g); |
137 | } |
138 | |
139 | { |
140 | string bacon = "Kevin Bacon" ; |
141 | string slater = "Christian Slater" ; |
142 | |
143 | typedef labeled_graph< directed_graph< Actor, Movie >, string > Graph; |
144 | Graph g; |
145 | add_vertex(l: bacon, g); |
146 | add_vertex(l: slater, g); |
147 | add_edge_by_label(u: bacon, v: slater, p: murder, g); |
148 | } |
149 | } |
150 | |