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

Subject: Re: [Boost-users] [graph] Overkill to use graph library for 'small' graphs?
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-09-10 08:34:01

On Wed, Sep 10, 2008 at 5:22 AM, Rainer Thaden <RThaden_at_[hidden]> 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<boost::listS, boost::vecS,
boost::bidirectionalS, VertexProperties, EdgeProperties> 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