de.unihalle.informatik.MiToBo.tracking.multitarget.algo

Class GreedyGourmetPartitioning

java.lang.Object

de.unihalle.informatik.MiToBo.tracking.multitarget.algo.GreedyGourmetPartitioning

public class GreedyGourmetPartitioning
extends Object

greedyGourmet graph partitioning algorithm following:
J. Kutzera, "Gruppierung von LC/MS-Pseudospektren aus multiplen Messungen", Martin Luther University Halle-Wittenberg, 2009, Diploma Thesis

Author:

Oliver Gress

Field Summary

Fields

Modifier and Type	Field and Description
protected MatchingAdjacencyMatrix	adjMatrix
(package private) double	limit
protected boolean	maxWeights
(package private) HashMap<Integer,Vector<MTBGraphNode<PartitGraphNodeID>>>	partitions
private Vector<MTBGraph>	subgraphs

Constructor Summary

Constructors

Constructor and Description
GreedyGourmetPartitioning(MatchingAdjacencyMatrix adjMatrix, boolean maximizeWeights, double limit) Constructor.

Method Summary

Modifier and Type	Method and Description
Vector<MTBGraph>	computeSubgraphs() Compute subgraphs with greedyGourmet algorithm.
private boolean	connectNodesCase1(MTBGraphNode<PartitGraphNodeID> n1, MTBGraphNode<PartitGraphNodeID> n2, MTBGraphNode<PartitGraphNodeID> nstar1, MTBGraphNode<PartitGraphNodeID> nstar2, boolean do_connect) Connect nodes if case 1
private MTBGraphNode<PartitGraphNodeID>	getGraphNode(int subgraphID, int partitionID) Get the graph node from partition 'partitionID' in subgraph 'subgraphID'.
private MTBGraphNode<PartitGraphNodeID>	getOptimalNeighbor(MTBGraphNode<PartitGraphNodeID> currentNode, int partitionID) Get node of partition 'partitionID' which is connected to current node and has optimal weight
private int	numOfConnectedNodes(PartitGraphNodeID currentNode, int partitionID) Get number of nodes from partition 'partitionID' connected to current node

Methods inherited from class java.lang.Object

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

Field Detail

adjMatrix

protected MatchingAdjacencyMatrix adjMatrix

maxWeights

protected boolean maxWeights

subgraphs

private Vector<MTBGraph> subgraphs

partitions

HashMap<Integer,Vector<MTBGraphNode<PartitGraphNodeID>>> partitions

limit

double limit

Constructor Detail

GreedyGourmetPartitioning

public GreedyGourmetPartitioning(MatchingAdjacencyMatrix adjMatrix,
                                 boolean maximizeWeights,
                                 double limit)

Constructor.

Parameters:

adjMatrix - adjacency matrix of the multipartite graph

maximizeWeights - flag if sum of weights are to be maximized

limit - only edge weights larger (maximize weights) or smaller (minimize weights) are considered

Method Detail

computeSubgraphs

public Vector<MTBGraph> computeSubgraphs()

Compute subgraphs with greedyGourmet algorithm.

Returns:

connectNodesCase1

private boolean connectNodesCase1(MTBGraphNode<PartitGraphNodeID> n1,
                                  MTBGraphNode<PartitGraphNodeID> n2,
                                  MTBGraphNode<PartitGraphNodeID> nstar1,
                                  MTBGraphNode<PartitGraphNodeID> nstar2,
                                  boolean do_connect)

Connect nodes if case 1

getOptimalNeighbor

private MTBGraphNode<PartitGraphNodeID> getOptimalNeighbor(MTBGraphNode<PartitGraphNodeID> currentNode,
                                                           int partitionID)

Get node of partition 'partitionID' which is connected to current node and has optimal weight

Parameters:

currentNode - current node

partitionID - ID of partition

limit - optimal neighbors must have edge weights larger (max weight) or smaller (min weight) than limit to be considered

Returns:

optimal neighbor node

getGraphNode

private MTBGraphNode<PartitGraphNodeID> getGraphNode(int subgraphID,
                                                     int partitionID)

Get the graph node from partition 'partitionID' in subgraph 'subgraphID'. If none is available in the subgraph, null is returned.

numOfConnectedNodes

private int numOfConnectedNodes(PartitGraphNodeID currentNode,
                                int partitionID)

Get number of nodes from partition 'partitionID' connected to current node