CODEWITHSUNDEEP
c++boostvectorgraph
user3543260
user3543260

Reputation: 27

Implementing a graph with vectors using boost

I'm trying to implement a graph using boost with three separate vectors:

std::vector<std::string> vertex_array;
std::vector<Edge> edge_array;
std::vector<int> weight_array;

Edge is defined as:

typedef std::pair<std::string, std::string> Edge;

and my Graph is defined as:

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

The arrays are all filled with data that I got from an input file, so the first element in the vertex vector would be something like "A", the first element in the edge vector would be something like (B, C) and the first element in the weight vector would be the weight of the first edge in the edge vector, or B-C in this case.

The problem is, I'm not very fluent in C++ and I'm new to boost and graphs as well. I've tried looking at the example code on the boost website, but they all use arrays instead of vectors. I did try this example code:

Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);

and I do have a num_vertices variable, but it still is giving me an error.

Does anyone know how to create a graph with a vector of Edges, vertices and weights that I would eventually be able to use the boost version of Dijkstra's on?

Sorry if this question is really vague or elementary, I seriously don't know anything about using boost and implementing graphs.

Upvotes: 1

Views: 746

Answers (1)

sehe
sehe

Reputation: 393064

From the docs:

The type Graph must be a model of Vertex List Graph and Incidence Graph.

There's an example too that uses an adjacency_list graph.

When you replace listS with vecS in that sample, the exact same response is returned (I haven't checked all the code for sanity of this change though)

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

from this line it seems there is no weight property on edges. It's going to be confusin g for Dijkstra to choose the optimal path without that information. From a quick glance at the docs, I think you can supply a an external weight map. Also note:

Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one.

Upvotes: 1

Related Questions