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;
}

There are two ways to get the code of this example:

1. download the following zip archive(s), extract them and import them as new Eclipse projects
   • org.eclipse.epsilon.examples.shortestpath.zip
2. or 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. right click the .launch file in the org.eclipse.epsilon.examples.shortestpath project
2. select Run as... and click the first item in the menu that pops up