Re: [Boost-users] [graph] Overkill to use graph library for 'small' graphs?

On Wed, Sep 10, 2008 at 5:22 AM, Rainer Thaden wrote:

Hi all,

I have to manage connections between different items in an audio control software. Currently, I am using several maps to manage "connections". I was thinking of using a graph for this but there are several questions arising. Maybe, someone can enlighten this:

I am controlling a hardware which has several inputs and outputs and between it a layer of nodes. The inputs are connected to the nodes as well as the outputs. An input can be connected to several nodes, an output only to one node. So, the graph has to represent connections between inputs, nodes, and outputs. (Actually, there are more layers, but to keep it simple I show only these 3). The inputs, outputs, etc. in the end are integers, which are sent to the device. I represent them as enums.

<snip>

Do I have to use a graph with elements of type ints and cast them to my enums?

<snip>

When I e.g. need all vertices, connected to NodeM, I get two ints. One of them represents a member of enum Inputs, the other one a member of enum Outputs. Their numbers overlap, so I can not tell which is an Input and which is an Output (the hardware device needs the numbers starting from 0). Any idea how do solve this?

Hi Rainer, You might want to think about using edge and vertex properties for both of the problems you describe above (having enum labels for vertices and representing input/outputs of vertices). For example, using bundled properties (http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/bundles.html), you could do something like: struct VertexProperties { int enum_label; }; struct EdgeProperties { int Input; int Output; }; Then, define your graph as: typedef boost::adjacency_list graph_t; (You haven't said specifically what type of graph you want, so I made up the first three template parameters.) Now, you can access the label of any vertex v in graph g using "g[v].enum_label", you can access the inputs of a vertex v by iterating over all adjacent edges e to v and using "g[e].Input" (and similarly, Output for outputs).

Secondly, is there a big advantage of using a graph? There are about 25 different inputs, 8 nodes and 10 outputs and 2-3 additional layers. It may be more elegant to use one graph instead of several maps. I can not estimate the effort and performance of the graph. Would it be overkill in both, performance and time to implement to use a graph for that?

The answer depends on what you want to actually do with the graph. One point of putting all of your data in a graph-like structure is that you get to use any of the traversals or algorithms that come with the BGL. Regards, Aaron