Aritalab:Lecture/Programming/Java/Graph

グラフの構造

頂点の集合 V と、常に2頂点を結ぶ辺の集合 E の組をグラフ G(V, E) と書きます。 頂点には任意の数の辺が接続しうるので、グラフ構造をプログラミング言語で実現するには二重リスト構造を使います。 以下のプログラムのほかに

• 頂点の実装
• 辺の実装
• リストの実装
• リストの実装2

ファイルを用います。

public class Graph
  {
    private boolean directed = true;

    private int max_node_id = 0;
    private int max_edge_id = 0;

    private LinkedList v_list = new LinkedList();
    private LinkedList e_list = new LinkedList();

    public Graph() {}

    public void removeEdge(GraphEdge e)
      {
        GraphNode v = source(e);
        GraphNode w = target(e);

        if (v.owner != this)
          throw new Exception("removeEdge(e): e is not in G");

        v.del_out_edge(e);
        w.del_in_edge(e);

        e_list.remove(e);
      }

    public void removeNode(GraphNode v)
      {
        if (v.owner != this)
          throw new Exception("removeNode(v): v is not in G");

        GraphEdge e;
        for (int i = 0; i < 2; i)
              {
                v.first_inout_edge[i] = null;
                v.last_inout_edge[i] = null;
                v.inout_deg[i] = 0;
              }
          }
      }

    public void clear()
      {
        del_all_edges();
        v_list.clear();
        max_node_id = 0;
      }

    // 頂点の作成
    private GraphNode createNode(NodeData nd)
      {
        GraphNode v = new GraphNode(nd);
        v.owner = this;
        v.v_id = max_edge_id;
        this.e_list.append(e);
        v.add_out_edge(e);
        w.add_in_edge(e);

        return e;
      }

    public GraphEdge newEdge(GraphNode v, GraphNode w,
        EdgeData ed)
      {
        return createEdge(v, w, ed);
      }

    public GraphEdge newEdge(GraphNode v, GraphNode w)
      {
        return createEdge(v, w, new EdgeData());
      }

    // グラフを通して頂点や辺のデータを取得する
    public int index(GraphNode v)
      {
        return v.v_id;
      }

    public int index(GraphEdge e)
      {
        return e.e_id;
      }

    public int degree(GraphNode v)
      {
        return directed ? v.outdeg() : v.inoutdeg();
      }

    public int indeg(GraphNode v)
      {
        return v.indeg();
      }

    public int outdeg(GraphNode v)
      {
        return v.outdeg();
      }

    public int numberOfNodes()
      {
        return v_list.size();
      }

    public int numberOfEdges()
      {
        return e_list.size();
      }

    public GraphNode source(GraphEdge e)
      {
        return e.source;
      }

    public GraphNode target(GraphEdge e)
      {
        return e.target;
      }

    public GraphNode opposite(GraphEdge e, GraphNode v)
      {
        return (v == source(e)) ? target(e) : source(e);
      }

    public GraphNode firstNode()
      {
        return (GraphNode) v_list.head();
      }

    public GraphNode lastNode()
      {
        return (GraphNode) v_list.tail();
      }

    public GraphNode succNode(GraphNode v)
      {
        return (v != null) ? (GraphNode) v_list.Succ(v)
            : null;
      }

    public GraphNode predNode(GraphNode v)
      {
        return (v != null) ? (GraphNode) v_list.Pred(v)
            : null;
      }

    public GraphEdge firstEdge()
      {
        return (GraphEdge) e_list.head();
      }

    public GraphEdge lastEdge()
      {
        return (GraphEdge) e_list.tail();
      }

    public GraphEdge succEdge(GraphEdge e)
      {
        return (e != null) ? (GraphEdge) e_list.Succ(e)
            : null;
      }

    public GraphEdge predEdge(GraphEdge e)
      {
        return (e != null) ? (GraphEdge) e_list.Pred(e)
            : null;
      }

    public GraphEdge firstInEdge(GraphNode v)
      {
        return v.first_in_edge();
      }

    public GraphEdge firstOutEdge(GraphNode v)
      {
        return v.first_out_edge();
      }

    public GraphEdge succInEdge(GraphEdge e)
      {
        return e.succ_in_edge();
      }

    public GraphEdge succOutEdge(GraphEdge e)
      {
        return e.succ_out_edge();
      }

    public GraphEdge predInEdge(GraphEdge e)
      {
        return e.pred_in_edge();
      }

    public GraphEdge predOutEdge(GraphEdge e)
      {
        return e.pred_out_edge();
      }

    public boolean isDirected()
      {
        return directed;
      }

    public void makeDirected()
      {
        directed = true;
      }

    public void makeUndirected()
      {
        directed = false;
      }

    public GraphNode[] adjNodes(GraphNode v)
      {
        GraphNode[] ret = new GraphNode[degree(v)];
        int pos = 0;
        for (GraphEdge e = firstOutEdge(v); e != null; e = succOutEdge(e))
          ret[pos] = opposite(e, v);
        return ret;
      }

    public GraphEdge[] adjEdges(GraphNode v)
      {
        GraphEdge[] ret = new GraphEdge[degree(v)];
        int pos = 0;
        for (GraphEdge e = firstOutEdge(v); e != null; e = succOutEdge(e))
          ret[pos] = e;
        return ret;
      }

    public GraphEdge[] allEdges()
      {
        GraphEdge[] ret = new GraphEdge[numberOfEdges()];
        int i = 0;
        for (GraphEdge e = firstEdge(); e != null; e = succEdge(e))
          ret[i] = v;
        return ret;
      }
  }

ヒント

頂点や辺のデータにアクセスするにはメソッドを使う

汎用性のために頂点や辺が持つデータの型はObjectにしておきます。そうすると、実際に整数型が入っているときは以下のように使うことになります。

Integer i = (Integer)edge.target.data;

しかしこれでは、クラスの中身が丸見えで、後日リファクタリング等を行なう際の妨げにもなります。そのため各フィールドにアクセスするのにメソッドを使います。

Integer i = (Integer)edge.target().getData();

こうしておくと、後日たとえばtargetというフィールド名をtarget2変更したときに、コード中のtarget文字列を変更する必要はなくなります。

Node target() { return target2; }

というようにメソッドだけ変更すれば済むからです。

整数値と文字列の変換

Javaからユーザ入力された値を整数や実数として扱いたい場合が多々あります。スペース区切りの数値データを使う方法は以下のとおりです。

String input = "ここにデータが入る";

String[] data = input.split();

for (int i=0; i < data.length; i+ +)

{ int value = Integer.parseInt(data[i]); }

実数なら、Double.parseDouble(文字列); という関数があります。Boolean等も同じです。

データの隠蔽を心がける

Javaでコードを書くときは、そのコードを「ライブラリとして」後日使うことを意識すると便利です。例えば、グラフ構造のコードの中に、グラフ構造向けのアルゴリズムのコードが含まれることは望ましくありません。アルゴリズムはグラフ構造の外側からアクセスすべきです。

グラフ構造作成の好ましくない例

LinkedList edges = new LinkedList();

LinkedList nodes = new LinkedList();

Graph G = new Graph(nodes, edges);

こうしてしまうと、Graphクラス中で利用するデータ構造がLinkedListクラスであることがわかりますし、中身の入った別のLinkedListを渡すことも出来てしまいます。上記の実装は例えば以下のようにすべきです。

Class Graph {

LinkedList nodes, edges;

Graph() { nodes = new LinkedList(); edges = new LinkedList(); }

}

こうしてGraphクラスを作っていくと、例えばダイクストラ法で「頂点をvisitしたかどうか」をどう判定するか悩むことになります。Graphが使うNodeクラス中に、boolean visited; というフィールドを設けることは簡単ですが、これは他のほとんどの用途において無駄なフィールドになってしまいます。そのために、外部から全頂点や全辺の配列を得るメソッドを用意してあるのです。

Class Graph {

Node[] allNodes() {

Node[] ret = new Node[numberOfNodes()];

int i=0;

for(Node n = nodes.head(); n != null; n = n.next()) ret[i+ +] = n;

return ret;

}

}

この戻り値は配列である必要はなく、ハッシュテーブルや双方向リストのままでもOKです。ただし、

LinkedList allNodes() { return nodes; }

という実装は好ましくありません。これはGraphクラスの中身をそのまま渡してしまうため、せっかく隠蔽している意味がなくなってしまいます。