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
main()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 {
ActorActor41 Actor() {}
ActorActor42 Actor(string const& s) : name(s) {}
43 string name;
44 };
45
46 struct Movie
47 {
MovieMovie48 Movie() {}
MovieMovie49 Movie(string const& s) : name(s) {}
50 string name;
51 };
52
init_graph(Graph & g)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
label_graph(Graph & g)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
build_graph(Graph & g)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
test_norm()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
test_temp()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(lg);
118 build_graph(lg);
119 }
120
121 //////////////////////////////////////
122 // Labeled w/ Properties
123 //////////////////////////////////////
124
test_bacon()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(bacon, g);
135 add_vertex(slater, g);
136 add_edge_by_label(bacon, slater, 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(bacon, g);
146 add_vertex(slater, g);
147 add_edge_by_label(bacon, slater, murder, g);
148 }
149 }
150