123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377 |
- // Copyright 2004 The Trustees of Indiana University.
- // Use, modification and distribution is subject to the Boost Software
- // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Authors: Douglas Gregor
- // Andrew Lumsdaine
- #include <boost/config.hpp>
- #ifdef BOOST_MSVC
- // Without disabling this we get hard errors about initialialized pointers:
- #pragma warning(disable:4703)
- #endif
- #include <boost/graph/fruchterman_reingold.hpp>
- #include <boost/graph/random_layout.hpp>
- #include <boost/graph/kamada_kawai_spring_layout.hpp>
- #include <boost/graph/circle_layout.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/point_traits.hpp>
- #include <boost/random/linear_congruential.hpp>
- #include <boost/test/minimal.hpp>
- #include <iostream>
- #include <boost/limits.hpp>
- #include <fstream>
- #include <string>
- using namespace boost;
- enum vertex_position_t { vertex_position };
- namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }
- typedef square_topology<>::point_type point;
- template<typename Graph, typename PositionMap, typename Topology>
- void print_graph_layout(const Graph& g, PositionMap position, const Topology& topology)
- {
- typedef typename Topology::point_type Point;
- // Find min/max ranges
- Point min_point = position[*vertices(g).first], max_point = min_point;
- BGL_FORALL_VERTICES_T(v, g, Graph) {
- min_point = topology.pointwise_min(min_point, position[v]);
- max_point = topology.pointwise_max(max_point, position[v]);
- }
- for (int y = (int)min_point[1]; y <= (int)max_point[1]; ++y) {
- for (int x = (int)min_point[0]; x <= (int)max_point[0]; ++x) {
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- // Find vertex at this position
- typename graph_traits<Graph>::vertices_size_type index = 0;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++index) {
- if ((int)position[*vi][0] == x && (int)position[*vi][1] == y)
- break;
- }
- if (vi == vi_end) std::cout << ' ';
- else std::cout << (char)(index + 'A');
- }
- std::cout << std::endl;
- }
- }
- template<typename Graph, typename PositionMap>
- void dump_graph_layout(std::string name, const Graph& g, PositionMap position)
- {
- std::ofstream out((name + ".dot").c_str());
- out << "graph " << name << " {" << std::endl;
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- out << " n" << get(vertex_index, g, *vi) << "[ pos=\""
- << (int)position[*vi][0] + 25 << ", " << (int)position[*vi][1] + 25
- << "\" ];\n";
- }
- typename graph_traits<Graph>::edge_iterator ei, ei_end;
- for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- out << " n" << get(vertex_index, g, source(*ei, g)) << " -- n"
- << get(vertex_index, g, target(*ei, g)) << ";\n";
- }
- out << "}\n";
- }
- template<typename Graph>
- void
- test_circle_layout(Graph*, typename graph_traits<Graph>::vertices_size_type n)
- {
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
- Graph g(n);
- // Initialize vertex indices
- vertex_iterator vi = vertices(g).first;
- for (vertices_size_type i = 0; i < n; ++i, ++vi)
- put(vertex_index, g, *vi, i);
- circle_graph_layout(g, get(vertex_position, g), 10.0);
- std::cout << "Regular polygon layout with " << n << " points.\n";
- square_topology<> topology;
- print_graph_layout(g, get(vertex_position, g), topology);
- }
- struct simple_edge
- {
- int first, second;
- };
- struct kamada_kawai_done
- {
- kamada_kawai_done() : last_delta() {}
- template<typename Graph>
- bool operator()(double delta_p,
- typename boost::graph_traits<Graph>::vertex_descriptor /*p*/,
- const Graph& /*g*/,
- bool global)
- {
- if (global) {
- double diff = last_delta - delta_p;
- if (diff < 0) diff = -diff;
- last_delta = delta_p;
- return diff < 0.01;
- } else {
- return delta_p < 0.01;
- }
- }
- double last_delta;
- };
- template<typename Graph>
- void
- test_triangle(Graph*)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- Graph g;
-
- vertex_descriptor u = add_vertex(g); put(vertex_index, g, u, 0);
- vertex_descriptor v = add_vertex(g); put(vertex_index, g, v, 1);
- vertex_descriptor w = add_vertex(g); put(vertex_index, g, w, 2);
- edge_descriptor e1 = add_edge(u, v, g).first; put(edge_weight, g, e1, 1.0);
- edge_descriptor e2 = add_edge(v, w, g).first; put(edge_weight, g, e2, 1.0);
- edge_descriptor e3 = add_edge(w, u, g).first; put(edge_weight, g, e3, 1.0);
- circle_graph_layout(g, get(vertex_position, g), 25.0);
- bool ok = kamada_kawai_spring_layout(g,
- get(vertex_position, g),
- get(edge_weight, g),
- square_topology<>(50.0),
- side_length(50.0));
- BOOST_CHECK(ok);
- std::cout << "Triangle layout (Kamada-Kawai).\n";
- print_graph_layout(g, get(vertex_position, g));
- }
- template<typename Graph>
- void
- test_cube(Graph*)
- {
- enum {A, B, C, D, E, F, G, H};
- simple_edge cube_edges[12] = {
- {A, E}, {A, B}, {A, D}, {B, F}, {B, C}, {C, D}, {C, G}, {D, H},
- {E, H}, {E, F}, {F, G}, {G, H}
- };
- Graph g(&cube_edges[0], &cube_edges[12], 8);
-
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- vertex_iterator vi, vi_end;
- int i = 0;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- put(vertex_index, g, *vi, i++);
- edge_iterator ei, ei_end;
- for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- put(edge_weight, g, *ei, 1.0);
- std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')
- << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')
- << ") ";
- }
- std::cerr << std::endl;
- circle_graph_layout(g, get(vertex_position, g), 25.0);
- bool ok = kamada_kawai_spring_layout(g,
- get(vertex_position, g),
- get(edge_weight, g),
- square_topology<>(50.0),
- side_length(50.0),
- kamada_kawai_done());
- BOOST_CHECK(ok);
- std::cout << "Cube layout (Kamada-Kawai).\n";
- print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
- dump_graph_layout("cube", g, get(vertex_position, g));
- minstd_rand gen;
- typedef square_topology<> Topology;
- Topology topology(gen, 50.0);
- std::vector<Topology::point_difference_type> displacements(num_vertices(g));
- rectangle_topology<> rect_top(gen, 0, 0, 50, 50);
- random_graph_layout(g, get(vertex_position, g), rect_top);
- fruchterman_reingold_force_directed_layout
- (g,
- get(vertex_position, g),
- topology,
- square_distance_attractive_force(),
- square_distance_repulsive_force(),
- all_force_pairs(),
- linear_cooling<double>(100),
- make_iterator_property_map(displacements.begin(),
- get(vertex_index, g),
- Topology::point_difference_type()));
- std::cout << "Cube layout (Fruchterman-Reingold).\n";
- print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
- dump_graph_layout("cube-fr", g, get(vertex_position, g));
- }
- template<typename Graph>
- void
- test_triangular(Graph*)
- {
- enum {A, B, C, D, E, F, G, H, I, J};
- simple_edge triangular_edges[18] = {
- {A, B}, {A, C}, {B, C}, {B, D}, {B, E}, {C, E}, {C, F}, {D, E}, {D, G},
- {D, H}, {E, F}, {E, H}, {E, I}, {F, I}, {F, J}, {G, H}, {H, I}, {I, J}
- };
- Graph g(&triangular_edges[0], &triangular_edges[18], 10);
-
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- vertex_iterator vi, vi_end;
- int i = 0;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- put(vertex_index, g, *vi, i++);
- edge_iterator ei, ei_end;
- for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- put(edge_weight, g, *ei, 1.0);
- std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')
- << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')
- << ") ";
- }
- std::cerr << std::endl;
- typedef square_topology<> Topology;
- minstd_rand gen;
- Topology topology(gen, 50.0);
- Topology::point_type origin;
- origin[0] = origin[1] = 50.0;
- Topology::point_difference_type extent;
- extent[0] = extent[1] = 50.0;
- circle_graph_layout(g, get(vertex_position, g), 25.0);
- bool ok = kamada_kawai_spring_layout(g,
- get(vertex_position, g),
- get(edge_weight, g),
- topology,
- side_length(50.0),
- kamada_kawai_done());
- BOOST_CHECK(ok);
- std::cout << "Triangular layout (Kamada-Kawai).\n";
- print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
- dump_graph_layout("triangular-kk", g, get(vertex_position, g));
- rectangle_topology<> rect_top(gen, -25, -25, 25, 25);
- random_graph_layout(g, get(vertex_position, g), rect_top);
- dump_graph_layout("random", g, get(vertex_position, g));
- std::vector<Topology::point_difference_type> displacements(num_vertices(g));
- fruchterman_reingold_force_directed_layout
- (g,
- get(vertex_position, g),
- topology,
- attractive_force(square_distance_attractive_force()).
- cooling(linear_cooling<double>(100)));
- std::cout << "Triangular layout (Fruchterman-Reingold).\n";
- print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
- dump_graph_layout("triangular-fr", g, get(vertex_position, g));
- }
- template<typename Graph>
- void
- test_disconnected(Graph*)
- {
- enum {A, B, C, D, E, F, G, H};
- simple_edge triangular_edges[13] = {
- {A, B}, {B, C}, {C, A},
- {D, E}, {E, F}, {F, G}, {G, H}, {H, D},
- {D, F}, {F, H}, {H, E}, {E, G}, {G, D}
- };
- Graph g(&triangular_edges[0], &triangular_edges[13], 8);
-
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- vertex_iterator vi, vi_end;
- int i = 0;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- put(vertex_index, g, *vi, i++);
- edge_iterator ei, ei_end;
- for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- put(edge_weight, g, *ei, 1.0);
- std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')
- << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')
- << ") ";
- }
- std::cerr << std::endl;
- circle_graph_layout(g, get(vertex_position, g), 25.0);
- bool ok = kamada_kawai_spring_layout(g,
- get(vertex_position, g),
- get(edge_weight, g),
- square_topology<>(50.0),
- side_length(50.0),
- kamada_kawai_done());
- BOOST_CHECK(!ok);
- minstd_rand gen;
- rectangle_topology<> rect_top(gen, -25, -25, 25, 25);
- random_graph_layout(g, get(vertex_position, g), rect_top);
- typedef square_topology<> Topology;
- Topology topology(gen, 50.0);
- std::vector<Topology::point_difference_type> displacements(num_vertices(g));
- fruchterman_reingold_force_directed_layout
- (g,
- get(vertex_position, g),
- topology,
- attractive_force(square_distance_attractive_force()).
- cooling(linear_cooling<double>(50)));
- std::cout << "Disconnected layout (Fruchterman-Reingold).\n";
- print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
- dump_graph_layout("disconnected-fr", g, get(vertex_position, g));
- }
- int test_main(int, char*[])
- {
- typedef adjacency_list<listS, listS, undirectedS,
- // Vertex properties
- property<vertex_index_t, int,
- property<vertex_position_t, point> >,
- // Edge properties
- property<edge_weight_t, double> > Graph;
- test_circle_layout((Graph*)0, 5);
- test_cube((Graph*)0);
- test_triangular((Graph*)0);
- test_disconnected((Graph*)0);
- return 0;
- }
|