Package edu.claflin.finder.algo

# Class BronKerbosch

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

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

public class BronKerbosch extends Algorithm
Bron-Kersboch Algorithm to find Maximal Cliques and Bicliques.

See Also:
  - Wikipedia Summary
  - Original Paper
  - Pivoting Variant

- ## Nested Class Summary

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

  `Algorithm.GraphSortOrder`

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `private boolean`
  `bipartite`

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

  `args, PROP_PROGRESS`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `BronKerbosch(ArgumentsBundle bundle)`
  Public constructor for initializing the Bron Kersbboch with default conditions.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `private void`
  `addEdgesInParititeSet(Graph graph, List<Node> list)`
  Adds edges to a Graph between all Nodes in a partite set.
  `private void`
  `bronKerbosch(List<List<Node>> results, List<Node> clique, List<Node> candidates, List<Node> excluded)`
  Recursive helper method to do the above.
  `private List<Graph>`
  `bronKerboschBiclique(Graph graph)`
  Finds all bicliques within a bipartite graph.
  `private List<Graph>`
  `bronKerboschClique(Graph graph)`
  Given a graph, finds all complete subgraphs.
  `private List<Graph>`
  `maximalBicliques(Graph graph)`
  Gets the Maximal Complete Bipartite Graphs from the input Graph using Bron-Kersboch.
  `private List<Graph>`
  `maximalCliques(Graph graph)`
  Given a graph, finds all complete subgraphs, and then returns the largest one.
  `private List<Graph>`
  `nameGraphs(List<Graph> graphs, String originalName, boolean bipartite)`
  `ArrayList<Graph>`
  `process(Graph graph)`
  Processes data.
  `private void`
  `removeEdgesInPartiteSet(Graph graph, List<Node> list)`
  Removes edges in a Graph between all Nodes in a partite set.
  `String`
  `toString()`

  ### 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, wait, wait, wait`

- ## Field Details

  - ### bipartite

    private boolean bipartite

- ## Constructor Details

  - ### BronKerbosch

    public BronKerbosch(ArgumentsBundle bundle)
    Public constructor for initializing the Bron Kersbboch with default conditions.
    Parameters:
      `bundle` - the ArgumentsBundle containing the instantiation arguments.

- ## Method Details

  - ### toString

    public String toString()
    Overrides:
      `toString` in class `Object`

  - ### process

    public ArrayList<Graph> process(Graph graph)
    Processes data.
    Finds the Maximal Cliques of a Graph or the Maximal Biclique of a Bipartite Graph if the bipartite argument is set to true.
    Parameters:
      `graph` - the `Graph` object to search through.
    Returns:
      the ArrayList of Graph objects holding all found subgraphs.

  - ### maximalCliques

    private List<Graph> maximalCliques(Graph graph)
    Given a graph, finds all complete subgraphs, and then returns the largest one.
    Parameters:
      `graph` - the graph
    Returns:
      the largest complete subgraph (clique)

  - ### maximalBicliques

    private List<Graph> maximalBicliques(Graph graph)
    Gets the Maximal Complete Bipartite Graphs from the input Graph using Bron-Kersboch.
    Parameters:
      `graph` - the input Graph
    Returns:
      the Maximal Complete Bipartite Graphs

  - ### bronKerboschClique

    private List<Graph> bronKerboschClique(Graph graph)
    Given a graph, finds all complete subgraphs.
    Parameters:
      `graph` - the graph
    Returns:
      a List of complete subgraphs, unordered

  - ### bronKerboschBiclique

    private List<Graph> bronKerboschBiclique(Graph graph)
    Finds all bicliques within a bipartite graph. This is done by adding edges between every nodes in a partite set in both partite sets, using the above algorithm, and then removing all the added edges from the results. THIS ONLY WORKS ON GRAPHS THAT ARE BIPARTITE!
    Parameters:
      `graph` - the bipartite graph
    Returns:
      array list of bicliques

  - ### bronKerbosch

    private void bronKerbosch(List<List<Node>> results, List<Node> clique, List<Node> candidates, List<Node> excluded)
    Recursive helper method to do the above.
    Parameters:
      `results` - result list. Passed between recursive calls to create output
      `clique` - the current Clique being constructed; Graph r in Wikipedia link
      `candidates` - the candidate Nodes for the Clique; Graph p in Wikipedia link
      `excluded` - the Nodes to be excluded from the Clique; Graph x in Wikipedia link

  - ### addEdgesInParititeSet

    private void addEdgesInParititeSet(Graph graph, List<Node> list)
    Adds edges to a Graph between all Nodes in a partite set. Remove these edges later with `removeEdgesInPartiteSet(edu.claflin.finder.logic.Graph,java.util.List<edu.claflin.finder.logic.Node>)`.
    Parameters:
      `graph` - the Graph to add the Edges to
      `list` - the partite set

  - ### removeEdgesInPartiteSet

    private void removeEdgesInPartiteSet(Graph graph, List<Node> list)
    Removes edges in a Graph between all Nodes in a partite set.
    Parameters:
      `graph` - the Graph to remove the Edges from
      `list` - the partite set

  - ### nameGraphs

    private List<Graph> nameGraphs(List<Graph> graphs, String originalName, boolean bipartite)