CPP/Boost/BGL/PrimMST - Revision history

Daviddoria at 01:51, 17 November 2016

2016-11-17T01:51:03Z

Daviddoria at 11:58, 10 November 2016

2016-11-10T11:58:11Z

Daviddoria: Created page with "==DijkstraDirected.cpp== #include #include #include #include
2016-11-10T11:45:19Z

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_..."

New page
==DijkstraDirected.cpp==
<source lang="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;

int main(int,char*[])
{
// Create a graph object
Graph g(3);

EdgeWeightProperty e1 = 5;
add_edge(0, 1, e1, g);

EdgeWeightProperty e2 = 3;
add_edge(1, 2, e2, g);

std::vector < boost::graph_traits < Graph >::vertex_descriptor > parents(num_vertices(g));

// "named parameter" signature
prim_minimum_spanning_tree(g, &parents[0], boost::root_vertex(1));

for (std::size_t i = 0; i != parents.size(); ++i) {

if (parents[i] != i) {
std::cout << "parent[" << i << "] = " << parents[i] << std::endl;
}
else {
std::cout << "parent[" << i << "] = no parent" << std::endl;
}
}

return 0;
}

</source>

==CMakeLists.txt==
<source lang="cmake">
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)

</source>

@@ Line 1: / Line 1: @@
-==DijkstraDirected.cpp==
+==PrimMST.cpp==
 <source lang="cpp">
 #include <iostream>
@@ Line 7: / Line 7: @@
 #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) {
@@ 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;
      for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first) {
@@ Line 42: / Line 42: @@
+{
      // Create a graph object
-     Graph g(3);
+     GraphType g(3);
      // Create a "triangle"
@@ Line 73: / Line 73: @@
+     }
-     Graph mst = CreateGraphFromPredecessors(predecessors);
+     GraphType mst = CreateGraphFromPredecessors(predecessors);
      PrintEdges(mst);
@@ Line 79: / Line 79: @@
      return 0;
+}
 </source>

@@ Line 12: / Line 12: @@
                                boost::vecS, // VertexContainer
                                boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph;
 int main(int,char*[])
@@ Line 18: / Line 44: @@
      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;
      // "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 {
-         std::cout << "parent[" << i << "] = no parent" << std::endl;
+         std::cout << "parent[" << i << "] = no predecessors (i.e. root node)" << std::endl;
+       }
+     }
      return 0;
+}
 </source>