我們大多數(shù)人已經(jīng)編寫了一些程序來處理圖論算法，例如查找兩個頂點之間的最短路徑，查找給定圖的最小生成樹等等。 在這些算法的每一種中，表示圖形的編程方式是使用鄰接矩陣或鄰接表 。 兩者都不是定義圖形輸入的非常直觀的方法。 例如，如果未在正確的列和行中進(jìn)行輸入，則鄰接矩陣可能會導(dǎo)致錯誤。 而且，在運行時，您不太確定哪個行/列代表哪個邊，當(dāng)涉及到具有大量頂點的圖形的輸入時，事情會變得更加復(fù)雜。

在我的工程研究期間，我已經(jīng)用Java實現(xiàn)了許多圖形算法，并且在所有這些圖形算法中，我都嵌套了for循環(huán)以獲取鄰接矩陣輸入。 最近，當(dāng)我閱讀Martin Fowlers的DSL書籍時，我想到了創(chuàng)建DSL來提供圖形輸入的想法，即DSL，它允許用戶指定頂點，邊和權(quán)重。 我選擇了已實現(xiàn)的圖形算法，只是去除了鄰接矩陣輸入，而是使用了我創(chuàng)建的DSL。 該算法就像一個魅力。

在這篇文章中，我將通過采用不同的圖形輸入并為它們顯示DSL來顯示DSL的有效語法。 然后，我將向您展示我創(chuàng)建的庫，該庫由圖的語義模型，DSL的解析器和詞法分析器以及一個簡單的構(gòu)建器API組成，該API從DSL腳本中填充語義模型。 解析器和詞法分析器是使用ANTLR生成的，因此此庫要求ANTLR Jar在類路徑中可用。 最后，我將展示如何使用Kruskals算法將該DSL用于查找最小生成樹。

DSL語法和一些示例

下圖（g1）的DSL：

圖表G1

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

請注意，上述DSL中的元素之間存在不同的空間。 這只是為了顯示可以編寫DSL的不同方式。

下圖（g2）的DSL為：

圖G2

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

請注意，“圖形”和“ {”之間沒有空格。 這只是為了顯示它的不同編寫方式。

下圖（g3）的DSL為：

圖G3

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

現(xiàn)在顯示一些無效的DSL腳本：

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

上面的無效，因為頂點名稱以數(shù)字開頭。

Graph { }

上面的方法無效，因為Graph希望至少定義一個頂點。 但是它可以具有零個或多個邊。

基于DSL的圖形輸入庫

我已經(jīng)利用ANTLR來完成為我為DSL定義的語法創(chuàng)建詞法分析器和解析器的所有任務(wù)。 這樣，我不必?fù)?dān)心創(chuàng)建解析器或擔(dān)心從DSL輸入腳本創(chuàng)建令牌。

解析器和詞法分析器類以及語義模型類一起打包到一個jar中，并且必須將這個jar和ANTLR jar一起包括在內(nèi)，以利用編寫用于圖形輸入的DSL來使用。

DSL jar的結(jié)構(gòu)可以在下面的屏幕截圖中看到：

GraphDSL Jar

圖包中的類對應(yīng)于語義模型，即它們是通用類，可以在不考慮是否有人在使用DSL的情況下使用。 graph.dsl中的類對應(yīng)于ANTLR為lexer和parser生成的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;

上面的語法有待改進(jìn)，但作為我的第一次嘗試，我試圖將其保持在這個水平。

• 從此處下載DSL jar（GraphDSL.jar）。
• 從此處下載ANTLR jar（antlr-4.1-complete.jar）。

注意：此DSL是使用ANTLR版本4開發(fā)的。

對于使用ANTLR的外部DSL的推薦書是《 語言實現(xiàn)模式：創(chuàng)建自己的域》特定和通用編程語言

Kruskals算法找到最小生成樹

用于測試此算法實現(xiàn)的圖形為：

樣本圖

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

讓我們看一下實現(xiàn)：

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 DSLGraph 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 forestfor (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 weightCollections.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 belongint 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;} }

上面的代碼從dslgraph.gr加載圖形數(shù)據(jù)。 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

并以示意圖形式顯示

最小生成樹

參考：來自CG的合作伙伴 Mohamed Sanaulla（來自Experiences Unlimited博客）中的基于DSL的方法，用于在基于圖論的Java程序中輸入圖數(shù)據(jù) 。

翻譯自: https://www.javacodegeeks.com/2013/07/dsl-based-approach-to-input-graph-data-in-graph-theory-based-java-programs.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的在基于图论的Java程序中基于DSL的输入图数据的方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。