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) |
||
Line 12: | Line 12: | ||
boost::vecS, // VertexContainer | boost::vecS, // VertexContainer | ||
boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph; | boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph; | ||
+ | |||
+ | using PredecessorContainer = std::vector<boost::graph_traits < Graph >::vertex_descriptor>; | ||
+ | |||
+ | Graph CreateGraphFromPredecessors(const PredecessorContainer& predecessors) | ||
+ | { | ||
+ | Graph 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(Graph g) | ||
+ | { | ||
+ | typedef boost::graph_traits<Graph>::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*[]) | ||
Line 18: | Line 44: | ||
Graph g(3); | Graph 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; |
} | } | ||
} | } | ||
+ | Graph mst = CreateGraphFromPredecessors(predecessors); | ||
+ | |||
+ | PrintEdges(mst); | ||
return 0; | return 0; | ||
} | } | ||
− | |||
</source> | </source> | ||
Revision as of 07:58, 10 November 2016
DijkstraDirected.cpp
#include <iostream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty; typedef boost::adjacency_list<boost::setS, // OutEdgeContainer boost::vecS, // VertexContainer boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph; using PredecessorContainer = std::vector<boost::graph_traits < Graph >::vertex_descriptor>; Graph CreateGraphFromPredecessors(const PredecessorContainer& predecessors) { Graph 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(Graph g) { typedef boost::graph_traits<Graph>::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 Graph 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; } } Graph 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)