Difference between revisions of "CPP/Boost/BGL/PrimMST"
From ProgrammingExamples
< CPP
Daviddoria (Talk | contribs) (Created page with "==DijkstraDirected.cpp== <source lang="cpp"> #include <iostream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_...") |
Daviddoria (Talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
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 < 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*[]) | int main(int,char*[]) | ||
{ | { | ||
// Create a graph object | // Create a graph object | ||
− | + | GraphType g(3); | |
− | + | // Create a "triangle" | |
− | + | ||
− | EdgeWeightProperty | + | EdgeWeightProperty weight0 = 5; |
− | add_edge( | + | 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 | // "named parameter" signature | ||
− | prim_minimum_spanning_tree(g, & | + | prim_minimum_spanning_tree(g, &predecessors[0], boost::root_vertex(1)); |
− | for (std::size_t i = 0; i != | + | for (std::size_t i = 0; i != predecessors.size(); ++i) { |
− | if ( | + | if (predecessors[i] != i) { |
− | std::cout << "parent[" << i << "] = " << | + | std::cout << "parent[" << i << "] = " << predecessors[i] << std::endl; |
} | } | ||
else { | else { | ||
− | std::cout << "parent[" << i << "] = no | + | std::cout << "parent[" << i << "] = no predecessors (i.e. root node)" << std::endl; |
} | } | ||
} | } | ||
+ | GraphType mst = CreateGraphFromPredecessors(predecessors); | ||
+ | |||
+ | PrintEdges(mst); | ||
return 0; | return 0; |
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)