利用jgrapht库进行图的操作
在 了解数据结构图 （graph） 的学习中，我们了解到了图的基本概念，并通过学习 迪杰斯特拉 ( Dijkstra ) 最短路径算法 和 DFS(深度优先遍历) 以及 BFS(广度优先遍历) ，可以了解到怎么求图中的最短路径。为什么学习图呢？在调度任务中，大量使用了图的概念，处理任务的依赖关系，所以，为了彻底弄懂原理，有必要系统粗略地学习下。除此之外，在机器学习中例如知识图谱、推荐系统等也大量使用了图。
接下来，我们通过 jgrapht 库，对图进行操作。 jgrapht 库提供了在 java 中进行图运算的能力，开源地址：https://github.com/jgrapht/jgrapht 。下面我们将通过一些小栗子，学习该库的使用。
例子1：基本的API
在 图 中，有一些基本的概念，例如 顶点Vertex、边edge、度degree、有环、无环。如果不了解，可以在上面提到的文章中了解。好了，下面实操实操。
代码中，描述了下图所示中的有向图
@Test public void testOtherAPI() {
String a = "A";
String b = "B";
String c = "C";
String d = "D";
String e = "E";
String f = "F";
// 构建图
Graph<String, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);
// 添加顶点
g.addVertex(a);
g.addVertex(b);
g.addVertex(c);
g.addVertex(d);
g.addVertex(e);
g.addVertex(f);
// 添加边
g.addEdge(a, b);
g.addEdge(a, c);
g.addEdge(b, d);
g.addEdge(c, e);
g.addEdge(d, f);
g.addEdge(e, f);
// 度
System.out.println(g.degreeOf(a)); // 出度 output: 2
System.out.println(g.inDegreeOf(a)); // 入度 output: 0
System.out.println(g.outDegreeOf(a)); // 入度 output: 2
// Graphs 工具类
// 当前顶点的后续节点列表 output: [B, C]
System.out.println(Graphs.successorListOf(g, a));
// 当前顶点的后续节点列表 output: [D, E]
System.out.println(Graphs.predecessorListOf(g, f));
// 图中“环”的操作
CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(g);
// 探测图中是否有环 output: false
System.out.println(cycleDetector.detectCycles());
// 找出图中的环 output: []
System.out.println(cycleDetector.findCycles());
}
例子2：有向图
@Test public void testDirectedGraph() {
// create a graph based on URL objects
Graph<URL, DefaultEdge> hrefGraph = createHrefGraph();
// note directed edges are printed as: (<v1>,<v2>)
// 打印所有的路径，默认是第一个添加的edge是起始点顶点
// 前面的 [] 是显示顶点数；第二个 [] 是路径
// 打印([http://www.amazon.com, http://www.yahoo.com, http://www.ebay.com], [(http://www.yahoo.com,http://www.amazon.com), (http://www.yahoo.com,http://www.ebay.com)])
System.out.println(hrefGraph.toString());
}
private static Graph<URL, DefaultEdge> createHrefGraph() {
Graph<URL, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);
try {
URL amazon = new URL("http://www.amazon.com");
URL yahoo = new URL("http://www.yahoo.com");
URL ebay = new URL("http://www.ebay.com");
// add the vertices
// 顶点
g.addVertex(amazon);
g.addVertex(yahoo);
g.addVertex(ebay);
// 边缘
// add edges to create linking structure
g.addEdge(yahoo, amazon);
g.addEdge(yahoo, ebay);
} catch (MalformedURLException e) {
e.printStackTrace();
}
return g;
}
例子3：广度优先和深度优先算法遍历有向无环图
/** * 测试广度优先遍历
*
* ([v1, v2, v3, v4, v5], [(v1,v5), (v5,v3), (v3,v4), (v1,v2), (v4,v2)])
* []
* [v2, v3, v4, v5]
* v1
* v5
* v2
* v3
* v6
* v4
*/
@Test
public void testBreadthFirstIterator() {
DirectedAcyclicGraph<String, DefaultEdge> dag = createGraph();
System.out.println(dag);
System.out.println(dag.getAncestors("v1"));
System.out.println(dag.getDescendants("v1"));
BreadthFirstIterator<String, DefaultEdge> bfi = new BreadthFirstIterator<>(dag, "v1");
while (bfi.hasNext()) {
System.out.println(bfi.next());
}
}
/**
([v1, v2, v3, v4, v5], [(v1,v5), (v5,v3), (v3,v4), (v1,v2), (v4,v2)])
[]
[v2, v3, v4, v5]
v1
v2
v6
v5
v3
v4
* 测试深度优先遍历
*/
@Test
public void testDepthFirstIterator() {
DirectedAcyclicGraph<String, DefaultEdge> dag = createGraph();
System.out.println(dag);
System.out.println(dag.getAncestors("v1"));
System.out.println(dag.getDescendants("v1"));
DepthFirstIterator<String, DefaultEdge> dfi = new DepthFirstIterator<>(dag, "v1");
while (dfi.hasNext()) {
System.out.println(dfi.next());
}
}
/**
* DAG有向无环图
*/
private static DirectedAcyclicGraph<String, DefaultEdge> createGraph() {
DirectedAcyclicGraph<String, DefaultEdge> g = new DirectedAcyclicGraph<>(DefaultEdge.class);
String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
String v4 = "v4";
String v5 = "v5";
String v6 = "v6";
// add the vertices
g.addVertex(v1);
g.addVertex(v2);
g.addVertex(v3);
g.addVertex(v4);
g.addVertex(v5);
g.addVertex(v6);
// 如果出现了环状，抛异常 IllegalArgumentException
// add edges to create a circuit
g.addEdge(v1, v5);
g.addEdge(v5, v3);
g.addEdge(v3, v4);
g.addEdge(v1, v2);
g.addEdge(v2, v6);
return g;
}
例子4：Dijkstra算法获取最短路径
@Test public void testShortestPath() {
Graph<String, DefaultEdge> g2 = new DefaultDirectedGraph<>(DefaultEdge.class);
String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
// add the vertices
g2.addVertex(v1);
g2.addVertex(v2);
g2.addVertex(v3);
// v1 -> v2 -> v3
// add edges to create a circuit
g2.addEdge(v1, v2);
g2.addEdge(v2, v3);
DijkstraShortestPath shortestPath = new DijkstraShortestPath(g2);
ShortestPathAlgorithm.SingleSourcePaths paths = shortestPath.getPaths(v2);
System.out.println(paths.toString());
GraphPath<Integer, DefaultWeightedEdge> shortestPath1 = shortestPath.getPath(v1, v3);
GraphPath<Integer, DefaultWeightedEdge> shortestPath2 = shortestPath.getPath(v1, v2);
GraphPath<Integer, DefaultWeightedEdge> shortestPath3 = shortestPath.getPath(v1, v1);
GraphPath<Integer, DefaultWeightedEdge> shortestPath4 = shortestPath.getPath(v2, v1);
GraphPath<Integer, DefaultWeightedEdge> shortestPath5 = shortestPath.getPath(v2, v3);
// [(v1 : v2), (v2 : v3)]
System.out.println(shortestPath1.toString());
// [(v1 : v2)]
System.out.println(shortestPath2.toString());
// [v1]
System.out.println(shortestPath3.toString());
//路径没有联通，所有返回的是null
Assert.assertNull(shortestPath4);
// [(v2 : v3)]
System.out.println(shortestPath5.toString());
}
例子5：有向加权图
获取从v0到v7的最短路径
@Test public void testDirectedWeightedGraph() {
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = createGraph();
printShortestPath(graph);
}
/**
* 创建一个有向带权图
*/
public SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> createGraph() {
String[] str = {"v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7"};
int[] startPoint = {0, 0, 0, 1, 1, 3, 3, 3, 3, 2, 4, 5, 5, 4, 6};
int[] endPoint = {1, 3, 2, 4, 3, 4, 5, 6, 2, 6, 5, 6, 7, 7, 7};
double[] weights = {2, 8, 1, 1, 6, 5, 1, 2, 7, 9, 3, 4, 6, 9, 3};
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> directedGraph =
new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
//添加顶点
for (String s : str) {
directedGraph.addVertex(s);
}
// 起点
DefaultWeightedEdge[] edgeSources = new DefaultWeightedEdge[startPoint.length];
// 终点
DefaultWeightedEdge[] edgeTargets = new DefaultWeightedEdge[startPoint.length];
for (int i = 0; i < endPoint.length; i++) {
edgeSources[i] = directedGraph.addEdge(str[startPoint[i]], str[endPoint[i]]);
edgeTargets[i] = directedGraph.addEdge(str[endPoint[i]], str[startPoint[i]]);
directedGraph.setEdgeWeight(edgeSources[i], weights[i]);
directedGraph.setEdgeWeight(edgeTargets[i], weights[i]);
}
return directedGraph;
}
/**
* 根据得到的带权有向图，Dijkstra计算最短路径，并保存他们的路径权值之和到数组Dij中
*/
public static void printShortestPath(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph) {
DijkstraShortestPath<String, DefaultWeightedEdge> dijkstraAlg = new DijkstraShortestPath<>(graph);
//获取从u0到u7的最短路径
System.out.println("Shortest path from v1 to v8:");
ShortestPathAlgorithm.SingleSourcePaths<String, DefaultWeightedEdge> sourcePaths = dijkstraAlg.getPaths("v0");
GraphPath<String, DefaultWeightedEdge> u0ToU7ShortestPath = sourcePaths.getPath("v7");
//打印路径
List<String> pathsList = u0ToU7ShortestPath.getVertexList();
StringBuilder sb = new StringBuilder();
boolean firstElement = true;
for (String s : pathsList) {
if (firstElement) {
sb.append(s);
firstElement = false;
} else {
sb.append("->").append(s);
}
}
System.out.println(sb);
System.out.println("Shortest path weight:" + u0ToU7ShortestPath.getWeight());
}
输出：
Shortest path from v0 to v7:v0->v1->v4->v7
Shortest path weight:12.0
以上是 利用jgrapht库进行图的操作 的全部内容， 来源链接： utcz.com/z/511158.html
