EnumerateMaximalCliques

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

nz.ac.waikato.mcennis.rat.graph.algorithm.clustering
Class EnumerateMaximalCliques

java.lang.Object
  nz.ac.waikato.mcennis.rat.graph.model.ModelShell
      nz.ac.waikato.mcennis.rat.graph.algorithm.clustering.EnumerateMaximalCliques

All Implemented Interfaces:: java.io.Serializable, Component, Algorithm, Model

public class EnumerateMaximalCliques
extends ModelShell
implements Algorithm
extends ModelShell
implements Algorithm

Maximal cliques are defined as a fully connected subgraph such that any additional node added to the subgraph is not fully connected. This problem is NP-Complete, but can be completed in O(nlog(n)) where n is the number of nodes in the graph and exponential over k where k is the maximum out degree of the graph. For many applications, including web page hyperlink structure and social network data, k is suffeciantly small that the algorithm's cost is manageable.

See Also:: Serialized Form

Field Summary

Fields inherited from class nz.ac.waikato.mcennis.rat.graph.model.ModelShell
`listener`

Constructor Summary
`EnumerateMaximalCliques()` Creates a new instance of EnumerateMaximalCliques

Method Summary
`protected void`	`assertMaximal(java.util.HashSet<Clique> maximal)` This functions identify those cliques that are subsets of maixmal cliques rather than maximal cliques themselves.
`void`	`execute(Graph g)` execute the algorithm against the given graph
`protected void`	`extend(Clique seed, Actor[] intersection)` create a set of new cliques of size n+1 from a clique of size n.
`InputDescriptor[]`	`getInputType()` The input type describes all the different kinds of graph objects that are utilized (and hence required) by this object.
`OutputDescriptor[]`	`getOutputType()` The output type describes all the different kinds of graph objects that are created during the execution of this algorithm.
`Parameter[]`	`getParameter()` List of all parameters this component accepts.
`Parameter`	`getParameter(java.lang.String param)` Returns the specific parameter identified by its key-name.
`SettableParameter[]`	`getSettableParameter()` Returns settable (i.e.
`SettableParameter`	`getSettableParameter(java.lang.String param)` Return the settable parameter namede by this key-name.
`void`	`init(java.util.Properties map)` Parameters for init: 'name' - name for this instance of the algorithm.

Methods inherited from class nz.ac.waikato.mcennis.rat.graph.model.ModelShell
`addListener, fireChange`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Methods inherited from interface nz.ac.waikato.mcennis.rat.graph.model.Model
`addListener`

Constructor Detail

EnumerateMaximalCliques

public EnumerateMaximalCliques()

Creates a new instance of EnumerateMaximalCliques

Method Detail

execute

public void execute(Graph g)

Description copied from interface: Algorithm

execute the algorithm against the given graph

Specified by:: execute in interface Algorithm

Parameters:: g - graph to be modified

extend

protected void extend(Clique seed,
                      Actor[] intersection)

create a set of new cliques of size n+1 from a clique of size n. This only need to be done for actors strictly greater than the largest actor in the set. This is acceptable since every clique involving a smaller actor will already generate this clique in a previous iteration. However, this generates some spurious maximal cliques that are subsets of other cliques. These are weeded out by assertMaximal algorithm

assertMaximal

protected void assertMaximal(java.util.HashSet<Clique> maximal)

This functions identify those cliques that are subsets of maixmal cliques rather than maximal cliques themselves. These are removed from the set of maximal cliques before they are added to the global clique set. The test is to sequentially test whether or not there exists a node in the intersection that creates a new clique (hence the current clique is not maximal). Since this clique will be created by another clique or seed, this clique can be safely discarded.