[graph] Overkill to use graph library for 'small' graphs?
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. So I have, e.g. enum Inputs{ Input1 = 0, Input2, InputNone }; enum Nodes{ NodeM=0, NodeN, NodeNone }; enum Outputs{ AnalogOut1 = 0, AnalogOut2 OutputNone }; Now, to use graphs, I have to define vertices. These have to be of "one" type, as far as I understand that. How do I use the enums as shown above? A vertice-value may be in enum Inputs or Nodes or Outputs. Do I have to use a graph with elements of type ints and cast them to my enums? From the introduction to BGL, modified: const int num_vertices = InputNone + NodeNone + OutputNone; // writing out the edges in the graph typedef std::pair<int, int> Edge; Edge edge_array[] = { Edge(Input1,NodeM), Edge(Input2,NodeN), Edge(AnalogOut1,NodeM), Edge(AnalogOut2,NodeN)}; const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]); // declare a graph object Graph g(num_vertices); // add the edges to the graph object for (int i = 0; i < num_edges; ++i) add_edge(edge_array[i].first, edge_array[i].second, g); 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? 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? Thanks in advance and regards, Rainer
On Wed, Sep 10, 2008 at 5:22 AM, Rainer Thaden <RThaden@web.de> 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
Dear Aaron,
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;
thanks for your quick answer. I understand what you are suggesting. I thought a bit further on that. Apart from the integers, I have some classes representing the Inputs and Outputs, etc. which allow to make settings on them, which contain a name and additional parameters etc. Also, there are additional layers, which the audio signal runs through. It would be desirable to have something like "Give me the output that is connected to input 1" But also: "give me the audio processing block that is connected to NodeM". As there are existing classes, it would be nice if I could just use these for the graph. I guess, all these, then, must have a common base class, right? And I need RTTI to figure out the class type after I asked the graph for the neighbour of NodeM, e.g., right? I expect some benefit in simplicity and maintainability of the code. Currently I have a "RoutingManager" which I ask for an Output connected to a Node, etc. This manager has a lot of different methods which makes it a bit hard to maintain. Kind regards, Rainer
participants (2)
-
Aaron Windsor -
Rainer Thaden