CODEWITHSUNDEEP
c++algorithmboost
NeerP84
NeerP84

Reputation: 47

c++ Prim minimum spanning tree using Boost Library

I am working on a project where I need to implement Dijkstra's, Prim's and A* algorithms on an input file my professor will provide. I have successfully written working code for Dijkstra's but I am hitting a wall trying to get my same graph to work for Prim's as well. I feel like my problem is not properly having a min spanning tree map to pull my info from but I cant really wrap my head around what the problem is, any help would be greatly appreciated.

structs and graph traits for edges and verts:

typedef boost::adjacency_list_traits<vecS, vecS, undirectedS, listS> GraphTraits;
// type 'Vertex' identifies each vertex uniquely:
typedef GraphTraits::vertex_descriptor Vertex;
// Property type associated to each vertex:
struct VertexProperty {
    string name;  // Name of vertex (i.e., "location")
    Vertex predecessor; // Predecessor along optimal path.
    double distance; // Distance to the goal, along shortest path.
    default_color_type color; // for use by dijkstra.
    VertexProperty(const string& aName = "") : name(aName) { };
};
// Property type associated to each edge:
struct EdgeProperty {
    double weight; // distance to travel along this edge.
    EdgeProperty(double aWeight = 0.0) : weight(aWeight) { };
};
// Type of the graph used:
typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
// Create a global graph object 'g'
Graph g;
// This is a visitor for the dijkstra algorithm. This visitor does nothing special.
struct do_nothing_dijkstra_visitor {
    template <typename Vertex, typename Graph>
    void initialize_vertex(Vertex u, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void examine_vertex(Vertex u, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void examine_edge(Edge e, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void discover_vertex(Vertex u, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void edge_relaxed(Edge e, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void edge_not_relaxed(Edge e, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void finish_vertex(Vertex u, const Graph& g) const { };
};

Variables:

string tempName1, tempName2, tempString, data2;
int weight;
string inputFile;
int choice;
Vertex cur_v, start_v, goal_v;
map<string, Vertex> name2v, name1v;
double totalDist, tempDist;
int numVert = 0;

Graph constructions based on file uploaded:

            //build graph based on file loaded
            getline(fin, tempString); 
            getline(fin, tempString);
            stringstream tempSS(tempString);
            while (getline(tempSS, tempName1, ',')) {
                name2v[tempName1] = add_vertex(VertexProperty(tempName1), g);
                numVert++;
            }
            getline(fin, tempString);
            while (getline(fin, tempString)) {
                tempString.erase(tempString.begin(), tempString.begin() + tempString.find('(') + 1);
                tempString.erase(tempString.begin() + tempString.find(')'), tempString.end());
                stringstream temp_ss(tempString);
                getline(temp_ss, tempName1, ',');
                getline(temp_ss, tempName2, ',');
                temp_ss >> weight;
                add_edge(name2v[tempName1], name2v[tempName2], EdgeProperty(weight), g);
            }
            name1v = name2v;

Prim's call:

cout << "Please enter the Vertex you would like to start at: ";
            cin >> tempName1;
            transform(tempName1.begin(), tempName1.end(), tempName1.begin(), ::toupper);
            start_v = name1v[tempName1];
            prim_minimum_spanning_tree(g, start_v, 
                get(&VertexProperty::predecessor, g), 
                get(&VertexProperty::distance, g),
                get(&EdgeProperty::weight, g), 
                identity_property_map(), 
                do_nothing_dijkstra_visitor());

I tried to just include the code that matters. Like I said this code will work for Dijkstra but I am not sure how to make it work for Prim's. I am thinking I need to add more to the struct for the VertexProperty or have a map to store the min spannning tree. Thanks in advance.

Upvotes: 1

Views: 1001

Answers (1)

sehe
sehe

Reputation: 392833

I don't see what exactly you are asking (aside from code style and quality issues).

Here it is, note

  • the reduced visitor
  • removed confusing comments
  • and of course that I'm generating a random graph here because we don't have your input

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/random.hpp>
#include <fstream>
#include <map>
#include <random>
#include <sstream>

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::undirectedS> GraphTraits;
typedef GraphTraits::vertex_descriptor Vertex;

struct DijkstraStuff {
    Vertex predecessor;
    double distance;
    boost::default_color_type color; // for use by dijkstra.
};

struct VertexProperty : DijkstraStuff {
    std::string name;
    VertexProperty(const std::string &aName = "") : name(aName){};
};

struct EdgeProperty {
    double weight; // distance to travel along this edge.
    EdgeProperty(double aWeight = 0.0) : weight(aWeight){};
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;

struct do_nothing_dijkstra_visitor : boost::default_dijkstra_visitor {};

int main() {
    Graph g;
    std::map<std::string, Vertex> name_map;

    // read graph (random for now)
    {
        std::mt19937 prng{ 42 };
        generate_random_graph(g, 10, 20, prng);

        for (auto vd : boost::make_iterator_range(vertices(g))) {
            name_map[g[vd].name = "NAME" + std::to_string(vd)] = vd;
        }

        std::uniform_real_distribution<double> weight_dist(0, 1);
        for (auto ed : boost::make_iterator_range(edges(g))) {
            g[ed].weight = weight_dist(prng);
        }
    }

    print_graph(g, get(&VertexProperty::name, g));

    Graph::vertex_descriptor start_v;

    std::cout << "Please enter the Vertex you would like to start at: ";
    {
        std::string startName;
        std::cin >> startName;
        std::transform(startName.begin(), startName.end(), startName.begin(),
                       [](uint8_t ch) { return std::toupper(ch); });
        start_v = name_map.at(startName);
    }

    boost::prim_minimum_spanning_tree(g, start_v, get(&VertexProperty::predecessor, g),
          get(&VertexProperty::distance, g), get(&EdgeProperty::weight, g),
          boost::identity_property_map(), do_nothing_dijkstra_visitor());


}

Printing the result

The resulting MST is encoded as the predecessor map. Print it as follows:

for (auto vd : boost::make_iterator_range(vertices(g))) {
    auto p = g[vd].predecessor;
    std::cout << "Pred of " << g[vd].name << " is " << g[p].name << "\n";
}

(This assumes all vertices are in the MST, for simplicity. This is the same as assuming you didn't have unconnected vertices in the input)

Prints (for the given random seed and starting vertex):

Pred of NAME1 is NAME9
Pred of NAME2 is NAME2
Pred of NAME3 is NAME6
Pred of NAME4 is NAME1
Pred of NAME5 is NAME6
Pred of NAME6 is NAME1
Pred of NAME7 is NAME3
Pred of NAME8 is NAME7
Pred of NAME9 is NAME0

Upvotes: 2

Related Questions