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]

Amol wrote:

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
--
Please remove capital As from my address when replying by mail

[Daniel T.]

In article <11*********************@t39g2000cwt.googlegroups. com>,
"Amol" <am*************@gmail.com> wrote:

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.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Kai-Uwe Bux]

Amol wrote:

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