Подход на основе DSL для ввода данных графов в Java-программах на основе теории графов

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

График G2

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

Обратите внимание, что между ‘Graph’ и ‘{‘ нет пробела. Это просто для того, чтобы показать разные способы написания.

DSL для приведенного ниже графика (g3) будет:

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

Теперь, чтобы показать некоторые из недействительных сценариев DSL:

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

Выше недопустимо, потому что имя вершины начинается с цифры.

Graph {
}

Вышеуказанное недопустимо, потому что Граф ожидает, что будет определена хотя бы одна вершина Но он может иметь ноль или более ребер.

Библиотека для ввода графиков на основе DSL

Я использовал  ANTLR,  который выполняет всю задачу по созданию лексера и парсера для грамматики, которую я определил для моего DSL. Таким образом, мне не нужно беспокоиться о создании парсера или беспокоиться о создании токенов из входного скрипта DSL.

Классы parser и lexer вместе с классами семантической модели упакованы в jar, и этот jar вместе с ANTLR jar необходимо включить, чтобы использовать запись DSL для ввода в граф.

Структуру банки DSL можно увидеть на скриншоте ниже:

Классы в пакете графа соответствуют семантической модели, то есть это универсальные классы и могут использоваться независимо от того, использует ли кто-то DSL или нет. Классы в graph.dsl соответствуют сгенерированным ANTLR java-классам для лексера и анализатора.

Грамматика, используемая ANTLR для лексического анализа и анализа:

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;

Приведенная выше грамматика имеет возможности для улучшения, но в качестве первой попытки я постаралась удержать ее на этом уровне.

Загрузите банку DSL  отсюда (GraphDSL.jar).
Загрузите банку ANTLR  здесь (antlr-4.1-complete.jar).

Примечание. Этот DSL разработан с использованием ANTLR версии 4.

Алгоритм Крускала для нахождения минимального остовного дерева

График, который используется для проверки реализации этого алгоритма:

и DSL для того же:

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

Давайте посмотрим на реализацию:

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

Приведенный выше код загружает данные графика из dsl-graph.gr. Сценарии DSL должны быть помещены в пакет ресурсов, чтобы библиотека DSL могла найти его.

Выход для вышеуказанного кода:

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

и показывая то же самое схематично