mapss.dif.csdf.sdf.mem
Class PartitionedGraph

java.lang.Object
  mocgraph.Graph
      mapss.dif.csdf.sdf.mem.PartitionBase
          mapss.dif.csdf.sdf.mem.PartitionedGraph

All Implemented Interfaces:

java.lang.Cloneable

Direct Known Subclasses:

ConflictGraph

public class PartitionedGraph
extends PartitionBase

A graph of partitions with additional partition related tools. The partitions are not necessarily disjoint. Disjointness is up to the uers to maintain.

Version:

$Id: PartitionedGraph.java 406 2007-05-10 14:27:07Z plishker $

Author:

Mingyung Ko

Constructor Summary

PartitionedGraph()
A constructor.

PartitionedGraph(mocgraph.Graph graph)
Constructor for a given graph.

Method Summary

void	addPartition(GraphPartition partition) Add the given graph partition.
void	addPartitions(int partitionNumber) Add the given number of graph partitions.
java.util.List	ascendentPartitions() An ascendently ordered list of partitions.
java.util.List	descendentPartitions() A descendently ordered list of partitions.
GraphPartition	dualOf(GraphPartition partition) The dual/other partition of the given partition, assuming totally two partitions of the graph.
java.util.Collection	edgeCut() Get the edge cut set over all partitions.
java.util.Collection	edgeCutOf(java.util.Collection partitionCollection) Get edge cut set over a collection of partitions.
java.util.Collection	edgeCutOf(GraphPartition p1, GraphPartition p2) Get the edge cut set of two partitions.
java.lang.String	edgeCutString(java.util.Collection edgeCut) Display edge cut in a text string.
double	edgeCutValueOf(mocgraph.Node node) Evaluate the total value of cut edges incident to the node.
double	edgeNonCutValueOf(mocgraph.Node node) Evaluate the total value of non-cut edges incident to the node.
java.util.List	getPartitions() Get all the partitions.
int	partitionIndexOf(mocgraph.Element element) The partition index in the list of partitions.
int	partitionIndexOf(GraphPartition partition) Get the partition index for the given partition.
GraphPartition	partitionOf(mocgraph.Element element) Get the container partition of an element.
GraphPartition	partitionOf(int index) Get the partition for the given partition index.
java.util.Collection	partitionsOf(java.util.Collection elementCollection) Get the assigned partitions of a given collection of elements.
java.lang.String	partitionString() Display partitions in a text string.
void	resetPartitions() Remove all partitions.

Methods inherited from class mapss.dif.csdf.sdf.mem.PartitionBase

_checkGraphElement, ascendentListOf, descendentListOf, getIndex, removeEdge, removeNode, setElementValue, setElementValues, setIndex, valueOf

Methods inherited from class mocgraph.Graph

_addEdge, _connect, _connectEdge, _disconnect, _disconnectEdge, _emptyGraph, _initializeAnalyses, _registerChange, _registerEdge, _registerNode, addAnalysis, addEdge, addEdge, addEdge, addEdge, addEdge, addEdges, addGraph, addNode, addNode, addNodes, addNodeWeight, addNodeWeights, changeCount, clone, cloneAs, connectedComponents, containsEdge, containsEdgeWeight, containsNode, containsNodeWeight, edge, edge, edgeCount, edgeLabel, edgeLabel, edges, edges, edges, edgeWeight, equals, hashCode, hidden, hiddenEdgeCount, hiddenEdges, hideEdge, incidentEdgeCount, incidentEdges, neighborEdges, neighbors, node, node, nodeCount, nodeLabel, nodeLabel, nodes, nodes, nodes, nodeWeight, restoreEdge, selfLoopEdgeCount, selfLoopEdgeCount, selfLoopEdges, selfLoopEdges, subgraph, subgraph, toString, validateWeight, validateWeight, validateWeight, validateWeight, validEdgeWeight, validNodeWeight, weightArray

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

PartitionedGraph

public PartitionedGraph()

A constructor.

PartitionedGraph

public PartitionedGraph(mocgraph.Graph graph)

Constructor for a given graph. Construct the partitioned graph by duplicating all nodes and edges.

Parameters:

graph - The graph to construct from.

Method Detail

addPartition

public void addPartition(GraphPartition partition)

Add the given graph partition.

Parameters:

partition - The graph partition to add.

addPartitions

public void addPartitions(int partitionNumber)

Add the given number of graph partitions.

Parameters:

partitionNumber - The number of partitions to add.

ascendentPartitions

public java.util.List ascendentPartitions()

An ascendently ordered list of partitions. It is the associated total values, see PartitionBase.valueOf(Object), being sorted.

Returns:

An ascendent list of partitions.

descendentPartitions

public java.util.List descendentPartitions()

A descendently ordered list of partitions. It is the associated total values, see partitionBase#valueOf(Object), being sorted.

Returns:

A descendent list of partitions.

dualOf

public GraphPartition dualOf(GraphPartition partition)

The dual/other partition of the given partition, assuming totally two partitions of the graph.

Parameters:

partition - The given partition.

Returns:

The dual partition.

edgeCut

public java.util.Collection edgeCut()

Get the edge cut set over all partitions. See also edgeCutOf(Collection).

Returns:

The set of edge cut.

edgeCutOf

public java.util.Collection edgeCutOf(java.util.Collection partitionCollection)

Get edge cut set over a collection of partitions. Edge cut is a set of edges with ending nodes in distinct partitions.

Parameters:

partitionCollection - A collection of partitions.

Returns:

The set of edge cut.

edgeCutOf

public java.util.Collection edgeCutOf(GraphPartition p1,
                                      GraphPartition p2)

Get the edge cut set of two partitions. See also edgeCutOf(Collection).

Parameters:

p1 - The first partition.

p2 - The second partition.

Returns:

The set of edge cut.

edgeCutString

public java.lang.String edgeCutString(java.util.Collection edgeCut)

Display edge cut in a text string.

Parameters:

edgeCut - The edge cut to print.

Returns:

The output.

edgeCutValueOf

public double edgeCutValueOf(mocgraph.Node node)

Evaluate the total value of cut edges incident to the node. It is also called "external cost" in Kernighan and Lin's graph partitioning heuristic. See also edgeNonCutValueOf(Node).

Caution: It is assumed that all nodes are assigned with partitions before calling this method.

Parameters:

node - The node to evaluate the edge cut value.

Returns:

Value of the edge cut.

edgeNonCutValueOf

public double edgeNonCutValueOf(mocgraph.Node node)

Evaluate the total value of non-cut edges incident to the node. It is also called "internal cost" in Kernighan and Lin's graph partitioning heuristic. See also edgeCutValueOf(Node).

Caution: It is assumed that all nodes are assigned with partitions before calling this method.

Parameters:

node - The node to evaluate the non-cut edges' value.

Returns:

Value of the non-cut edges.

getPartitions

public java.util.List getPartitions()

Get all the partitions. The partition list returned is not allowed to modify. This is to ensure that partition additions are through addPartition(GraphPartition).

Returns:

Present partitions in type of List.

partitionIndexOf

public int partitionIndexOf(mocgraph.Element element)

The partition index in the list of partitions.

Parameters:

element - The graph element to get the belonged partition.

Returns:

The partition index.

partitionIndexOf

public int partitionIndexOf(GraphPartition partition)

Get the partition index for the given partition.

Parameters:

partition - The graph partition.

Returns:

The partition index.

partitionOf

public GraphPartition partitionOf(int index)

Get the partition for the given partition index.

Parameters:

index - The partition index.

Returns:

The partition.

partitionOf

public GraphPartition partitionOf(mocgraph.Element element)

Get the container partition of an element.

Parameters:

element - The given element.

Returns:

The container partition.

partitionsOf

public java.util.Collection partitionsOf(java.util.Collection elementCollection)

Get the assigned partitions of a given collection of elements.

Parameters:

elementCollection - The collection of elements.

Returns:

The assigned partitions.

partitionString

public java.lang.String partitionString()

Display partitions in a text string.

Returns:

The output.

resetPartitions

public void resetPartitions()

Remove all partitions.