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