Sign in to follow this  
TheUnbeliever

Couple graph questions

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this