Couple graph questions
Author
First question is a terminology one, to give me something to search for.
Is there a specific name for a graph where every vertex is connected by a weighted edge to every other vertex?
Follow up question: what is a reasonably efficient/common representation for such a graph?
Background: I thought I'd have a crack at writing a multithreaded/memoizing TSP solver using the Boost libraries, particularly the BGL, as a familiarization process for some of the tools it offers.
What you're thinking of is a complete graph. You could probably represent such a graph using the upper/lower triangle of a square matrix. If the edges are directional, then you can use the whole matrix. Each element would simply give the weight going from the row node to the column node, and/or vice versa.
Author
Thanks, that looks to be what I need.
Incidentally, am I right in saying that the BGL adjacency_matrix class doesn't support weighted edges (and that I would therefore either have to roll my own, which should be easy enough, or use the adjacency_list class — which wouldn't be the most efficient use of space but that's more or less irrelevant).
Incidentally, am I right in saying that the BGL adjacency_matrix class doesn't support weighted edges (and that I would therefore either have to roll my own, which should be easy enough, or use the adjacency_list class — which wouldn't be the most efficient use of space but that's more or less irrelevant).
If you know the graph is dense (complete graphs are dense), then you're almost always going to be better off storing the graph as an adjacency matrix.
For a hand rolled adjacency matrix you can store the costs within the matrix. If you use BGL I'm pretty sure you need to use property maps. See http://boost.org/libs/graph/example/undirected.cpp for an example.
I would recommend avoiding BGL and even C++ in the short term, some type of scripting language is probably going to be much easier to prototype this in. Once your prototype is correct, then port it to use BGL or some other graph library.
For a hand rolled adjacency matrix you can store the costs within the matrix. If you use BGL I'm pretty sure you need to use property maps. See http://boost.org/libs/graph/example/undirected.cpp for an example.
I would recommend avoiding BGL and even C++ in the short term, some type of scripting language is probably going to be much easier to prototype this in. Once your prototype is correct, then port it to use BGL or some other graph library.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
