Amol wrote:
> Hi folks,
>
> If I am given a graph, I am supposed to walk the graph and eliminate
> the internal nodes and create paths from input to different outputs.
>
> For e.g.
>
>        2 ---- 3 --
>      /               \                     --------
>     /                 \                 /             \
>   1                   6    ==>         1               6
>    \                  /                 \              /
>       4 ----  5 ---                       ---------
>
>
> should create 2 different paths from 1 to 6 with different costs
> possibly by adding the weights of the edges comprising the path. I
> should be able to start from any such internal node and write a routine
> such as compressNode(someInternalNode) that would eliminate the node
> and create new paths from its source to its sink. How should i design
> the data structures for representing this graph?
>
> -Amol

You should get any reasonable data structures book and look up the
"adjacency list" representation for a graph.  In this case your life
will be a little easier if you keep both "forward" and "reverse"
adjacencies. I.e. for each node, two lists--one containing  each node
pointed _to_ by an out-edge (along with the edge weight) and another
containing each node pointed _from_ by an in-edge.  The algorithm you
need is just a standard Depth First Search.  When you find a node N
that has one in-edge A->N and one out-edge N->B (easy to determine from
the forward and reverse adjacency lists), delete both these edges (by
deleting respective 4 entries in adjacency lists) and add an edge A->B
(by adding two new list entries), assigning the sum of weights of the
old edges.  Then go on to search B.


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to