DoubleKuruskal.java

/*
 * Created on 2006/12/09
 * Copyright (C) 2006 Koga Laboratory. All rights reserved.
 *
 */
package org.mklab.tool.control.system.graph;

import java.util.ArrayList;
import java.util.List;

import org.mklab.nfc.matrix.DoubleMatrix;
import org.mklab.nfc.matrix.ElementHolder;
import org.mklab.nfc.scalar.DoubleNumber;


/**
 * J.B.クルスカルのアルゴリズムを用いて最小全域木を求めるクラスです。
 * 
 * @author koga
 * @version $Revision: 1.5 $, 2006/12/09
 */
public class DoubleKuruskal {

  /** グラフの隣接行列 */
  private DoubleMatrix adjacencyMatrix;
  /** 最小全域木の隣接行列 */
  private DoubleMatrix minimumSpanningTree;

  /** 最小全域木を作るために切るべきノードのリスト */
  private List<Integer> cuttingNodes;

  /**
   * 新しく生成された<code>Kuruskal</code>オブジェクトを初期化します。
   * 
   * @param adjacencyMatrix グラフの隣接行列
   */
  public DoubleKuruskal(DoubleMatrix adjacencyMatrix) {
    this.adjacencyMatrix = adjacencyMatrix;
  }

  /**
   * 最小全域木を作るために切るべきノードのリストを返します。
   * 
   * @return 最小全域木を作るために切るべきノードのリスト
   * @throws RuntimeException 最小全域木の生成に失敗した場合
   */
  public List<Integer> getCuttingNodes() {
    if (this.minimumSpanningTree == null) {
      getMinimumSpanningTreeAndCuttingNodes();
    }

    return this.cuttingNodes;
  }

  /**
   * 最小全域木の隣接行列を返します。
   * 
   * @return 最小全域木の隣接行列
   * @throws RuntimeException 最小全域木の生成に失敗した場合
   */
  public DoubleMatrix getMinimumSpanningTree() {
    if (this.minimumSpanningTree == null) {
      getMinimumSpanningTreeAndCuttingNodes();
    }

    return this.minimumSpanningTree;
  }

  /**
   * 最小全域木、および、最小全域木を作るために切るべきノードを求めます。
   * 
   * @throws RuntimeException 最小全域木の生成に失敗した場合
   */
  @SuppressWarnings("boxing")
  private void getMinimumSpanningTreeAndCuttingNodes() {
    DoubleMatrix adjMatrix = this.adjacencyMatrix.createClone();

    this.minimumSpanningTree = DoubleMatrix.zero(adjMatrix);
    this.cuttingNodes = new ArrayList<>();

    int size = adjMatrix.getRowSize();
    for (int count = 0; count < size * size; count++) {
      if (adjMatrix.isZero()) {
        return;
      }

      ElementHolder<DoubleNumber> minimumEdge = adjMatrix.minimum();
      double weight = minimumEdge.getElement().doubleValue();

      int row = minimumEdge.getRow();
      int column = minimumEdge.getColumn();
      this.minimumSpanningTree.setElement(row, column, weight);

      if (new DoubleCycleMatrix(this.minimumSpanningTree).hasCycle()) {
        this.minimumSpanningTree.setElement(row, column, 0);
        this.cuttingNodes.add(column);
      }

      adjMatrix.setElement(row, column, 0.0);
    }

    throw new RuntimeException(Messages.getString("Kuruskal.0")); //$NON-NLS-1$
  }
}