Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » VIATRA2 » Algorithm implementation
Algorithm implementation [message #990892] Fri, 14 December 2012 12:00 Go to next message
Cristina Murillo is currently offline Cristina Murillo
Messages: 25
Registered: December 2011
Junior Member
Hello,

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
Re: Algorithm implementation [message #990902 is a reply to message #990892] Fri, 14 December 2012 13:42 Go to previous messageGo to next message
Abel Hegedus is currently offline Abel Hegedus
Messages: 91
Registered: July 2009
Member
Hi 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.
Re: Algorithm implementation [message #991227 is a reply to message #990902] Mon, 17 December 2012 16:34 Go to previous messageGo to next message
Cristina Murillo is currently offline Cristina Murillo
Messages: 25
Registered: December 2011
Junior Member
Hi Abel,

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

Cristina
Re: Algorithm implementation [message #1003141 is a reply to message #991227] Sun, 20 January 2013 06:06 Go to previous messageGo to next message
Cristina Murillo is currently offline Cristina Murillo
Messages: 25
Registered: December 2011
Junior Member
Hi!

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
Re: Algorithm implementation [message #1003273 is a reply to message #1003141] Sun, 20 January 2013 16:04 Go to previous message
Abel Hegedus is currently offline Abel Hegedus
Messages: 91
Registered: July 2009
Member
Hi!

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:


  1. Find all hops (From,To) in any path between two nodes (Source,Target)
  2. 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.
Previous Topic:Error on importing EMF model
Next Topic:[Import of uml file to model space] Not all Model elements imported
Goto Forum:
  


Current Time: Wed Aug 27 19:12:19 EDT 2014

Powered by FUDForum. Page generated in 0.01776 seconds