开网站做彩票赚钱吗,网站建设金手指15,成都到西安距离,企业排名查询我们大多数人已经编写了一些程序来处理图论算法#xff0c;例如查找两个顶点之间的最短路径#xff0c;查找给定图的最小生成树等等。 在这些算法的每一种中#xff0c;表示图形的编程方式是使用邻接矩阵或邻接表 。 两者都不是定义图形输入的非常直观的方法。 例如#xf… 我们大多数人已经编写了一些程序来处理图论算法例如查找两个顶点之间的最短路径查找给定图的最小生成树等等。 在这些算法的每一种中表示图形的编程方式是使用邻接矩阵或邻接表 。 两者都不是定义图形输入的非常直观的方法。 例如如果未在正确的列和行中进行输入则邻接矩阵可能会导致错误。 而且在运行时您不太确定哪个行/列代表哪个边当涉及到具有大量顶点的图形的输入时事情会变得更加复杂。 在我的工程研究期间我已经用Java实现了许多图形算法并且在所有这些图形算法中我都嵌套了for循环以获取邻接矩阵输入。 最近当我阅读Martin Fowlers的DSL书籍时我想到了创建DSL来提供图形输入的想法即DSL它允许用户指定顶点边和权重。 我选择了已实现的图形算法只是去除了邻接矩阵输入而是使用了我创建的DSL。 该算法就像一个魅力。 在这篇文章中我将通过采用不同的图形输入并为它们显示DSL来显示DSL的有效语法。 然后我将向您展示我创建的库该库由图的语义模型DSL的解析器和词法分析器以及一个简单的构建器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)
} 现在显示一些无效的DSL脚本 Graph {1A - B (12.3)B - C (0.98)
} 上面的无效因为顶点名称以数字开头。 Graph {
} 上面的方法无效因为Graph希望至少定义一个顶点。 但是它可以具有零个或多个边。 基于DSL的图形输入库 我已经利用ANTLR来完成为我为DSL定义的语法创建词法分析器和解析器的所有任务。 这样我不必担心创建解析器或担心从DSL输入脚本创建令牌。 解析器和词法分析器类以及语义模型类一起打包到一个jar中并且必须将这个jar和ANTLR jar一起包括在内以利用编写用于图形输入的DSL来使用。 DSL jar的结构可以在下面的屏幕截图中看到 GraphDSL Jar 图包中的类对应于语义模型即它们是通用类可以在不考虑是否有人在使用DSL的情况下使用。 graph.dsl中的类对应于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; 上面的语法有待改进但作为我的第一次尝试我试图将其保持在这个水平。 从此处下载DSL jarGraphDSL.jar。 从此处下载ANTLR jarantlr-4.1-complete.jar。 注意此DSL是使用ANTLR版本4开发的。 对于使用ANTLR的外部DSL的推荐书是《 语言实现模式创建自己的域》特定和通用编程语言 Kruskals算法找到最小生成树 用于测试此算法实现的图形为 样本图 和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 DSLGraph g new GraphBuilder().buildGraph(graph.gr);ArrayListSet forest new ArrayListSet();ArrayListEdge finalEdgeSet new ArrayListEdge();//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 ComparatorEdge(){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 ArrayListVertex vertexList;private int representative;static int count;public Set() {vertexList new ArrayListVertex();this.representative (Set.count);}//Find the set identifier in which the given vertex belongs to.public static int findRep(Vertex vertex, ArrayListSet 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, ArrayListSet 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, ArrayListSet 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 ArrayListVertex getVertexList() {return vertexList;}public int getRepresentative() {return representative;}
} 上面的代码从dslgraph.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 并以示意图形式显示 最小生成树 参考来自CG的合作伙伴 Mohamed Sanaulla来自Experiences Unlimited博客中的基于DSL的方法用于在基于图论的Java程序中输入图数据 。 翻译自: https://www.javacodegeeks.com/2013/07/dsl-based-approach-to-input-graph-data-in-graph-theory-based-java-programs.html
