nct.graph
Class BasicKPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>

java.lang.Object
  nct.graph.BasicGraph<NodeType,WeightType>
      nct.graph.BasicKPartiteGraph<NodeType,WeightType,PartitionType>

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Comparable<Graph<NodeType,WeightType>>, Graph<NodeType,WeightType>, KPartiteGraph<NodeType,WeightType,PartitionType>

Direct Known Subclasses:

HomologyGraph

public class BasicKPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>
extends BasicGraph<NodeType,WeightType>
implements KPartiteGraph<NodeType,WeightType,PartitionType>, java.lang.Comparable<Graph<NodeType,WeightType>>, java.lang.Cloneable

A generic implementation of the KPartiteGraph interface.

Field Summary

protected int	K The number of partitions allowed in the graph, not necessarily the number currently contained in the graph.
protected java.util.Map<NodeType,PartitionType>	partitionMap A mapping of nodes to partitions.
static int	UNLIMITED_PARTITIONS This value indicates that an unlimited number of partitions is allowed in This graph.

Fields inherited from class nct.graph.BasicGraph

assumeGraphFinished, descMap, id, numEdges, score, weightMap

Constructor Summary

BasicKPartiteGraph()
Constructor that names the graph "none" and allows unlimited partitions.

BasicKPartiteGraph(java.lang.String name)
Constructor that names the graph as specified and allows unlimited partitions.

BasicKPartiteGraph(java.lang.String name, int K)
Constructor that names the graph as specified and limits the number of partitions allowed in this graph.

Method Summary

boolean	addEdge(NodeType nodeA, NodeType nodeB, WeightType weight) Adds an edge to the graph.
boolean	addNode(NodeType node) This method overrides the BasicGraph implementation of addNode and always returns false because it is impossible to add a node to a k-paritite graph without also specifying the partition.
boolean	addNode(NodeType node, PartitionType partition) Adds a node to the graph.
java.util.List<java.util.List<NodeType>>	getAllKCliques() Returns a list of all k-cliques that exist in the graph.
int	getK() This method returns the number of possible partitions.
int	getNumPartitions() This method returns the number of existing partitions.
java.util.List<PartitionType>	getPartitions() Returns a list of the partitions currently contained in the graph (not necessarily K if K partitions haven't yet been added).
boolean	isPartition(PartitionType p) Checks whether a specified partition is one of the partitions used in the graph.

Methods inherited from class nct.graph.BasicGraph

addEdge, clone, compareTo, degreeOfNode, getEdge, getEdgeDescription, getEdgeList, getEdges, getEdgeWeight, getId, getNeighbors, getNodes, getScore, isEdge, isNode, numberOfEdges, numberOfNodes, removeEdge, removeNode, setEdgeDescription, setEdgeWeight, setScore, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface nct.graph.Graph

addEdge, clone, compareTo, degreeOfNode, getEdge, getEdgeDescription, getEdgeList, getEdges, getEdgeWeight, getId, getNeighbors, getNodes, getScore, isEdge, isNode, numberOfEdges, numberOfNodes, removeEdge, removeNode, setEdgeDescription, setEdgeWeight, setScore, toString

Field Detail

partitionMap

protected java.util.Map<NodeType extends java.lang.Comparable<? super NodeType>,PartitionType extends java.lang.Comparable<? super PartitionType>> partitionMap

A mapping of nodes to partitions.

K

protected int K

The number of partitions allowed in the graph, not necessarily the number currently contained in the graph.

UNLIMITED_PARTITIONS

public static int UNLIMITED_PARTITIONS

This value indicates that an unlimited number of partitions is allowed in This graph.

Constructor Detail

BasicKPartiteGraph

public BasicKPartiteGraph()

Constructor that names the graph "none" and allows unlimited partitions.

BasicKPartiteGraph

public BasicKPartiteGraph(java.lang.String name)

Constructor that names the graph as specified and allows unlimited partitions.

Parameters:

name - The name of the graph.

BasicKPartiteGraph

public BasicKPartiteGraph(java.lang.String name,
                          int K)

Constructor that names the graph as specified and limits the number of partitions allowed in this graph.

Parameters:

name - The name of the graph.

K - The number of allowed partitions in this graph.

Method Detail

addNode

public boolean addNode(NodeType node)

This method overrides the BasicGraph implementation of addNode and always returns false because it is impossible to add a node to a k-paritite graph without also specifying the partition.

Specified by:

addNode in interface Graph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>>

Overrides:

addNode in class BasicGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>>

Parameters:

node - The node that will NOT be added.

Returns:

Always returns false.

addNode

public boolean addNode(NodeType node,
                       PartitionType partition)

Adds a node to the graph. This implementation assumes that nodes are unique, independent of their partitions. For instance it would NOT be allowed to have a node (of type String) "homer" in partition one and a node "homer" in partition two. The partition the node is added to is also checked. If the partition is not currently in the graph, but the graph already contains K partitions, then the node and partition will not be added. The node and partition will be added if unlimited partitions are allowed or if the number of current partitions is less than K.

Specified by:

addNode in interface KPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>

Parameters:

node - The node to be added to the graph.

partition - The partition the node should be added to.

Returns:

Whether or not the node was successfully added.

addEdge

public boolean addEdge(NodeType nodeA,
                       NodeType nodeB,
                       WeightType weight)

Adds an edge to the graph. Does not add the edge (returns false) if the nodes are contained in the same partition.

Specified by:

addEdge in interface Graph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>>

Overrides:

addEdge in class BasicGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>>

Parameters:

nodeA - The source node of the edge.

nodeB - The target node of the edge.

weight - The edge weight.

Returns:

Whether or not the edge was successfully added.

getPartitions

public java.util.List<PartitionType> getPartitions()

Returns a list of the partitions currently contained in the graph (not necessarily K if K partitions haven't yet been added).

Specified by:

getPartitions in interface KPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>

Returns:

A List of the current partitions in the graph.

getNumPartitions

public int getNumPartitions()

This method returns the number of existing partitions. It is possible that more partitions could be added to the graph.

Specified by:

getNumPartitions in interface KPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>

getK

public int getK()

This method returns the number of possible partitions. The "K" in K-partite.

Specified by:

getK in interface KPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>

isPartition

public boolean isPartition(PartitionType p)

Checks whether a specified partition is one of the partitions used in the graph.

Specified by:

isPartition in interface KPartiteGraph<NodeType extends java.lang.Comparable<? super NodeType>,WeightType extends java.lang.Comparable<? super WeightType>,PartitionType extends java.lang.Comparable<? super PartitionType>>

Parameters:

p - The partition to check.

Returns:

Whether or not the specified partition is one of the partitions used in the graph.

getAllKCliques

public java.util.List<java.util.List<NodeType>> getAllKCliques()

Returns a list of all k-cliques that exist in the graph. Currently not implemented and returns null.

Returns:

A list of lists of nodes that define a k-clique.