|
|
Boost : |
From: Magnus Ekdahl (maguno_at_[hidden])
Date: 2006-08-24 14:47:23
Douglas Gregor wrote:
>On Aug 24, 2006, at 4:49 AM, Magnus Ekdahl wrote:
>
>
>>First let me argue that there is room for improvement. I have made a
>>test program that constructs 1000 random complete graphs with 1000
>>nodes
>>and the execution time is as follows
>>
>>actually implementing jarniks algorithm
>>prim_minimum_spanning_tree 47.585s
>>
>>current prim (djikstra wrapper) 3m2638s (338% slower)
>>
>>kruskal_minimum_spanning_tree 40m57s (5063% slower)
>>
>>
>
>Those times seem... horrible. What compiler are you using?
>
g++ (GCC) 4.0.4 20060630 (prerelease) (Debian 4.0.3-5)
>With which
>optimization flags?
>
g++ -O3 -g0 -mtune=pentium4
>Can you post the sample code, so we can see what
>is going wrong?
>
>
>
attached :)
>>I also want to take the opportunity to ask about the meaning of the
>>minimum spanning tree algorithm as such, since efficient
>>implementations
>>in the future could be helped a lot by knowing exactly what the
>>problem
>>that should be solved is.
>>
>>
>
>Wikipedia has a decent definition:
>
> http://en.wikipedia.org/wiki/Minimum_spanning_tree
>
>
Nice, the key here is undirected graph, which in the boost context would
mean no parallel edges and self loops I guess.
>
>
>>Given the hardness to understand the actual generality of the MST
>>problem the current implementation tries to solve, I find it difficult
>>to see how efficient algorithms can be heuristically selected. I.e.
>>can
>>you use num_edges(g) as an indicator of sparseness?
>>
>>
>
>We would need to run some benchmarks to determine what heuristic to
>use to dynamically select the most efficient algorithm. We haven't
>really done this yet for the BGL, but we should. MST is one good
>example; all-pairs shortest-paths is another good example, because,
>e.g., the Floyd-Warshall algorithm is much better for dense graphs
>while Johnson's algorithm is much better for sparse graphs. I imagine
>that we could use some kind of threshold for num_edges(g)/
>(num_vertices(g)*num_vertices(g)) to decide whether a graph is sparse
>or dense.
>
>
I'll take this into account. For MST the relaxed_heap is surprisingly
fast though, so it will be an issue when something faster is found.
My original intension was to submit an O(|E|) array implementation for
the complete graph case. But it is for current test cases slower than
prim/relaxed so it have to be improved first (if at all possible).
-- Magnus Ekdahl
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <iostream>
#include <cstdlib>
#include<string>
#include<list>
#include <iostream>
#include "mst.h"
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <iostream>
#include <vector>
#include <boost/graph/random.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <algorithm>
#include <boost/pending/fibonacci_heap.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/pending/relaxed_heap.hpp>
using namespace std;
using namespace boost;
typedef adjacency_list < vecS, vecS, undirectedS, no_property, property < edge_weight_t, double > > Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::pair<int, int> E;
void initGraph(Graph& g,const unsigned size)
{
for(unsigned i=0;i<size;i++)
{
for(unsigned j=i+1;j<size;j++)
add_edge(i, j, g);
}
}
void randGraph(Graph& g, const unsigned size)
{
property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
graph_traits<Graph>::edge_iterator ei, eiend;
for (boost::tie(ei, eiend) = edges(g); ei != eiend; ++ei)
{
weightmap[*ei] = rand();
}
}
int main(int argc, char* argv[])
{
srand(0);
const unsigned NR_TESTS=1000;
const unsigned size=1000;
vector < Edge > spanning_tree_mwst;
Graph g(size);
std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
initGraph(g,size);
cout << "Generating randum graphs with weights from 0 to "<< RAND_MAX << " of size "<< size <<"\n";
for(unsigned i=0;i<NR_TESTS;i++)
{
randGraph(g,size);
//prim_minimum_spanning_tree2(g,std::back_inserter(spanning_tree_mwst));
prim_minimum_spanning_tree(g,&p[0]);
spanning_tree_mwst.clear();
}
}
/***************************************************************************
* Copyright (C) 2006 by Magnus Ekdahl *
* maguno_at_[hidden] *
* *
* Permission is hereby granted, free of charge, to any person obtaining *
* a copy of this software and associated documentation files (the *
* "Software"), to deal in the Software without restriction, including *
* without limitation the rights to use, copy, modify, merge, publish, *
* distribute, sublicense, and/or sell copies of the Software, and to *
* permit persons to whom the Software is furnished to do so, subject to *
* the following conditions: *
* *
* The above copyright notice and this permission notice shall be *
* included in all copies or substantial portions of the Software. *
* *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, *
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF *
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. *
* IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR *
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
* OTHER DEALINGS IN THE SOFTWARE. *
***************************************************************************/
#ifndef __MST_HH__
#define __MST_HH__
#include <map>
#include <functional>
#include <boost/graph/adjacency_list.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/pending/relaxed_heap.hpp>
#include <iostream>
namespace boost
{
namespace detail
{
// This is Prim's algorithm to calculate the Minimum Spanning Tree
// for an undirected graph with weighted edges.
template <class Graph, class OutputIterator, class Weight>
inline void
prim_mst_impl(const Graph& G,
OutputIterator spanning_tree_edges,Weight weight)
{
function_requires<VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::edge_descriptor Edge;
function_requires<ReadablePropertyMapConcept<Weight, Edge> >();
typedef typename property_traits<Weight>::value_type W_value;
function_requires<ComparableConcept<W_value> >();
if (num_vertices(G) <= 1) return; // Nothing to do in this case
typedef typename graph_traits<Graph>::vertices_size_type size_type;
typedef typename boost::property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, G);
const size_type size = num_vertices(G);
W_value* the_weights = new W_value[size];
Edge* the_edges = new Edge[size];
bool* vertices_in_mwst = new bool[size];
bool* discovered_vertices = new bool[size];
typedef indirect_cmp<W_value*,std::less<W_value> > ICmp;
ICmp cmp(&the_weights[0], std::less<W_value>());
relaxed_heap<size_type, ICmp> Q(size, cmp);
Q.push(0);
while(Q.empty()!=true)
{
const size_type u=Q.top();
Q.pop();
vertices_in_mwst[u]=true;
typename graph_traits<Graph>::out_edge_iterator ei, eiend;
for (boost::tie(ei,eiend)=out_edges(u,G); ei != eiend; ++ei)
{
const size_type v = index[target(*ei,G)];
if (vertices_in_mwst[v]==false)
{
W_value w = get(edge_weight, G,*ei);
if(discovered_vertices[v]==false)
{
discovered_vertices[v]=true;
the_weights[v]=w;
the_edges[v]=*ei;
Q.push(v);
}
else if(w<the_weights[v])
{
the_weights[v]=w;
the_edges[v]=*ei;
Q.update(v);
}
}
}
}
for(size_type i=1;i<size;++i)
*spanning_tree_edges++ = the_edges[i];
delete the_weights;
delete the_edges;
delete vertices_in_mwst;
delete discovered_vertices;
}
}
template <class VertexListGraph, class PredecessorMap>
inline void prim_minimum_spanning_tree2
(const VertexListGraph& g, PredecessorMap p_map)
{
detail::prim_mst_impl(g, p_map,get(edge_weight, g));
}
}
#endif
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk