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

java.lang.Object
  extended by de.unihalle.informatik.MiToBo.tracking.multitarget.algo.GreedyGourmetPartitioning

public class GreedyGourmetPartitioning
extends java.lang.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
protected  MatchingAdjacencyMatrix adjMatrix
           
(package private)  double limit
           
protected  boolean maxWeights
           
(package private)  java.util.HashMap<java.lang.Integer,java.util.Vector<MTBGraphNode<PartitGraphNodeID>>> partitions
           
private  java.util.Vector<MTBGraph> subgraphs
           
 
Constructor Summary
GreedyGourmetPartitioning(MatchingAdjacencyMatrix adjMatrix, boolean maximizeWeights, double limit)
          Constructor.
 
Method Summary
 java.util.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

limit

double limit

maxWeights

protected boolean maxWeights

partitions

java.util.HashMap<java.lang.Integer,java.util.Vector<MTBGraphNode<PartitGraphNodeID>>> partitions

subgraphs

private java.util.Vector<MTBGraph> subgraphs
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 java.util.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


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.


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

numOfConnectedNodes

private int numOfConnectedNodes(PartitGraphNodeID currentNode,
                                int partitionID)
Get number of nodes from partition 'partitionID' connected to current node