Graph optimization

[Amol]

I am working on an interesting graph optimization problem and I would
like to have a few expert opinions for helping me with a solution.

So here goes ...

I have a black box with a complex internal circuitry that is
represented in the form of a graph. I have to abstract the graph by
reducing the number of internal points and constructing cumulative
paths from each input to every possible output in case a path exists (a
series combination of edges). Each edge of the graph has a weight
associated with it. I have to add up all the weights to form the
resultant path.

My representation of the graph is in the form of a linked list
structure as I do not know the number of nodes in the graph apriori ..

A simple situation would be as follows ..

a b a+b
1----> 2 ----> 3 ====> 1 ----> 3

An edge from 1 to 2 with weight 'a' and an edge from 2 to 3 with weight
'b' should be transformed into an edge from 1 to 3 with weight 'a+b'.
Of course, this is a naive example but one can imagine different
scenarios with multiple input arcs and multiple output arcs into/from
internal nodes. I have to find a cumulative path from each input to
every possible output in the most efficient manner. I know the input
points as well as the output points.

Can any C++ guru suggest an detailed algorithm with pseudo code for
solving this problem ?

 

[Victor Bazarov]

I am working on an interesting graph optimization problem and I would
like to have a few expert opinions for helping me with a solution.

So here goes ...
[...]
Can any C++ guru suggest an detailed algorithm with pseudo code for
solving this problem ?

Why are you asking for an algorithm in a _language_ newsgroup? Please
consider posting general programming questions like that to the relevant
newsgroup: 'comp.programming'. Come back when you have a _language_
question, we'll be happy to accommodate you.

V

 

[Daniel T.]

I am working on an interesting graph optimization problem and I would
like to have a few expert opinions for helping me with a solution.

So here goes ...

I have a black box with a complex internal circuitry that is
represented in the form of a graph. I have to abstract the graph by
reducing the number of internal points and constructing cumulative
paths from each input to every possible output in case a path exists (a
series combination of edges). Each edge of the graph has a weight
associated with it. I have to add up all the weights to form the
resultant path.

My representation of the graph is in the form of a linked list
structure as I do not know the number of nodes in the graph apriori ..

A simple situation would be as follows ..

a b a+b
1----> 2 ----> 3 ====> 1 ----> 3

An edge from 1 to 2 with weight 'a' and an edge from 2 to 3 with weight
'b' should be transformed into an edge from 1 to 3 with weight 'a+b'.
Of course, this is a naive example but one can imagine different
scenarios with multiple input arcs and multiple output arcs into/from
internal nodes. I have to find a cumulative path from each input to
every possible output in the most efficient manner. I know the input
points as well as the output points.

Can any C++ guru suggest an detailed algorithm with pseudo code for
solving this problem ?

I would first input the graph as an n-ary tree. Then do a breadth-first
search from each input to all outputs adding the weight of each node as
I go along. There may be a more efficient search algorithm for this
particular problem though. As a bonus, I would have each search run in a
different thread...

If this is professional code, and not a class/learning project, then I
would use the Boost Graph Library.

 

[Kai-Uwe Bux]

I am working on an interesting graph optimization problem and I would
like to have a few expert opinions for helping me with a solution.

So here goes ...

I have a black box with a complex internal circuitry that is
represented in the form of a graph. I have to abstract the graph by
reducing the number of internal points and constructing cumulative
paths from each input to every possible output in case a path exists (a
series combination of edges). Each edge of the graph has a weight
associated with it. I have to add up all the weights to form the
resultant path.

My representation of the graph is in the form of a linked list
structure as I do not know the number of nodes in the graph apriori ..

A simple situation would be as follows ..

a b a+b
1----> 2 ----> 3 ====> 1 ----> 3

An edge from 1 to 2 with weight 'a' and an edge from 2 to 3 with weight
'b' should be transformed into an edge from 1 to 3 with weight 'a+b'.
Of course, this is a naive example but one can imagine different
scenarios with multiple input arcs and multiple output arcs into/from
internal nodes. I have to find a cumulative path from each input to
every possible output in the most efficient manner. I know the input
points as well as the output points.

Can any C++ guru suggest an detailed algorithm with pseudo code for
solving this problem ?

There is nothing C++ specific about your problem. You will be way better off
in comp.programming.

Nonetheless, my understanding is that boost has a nice collection of graph
algorithms. Another thing that comes to mind is LEDA. Here, Google is your
friend.


Best

Kai-Uwe Bux