Aritalab:Lecture/Programming/Java/Graph/Node

Latest revision as of 10:05, 28 April 2011

[edit] グラフ頂点のリスト構造

グラフ頂点は二重リンクリストの要素として実現します。

public class GraphNode extends ListEntry
  {
    protected int v_id = 0;

    protected Graph owner = null;

    protected GraphEdge[] first_inout_edge = new GraphEdge[2];

    protected GraphEdge[] last_inout_edge = new GraphEdge[2];

    protected int[] inout_deg = new int[2];

    public String toString()
      {
        return ("Node " + v_id + " (" + data + ")");
      }

    private void add_adj_edge(GraphEdge e, int in_out)
      {
        GraphEdge last = this.last_inout_edge[in_out];

        if (last == null)
          { // first edge
            first_inout_edge[in_out] = e;
            last_inout_edge[in_out] = e;
          }
        else
          { // addLast
            last.succ_inout_edge[in_out] = e;
            e.pred_inout_edge[in_out] = last;
            last_inout_edge[in_out] = e;
          }
        inout_deg[in_out]++;
      }

    private void del_adj_edge(GraphEdge e, int in_out)
      {
        GraphEdge e_succ = e.succ_inout_edge[in_out];
        GraphEdge e_pred = e.pred_inout_edge[in_out];

        if (e_succ != null)
          {
            e_succ.pred_inout_edge[in_out] = e_pred;
            e.succ_inout_edge[in_out] = null;
          }
        else
          last_inout_edge[in_out] = e_pred;

        if (e_pred != null)
          {
            e_pred.succ_inout_edge[in_out] = e_succ;
            e.pred_inout_edge[in_out] = null;
          }
        else
          first_inout_edge[in_out] = e_succ;

        inout_deg[in_out]--;
      }

    public GraphNode()
      {
        data = new NodeData();
      }

    public GraphNode(NodeData nd)
      {
        data = nd;
      }

    protected void add_in_edge(GraphEdge e)
      {
        add_adj_edge(e, 0);
      }

    protected void add_out_edge(GraphEdge e)
      {
        add_adj_edge(e, 1);
      }

    protected void del_in_edge(GraphEdge e)
      {
        del_adj_edge(e, 0);
      }

    protected void del_out_edge(GraphEdge e)
      {
        del_adj_edge(e, 1);
      }

    protected GraphEdge first_in_edge()
      {
        return first_inout_edge[0];
      }

    protected GraphEdge first_out_edge()
      {
        return first_inout_edge[1];
      }

    protected int indeg()
      {
        return inout_deg[0];
      }

    protected int outdeg()
      {
        return inout_deg[1];
      }

    protected int inoutdeg()
      {
        return (inout_deg[0] + inout_deg[1]);
      }
  }