# Couple graph questions

This topic is 4062 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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.

1. 1
2. 2
3. 3
4. 4
Rutin
12
5. 5

• 12
• 19
• 10
• 14
• 10
• ### Forum Statistics

• Total Topics
632664
• Total Posts
3007708
• ### Who's Online (See full list)

There are no registered users currently online

×