123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145 |
- // (C) Copyright 2009 Andrew Sutton
- //
- // Use, modification and distribution are subject to the
- // Boost Software License, Version 1.0 (See accompanying file
- // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
- #include <iostream>
- #include <string>
- #include <set>
- #include <boost/assert.hpp>
- #include <boost/range.hpp>
- #include <boost/graph/undirected_graph.hpp>
- #include <boost/graph/directed_graph.hpp>
- #include <boost/graph/labeled_graph.hpp>
- #include "typestr.hpp"
- using std::cout;
- using std::string;
- using namespace boost;
- void test_norm();
- void test_temp();
- void test_bacon();
- int main() {
- test_norm();
- test_temp();
- test_bacon();
- }
- //////////////////////////////////////
- // Utility Functions and Types
- //////////////////////////////////////
- struct Actor {
- Actor() { }
- Actor(string const& s) : name(s) { }
- string name;
- };
- struct Movie {
- Movie() { }
- Movie(string const& s) : name(s) { }
- string name;
- };
- template <typename Graph>
- void init_graph(Graph& g) {
- for(int i = 0; i < 6; ++i) {
- add_vertex(i, g);
- }
- }
- template <typename Graph>
- void label_graph(Graph& g)
- {
- typedef typename graph_traits<Graph>::vertex_iterator Iter;
- Iter f, l;
- int x = 0;
- for(boost::tie(f, l) = vertices(g); f != l; ++f, ++x) {
- label_vertex(*f, x, g);
- }
- }
- template <typename Graph>
- void build_graph(Graph& g) {
- // This is the graph shown on the wikipedia page for Graph Theory.
- add_edge_by_label(5, 3, g);
- add_edge_by_label(3, 4, g);
- add_edge_by_label(3, 2, g);
- add_edge_by_label(4, 1, g);
- add_edge_by_label(4, 0, g);
- add_edge_by_label(2, 1, g);
- add_edge_by_label(1, 0, g);
- BOOST_ASSERT(num_vertices(g) == 6);
- BOOST_ASSERT(num_edges(g) == 7);
- }
- //////////////////////////////////////
- // Temporal Labelings
- //////////////////////////////////////
- void test_norm() {
- {
- typedef labeled_graph<undirected_graph<>, unsigned> Graph;
- Graph g;
- init_graph(g);
- build_graph(g);
- }
- {
- typedef labeled_graph<directed_graph<>, unsigned> Graph;
- Graph g;
- init_graph(g);
- build_graph(g);
- }
- }
- //////////////////////////////////////
- // Temporal Labelings
- //////////////////////////////////////
- void test_temp() {
- typedef undirected_graph<> Graph;
- typedef labeled_graph<Graph*, int> LabGraph;
- Graph g(6);
- LabGraph lg(&g);
- label_graph(lg);
- build_graph(lg);
- }
- //////////////////////////////////////
- // Labeled w/ Properties
- //////////////////////////////////////
- void test_bacon() {
- string bacon("Kevin Bacon");
- string slater("Christian Slater");
- Movie murder("Murder in the First");
- {
- typedef labeled_graph<undirected_graph<Actor, Movie>, string> Graph;
- Graph g;
- add_vertex(bacon, g);
- add_vertex(slater, g);
- add_edge_by_label(bacon, slater, murder, g);
- }
- {
- string bacon = "Kevin Bacon";
- string slater = "Christian Slater";
- typedef labeled_graph<directed_graph<Actor, Movie>, string> Graph;
- Graph g;
- add_vertex(bacon, g);
- add_vertex(slater, g);
- add_edge_by_label(bacon, slater, murder, g);
- }
- }
|