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

From ProgrammingExamples
< CPP
Jump to: navigation, search
(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_...")
 
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);
  
     EdgeWeightProperty e1 = 5;
+
     // Create a "triangle"
    add_edge(0, 1, e1, g);
+
  
     EdgeWeightProperty e2 = 3;
+
     EdgeWeightProperty weight0 = 5;
     add_edge(1, 2, e2, g);
+
     add_edge(0, 1, weight0, g);
  
     std::vector < boost::graph_traits < Graph >::vertex_descriptor > parents(num_vertices(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, &parents[0], boost::root_vertex(1));
+
     prim_minimum_spanning_tree(g, &predecessors[0], boost::root_vertex(1));
  
     for (std::size_t i = 0; i != parents.size(); ++i) {
+
     for (std::size_t i = 0; i != predecessors.size(); ++i) {
  
       if (parents[i] != i) {
+
       if (predecessors[i] != i) {
         std::cout << "parent[" << i << "] = " << parents[i] << std::endl;
+
         std::cout << "parent[" << i << "] = " << predecessors[i] << std::endl;
 
       }
 
       }
 
       else {
 
       else {
         std::cout << "parent[" << i << "] = no parent" << std::endl;
+
         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)