Graph G2

Graph{
  A1 -> B2 (12.3)
  B2 -> C3 (0.98)
  C3 -> D4 (2)
  E5
}

Note that there is no space between ‘Graph’ and ‘{‘. This is just to show different ways it can be written.

The DSL for the below graph (g3) would be:

Graph G3

Graph {
  A -> B (12.3)
  B -> C (0.98)
  C -> D (2)
  D -> E (12.45)
}

Now to show some of the invalid DSL scripts:

Graph {
  1A -> B (12.3)
  B -> C (0.98)
}

The above is invalid because the vertex name begins with a digit.

Graph {
}

The above is invalid because the Graph expects atleast one vertex to be defined. But it can have zero or more edges.

Library for DSL based graph input

I have made use of ANTLR which does all the task of creating lexer and parser for the grammar which I defined for my DSL. This way I need not worry about creating parser or worry about creating tokens from the DSL input script.

The parser and lexer classes along with the semantic model classes are package into a jar and this jar along with the ANTLR jar have to be included to make use of writing a DSL for graph input.

The structure of the DSL jar can be seen in the screenshot below:

GraphDSL Jar

The classes in the graph package correspond to the semantic model i.e these are generic classes and can be used irrespecitve of whether someone is using a DSL or not. The classes in graph.dsl correspond to the ANTLR generated java classes for lexer and parser.

The grammar which is used by ANTLR for lexical analysis and parsing is:

grammar Graph;

graph: GRAPH_START (edge|vertex)+ GRAPH_END;
edge: (vertex) TO (vertex) weight;
vertex: ID;
weight: '(' NUM ')';
GRAPH_START : 'Graph'([ ])*'{';
GRAPH_END : '}';
WEIGHT_START: '(';
WEIGHT_END: ')'; 
TO: '->';
ID: ^[a-zA-Z][a-zA-Z0-9]*;
NUM: [0-9]*[.]?[0-9]+;
WS: [ \t\r\n]+ -> skip;

The above grammar has scope for improvement but as my first attempt I have tried to keep it to this level.

Download the DSL jar from here(GraphDSL.jar).
Download the ANTLR jar from here(antlr-4.1-complete.jar).

Note: This DSL is developed using ANTLR Version 4.

Kruskals Algorithm to find minimum spanning tree

The graph which is used to test this algorithm implementation is:

Sample Graph

and the DSL for the same is:

Graph  {
  A -> B (7)
  B -> C (8)
  A -> D (5)
  B -> D (9)
  D -> E (15)
  D -> F (6)
  E -> F (8)
  E -> C (5)
  B -> E (7)
  E -> G (9)
  F -> G (11)
}

Lets look at the implementation:

package kruskalsalgo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import graph.Edge;
import graph.Graph;
import graph.Vertex;
import graph.GraphBuilder;
import java.io.IOException;
import java.util.Comparator;

public class KruskalsAlgorithm {

  public static void main(String[] args) throws IOException {

    //Load the graph data from the DSL
    Graph g = new GraphBuilder().buildGraph("graph.gr");
    ArrayList<Set> forest = new ArrayList<Set>();
    ArrayList<Edge> finalEdgeSet = new ArrayList<Edge>();
    
    //Creating disjoint set of vertices which represents the initial forest
    for (Vertex v : g.getVertices()) {
      Set newSet = new Set();
      newSet.getVertexList().add(v);
      forest.add(newSet); //Creating Disjoint Sets

    }
    
    //sort the edges in the graph based on their weight
    Collections.sort(g.getEdges(), new Comparator<Edge>(){

      public int compare(Edge o1, Edge o2) {
        return o1.getWeight().compareTo(o2.getWeight());
      }
      
    });
    
    
    for (Edge edge : g.getEdges()) {
      //Find in which set the vertices in the edges belong
      int rep1 = Set.findRep(edge.getFromVertex(), forest);
      int rep2 = Set.findRep(edge.getToVertex(), forest);
      
      //If in different sets then merge them into one set and pick the edge.
      if (rep1 != rep2) {
        finalEdgeSet.add(edge);
        Set.Union(rep1, rep2, forest);
      }
    }

    System.out.println("The Minimum Spanning tree is");
    for (Edge edge : finalEdgeSet) {
      System.out.println("Vertex: " + edge.getFromVertex().getLabel() + 
              " to Vertex: " + edge.getToVertex().getLabel());
    }
    
    System.out.println("");

  }//End of Main
}

class Set {

  private ArrayList<Vertex> vertexList;
  private int representative;
  static int count;

  public Set() {
    vertexList = new ArrayList<Vertex>();
    this.representative = ++(Set.count);
  }

  //Find the set identifier in which the given vertex belongs to.
  public static int findRep(Vertex vertex, ArrayList<Set> forest) {
    int rep = 0;
    for (Set set : forest) {
      for (Vertex v : set.getVertexList()) {
        if (v.getLabel().equals(vertex.getLabel())) {
          return set.getRepresentative();
        }
      }
    }

    return rep;
  }

  //Find the set given the step identifier.
  public static Set findSet(int rep, ArrayList<Set> forest) {
    Set resultSet = null;
    for (Set set : forest) {
      if (set.getRepresentative() == rep) {
        return set;
      }
    }
    return resultSet;
  }

  //Merge the set into another and remove it from the main set.
  public static void Union(int rep1, int rep2, ArrayList<Set> forest) {
    Set set1 = Set.findSet(rep1, forest);
    Set set2 = Set.findSet(rep2, forest);

    for (Vertex v : set2.getVertexList()) {
      set1.getVertexList().add(v);
    }
    forest.remove(set2);
  }

  public ArrayList<Vertex> getVertexList() {
    return vertexList;
  }
  
  public int getRepresentative() {
    return representative;
  }
}

The above code loads the graph data from the dsl- graph.gr. The DSL scripts have to be placed in the resources package so that the DSL library can locate it.

The output for the above code:

The Minimum Spanning tree is
Vertex: A to Vertex: D
Vertex: E to Vertex: C
Vertex: D to Vertex: F
Vertex: A to Vertex: B
Vertex: B to Vertex: E
Vertex: E to Vertex: G

and showing the same diagramatically