Package edu.claflin.finder.algo

# Class MatrixPatternAnalyzer

java.lang.Object
edu.claflin.finder.algo.Algorithm
edu.claflin.finder.algo.MatrixPatternAnalyzer

All Implemented Interfaces:
  `Processable<Graph,Graph>`

@Deprecated public class MatrixPatternAnalyzer extends Algorithm
Deprecated.
No replacement yet. Inefficient and utilizes old algorithm strategy.
Processes a `Graph` searching for bipartite subgraphs by analyzing the matrices of said Graph.

Version:
  3.0.2 February 4, 2016
Author:
  Charles Allen Schultz II

- ## Nested Class Summary

  ## Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

  `Algorithm.GraphSortOrder`

- ## Field Summary

  ### Fields inherited from class edu.claflin.finder.algo.Algorithm

  `args, PROP_PROGRESS`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `MatrixPatternAnalyzer()`
  Deprecated.
  Public constructor for initializing the analyzer.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `private boolean`
  `checkNodeGroupings(Graph inGraph)`
  Deprecated.
  Step 2: Iterate on Step 1 through all contiguous node groupings.
  `private Graph`
  `checkSubGraphs(Graph inGraph, int transpositions)`
  Deprecated.
  Step 3: Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
  `private boolean`
  `checkZeroMatrices(Graph inGraph, int nodeCap)`
  Deprecated.
  Step 1: Check for valid 0 Sub-matrices.
  `ArrayList<Graph>`
  `process(Graph graph)`
  Deprecated.
  Processes data.

  ### Methods inherited from class edu.claflin.finder.algo.Algorithm

  `addPropertyChangeListener, cull, getGraphSortOrder, getMinNodeCount, getPartiteNumber, getWeightName, removePropertyChangeListener, setGraphSortOrder, setMinNodeCount, setPartiteNumber, setProgress, setWeightName, zeropad`

  ### Methods inherited from class java.lang.Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Constructor Details

  - ### MatrixPatternAnalyzer

    public MatrixPatternAnalyzer()
    Deprecated.
    Public constructor for initializing the analyzer. Currently ignores state variables given it doesn't operate on an expansion basis.

- ## Method Details

  - ### process

    public ArrayList<Graph> process(Graph graph)
    Deprecated.
    Processes data.
    Processes the `Graph` object in four steps.
    1) Check for valid 0 Sub-matrices.
    2) Iterate on Step 1 through all contiguous node groupings.
    3) Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
    4) Repeat Step 3 for each transposition of the Graph. Each step is carried out in its own method. This method controls Step 4 by looping through all the permutations of the supplied Graph object. The permutation code is based on the "Counting QuickPerm Algorithm" found here:
    Parameters:
      `graph` - the Graph object to search for Bipartite subgraphs.
    Returns:
      the ArrayList of Graph objects containing found bipartite subgraph objects.

  - ### checkSubGraphs

    private Graph checkSubGraphs(Graph inGraph, int transpositions)
    Deprecated.
    Step 3: Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
    A "Cornered" sub-matrix is a sub-matrix whose upper left node lies in the upper left corner of the main matrix. I.e. A(0,0) = B(0,0) if A is the main matrix and B is the sub-matrix.
    This method processes Step 2 with each of the n - 1 cornered matrices contained in the original matrix. The smallest cornered matrix containing only one node is not processed (due to it being impossible to sort one node into two disjoint sets.
    Parameters:
      `inGraph` - the graph
      `transpositions` - the number of transpositions
    Returns:
      result of step 3

  - ### checkNodeGroupings

    private boolean checkNodeGroupings(Graph inGraph)
    Deprecated.
    Step 2: Iterate on Step 1 through all contiguous node groupings. Bipartite graphs may have a ratio of m:n nodes in each disjoint set. Since both node counts are independent of each other, all possible options (except cases where m or n = 0) must be checked.
    This section of the algorithm instructs the previous to examine a very specific section of the subgraphs for contiguous zeroes. It iterates through all valid contiguous groupings.
    Parameters:
      `inGraph` - the (sub) `Graph` object to check for bipartiteness.
    Returns:
      the boolean primitive indicating if the Graph was bipartite.

  - ### checkZeroMatrices

    private boolean checkZeroMatrices(Graph inGraph, int nodeCap)
    Deprecated.
    Step 1: Check for valid 0 Sub-matrices.
    Undirected bipartite graphs, when ordered correctly, have two noticeable regions containing no edges, or, if the graph is represented by ones and zeroes, two regions of zeros. The following graph demonstrates this.

         [ 0 0 0 0 1 ]

         [ 0 0 0 1 1 ]

         [ 0 0 0 1 0 ]

         [ 0 1 1 0 0 ]

         [ 1 1 0 0 0 ]

    This section of the code verifies that these contiguous regions exist. If they don't, the provided Graph object (or subgraph object in this case) is not Bipartite. This is the core comparison to be performed.
    Parameters:
      `inGraph` - the `Graph` object to check for valid 0 sub-matrices.
      `nodeCap` - the furthest node inward which the upperLeft Matrix should extend to.
    Returns:
      the boolean primitive indicating if the sub-matrix is bipartite.