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

// 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:

  1. register any .ecore metamodels in the org.eclipse.epsilon.examples.shortestpath project
  2. right click the .launch file in the org.eclipse.epsilon.examples.shortestpath project
  3. 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.

What are .emf files?

.emf files are Ecore metamodels expressed using the Emfatic textual syntax.

More examples...

Epsilon Object Language
Epsilon Transformation Language
Epsilon Generation Language
Epsilon Validation Language
Epsilon Merging Language
Epsilon Flock
Combining the Epsilon Languages
EuGENia
EUnit

Even more examples...

More examples are available in the examples folder of the SVN repository.