まず簡単なグラフとして、三つのノード(vertex、node)、二つのエッジ(edge)を持つ無向グラフを作成しましょう。
1: import edu.uci.ics.jung.graph._ 2: object Sample1a { 3: def main(args: Array[String]): Unit = { 4: val graph: Graph[Int,Int] = new UndirectedSparseGraph[Int,Int] 5: graph.addVertex(1) 6: graph.addVertex(2) 7: graph.addVertex(3) 8: graph.addEdge(101, 1, 2) 9: graph.addEdge(102, 2, 3) 10: println("Graph G = " + graph.toString) 11: } 12: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:1,2,3 Edges:102[2,3] 101[1,2]
グラフはトレイトGraph[V,E]で表されます。これはジェネリック型のトレイトなので、型パラメータのVとEに適当なクラスを挿入することで、様々なクラスをノードやエッジとして使用できます。上のプログラムでは、ノードとエッジをどちらもInt型で表しています。Graph[Int,Int]はノードとエッジをIntオブジェクトで表現するグラフのトレイトです。UndirectedSparseGraph[Int,Int]はこのトレイトを実装したクラスとなります。ノードの追加はaddVertex()メソッドで、エッジの追加はaddEdge()メソッドで行います。graph.addVertex(1)はノード「1」を作成します。graph.addEdge(101, 1, 2)はエッジ「101」を作成します。ノード「1」と「2」がこのエッジの両端になります。
【注】JUNG2.0はJavaのライブラリなので、Graph[V,E]などは「トレイト」ではなく、「インタフェース」として提供されています。ここではScalaでの利用を想定しているので、Scalaの用語に合わせて「トレイト」や「ミックスイン」を使っています。
Sample1a.scalaはノードもエッジもInt型で表されました。次の例では同じ構造の無向グラフ(三つのノードと二つのエッジ)を、ノードとエッジをString型で表しましょう。こうすることで、ノードやエッジにラベル(文字列)を付けることができます。
1: import edu.uci.ics.jung.graph._ 2: object Sample1b { 3: def main(args: Array[String]): Unit = { 4: val graph: Graph[String,String] = new UndirectedSparseGraph[String,String] 5: graph.addVertex("n1") 6: graph.addVertex("n2") 7: graph.addVertex("n3") 8: graph.addEdge("e1", "n1", "n2") 9: graph.addEdge("e2", "n2", "n3") 10: println("Graph G = " + graph.toString) 11: } 12: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:n1,n3,n2 Edges:e1[n1,n2] e2[n2,n3]
ノードとエッジを異なる型で表すこともできます。次の例ではノードはInt型で、エッジはString型で表されます。
1: import edu.uci.ics.jung.graph._ 2: object Sample1c { 3: def main(args: Array[String]): Unit = { 4: val graph: Graph[Int,String] = new UndirectedSparseGraph[Int,String] 5: graph.addVertex(1) 6: graph.addVertex(2) 7: graph.addVertex(3) 8: graph.addEdge("e1", 1, 2) 9: graph.addEdge("e2", 2, 3) 10: println("Graph G = " + graph.toString) 11: } 12: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:1,2,3 Edges:e1[1,2] e2[2,3]
応用によってはノードやエッジに文字列以外の情報を付与したいこともあるでしょう。そのような時にはノードやエッジのクラスを独自に定義することも可能です。自分が独自に定義したクラスをノードとエッジにしてグラフを作成してみましょう。
次の例ではまずMyNodeクラスとMyEdgeクラスを定義し、それらを使ったグラフを作成します。MyNodeクラスもMyEdgeクラスも簡単にするために、フィールドとしてString型のlabelだけを持ちます。
1: class MyNode(val label: String) { 2: override def toString: String = label 3: }
1: class MyEdge(val label: String) { 2: override def toString: String = label 3: }
1: import edu.uci.ics.jung.graph._ 2: object Sample2a { 3: def main(args: Array[String]): Unit = { 4: val graph: Graph[MyNode,MyEdge] = new UndirectedSparseGraph[MyNode,MyEdge] 5: val n1 = new MyNode("n1") 6: val n2 = new MyNode("n2") 7: val n3 = new MyNode("n3") 8: graph.addVertex(n1) 9: graph.addVertex(n2) 10: graph.addVertex(n3) 11: graph.addEdge(new MyEdge("e1"), n1, n2) 12: graph.addEdge(new MyEdge("e2"), n2, n3) 13: println("Graph G = " + graph.toString) 14: } 15: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:n1,n2,n3 Edges:e1[n1,n2] e2[n2,n3]
次の例ではエッジに接続するノードにアクセスする方法を紹介します。
1: import edu.uci.ics.jung.graph._ 2: import edu.uci.ics.jung.graph.util.Pair 3: object Sample2b { 4: def main(args: Array[String]): Unit = { 5: val graph: Graph[MyNode,MyEdge] = new UndirectedSparseGraph[MyNode,MyEdge] 6: val n1 = new MyNode("n1") 7: val n2 = new MyNode("n2") 8: val n3 = new MyNode("n3") 9: graph.addVertex(n1) 10: graph.addVertex(n2) 11: graph.addVertex(n3) 12: val e1 = new MyEdge("e1") 13: val e2 = new MyEdge("e2") 14: graph.addEdge(e1, n1, n2); 15: graph.addEdge(e2, n2, n3); 16: println("Graph G = " + graph.toString) 17: val pair: Pair[MyNode] = graph.getEndpoints(e1) 18: val m1 = pair.getFirst 19: val m2 = pair.getSecond 20: println(e1.label + " = {" + m1 + ", " + m2 + "}") 21: } 22: }
Sample2b.scalaでは、Sample2a.scalaとは違い、エッジの端点(エッジに接続するノード)にアクセスできるように、12行目(と13行目)で、MyEdge型の変数e1(とe2)を用意して、MyEdgeのインスタンスを代入しています。
また、17行目から20行目が追加されています。getEndpoints()メソッドはエッジを引数として、それに接続するノードの組(pair)を返します。getFirst()メソッドとgetSecond()メソッドは組から要素(この場合はMyNodeのインスタンス)を返します。
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:n2,n1,n3 Edges:e2[n2,n3] e1[n1,n2] e1 = {n1, n2}
グラフを視覚的に表示するためには、グラフをレイアウトする必要があります。つまりノードを適切に配置し、エッジをその両端のノードを接続するように配線しなければなりません。自動的にレイアウトする方法は後で説明することにして、まずはマニュアルでレイアウトしてグラフを描く方法を説明しましょう。
マニュアルレイアウトではノード毎に具体的な座標を指定します。JUNGではエッジはノードを接続するように描かれるので配線については気にする必要はありません。
1: import java.awt.Dimension 2: import java.awt.geom.Point2D 3: import javax.swing.JFrame 4: import edu.uci.ics.jung.algorithms.layout.{Layout,StaticLayout} 5: import edu.uci.ics.jung.graph.{Graph,UndirectedSparseGraph} 6: import edu.uci.ics.jung.visualization.BasicVisualizationServer 7: object Sample3a { 8: def main(args: Array[String]): Unit = { 9: val graph: Graph[MyNode,MyEdge] = new UndirectedSparseGraph[MyNode,MyEdge] 10: val n1 = new MyNode("n1") 11: val n2 = new MyNode("n2") 12: val n3 = new MyNode("n3") 13: graph.addVertex(n1) 14: graph.addVertex(n2) 15: graph.addVertex(n3) 16: graph.addEdge(new MyEdge("e1"), n1, n2) 17: graph.addEdge(new MyEdge("e2"), n2, n3) 18: val layout: Layout[MyNode,MyEdge] = new StaticLayout[MyNode,MyEdge](graph) 19: layout.setLocation(n1, new Point2D.Double(100, 100)) 20: layout.setLocation(n2, new Point2D.Double(200, 100)) 21: layout.setLocation(n3, new Point2D.Double(150, 200)) 22: val panel = new BasicVisualizationServer[MyNode,MyEdge](layout, new Dimension(300, 300)) 23: val frame: JFrame = new JFrame("Graph View: Manual Layout") 24: frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE) 25: frame.getContentPane.add(panel) 26: frame.pack() 27: frame.setVisible(true) 28: } 29: }
9行目から17行目でグラフgraphを作成したあと、18行目から21行目でレイアウトを作成しています。Layout[MyNode,MyEdge]はMyNodeとMyEdgeからなるグラフのレイアウトを表わすトレイトです。StaticLayout[MyNode,MyEdge]はこのトレイトを拡張したクラスです。setLocation()メソッドで、各ノードの位置を指定しています。たとえば、layout.setLocation(n1, new Point2D.Double(100, 100))はノードn1に座標(100, 100)を指定しています。
レイアウトを生成したあと、22行目で、そのレイアウトを引数として、BasicVisualizationServer[MyNode,MyEdge]クラスのインスタンスを生成しています。BasicVisualizationServer[MyNode,MyEdge]はjavax.swing.JPanelクラスのサブクラスです。引数として指定したレイアウトがJPanel上に描かれます。第二引数は描画エリアのサイズで、この場合は300×300ピクセル、を指定しています。
23行目から後の部分ではウィンドウ(フレーム)を作成しています。Swingを用いたプログラムで良く見られる基本的なパターンです。25行目では、frame.getContentPane.add(panel)で、フレームのcontentPaneオブジェクト(java.awt.Containerクラスのインスタンス)を取り出し、それに上で作成したpanelオブジェクト(BasicVisualizationServer[MyNode,MyEdge]クラスのインスタンス)を追加しています。
このプログラムを実行するとすると下のようなウィンドウが現われます。
プログラムがだいぶ長くなってロジックが見え難くくなったので、いくつかの変形を紹介する前にグラフを作成する部分をメソッドに切り出しましょう。下はSample3a.scalaを改造して、グラフを作成する部分をcreateGraphメソッドに切り出したものです。このメソッドはグラフとレイアウトを組にして返します。
1: import java.awt.Dimension 2: import java.awt.geom.Point2D 3: import javax.swing.JFrame 4: import edu.uci.ics.jung.algorithms.layout.{Layout,StaticLayout} 5: import edu.uci.ics.jung.graph.{Graph,UndirectedSparseGraph} 6: import edu.uci.ics.jung.visualization.BasicVisualizationServer 7: object Sample3a1 { 8: def main(args: Array[String]): Unit = { 9: val (graph, layout) = createGraph 10: val panel = new BasicVisualizationServer[MyNode,MyEdge](layout, new Dimension(300, 300)) 11: val frame: JFrame = new JFrame("Graph View: Manual Layout") 12: frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE) 13: frame.getContentPane.add(panel) 14: frame.pack() 15: frame.setVisible(true) 16: } 17: def createGraph: Tuple2[Graph[MyNode,MyEdge],Layout[MyNode,MyEdge]] = { 18: val graph: Graph[MyNode,MyEdge] = new UndirectedSparseGraph[MyNode,MyEdge]() 19: val n1 = new MyNode("n1") 20: val n2 = new MyNode("n2") 21: val n3 = new MyNode("n3") 22: graph.addVertex(n1) 23: graph.addVertex(n2) 24: graph.addVertex(n3) 25: graph.addEdge(new MyEdge("e1"), n1, n2) 26: graph.addEdge(new MyEdge("e2"), n2, n3) 27: val layout: Layout[MyNode,MyEdge] = new StaticLayout[MyNode,MyEdge](graph) 28: layout.setLocation(n1, new Point2D.Double(100, 100)) 29: layout.setLocation(n2, new Point2D.Double(200, 100)) 30: layout.setLocation(n3, new Point2D.Double(150, 200)) 31: (graph, layout) 32: } 33: }
ScalaではSwingのアプリケーションを作成するためのフレームワークを提供するSwingApplicationクラスが用意されています。そのサブクラスであるSimpleSwingApplicationを使用してみましょう。これを使用するとJFrameに関する基本的なコードをいくつか省略できます。
1: import swing._ 2: import java.util._ (中略) 8: object Sample3a3 extends SimpleSwingApplication { 9: def top = new MainFrame { 10: title = "Graph View: Manual Layout" 11: val (graph, layout) = createGraph 12: val panel = new BasicVisualizationServer[MyNode,MyEdge](layout, new Dimension(300, 300)) 13: contents = Component.wrap(panel) 14: } 15: def createGraph: Tuple2[Graph[MyNode,MyEdge],Layout[MyNode,MyEdge]] = { (中略) 30: } 31: }
8行目でSimpleSwingApplicationを拡張してオブジェクトを定義しています。メインメソッドの代りに、topを定義しています。JFrameの代りにscala.swing.FrameクラスのサブクラスであるMainFrameクラスのオブジェクトを使用します。10行目はウィンドウのタイトルを設定しています。11行目と12行目は、Sample3a1.scalaの9行目から10行目と同じです。13行目がSample3a1.scalaの13行目に相当します。もしpanelがscala.swing.Component型であれば、単に下のように代入すれば良いのですが、実際にはjavax.swing.JPanel型ですのでそのままでは代入できません。
contents = panel
そこで、13行目のようにComponent.wrap()メソッドでJPanel型をscala.swing.Component型に変換しています。Component.wrap()メソッドはjavax.swing.JComponent型をscala.swing.Component型に変換してくれます。
下のように改造することでjavax.swing.JComponent型からscala.swing.Component型への変換に、暗黙の型変換を利用することもできます。ただし、ここで紹介している例では、変換は1度だけなので、暗黙の型変換を使うよりもSample3a3.scalaのように明示的に変換した方が、明確で良いでしょう。
8: object Sample3a4 extends SimpleSwingApplication { 9: def top = new MainFrame { 10: title = "Graph View: Manual Layout" 11: val (graph, layout) = createGraph 12: val panel = new BasicVisualizationServer[MyNode,MyEdge](layout, new Dimension(300, 300)) 13: contents = panel 14: } 15: implicit def componentWrapper(c: javax.swing.JComponent): Component = Component.wrap(c)
これまでの例はすべて無向グラフを扱いましたが、JUNG2.0では無向グラフだけでなく、有向グラフも扱うことができます。詳細はJUNG API Javadoc (version 2.0)を参照して下さい。
トレイトGraph[V,E]のサブトレイトとして、無向グラフを表すUndirectedGraph[V,E]と有向グラフを表すDirectedGraph[V,E]が用意されています。これ以外にK部グラフ(ノードがK個の部分集合に分けられ、それぞれの部分集合内のノードをつなぐエッジが存在しないようなグラフ)を表すKPartiteGraph[V,E]もトレイトGraph[V,E]のサブトレイトとして用意されています。また、DirectedGraph[V,E]のサブトレイトとして森を表すForest[V,E]があり、さらにそのサブトレイトとして有向(根付き)木を表すTree[V,E]があります。
上記のトレイトを拡張したクラスがいくつか用意されています。
Sample3a.scalaを改造して、UndirectedSparseGraph[MyNode,MyEdge]の代りにDirectedSparseGraph[MyNode,MyEdge]を使用すると、下のようにエッジが向きを表す矢印で描かれます。