I need to implement an algorithm to find all possible paths between two nodes. Can anyone tell me if the implementation can be done in viatra?

Thank you,

Cristina]]>

this is an interesting problem that has popped up in several occasions now.

First, the pattern language cannot completely cover this use case, since it is not possible to return a "list of elements" that constitute the path.

Before reading the code below, please take a moment to read this: https://viatra.inf.mit.bme.hu/publications/inctc

Because what you're trying to do probably need transitive closure and the VIATRA2 incremental pattern has only prototypical support for it.

However, you can use a few patterns and a bit of command language to create an algorithm. I think a possible way is the following (might be syntactically incorrect, sorry):

pattern oneHopOnPath(From, To) = { // describe possible connections that build up the path } // this should be replaced with the transitive closure call on oneHopOnPath pattern pathExists(From, Next, To) = { find oneHopOnPath(From, Next); Next == To; // I'm not sure, maybe you need 'shareable' mode } or { find onehopOnPath(From, Next); find pathExists(Next, To); } rule findPaths(From, To) = seq{ iterate choose First with find pathExists(From, First, To) do seq{ if(First == To) do seq{ println("Single-hop path: " + name(From) + "->" + name(To)); } else seq{ println("Finding pathes " + name(From) + "->" + name(First) + "->" + name(To)); call findPaths(First,To); } } }

Note that the above code obviously won't store the paths, but I think it will iterate through all of them. The basic idea is to:

1. Ensure that there is at least one path between From and To.

1. Query the Next elements on any of these paths.

1. Using the Next elements as starting points, find all paths between Next and To.

Hope that helps.]]>

Thank you so much for the information. I will check it and give it a try!!

Cristina]]>

I am not sure if this is a feasible or even valid idea, but I was wondering if it is possible to use a Native ASM function to write the algorithm in Java. Could you please give me some hints about it?

Thank you,

Cristina

]]>

It is possible to use native functions to create something like this, however model navigation over VPM in Java is quite slow and I'm not sure what is it that you cannot do in VTCL, that you could in Java?

A simple solution would be to pass the native function the source and target nodes, then use Java to calculate the paths and return it into the transformation in some way (probably by storing it in the model space).

A more integrated solution would be to only use native functions to log the paths in some Java structure and call this function with the results of the one-hop pattern. This way you could have something like this:

forall From,To with find oneStepOnPath(From,To) do call myNativeStoreHop(From,To); call myNativeFindAllRoutes(Source,Target,Result); forall Path with find pathInResult(Path,Result) do seq{ // evaluate and use path }

In your native function implementation, you fill a hashmap with the myNativeStoreHop(From,To) call, and then use the same hashmap to calculate the paths in Java with some simple search algorithm, and if you need the results in the transformation, then put it back in the modelspace in some structure you define.

Note that this is quite similar to the algorithm I described in VTCL:

- Find all hops (From,To) in any path between two nodes (Source,Target)

- For each possible hop where From == Source, store the hop and recursively call the algorithm for (To,Target)

Obviously, you don't have to include the "in any path between two nodes" constraint, but then you will have to explore all paths leading from Source to any nodes and somehow decide when a path is no longer interesting, or if you are caught in a loop etc.]]>