Kuruskal.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.ComplexNumericalMatrix;
import org.mklab.nfc.matrix.ElementHolder;
import org.mklab.nfc.matrix.RealNumericalMatrix;
import org.mklab.nfc.scalar.ComplexNumericalScalar;
import org.mklab.nfc.scalar.RealNumericalScalar;


/**
 * J.B.クルスカルのアルゴリズムを用いて最小全域木を求めるクラスです。
 * 
 * @author koga
 * @version $Revision: 1.5 $, 2006/12/09
 * @param <RS> type of real scalar
 * @param <RM> type of real matrix
 * @param <CS> type of complex scalar
 * @param <CM> type of complex matrix
 */
public class Kuruskal<RS extends RealNumericalScalar<RS, RM, CS, CM>, RM extends RealNumericalMatrix<RS, RM, CS, CM>, CS extends ComplexNumericalScalar<RS, RM, CS, CM>, CM extends ComplexNumericalMatrix<RS, RM, CS, CM>> {

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

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

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

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

    return this.cuttingNodes;
  }

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

    return this.minimumSpanningTree;
  }

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

    RS sunit = this.adjacencyMatrix.getElement(1,1).createUnit();
    this.minimumSpanningTree = sunit.createZeroGrid(adjMatrix.getRowSize(), adjMatrix.getColumnSize());
    this.cuttingNodes = new ArrayList<>();

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

      ElementHolder<RS> minimumEdge = adjMatrix.minimum();
      RS weight = minimumEdge.getElement();

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

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

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

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