Aritalab:Lecture/Programming/Java/Graph

Revision as of 09:52, 28 April 2011

グラフの構造

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

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;
      }
  }