123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369 |
- // Copyright (C) 2006 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: Nick Edmonds
- // Andrew Lumsdaine
- // A test of the distributed compressed sparse row graph type
- #include <boost/graph/use_mpi.hpp>
- #include <boost/config.hpp>
- #include <boost/throw_exception.hpp>
- #include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
- #include <boost/graph/distributed/mpi_process_group.hpp>
- #include <boost/graph/distributed/concepts.hpp>
- #include <boost/graph/erdos_renyi_generator.hpp>
- #include <boost/graph/small_world_generator.hpp>
- #include <boost/graph/rmat_graph_generator.hpp>
- #include <boost/graph/breadth_first_search.hpp>
- #include <boost/graph/depth_first_search.hpp>
- #include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
- #include <boost/graph/dijkstra_shortest_paths.hpp>
- #include <boost/graph/distributed/page_rank.hpp>
- #include <boost/graph/distributed/boman_et_al_graph_coloring.hpp>
- #include <boost/graph/connected_components.hpp>
- #include <boost/graph/strong_components.hpp>
- #include <boost/graph/distributed/betweenness_centrality.hpp>
- #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
- #include <boost/graph/distributed/st_connected.hpp>
- #if 0 // Contains internal AdjList types not present in CSR graph
- # include <boost/graph/distributed/connected_components_parallel_search.hpp>
- #endif
- #include <boost/graph/distributed/vertex_list_adaptor.hpp> // Needed for MST
- #include <boost/random/linear_congruential.hpp>
- #include <boost/graph/graphviz.hpp>
- #include <boost/property_map/vector_property_map.hpp>
- #include <boost/test/minimal.hpp>
- #ifdef BOOST_NO_EXCEPTIONS
- void
- boost::throw_exception(std::exception const& ex)
- {
- std::cout << ex.what() << std::endl;
- abort();
- }
- #endif
- /****************************************************************************
- * Edge weight generator iterator *
- ****************************************************************************/
- template<typename F, typename RandomGenerator>
- class generator_iterator
- {
- public:
- typedef std::input_iterator_tag iterator_category;
- typedef typename F::result_type value_type;
- typedef const value_type& reference;
- typedef const value_type* pointer;
- typedef void difference_type;
- explicit
- generator_iterator(RandomGenerator& gen, const F& f = F())
- : f(f), gen(&gen)
- {
- value = this->f(gen);
- }
- reference operator*() const { return value; }
- pointer operator->() const { return &value; }
- generator_iterator& operator++()
- {
- value = f(*gen);
- return *this;
- }
- generator_iterator operator++(int)
- {
- generator_iterator temp(*this);
- ++(*this);
- return temp;
- }
- bool operator==(const generator_iterator& other) const
- { return f == other.f; }
- bool operator!=(const generator_iterator& other) const
- { return !(*this == other); }
- private:
- F f;
- RandomGenerator* gen;
- value_type value;
- };
- template<typename F, typename RandomGenerator>
- inline generator_iterator<F, RandomGenerator>
- make_generator_iterator( RandomGenerator& gen, const F& f)
- { return generator_iterator<F, RandomGenerator>(gen, f); }
- /****************************************************************************
- * Printing DFS Visitor *
- ****************************************************************************/
- struct printing_dfs_visitor
- {
- template<typename Vertex, typename Graph>
- void initialize_vertex(Vertex v, const Graph& g)
- {
- vertex_event("initialize_vertex", v, g);
- }
- template<typename Vertex, typename Graph>
- void start_vertex(Vertex v, const Graph& g)
- {
- vertex_event("start_vertex", v, g);
- }
- template<typename Vertex, typename Graph>
- void discover_vertex(Vertex v, const Graph& g)
- {
- vertex_event("discover_vertex", v, g);
- }
- template<typename Edge, typename Graph>
- void examine_edge(Edge e, const Graph& g)
- {
- edge_event("examine_edge", e, g);
- }
- template<typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g)
- {
- edge_event("tree_edge", e, g);
- }
- template<typename Edge, typename Graph>
- void back_edge(Edge e, const Graph& g)
- {
- edge_event("back_edge", e, g);
- }
- template<typename Edge, typename Graph>
- void forward_or_cross_edge(Edge e, const Graph& g)
- {
- edge_event("forward_or_cross_edge", e, g);
- }
- template<typename Vertex, typename Graph>
- void finish_vertex(Vertex v, const Graph& g)
- {
- vertex_event("finish_vertex", v, g);
- }
- private:
- template<typename Vertex, typename Graph>
- void vertex_event(const char* name, Vertex v, const Graph& g)
- {
- std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
- << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v)
- << ")\n";
- }
- template<typename Edge, typename Graph>
- void edge_event(const char* name, Edge e, const Graph& g)
- {
- std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
- << get_vertex_name(source(e, g), g) << ": "
- << local(source(e, g)) << "@" << owner(source(e, g)) << ", "
- << get_vertex_name(target(e, g), g) << ": "
- << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n";
- }
- };
- using namespace boost;
- using boost::graph::distributed::mpi_process_group;
- typedef int weight_type;
- struct WeightedEdge {
- WeightedEdge(weight_type weight = 0) : weight(weight) { }
-
- weight_type weight;
- template<typename Archiver>
- void serialize(Archiver& ar, const unsigned int /*version*/)
- {
- ar & weight;
- }
- };
- struct VertexProperties {
- VertexProperties(int d = 0)
- : distance(d) { }
- int distance;
- template<typename Archiver>
- void serialize(Archiver& ar, const unsigned int /*version*/)
- {
- ar & distance;
- }
- };
- int test_main(int argc, char* argv[])
- {
- mpi::environment env(argc, argv);
- typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge,
- no_property, distributedS<mpi_process_group> >
- Digraph;
- // Make sure we can build graphs using common graph generators
- typedef sorted_erdos_renyi_iterator<minstd_rand, Digraph> ERIter;
- typedef small_world_iterator<minstd_rand, Digraph> SWIter;
- typedef sorted_rmat_iterator<minstd_rand, Digraph> RMATIter;
- typedef graph_traits<Digraph>::edge_descriptor edge_descriptor;
- int n = 40;
- int k = 3;
- double prob = 0.1;
- int C = 10;
- double a = 0.5, b = 0.1, c = 0.25, d = 0.15;
- int iterations = 50;
- int num_colors = n / 10;
- int lookahead = C / 10;
- minstd_rand gen;
- // Directed Graphs
- Digraph g(ERIter(gen, n, prob), ERIter(),
- make_generator_iterator(gen, uniform_int<int>(0, C)),
- n);
- Digraph g2(SWIter(gen, n, k, prob), SWIter(), n);
- Digraph g3(RMATIter(gen, n, size_t(n*n*prob), a, b, c, d), RMATIter(), n);
- // Test BFS
- breadth_first_search(g, vertex(0, g), visitor(bfs_visitor<>()));
- // Test SSSP Algorithms
- graph::distributed::delta_stepping_shortest_paths(g,
- vertex(0, g),
- dummy_property_map(),
- get(&VertexProperties::distance, g),
- get(&WeightedEdge::weight, g));
- dijkstra_shortest_paths(g, vertex(0, g),
- distance_map(get(&VertexProperties::distance, g)).
- weight_map(get(&WeightedEdge::weight, g)));
- dijkstra_shortest_paths(g, vertex(0, g),
- distance_map(get(&VertexProperties::distance, g)).
- weight_map(get(&WeightedEdge::weight, g)).
- lookahead(lookahead));
- // Test PageRank
- using boost::graph::n_iterations;
- std::vector<double> ranks(num_vertices(g));
- page_rank(g,
- make_iterator_property_map(ranks.begin(),
- get(boost::vertex_index, g)),
- n_iterations(iterations), 0.85, vertex(0, g));
- // Test Graph Coloring
- typedef property_map<Digraph, vertex_index_t>::type vertex_index_map;
- std::vector<int> colors_vec(num_vertices(g));
- iterator_property_map<int*, vertex_index_map> color(&colors_vec[0],
- get(vertex_index, g));
- graph::boman_et_al_graph_coloring(g, color, num_colors);
- // Test DFS
- //
- // DFS requires an undirected graph, currently CSR graphs must be directed
- #if 0
- std::vector<vertex_descriptor> parent(num_vertices(g));
- std::vector<vertex_descriptor> explore(num_vertices(g));
- boost::graph::tsin_depth_first_visit
- (g,
- vertex(0, g),
- printing_dfs_visitor(),
- color,
- make_iterator_property_map(parent.begin(), get(vertex_index, g)),
- make_iterator_property_map(explore.begin(), get(vertex_index, g)),
- get(vertex_index, g));
- #endif
- // Test S-T Connected
- st_connected(g, vertex(0, g), vertex(1, g), color, get(vertex_owner, g));
- // Test Connected Components
- //
- // CC requires an undirected graph, currently CSR graphs must be directed
- #if 0
- std::vector<int> local_components_vec(num_vertices(g));
- typedef iterator_property_map<std::vector<int>::iterator,
- vertex_index_map> ComponentMap;
- ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
- assert(connected_components(g, component) ==
- connected_components_ps(g, component));
- #endif
- // Test Betweenness Centrality
- //
- // Betweenness Centrality is broken at the moment
- typedef iterator_property_map<std::vector<int>::iterator, vertex_index_map>
- CentralityMap;
- std::vector<int> centralityS(num_vertices(g), 0);
- CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
- brandes_betweenness_centrality(g, centrality);
- //
- // Test MST
- //
- std::vector<edge_descriptor> mst_edges;
- dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
- get(&WeightedEdge::weight, g),
- std::back_inserter(mst_edges));
- mst_edges.clear();
- merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g),
- get(&WeightedEdge::weight, g),
- std::back_inserter(mst_edges));
- mst_edges.clear();
- boruvka_then_merge(make_vertex_list_adaptor(g),
- get(&WeightedEdge::weight, g),
- std::back_inserter(mst_edges));
- mst_edges.clear();
- boruvka_mixed_merge(make_vertex_list_adaptor(g),
- get(&WeightedEdge::weight, g),
- std::back_inserter(mst_edges));
- // Test Strong Components
- //
- // Can't build reverse graph of a CSR graph
- #if 0
- std::vector<int> local_components_vec(num_vertices(g));
- typedef iterator_property_map<std::vector<int>::iterator,
- vertex_index_map> ComponentMap;
- ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
- int num_components = strong_components(g, component);
- #endif
- std::ofstream out("dcsr.dot");
- write_graphviz(out, g);
- return 0;
- }
|