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