まず簡単なグラフとして、三つのノード(vertex、node)、二つのエッジ(edge)を持つ無向グラフを作成しましょう。
1: import edu.uci.ics.jung.graph.Graph; 2: import edu.uci.ics.jung.graph.UndirectedSparseGraph; 3: public class Sample1a { 4: public static void main(String[] args) { 5: Graph<Integer,Integer> graph = new UndirectedSparseGraph<Integer,Integer>(); 6: graph.addVertex(1); 7: graph.addVertex(2); 8: graph.addVertex(3); 9: graph.addEdge(101, 1, 2); 10: graph.addEdge(102, 2, 3); 11: System.out.println("Graph G = " + graph.toString()); 12: } 13: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:1,2,3 Edges:102[2,3] 101[1,2]
グラフはインタフェースGraph<V, E>で表わされます。これはジェネリック型のインタフェースなので、型パラメータのVとEに適当なクラスを挿入することで、様々なクラスをノードやエッジとして使用できます。上のプログラムでは、ノードとエッジをIntegerで表しています。Graph<Integer, Integer>はノードとエッジをIntegerオブジェクトで表現するグラフのインタフェースです。UndirectedSparseGraph<Integer, Integer>はこのインタフェースが実装されたクラスとなります。ノードの追加はaddVertex()メソッドで行います。また、エッジの追加はaddEdge()メソッドで行います。graph.addVertex(1);はノード「1」を作成します。正式にはgraph.addVertex(new Integer(1));と書きます。graph.addEdge(101, 1, 2);はエッジ「101」を作成します。ノード「1」と「2」がこのエッジの両端になります。
(補足)graph.addEdge(101, 1, 2);が呼ばれたときにノード「1」が無ければ、自動的にノード「1」を作ってくれるようです。つまり、graph.addVertex(1);〜graph.addVertex(3);を省略しても特に問題無いようです。
Sample1a.javaはノードもエッジもIntegerクラスで表されました。次の例では同じ構造の無向グラフ(三つのノードと二つのエッジ)ですが、ノードとエッジをStringクラスで表しましょう。こうすることで、ノードやエッジにラベル(文字列)を付けることができます。
1: import edu.uci.ics.jung.graph.Graph; 2: import edu.uci.ics.jung.graph.UndirectedSparseGraph; 3: public class Sample1b { 4: public static void main(String[] args) { 5: Graph<String,String> graph = new UndirectedSparseGraph<String,String>(); 6: graph.addVertex("n1"); 7: graph.addVertex("n2"); 8: graph.addVertex("n3"); 9: graph.addEdge("e1", "n1", "n2"); 10: graph.addEdge("e2", "n2", "n3"); 11: System.out.println("Graph G = " + graph.toString()); 12: } 13: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:n1,n3,n2 Edges:e1[n1,n2] e2[n2,n3]
ノードとエッジを異なるクラスで表すこともできます。次の例ではノードはIntegerクラスで、エッジはStringクラスで表されます。
1: import edu.uci.ics.jung.graph.Graph; 2: import edu.uci.ics.jung.graph.UndirectedSparseGraph; 3: public class Sample1c { 4: public static void main(String[] args) { 5: Graph<Integer,String> graph = new UndirectedSparseGraph<Integer,String>(); 6: graph.addVertex(1); 7: graph.addVertex(2); 8: graph.addVertex(3); 9: graph.addEdge("e1", 1, 2); 10: graph.addEdge("e2", 2, 3); 11: System.out.println("Graph G = " + graph.toString()); 12: } 13: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:1,2,3 Edges:e1[1,2] e2[2,3]
応用によってはノードやエッジに文字列以外の情報を付与したいこともあるでしょう。そのような時にはノードやエッジのクラスを独自に定義することも可能です。自分が独自に定義したクラスをノードとエッジにしてグラフを作成してみましょう。
次の例ではまずMyNodeクラスとMyEdgeクラスを定義し、それらを使ったグラフを作成します。MyNodeクラスもMyEdgeクラスも簡単にするために、Stringクラスのlabelだけを持ちます。
1: public class MyNode { 2: String label; 3: public MyNode(String label) { 4: this.label = label; 5: } 6: @Override 7: public String toString() { 8: return label; 9: } 10: }
1: public class MyEdge { 2: String label; 3: public MyEdge(String label) { 4: this.label = label; 5: } 6: @Override 7: public String toString() { 8: return label; 9: } 10: }
1: import edu.uci.ics.jung.graph.Graph; 2: import edu.uci.ics.jung.graph.UndirectedSparseGraph; 3: public class Sample2a { 4: public static void main(String[] args) { 5: Graph<MyNode,MyEdge> graph = new UndirectedSparseGraph<MyNode,MyEdge>(); 6: MyNode n1 = new MyNode("n1"); 7: MyNode n2 = new MyNode("n2"); 8: MyNode n3 = new MyNode("n3"); 9: graph.addVertex(n1); 10: graph.addVertex(n2); 11: graph.addVertex(n3); 12: graph.addEdge(new MyEdge("e1"), n1, n2); 13: graph.addEdge(new MyEdge("e2"), n2, n3); 14: System.out.println("Graph G = " + graph.toString()); 15: } 16: }
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:n1,n2,n3 Edges:e1[n1,n2] e2[n2,n3]
次の例ではエッジに接続するノードを取り出す方法を紹介します。
1: import edu.uci.ics.jung.graph.Graph; 2: import edu.uci.ics.jung.graph.UndirectedSparseGraph; 3: import edu.uci.ics.jung.graph.util.Pair; 4: public class Sample2b { 5: public static void main(String[] args) { 6: Graph<MyNode,MyEdge> graph = new UndirectedSparseGraph<MyNode,MyEdge>(); 7: MyNode n1 = new MyNode("n1"); 8: MyNode n2 = new MyNode("n2"); 9: MyNode n3 = new MyNode("n3"); 10: graph.addVertex(n1); 11: graph.addVertex(n2); 12: graph.addVertex(n3); 13: MyEdge e1 = new MyEdge("e1"); 14: MyEdge e2 = new MyEdge("e2"); 15: graph.addEdge(e1, n1, n2); 16: graph.addEdge(e2, n2, n3); 17: System.out.println("Graph G = " + graph.toString()); 18: Pair<MyNode> pair = graph.getEndpoints(e1); 19: MyNode m1 = pair.getFirst(); 20: MyNode m2 = pair.getSecond(); 21: System.out.println(e1.label + " = {" + m1 + ", " + m2 + "}"); 22: } 23: }
Sample2b.javaでは、Sample2a.javaとは違い、エッジの端点(エッジに接続するノード)を取り出せるように、13行目と14行目で、MyEdgeクラスの変数e1とe2を用意して、MyEdgeのインスタンスを代入しています。
また、18行目から21行目が追加されています。getEndpoints()メソッドはエッジを引数として、それに接続するノードの組(pair)を返します。getFirst()メソッドとgetSecond()メソッドは組から要素(この場合はMyNodeのインスタンス)を返します。
このプログラムを実行すると下のような結果がコンソールに表示されます。
Graph G = Vertices:n3,n1,n2 Edges:e1[n1,n2] e2[n2,n3] e1 = {n1, n2}
【注意】MyEdge.javaとSample2b.javaは同じパッケージに入れて下さい。可視性がパッケージプライベートの変数(String label)にクラス外からアクセスしていますので(Sample2b.javaの21行目)、パッケージを別にするとコンパイルエラーが出ます。本来であれば、適切なsetterやgetterを用意すべきですが、ここではサンプルプログラムをできるだけシンプルにするために、極力説明に不要なメソッドやフィールドは定義しないようにしています。以後の例でも、紹介するクラスはすべて同じパッケージに入れて下さい。
グラフを視覚的に表示するためには、グラフをレイアウトする必要があります。つまりノードを適切に配置し、エッジをその両端のノードを接続するように配線しなければなりません。自動的にレイアウトする方法は後で説明することにして、まずはマニュアルでレイアウトすることとして、グラフを描く方法を説明しましょう。
マニュアルレイアウトではノード毎に具体的な座標を指定します。JUNG2.0ではエッジはノードを接続するように描かれるので配線については気にする必要はありません。
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; 5: import edu.uci.ics.jung.algorithms.layout.StaticLayout; 6: import edu.uci.ics.jung.graph.Graph; 7: import edu.uci.ics.jung.graph.UndirectedSparseGraph; 8: import edu.uci.ics.jung.visualization.BasicVisualizationServer; 9: public class Sample3a { 10: public static void main(String[] args) { 11: Graph<MyNode,MyEdge> graph = new UndirectedSparseGraph<MyNode,MyEdge>(); 12: MyNode n1 = new MyNode("n1"); 13: MyNode n2 = new MyNode("n2"); 14: MyNode n3 = new MyNode("n3"); 15: graph.addVertex(n1); 16: graph.addVertex(n2); 17: graph.addVertex(n3); 18: graph.addEdge(new MyEdge("e1"), n1, n2); 19: graph.addEdge(new MyEdge("e2"), n2, n3); 20: Layout<MyNode,MyEdge> layout = new StaticLayout<MyNode,MyEdge>(graph); 21: layout.setLocation(n1, new Point2D.Double(100, 100)); 22: layout.setLocation(n2, new Point2D.Double(200, 100)); 23: layout.setLocation(n3, new Point2D.Double(150, 200)); 24: BasicVisualizationServer<MyNode,MyEdge> panel = new BasicVisualizationServer<MyNode,MyEdge>(layout, new Dimension(300, 300)); 25: JFrame frame = new JFrame("Graph View: Manual Layout"); 26: frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 27: frame.getContentPane().add(panel); 28: frame.pack(); 29: frame.setVisible(true); 30: } 31: }
グラフgraphを作成したあと、20行目から23行目でレイアウトを作成しています。Layout<MyNode,MyEdge>はMyNodeとMyEdgeからなるグラフのレイアウトを表わすインタフェースです。StaticLayout<MyNode,MyEdge>はこのインタフェースが実装されたクラスです。setLocation()メソッドで、各ノードの位置を指定しています。たとえば、layout.setLocation(n1, new Point2D.Double(100, 100));はノードn1に座標(100, 100)を指定しています。
レイアウトを生成したあと、24行目で、そのレイアウトを第1引数として、BasicVisualizationServer<MyNode,MyEdge>クラスのインスタンスを生成しています。BasicVisualizationServer<MyNode,MyEdge>クラスはjavax.swing.JPanelクラスのサブクラスです。引数として指定したレイアウトがJPanel上に描かれます。第2引数は描画領域のサイズ、この場合は300×300ピクセルを指定しています。
25行目から後の部分ではウィンドウ(フレーム)を作成しています。Swingを用いたプログラムで良く見られる基本的なパターンです。frame.getContentPane().add(panel);の行では、フレームのcontentPaneオブジェクト(java.awt.Containerクラスのインスタンス)を取り出し、それに上で作成したpanelオブジェクト(BasicVisualizationServer<MyNode,MyEdge>クラスのインスタンス)を追加しています。
このプログラムを実行するとすると下のようなウィンドウが現われます。
これまでの例はすべて無向グラフを扱いましたが、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.javaを改造して、UndirectedSparseGraph<MyNode,MyEdge>の代りにDirectedSparseGraph<MyNode,MyEdge>を使用すると、下のようにエッジが向きを表す矢印で描かれます。