Re: Graph optimization

amol.panchabhai@xxxxxxxxx wrote:

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.

It is unclear from your description what you know about the box.
Normally, "black box" means that you have no /a priori/ description of
the contents, yet the description indicates you might know weights of
edges between internal nodes. This is confusing.

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 ..

Forget the data structure for a moment. What information, exactly,
are you given about your graph?

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.

Again what information do you have? If you know the graph and the
edge weights, you can use Dijkstra's algorithm for shortest path, if
that is what you are seeking.

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

Oh, sorry, I'm not a C++ guru. Ignore this post.

--
Thad
.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • Re: Standard graph API?
    ... I would rather have the weights be a separate dict ... >or function or whatever passed to the graph algorithm. ... [snip stuff about using dicts] ... "properties as separate mappings" and the Level 2 Graph API could add ...
    (comp.lang.python)
  • Re: Shortest Path finding with mutating weights
    ... > Dijkstra's algo can be used to find shortest path between 2 nodes in ... > a weighted graph. ... > How to find shortest paths in a graph with mutating weights? ... Connections from one time slice to the another ...
    (comp.theory)
  • Graph problem, is it NP-Complete?
    ... An undirected weighted graph, ... acyclic and all its vertices have 2 neighbours, ... YES if there exists a set of size <= K of connected subgraphs of the ... The sum of all the weights of each edge of each subgraph that "map" to ...
    (comp.theory)
  • Re: Modeling General Graphs in SQL
    ... You don't mention assigning weights to the edges, so can we assume that the ... Therefore a minimal spanning tree of a graph with n ... Or you might need to test if the graph is cyclic or acyclic. ... return the minimum path between two vertices (wow, ...
    (comp.databases)