DoubleDirectedCycleRemover.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.matrix.IntMatrix;
import org.mklab.nfc.scalar.DoubleNumber;


/**
 * 有向閉路をもたない(重み)最大連結グラフを求めるクラスです。
 * 
 * @author koga
 * @version $Revision: 1.6 $, 2006/12/09
 */
public class DoubleDirectedCycleRemover {

  /** グラフの隣接行列 */
  private DoubleMatrix adjacencyMatrix;
  /** 有向閉路をもたない(重み)最大連結グラフの隣接行列 */
  private DoubleMatrix maximumNoDirectedCycleGraph;

  /** 有向閉路をもたない(重み)最大連結グラフを作るために切るべきノードのリスト */
  private List<Integer> cuttingNodes;

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

  /**
   * 有向閉路をもたない(重み)最大連結グラフを作るために切るべきノードのリストを返します。
   * 
   * @return 有向閉路をもたない(重み)最大連結グラフを作るために切るべきノードのリスト
   * @throws RuntimeException 有向閉路をもたない(重み)最大連結グラフの生成に失敗した場合
   */
  public List<Integer> getCuttingNodes() {
    if (this.maximumNoDirectedCycleGraph == null) {
      getMaximumNoDirectedCycleGraphAndCuttingNodes();
    }

    return this.cuttingNodes;
  }

  /**
   * 有向閉路をもたない(重み)最大連結グラフの隣接行列を返します。
   * 
   * @return 有向閉路をもたない(重み)最大連結グラフの隣接行列
   * @throws RuntimeException 有向閉路をもたない(重み)最大連結グラフの生成に失敗した場合
   */
  public DoubleMatrix getMaximumNoDirectedCycleGraph() {
    if (this.maximumNoDirectedCycleGraph == null) {
      getMaximumNoDirectedCycleGraphAndCuttingNodes();
    }

    return this.maximumNoDirectedCycleGraph;
  }

  /**
   * 有向閉路をもたない(重み)最大連結グラフ、および、有向閉路をもたない(重み)最大連結グラフを作るために切るべきノードを求めます。
   * 
   * @throws RuntimeException 有向閉路をもたない(重み)最大連結グラフの生成に失敗した場合
   */
  @SuppressWarnings("boxing")
  private void getMaximumNoDirectedCycleGraphAndCuttingNodes() {
    final DoubleMatrix adjMatrix = this.adjacencyMatrix.createClone();

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

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

      final ElementHolder<DoubleNumber> maximumEdge = adjMatrix.maximum();
      final double weight = maximumEdge.getElement().doubleValue();
      final int row = maximumEdge.getRow();

      final IntMatrix nonZeroColumn = adjMatrix.getRowVector(row).compareElementWise(".!=", 0).find(); //$NON-NLS-1$

      for (int i = 1; i <= nonZeroColumn.length(); i++) {
        this.maximumNoDirectedCycleGraph.setElement(row, nonZeroColumn.getIntElement(i), weight);
      }

      if (new DoubleCycleMatrix(this.maximumNoDirectedCycleGraph).hasCycle()) {
        for (int i = 1; i <= nonZeroColumn.length(); i++) {
          this.maximumNoDirectedCycleGraph.setElement(row, nonZeroColumn.getIntElement(i), 0);
        }

        this.cuttingNodes.add(row);
      }

      for (int i = 1; i <= nonZeroColumn.length(); i++) {
        adjMatrix.setElement(row, nonZeroColumn.getIntElement(i), 0);
      }
    }

    if (adjMatrix.isZero()) {
      return;
    }

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