Epsilon - Examples

// This script implements Dijkstra"s shortest 
// path algorighm

var s : Node;
s = Node.allInstances.select(n|n.label = "a").first();

for (n in Node.allInstances) {
  n.~distance = 10000;
}

s.~distance = 0;

var Q : Sequence(Node);
Q = Node.allInstances.clone();

while (not Q.isEmpty()) {
  var u : Node;
  u = Q.extractMin();
  for (e in u.outgoing) {
    var v : Node;
    v = e.target;
    if (u.~distance + e.weight < v.~distance) {
      v.~distance = u.~distance + e.weight;
      v.~previous = u;
    }
  }
}

// Print distances and paths
for (n in Node.allInstances){
  ("Distance of " + n.label + " from " + s.label + " : " + 
    n.~distance + " via " + n.getPath()).println();
}

operation Sequence(Node) extractMin() : Node {
  var min : Node;
  min = self.select(n|self.forAll(
    n1|n.~distance <= n1.~distance)).first();
  self.remove(min);
  return min;
}

operation Node getPath() : String {
  if (self.~previous.isDefined()) {
    return self.~previous.getPath() + "->" + self.label;
  }return self.label;
}

context Node {
  
  constraint NotInCycle {
    check : not self.allIncoming().includes(self)
    message : "Node " + self.label + 
      " is part of a directed cycle"
  }
  
}

context Edge {
  
  constraint MustDefineSource {
    
    check : self.source.isDefined()
    
    message : "Edge does not have a source node"
    
  }
  
  constraint MustDefineTarget {
    check : self.target.isDefined()
    
    message : "Edge does not have a target node"
  }
  
  constraint PositiveWeight {
    
    guard : self.satisfies("MustDefineSource") and 
      self.satisfies("MustDefineTarget")
    
    check : self.weight >= 0
    
    message : "Edge " + self.source.label + "->" + 
      self.target.label + " has a negative weight" 
    
  }
  
}

operation Node allIncoming() : Set {
  return self.allIncoming(Set{});
}

operation Node allIncoming(visited : Set) : Set {
  for (n in self.incoming.collect(e|e.source)) {
    if (not visited.includes(n)) {
      visited.add(n);
      visited.addAll(n.allIncoming(visited));
    }
  }
  return visited;
}

@namespace(uri="DirectedGraph", prefix="DirectedGraph")
package DirectedGraph;

class Graph {
  val GraphElement[*]#graph contents;
}

abstract class GraphElement {
  ref Graph#contents graph;
}

class Node extends GraphElement {
  attr String label;
  ref Edge[*]#source outgoing;
  ref Edge[*]#target incoming;
}

class Edge extends GraphElement {
  attr Integer weight;
  ref Node#outgoing source;
  ref Node#incoming target;
}

Check out the code from the SVN:

go to the SVN repository
navigate to trunk/examples
check out the org.eclipse.epsilon.examples.shortestpath project

Once you have checked out/imported the code, to run the example you need to go through the following steps:

register any .ecore metamodels in the org.eclipse.epsilon.examples.shortestpath project
right click the .launch file in the org.eclipse.epsilon.examples.shortestpath project
select Run as... and click the first item in the menu that pops up

What's this?

In this example, we use EOL and EVL to implement Dijkstra's shortest path algorithm.

Example: Dijkstra's shortest path algorithm with EOL/EVL

What's this?

What are .emf files?

More examples...

Even more examples...