finding maximum paths between the two nodes in REXX

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

finding maximum paths between the two nodes in REXX

shiva kumar namulla
Hi Guys,

I have to find the all possible unique paths between the two nodes in the REXX  ,

EXAMPLE :

1 2

2  4

2   3

3   5
4    5

ANS :
possible paths
1 2 4 5
1 2 3 5


it would be very useful how to achieve this in REXX coding
Reply | Threaded
Open this post in threaded view
|

Re: finding maximum paths between the two nodes in REXX

Axel Niedenhoff
Here is my proposal:

arg s

edges. = ''

do i = 1 to words(s) / 2
  j = word(s, i * 2 - 1)
  edges.j = edges.j word(s, i * 2)
end

path.0 = 1
path.1 = 1

do until changed = 0
  changed = 0
  do i = 1 to path.0
    new_nodes = edges.[word(path.i, words(path.i))]
    n = words(new_nodes)
    if n = 0 then
      iterate
    changed = 1
    do j = 2 to n
      new_node = word(new_nodes, j)
      if pos(new_node, path.i) = 0 then
        path.[path.0 + j - 1] = path.i new_node
    end
    path.0 = path.0 + n - 1
    new_node = word(new_nodes, 1)
    if pos(new_node, path.i) = 0 then
      path.i = path.i new_node
  end
end

do i = 1 to path.0
  say path.i
end

I tested it using ooRexx; it might need a little tweaking here or there if you use some other Rexx.

To use your sample data, you start it like this:

ShowAllPaths.rex 1 2 2 4 2 3 3 5 4 5

Each pair of numbers represents an edge (so we have 1 => 2; 2 => 4; 2 => 3; …). The first part of the script turns that command line into a stem called edges with the source node as the key and the list of possible target nodes as the value. So we would get something like this:

edges.1 = '2'
edges.2 = '4 3'
edges.3 = '5'


After that we build the list of paths in the path stem. We prepare the action by filling in the root node “1”. And then we basically loop over our collection of paths that we have so far and look for continuations (indexing the edges stem with the last node in the path we are currently looking at). If we have more than one continuation, we append copies of the current path to the path stem, extended with each additional continuation. The one path we already had is extended in place. The “if” statements prevent cycles from forming in the graph.

We do this looping until we discover that our set of paths has not changed during the last iteration. That is when we know we are finished.

Do note that this code is not well tested, so do not use it in air traffic control systems, nuclear power plants (at least not near where I live) and such. ;-) It is also possible that this is the worst-performing solution imaginable. It is just what I could come up with.