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 test_norm();
30 test_temp();
31 test_bacon();
32 }
33
34 //////////////////////////////////////
35 // Utility Functions and Types
36 //////////////////////////////////////
37
38
39 struct Actor {
ActorActor40 Actor() { }
ActorActor41 Actor(string const& s) : name(s) { }
42 string name;
43 };
44
45 struct Movie {
MovieMovie46 Movie() { }
MovieMovie47 Movie(string const& s) : name(s) { }
48 string name;
49 };
50
51
52 template <typename Graph>
init_graph(Graph & g)53 void init_graph(Graph& g) {
54 for(int i = 0; i < 6; ++i) {
55 add_vertex(i, g);
56 }
57 }
58
59 template <typename Graph>
label_graph(Graph & g)60 void label_graph(Graph& g)
61 {
62 typedef typename graph_traits<Graph>::vertex_iterator Iter;
63 Iter f, l;
64 int x = 0;
65 for(boost::tie(f, l) = vertices(g); f != l; ++f, ++x) {
66 label_vertex(*f, x, g);
67 }
68 }
69
70 template <typename Graph>
build_graph(Graph & g)71 void build_graph(Graph& g) {
72 // This is the graph shown on the wikipedia page for Graph Theory.
73 add_edge_by_label(5, 3, g);
74 add_edge_by_label(3, 4, g);
75 add_edge_by_label(3, 2, g);
76 add_edge_by_label(4, 1, g);
77 add_edge_by_label(4, 0, g);
78 add_edge_by_label(2, 1, g);
79 add_edge_by_label(1, 0, g);
80 BOOST_ASSERT(num_vertices(g) == 6);
81 BOOST_ASSERT(num_edges(g) == 7);
82 }
83
84 //////////////////////////////////////
85 // Temporal Labelings
86 //////////////////////////////////////
87
test_norm()88 void test_norm() {
89 {
90 typedef labeled_graph<undirected_graph<>, unsigned> Graph;
91 Graph g;
92 init_graph(g);
93 build_graph(g);
94 }
95
96 {
97 typedef labeled_graph<directed_graph<>, unsigned> Graph;
98 Graph g;
99 init_graph(g);
100 build_graph(g);
101 }
102 }
103
104 //////////////////////////////////////
105 // Temporal Labelings
106 //////////////////////////////////////
107
108
test_temp()109 void test_temp() {
110 typedef undirected_graph<> Graph;
111 typedef labeled_graph<Graph*, int> LabGraph;
112 Graph g(6);
113 LabGraph lg(&g);
114 label_graph(lg);
115 build_graph(lg);
116 }
117
118 //////////////////////////////////////
119 // Labeled w/ Properties
120 //////////////////////////////////////
121
test_bacon()122 void test_bacon() {
123 string bacon("Kevin Bacon");
124 string slater("Christian Slater");
125 Movie murder("Murder in the First");
126 {
127
128 typedef labeled_graph<undirected_graph<Actor, Movie>, string> Graph;
129 Graph g;
130 add_vertex(bacon, g);
131 add_vertex(slater, g);
132 add_edge_by_label(bacon, slater, murder, g);
133 }
134
135 {
136 string bacon = "Kevin Bacon";
137 string slater = "Christian Slater";
138
139 typedef labeled_graph<directed_graph<Actor, Movie>, string> Graph;
140 Graph g;
141 add_vertex(bacon, g);
142 add_vertex(slater, g);
143 add_edge_by_label(bacon, slater, murder, g);
144 }
145 }
146