mapss.dif.graph
Class BacktrackingAllCliquesStrategy

java.lang.Object
  mocgraph.analysis.strategy.CachedStrategy
      mapss.dif.graph.BacktrackingAllCliquesStrategy

All Implemented Interfaces:

AllCliquesAnalyzer, mocgraph.analysis.analyzer.Analyzer, mocgraph.analysis.analyzer.GraphAnalyzer

public class BacktrackingAllCliquesStrategy
extends mocgraph.analysis.strategy.CachedStrategy
implements AllCliquesAnalyzer

Finding all cliques in a graph. The collection of cliques returned cannot be modified. This implementation is adapted from a backtracking algorithm, as taken from Combinatorial Algorithms: generation, enumeration and search by D. Kreher and D. Stinson. (CRC Press, 1998)

Version:

$Id: BacktrackingAllCliquesStrategy.java 409 2007-05-13 19:47:16Z plishker $

Author:

Ming-Yung Ko

See Also:

mapss.graph.AllCliquesAnalysis

Constructor Summary

BacktrackingAllCliquesStrategy(mocgraph.Graph graph)
Construct a cliques finding strategy for a given graph.

Method Summary

protected java.lang.Object	_compute() Find all cliques and maximal cliques of the graph.
java.util.Collection	cliques() Return the collection of all cliques.
java.util.Collection	maximalCliques() Return the maximal cliques.
java.lang.String	toString() Return a description of the analysis in finding all cliques.
boolean	valid() Check compatibility of the class of graph.

Methods inherited from class mocgraph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

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

Methods inherited from interface mocgraph.analysis.analyzer.GraphAnalyzer

graph

Constructor Detail

BacktrackingAllCliquesStrategy

public BacktrackingAllCliquesStrategy(mocgraph.Graph graph)

Construct a cliques finding strategy for a given graph.

Parameters:

graph - The given graph.

Method Detail

cliques

public java.util.Collection cliques()

Return the collection of all cliques. Each element is a collection of clique (completely connected) nodes.

Specified by:

cliques in interface AllCliquesAnalyzer

Returns:

The collection of cliques.

maximalCliques

public java.util.Collection maximalCliques()

Return the maximal cliques. A maximal clique is a clique not properly contained into another one. See also cliques()

Specified by:

maximalCliques in interface AllCliquesAnalyzer

Returns:

The collection of maximal cliques. Each element contains a maximal clique.

toString

public java.lang.String toString()

Return a description of the analysis in finding all cliques.

Specified by:

toString in interface mocgraph.analysis.analyzer.Analyzer

Overrides:

toString in class mocgraph.analysis.strategy.CachedStrategy

Returns:

A description of the analysis in finding all cliques.

valid

public boolean valid()

Check compatibility of the class of graph. The given graph must be an instance of Graph.

Specified by:

valid in interface mocgraph.analysis.analyzer.Analyzer

Returns:

True if the given graph is of class Graph.

_compute

protected java.lang.Object _compute()

Find all cliques and maximal cliques of the graph. The result is returned as a List where the first element is a collection of all the cliques and the second one is a collection of maximal cliques.

Overrides:

_compute in class mocgraph.analysis.strategy.CachedStrategy

Returns:

All cliques and maximal cliques.