Difference between revisions of "CPP/Boost/BGL/PrimMST"

From ProgrammingExamples
< CPP
Jump to: navigation, search
 
Line 1: Line 1:
==DijkstraDirected.cpp==
+
==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>
  
typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
+
using EdgeWeightProperty = boost::property<boost::edge_weight_t, double>;
  
typedef boost::adjacency_list<boost::setS, // OutEdgeContainer
+
using GraphType = boost::adjacency_list<boost::setS, // OutEdgeContainer
                              boost::vecS, // VertexContainer
+
                                        boost::vecS, // VertexContainer
                              boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph;
+
                                        boost::undirectedS, boost::no_property, EdgeWeightProperty> ;
  
using PredecessorContainer = std::vector<boost::graph_traits < Graph >::vertex_descriptor>;
+
using PredecessorContainer = std::vector<boost::graph_traits < GraphType >::vertex_descriptor>;
  
Graph CreateGraphFromPredecessors(const PredecessorContainer& predecessors)
+
GraphType CreateGraphFromPredecessors(const PredecessorContainer& predecessors)
 
{
 
{
     Graph g(predecessors.size());
+
     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(Graph g)
+
void PrintEdges(GraphType g)
 
{
 
{
     typedef boost::graph_traits<Graph>::edge_iterator edge_iter;
+
     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
     Graph g(3);
+
     GraphType g(3);
  
 
     // Create a "triangle"
 
     // Create a "triangle"
Line 73: Line 73:
 
     }
 
     }
  
     Graph mst = CreateGraphFromPredecessors(predecessors);
+
     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)