DoubleCycleMatrix.java

/*
 * Created on 2006/11/05
 * 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.BooleanMatrix;
import org.mklab.nfc.matrix.DoubleMatrix;
import org.mklab.nfc.matrix.FundamentalArray;
import org.mklab.nfc.matrix.IntMatrix;
import org.mklab.tool.control.system.DoubleSystemOperator;


/**
 * 閉路行列(Cycle Matrix)を表すクラスです。
 * 
 * @author koga
 * @version $Revision: 1.7 $, 2006/11/05
 */
public class DoubleCycleMatrix {

  /** 隣接連結行列 */
  private BooleanMatrix adjacencyConnectionMatrix;

  /** 閉路情報を表わす行列 */
  private BooleanMatrix cycleMatrix;

  /**
   * 新しく生成された<code>CycleMatrix</code>オブジェクトを初期化します。
   * 
   * @param adjacencyMatrix 隣接行列
   */
  public DoubleCycleMatrix(final FundamentalArray<DoubleSystemOperator,?> adjacencyMatrix) {
    setAdjacencyConnectionMatrix(adjacencyMatrix);
    BooleanMatrix rMatrix = new DoubleReachableMatrix(adjacencyMatrix).getBooleanMatrix();
    this.cycleMatrix = rMatrix.andElementWise(rMatrix.transpose());
  }

  /**
   * 新しく生成された<code>CycleMatrix</code>オブジェクトを初期化します。
   * 
   * @param adjacencyMatrix 隣接行列
   */
  public DoubleCycleMatrix(final DoubleMatrix adjacencyMatrix) {
    setAdjacencyConnectionMatrix(adjacencyMatrix);
    BooleanMatrix rMatrix = new DoubleReachableMatrix(adjacencyMatrix).getBooleanMatrix();
    this.cycleMatrix = rMatrix.andElementWise(rMatrix.transpose());
  }

  /**
   * 隣接連結行列の値を設定します。
   * 
   * @param adjacencyMatrix 隣接行列
   */
  private void setAdjacencyConnectionMatrix(final FundamentalArray<DoubleSystemOperator,?> adjacencyMatrix) {
    final int rowSize = adjacencyMatrix.getRowSize();
    final int columnSize = adjacencyMatrix.getColumnSize();
    this.adjacencyConnectionMatrix = new BooleanMatrix(rowSize, columnSize);

    for (int row = 1; row <= rowSize; row++) {
      for (int column = 1; column <= columnSize; column++) {
        if (adjacencyMatrix.getElement(row, column).isZero() == false) {
          this.adjacencyConnectionMatrix.setElement(row, column, true);
        }
      }
    }
  }

  /**
   * 隣接連結行列の値を設定します。
   * 
   * @param adjacencyMatrix 隣接行列
   */
  private void setAdjacencyConnectionMatrix(final DoubleMatrix adjacencyMatrix) {
    final int rowSize = adjacencyMatrix.getRowSize();
    final int columnSize = adjacencyMatrix.getColumnSize();
    this.adjacencyConnectionMatrix = new BooleanMatrix(rowSize, columnSize);

    for (int row = 1; row <= rowSize; row++) {
      for (int column = 1; column <= columnSize; column++) {
        if (adjacencyMatrix.getDoubleElement(row, column) != 0) {
          this.adjacencyConnectionMatrix.setElement(row, column, true);
        }
      }
    }
  }

  /**
   * 閉路が存在するか判定します。
   * 
   * @return 閉路が存在するならばtrue、そうでなければfalse
   */
  public boolean hasCycle() {
    final int size = this.cycleMatrix.getRowSize();

    for (int i = 1; i <= size; i++) {
      // 同一行のtrueに対応するノードは同じループ内に存在する
      IntMatrix nodes = this.cycleMatrix.getRowVector(i).find();
      int nodeSize = nodes.length();
      boolean hasOnlyConnectionSelfLoop = nodeSize == 1 && (this.adjacencyConnectionMatrix.getElement(i, i) == false);
      if (nodes.isEmpty() || hasOnlyConnectionSelfLoop) {
        continue;
      }

      return true;
    }

    return false;
  }

  /**
   * 極大閉路を形成するノードのリストのリストを返します。
   * 
   * @return 極大閉路を形成するノードのリストのリスト
   */
  @SuppressWarnings("boxing")
  public List<List<Integer>> getLocalMaximumCycles() {
    List<List<Integer>> cycleList = new ArrayList<>();

    final int size = this.cycleMatrix.getRowSize();

    for (int i = 1; i <= size; i++) {
      // 同一行のtrueに対応するノードは同じループ内に存在する
      IntMatrix nodes = this.cycleMatrix.getRowVector(i).find();
      int nodeSize = nodes.length();
      boolean hasOnlyConnectionSelfLoop = nodeSize == 1 && (this.adjacencyConnectionMatrix.getElement(i, i) == false);
      if (nodes.isEmpty() || hasOnlyConnectionSelfLoop) {
        continue;
      }

      List<Integer> cycle = new ArrayList<>();
      for (int j = 1; j <= nodeSize; j++) {
        cycle.add(nodes.getIntElement(j));
      }
      cycleList.add(cycle);

      // 同一ループ内のノードを検索対象から除外する
      for (int j = 1; j <= nodeSize; j++) {
        int node = nodes.getIntElement(j);
        this.cycleMatrix.setRowVector(node, new BooleanMatrix(1, size));
        this.cycleMatrix.setColumnVector(node, new BooleanMatrix(size, 1));
      }

      this.cycleMatrix.setRowVector(i, new BooleanMatrix(1, size));
      this.cycleMatrix.setColumnVector(i, new BooleanMatrix(size, 1));
    }

    return cycleList;
  }

  /**
   * 行列の次数を返します。
   * 
   * @return 行列の次数
   */
  public int getSize() {
    return this.cycleMatrix.getRowSize();
  }

  /**
   * 閉路情報を表わす行列を返します。
   * 
   * @return 閉路情報を表わす行列
   */
  public BooleanMatrix getBooleanMatrix() {
    return this.cycleMatrix.createClone();
  }

  /**
   * <code>row</code>行<code>column</code>列の成分を返します。
   * 
   * @param row 行番号
   * @param column 列番号
   * @return row行column列の成分
   */
  public boolean getElement(final int row, final int column) {
    return this.cycleMatrix.getElement(row, column);
  }

  /**
   * @see java.lang.Object#hashCode()
   */
  @Override
  public int hashCode() {
    final int PRIME = 31;
    int result = 1;
    result = PRIME * result + ((this.adjacencyConnectionMatrix == null) ? 0 : this.adjacencyConnectionMatrix.hashCode());
    result = PRIME * result + ((this.cycleMatrix == null) ? 0 : this.cycleMatrix.hashCode());
    return result;
  }

  /**
   * @see java.lang.Object#equals(java.lang.Object)
   */
  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass()) return false;
    final DoubleCycleMatrix other = (DoubleCycleMatrix)obj;
    if (this.adjacencyConnectionMatrix == null) {
      if (other.adjacencyConnectionMatrix != null) return false;
    } else if (!this.adjacencyConnectionMatrix.equals(other.adjacencyConnectionMatrix)) return false;
    if (this.cycleMatrix == null) {
      if (other.cycleMatrix != null) return false;
    } else if (!this.cycleMatrix.equals(other.cycleMatrix)) return false;
    return true;
  }

}