DirectedCycleRemover.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.IntMatrix;
import org.mklab.nfc.matrix.RealNumericalMatrix;
import org.mklab.nfc.scalar.ComplexNumericalScalar;
import org.mklab.nfc.scalar.RealNumericalScalar;


/**
 * 有向閉路をもたない(重み)最大連結グラフを求めるクラスです。
 * 
 * @author koga
 * @version $Revision: 1.6 $, 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 DirectedCycleRemover<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 maximumNoDirectedCycleGraph;

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

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

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

    return this.cuttingNodes;
  }

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

    return this.maximumNoDirectedCycleGraph;
  }

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

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

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

      final ElementHolder<RS> maximumEdge = adjMatrix.maximum();
      final RS weight = maximumEdge.getElement();
      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 CycleMatrix<>(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$
  }
}