Difference between revisions of "CPP/Boost/BGL/PrimMST"
From ProgrammingExamples
< CPP
Daviddoria (Talk | contribs) |
Daviddoria (Talk | contribs) |
||
Line 1: | Line 1: | ||
− | == | + | ==PrimMST.cpp== |
<source lang="cpp"> | <source lang="cpp"> | ||
#include <iostream> | #include <iostream> | ||
Line 7: | Line 7: | ||
#include <boost/graph/prim_minimum_spanning_tree.hpp> | #include <boost/graph/prim_minimum_spanning_tree.hpp> | ||
− | + | using EdgeWeightProperty = boost::property<boost::edge_weight_t, double>; | |
− | + | using GraphType = boost::adjacency_list<boost::setS, // OutEdgeContainer | |
− | + | boost::vecS, // VertexContainer | |
− | + | boost::undirectedS, boost::no_property, EdgeWeightProperty> ; | |
− | using PredecessorContainer = std::vector<boost::graph_traits < | + | using PredecessorContainer = std::vector<boost::graph_traits < GraphType >::vertex_descriptor>; |
− | + | GraphType CreateGraphFromPredecessors(const PredecessorContainer& predecessors) | |
{ | { | ||
− | + | GraphType g(predecessors.size()); | |
for(unsigned int vertexID = 0; vertexID < predecessors.size(); ++vertexID) { | for(unsigned int vertexID = 0; vertexID < predecessors.size(); ++vertexID) { | ||
Line 28: | Line 28: | ||
} | } | ||
− | void PrintEdges( | + | void PrintEdges(GraphType g) |
{ | { | ||
− | typedef boost::graph_traits< | + | typedef boost::graph_traits<GraphType>::edge_iterator edge_iter; |
std::pair<edge_iter, edge_iter> edgePair; | std::pair<edge_iter, edge_iter> edgePair; | ||
for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first) { | for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first) { | ||
Line 42: | Line 42: | ||
{ | { | ||
// Create a graph object | // Create a graph object | ||
− | + | GraphType g(3); | |
// Create a "triangle" | // Create a "triangle" | ||
Line 73: | Line 73: | ||
} | } | ||
− | + | GraphType mst = CreateGraphFromPredecessors(predecessors); | |
PrintEdges(mst); | PrintEdges(mst); | ||
Line 79: | Line 79: | ||
return 0; | return 0; | ||
} | } | ||
+ | |||
</source> | </source> | ||
Latest revision as of 21:51, 16 November 2016
PrimMST.cpp
#include <iostream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> using EdgeWeightProperty = boost::property<boost::edge_weight_t, double>; using GraphType = boost::adjacency_list<boost::setS, // OutEdgeContainer boost::vecS, // VertexContainer boost::undirectedS, boost::no_property, EdgeWeightProperty> ; using PredecessorContainer = std::vector<boost::graph_traits < GraphType >::vertex_descriptor>; GraphType CreateGraphFromPredecessors(const PredecessorContainer& predecessors) { GraphType g(predecessors.size()); for(unsigned int vertexID = 0; vertexID < predecessors.size(); ++vertexID) { if(predecessors[vertexID] != vertexID) { add_edge(predecessors[vertexID], vertexID, g); } } return g; } void PrintEdges(GraphType g) { typedef boost::graph_traits<GraphType>::edge_iterator edge_iter; std::pair<edge_iter, edge_iter> edgePair; for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first) { std::cout << *(edgePair.first) << std::endl; } std::cout << std::endl; } int main(int,char*[]) { // Create a graph object GraphType g(3); // Create a "triangle" EdgeWeightProperty weight0 = 5; add_edge(0, 1, weight0, g); EdgeWeightProperty weight1 = 3; add_edge(1, 2, weight1, g); EdgeWeightProperty weight2 = 4; add_edge(0, 2, weight2, g); PrintEdges(g); // Create a container to store the predecessors for each vertex. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. PredecessorContainer predecessors(num_vertices(g)); // "named parameter" signature prim_minimum_spanning_tree(g, &predecessors[0], boost::root_vertex(1)); for (std::size_t i = 0; i != predecessors.size(); ++i) { if (predecessors[i] != i) { std::cout << "parent[" << i << "] = " << predecessors[i] << std::endl; } else { std::cout << "parent[" << i << "] = no predecessors (i.e. root node)" << std::endl; } } GraphType mst = CreateGraphFromPredecessors(predecessors); PrintEdges(mst); return 0; }
CMakeLists.txt
cmake_minimum_required(VERSION 2.6) Project(PrimMST) set(Boost_USE_MULTITHREADED ON) FIND_PACKAGE(Boost 1.38 COMPONENTS program_options required) INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS}) LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS}) ADD_EXECUTABLE(PrimMST PrimMST.cpp)