JGraphTの紹介
1. 概要
ほとんどの場合、グラフベースのアルゴリズムを実装するときは、いくつかのユーティリティ関数も実装する必要があります。
JGraphT はオープンソースのJavaクラスライブラリであり、さまざまな種類のグラフだけでなく、最も頻繁に発生するグラフの問題を解決するための多くの便利なアルゴリズムも提供します。
この記事では、さまざまなタイプのグラフを作成する方法と、提供されているユーティリティを使用するのがどれほど便利かを説明します。
2. Mavenの依存関係
Mavenプロジェクトに依存関係を追加することから始めましょう:
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.0.1</version>
</dependency>
最新バージョンは、 MavenCentralにあります。
3. グラフの作成
JGraphTは、さまざまなタイプのグラフをサポートしています。
3.1. シンプルなグラフ
手始めに、Stringタイプの頂点を持つ単純なグラフを作成しましょう。
Graph<String, DefaultEdge> g
= new SimpleGraph<>(DefaultEdge.class);
g.addVertex(“v1”);
g.addVertex(“v2”);
g.addEdge(v1, v2);
3.2. 有向/無向グラフ
また、有向/無向グラフを作成することもできます。
この例では、有向グラフを作成し、それを使用して他の効用関数とアルゴリズムを示します。
DirectedGraph<String, DefaultEdge> directedGraph
= new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("v1");
directedGraph.addVertex("v2");
directedGraph.addVertex("v3");
directedGraph.addEdge("v1", "v2");
// Add remaining vertices and edges
3.3. 完全グラフ
同様に、完全グラフを生成することもできます。
public void createCompleteGraph() {
completeGraph = new SimpleWeightedGraph<>(DefaultEdge.class);
CompleteGraphGenerator<String, DefaultEdge> completeGenerator
= new CompleteGraphGenerator<>(size);
VertexFactory<String> vFactory = new VertexFactory<String>() {
private int id = 0;
public String createVertex() {
return "v" + id++;
}
};
completeGenerator.generateGraph(completeGraph, vFactory, null);
}
3.4. マルチグラフ
単純なグラフの他に、APIはマルチグラフ(2つの頂点間に複数のパスを持つグラフ)も提供します。
さらに、任意のグラフに加重/非加重またはユーザー定義のエッジを含めることができます。
重み付きエッジを持つマルチグラフを作成しましょう。
public void createMultiGraphWithWeightedEdges() {
multiGraph = new Multigraph<>(DefaultWeightedEdge.class);
multiGraph.addVertex("v1");
multiGraph.addVertex("v2");
DefaultWeightedEdge edge1 = multiGraph.addEdge("v1", "v2");
multiGraph.setEdgeWeight(edge1, 5);
DefaultWeightedEdge edge2 = multiGraph.addEdge("v1", "v2");
multiGraph.setEdgeWeight(edge2, 3);
}
これに加えて、サブグラフだけでなく、変更不可能(読み取り専用)およびリッスン可能(外部リスナーが変更を追跡できるようにする)グラフを作成できます。 また、これらのグラフのすべての構成をいつでも作成できます。
APIの詳細については、こちらをご覧ください。
4. APIアルゴリズム
本格的なグラフオブジェクトができたので、いくつかの一般的な問題とその解決策を見てみましょう。
4.1. グラフの反復
要件に応じて、 BroadthFirstIterator 、 DeepthFirstIterator 、 ClosestFirstIterator 、RandomWalkIteratorなどのさまざまなイテレーターを使用してグラフをトラバースできます。 グラフオブジェクトを渡すことで、それぞれのイテレータのインスタンスを作成する必要があります。
DepthFirstIterator depthFirstIterator
= new DepthFirstIterator<>(directedGraph);
BreadthFirstIterator breadthFirstIterator
= new BreadthFirstIterator<>(directedGraph);
イテレータオブジェクトを取得したら、 hasNext()および next()メソッドを使用して反復を実行できます。
4.2. 最短経路を見つける
org.jgrapht.alg.shortestpathパッケージのDijkstra、Bellman-Ford、Astar、FloydWarshallなどのさまざまなアルゴリズムの実装を提供します。
ダイクストラのアルゴリズムを使用して最短経路を見つけましょう。
@Test
public void whenGetDijkstraShortestPath_thenGetNotNullPath() {
DijkstraShortestPath dijkstraShortestPath
= new DijkstraShortestPath(directedGraph);
List<String> shortestPath = dijkstraShortestPath
.getPath("v1","v4").getVertexList();
assertNotNull(shortestPath);
}
同様に、ベルマンフォードアルゴリズムを使用して最短経路を取得するには、次のようにします。
@Test
public void
whenGetBellmanFordShortestPath_thenGetNotNullPath() {
BellmanFordShortestPath bellmanFordShortestPath
= new BellmanFordShortestPath(directedGraph);
List<String> shortestPath = bellmanFordShortestPath
.getPath("v1", "v4")
.getVertexList();
assertNotNull(shortestPath);
}
4.3. 強く接続されたサブグラフを見つける
実装に入る前に、強く接続されたサブグラフの意味を簡単に見てみましょう。 サブグラフは、その頂点の各ペアの間にパスがある場合にのみ、強く接続されていると言われます。
この例では、現在の頂点が何であるかに関係なく、任意の頂点にトラバースできる場合、{v1、v2、v3、v4}は強く接続されたサブグラフと見なすことができます。
上の画像に示されている有向グラフの4つのサブグラフをリストできます:{v9}、{v8}、{v5、v6、v7}、{v1、v2、v3、v4}
強く接続されたすべてのサブグラフをリストするための実装:
@Test
public void
whenGetStronglyConnectedSubgraphs_thenPathExists() {
StrongConnectivityAlgorithm<String, DefaultEdge> scAlg
= new KosarajuStrongConnectivityInspector<>(directedGraph);
List<DirectedSubgraph<String, DefaultEdge>> stronglyConnectedSubgraphs
= scAlg.stronglyConnectedSubgraphs();
List<String> stronglyConnectedVertices
= new ArrayList<>(stronglyConnectedSubgraphs.get(3)
.vertexSet());
String randomVertex1 = stronglyConnectedVertices.get(0);
String randomVertex2 = stronglyConnectedVertices.get(3);
AllDirectedPaths<String, DefaultEdge> allDirectedPaths
= new AllDirectedPaths<>(directedGraph);
List<GraphPath<String, DefaultEdge>> possiblePathList
= allDirectedPaths.getAllPaths(
randomVertex1, randomVertex2, false,
stronglyConnectedVertices.size());
assertTrue(possiblePathList.size() > 0);
}
4.4. オイラー回路
グラフのオイラー回路Gは、Gのすべての頂点とエッジを含む回路です。 それを持っているグラフはオイラーグラフです。
グラフを見てみましょう。
public void createGraphWithEulerianCircuit() {
SimpleWeightedGraph<String, DefaultEdge> simpleGraph
= new SimpleWeightedGraph<>(DefaultEdge.class);
IntStream.range(1,5)
.forEach(i-> simpleGraph.addVertex("v" + i));
IntStream.range(1,5)
.forEach(i-> {
int endVertexNo = (i + 1) > 5 ? 1 : i + 1;
simpleGraph.addEdge("v" + i,"v" + endVertexNo);
});
}
これで、APIを使用して、グラフにオイラー回路が含まれているかどうかをテストできます。
@Test
public void givenGraph_whenCheckEluerianCycle_thenGetResult() {
HierholzerEulerianCycle eulerianCycle
= new HierholzerEulerianCycle<>();
assertTrue(eulerianCycle.isEulerian(simpleGraph));
}
@Test
public void whenGetEulerianCycle_thenGetGraphPath() {
HierholzerEulerianCycle eulerianCycle
= new HierholzerEulerianCycle<>();
GraphPath path = eulerianCycle.getEulerianCycle(simpleGraph);
assertTrue(path.getEdgeList()
.containsAll(simpleGraph.edgeSet()));
}
4.5. ハミルトン閉路
各頂点を1回だけ訪問するGraphPathは、ハミルトンパスと呼ばれます。
ハミルトン閉路(またはハミルトン閉路)は、パスの最後の頂点から最初の頂点までのエッジ(グラフ内)が存在するようなハミルトンパスです。
HamiltonianCycle.getExplicitOptimalForCompleteGraph()メソッドを使用して、完全グラフに最適なハミルトン閉路を見つけることができます。
このメソッドは、おおよその最小限の巡回セールスマンツアー(ハミルトンサイクル)を返します。 最適な解はNP完全であるため、これは多項式時間で実行される適切な近似です。
public void
whenGetHamiltonianCyclePath_thenGetVerticeSequence() {
List<String> verticeList = HamiltonianCycle
.getApproximateOptimalForCompleteGraph(completeGraph);
assertEquals(verticeList.size(), completeGraph.vertexSet().size());
}
4.6. サイクル検出器
グラフにサイクルがあるかどうかも確認できます。 現在、CycleDetectorは有向グラフのみをサポートしています。
@Test
public void whenCheckCycles_thenDetectCycles() {
CycleDetector<String, DefaultEdge> cycleDetector
= new CycleDetector<String, DefaultEdge>(directedGraph);
assertTrue(cycleDetector.detectCycles());
Set<String> cycleVertices = cycleDetector.findCycles();
assertTrue(cycleVertices.size() > 0);
}
5. グラフの視覚化
JGraphTを使用すると、グラフの視覚化を生成して画像として保存できます。まず、MavenCentralからjgrapht-ext拡張依存関係を追加しましょう。
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-ext</artifactId>
<version>1.0.1</version>
</dependency>
次に、3つの頂点と3つのエッジを持つ単純な有向グラフを作成しましょう。
@Before
public void createGraph() {
File imgFile = new File("src/test/resources/graph.png");
imgFile.createNewFile();
DefaultDirectedGraph<String, DefaultEdge> g =
new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
String x1 = "x1";
String x2 = "x2";
String x3 = "x3";
g.addVertex(x1);
g.addVertex(x2);
g.addVertex(x3);
g.addEdge(x1, x2);
g.addEdge(x2, x3);
g.addEdge(x3, x1);
}
これで、このグラフを視覚化できます。
@Test
public void givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist() throws IOException {
JGraphXAdapter<String, DefaultEdge> graphAdapter =
new JGraphXAdapter<String, DefaultEdge>(g);
mxIGraphLayout layout = new mxCircleLayout(graphAdapter);
layout.execute(graphAdapter.getDefaultParent());
BufferedImage image =
mxCellRenderer.createBufferedImage(graphAdapter, null, 2, Color.WHITE, true, null);
File imgFile = new File("src/test/resources/graph.png");
ImageIO.write(image, "PNG", imgFile);
assertTrue(imgFile.exists());
}
ここでは、コンストラクター引数としてグラフを受け取る JGraphXAdapter を作成し、それにmxCircleLayoutを適用しました。 これにより、視覚化が循環的にレイアウトされます。
さらに、mxCellRendererを使用してBufferedImageを作成し、視覚化をpngファイルに書き込みます。
最終的な画像は、ブラウザまたはお気に入りのレンダラーで確認できます。
詳細については、公式ドキュメントをご覧ください。
6. 結論
JGraphTは、ほぼすべてのタイプのグラフとさまざまなグラフアルゴリズムを提供します。 いくつかの一般的なAPIの使用方法について説明しました。 ただし、公式ページでいつでもライブラリを探索できます。
これらすべての例とコードスニペットの実装は、Githubのにあります。