scpsolver.graph
Class BipartiteGraph

java.lang.Object
  scpsolver.graph.Graph
      scpsolver.graph.BipartiteGraph

All Implemented Interfaces:

GraphInterface

public class BipartiteGraph
extends Graph

Author:

hannes

Constructor Summary

BipartiteGraph()

Method Summary

Edge	addEdgeSecure(java.lang.String leftlabel, java.lang.String rightlabel) adds a directed edge between a left and right node.
Edge	addEdgeSecure(java.lang.String leftlabel, java.lang.String rightlabel, boolean reverse) Adds a directed edge between a left and right node.
Edge	addEdgeSecure(java.lang.String leftlabel, java.lang.String rightlabel, java.lang.String edgelabel, boolean reverse) Adds a directed labeled edge between a left and right node.
Node	addLeftNode(Node node)
Node	addRightNode(Node node)
java.util.ArrayList<Node>	findSimilarLeftNodes(Node node)
java.util.ArrayList<java.util.HashSet<Node>>	getAllComponents() Returns all components of the graph
java.util.HashSet<Node>	getComponent(Node n) Returns all nodes that are in the same graph component as n
LinearProgram	getDenseConveringWithSizeLinearProgram(int k)
LinearProgram	getDualCoverLinearProgram(int maxcost)
int	getIndex(Node node)
java.util.ArrayList<Node>	getLeftNodeWithActiveCardinality(int min, int max) Returns all nodes on left side that have active cardinality bigger than min and lower than max.
java.util.ArrayList<Node>	getLeftNodeWithCardinality(int min, int max) Returns all nodes on left side that have a cardinality bigger than min and lower than max.
Node	getNode(int index)
Node	getNode(java.lang.String label)
java.util.HashMap<java.lang.String,Node>	getNodes()
java.util.ArrayList<Node>	getNodeSet(java.util.ArrayList<java.lang.String> nodelist)
java.util.ArrayList<Node>	getNodeSet(java.lang.String nodestring)
java.util.HashMap<java.lang.String,Node>	getNodesleft()
java.util.HashMap<java.lang.String,Node>	getNodesright()
int	getNumberNodes()
int	getNumberOfLeftNodes() Returns the number of left nodes
int	getNumberOfRightNodes() Returns the number of rigth nodes
java.util.ArrayList<Node>	getRightNodeWithActiveCardinality(int min, int max) Returns all nodes on right side that have active cardinality bigger than min and lower than max.
java.util.ArrayList<Node>	getRightNodeWithCardinality(int min, int max) Returns all nodes on right side that have cardinality bigger than min and lower than max.
LinearProgram	getSetCoverLinearProgram(int mincover)
LinearProgram	getSetCoverLinearProgramMulticover()
LinearProgram	getSetCoverLinearProgramRelaxed(int mincover)
boolean	hasEdge(java.lang.String leftlabel, java.lang.String rightlabel) Checks if there is a edge between left node labeled leftlabel and a right node labeled rightlabel
boolean	isValidCovering(java.util.ArrayList<Node> set) Checks if a set of left nodes (subset) covers all right nodes (universe elements).
static void	main(java.lang.String[] args)
void	removeLeftNode(Node node) Remove a left node
void	reset()
java.util.ArrayList<Node>	solveCoveringProblemLP(LinearProgramSolver solver, int mincover)
java.util.ArrayList<Node>	solveCoveringProblemLPApproximation(LinearProgramSolver solver)
java.util.ArrayList<Node>	solveCoveringProblemLPMulticover(LinearProgramSolver solver)
java.util.ArrayList<Node>	solveDenseCoveringProblemLP(LinearProgramSolver solver, int max)
java.util.ArrayList<Node>	solveDualCoveringProblemLP(LinearProgramSolver solver, int maxcost)
java.util.ArrayList<Node>	solveLinearProgramForSubProblem(java.util.ArrayList<Node> proteinsublist, java.util.ArrayList<Node> epitopes, java.util.ArrayList<Node> solution, LinearProgramSolver solver)
java.util.ArrayList<Node>	solveSetCoveringProblemGreedy() Greedy heuristic for the set covering problem represented by the bipartite graph.
java.util.ArrayList<Node>	solveSetCoveringProblemGreedyActive(java.util.Comparator<Node> comp) Greedy heuristic for the set covering problem represented by the bipartite graph.
java.util.ArrayList<Node>	solveSetCoveringProblemGreedyActive(java.util.Comparator<Node> comp, int max) Greedy heuristic for the set covering problem represented by the bipartite graph.
java.util.ArrayList<Node>	sortCovering(java.util.ArrayList<Node> pset, java.lang.String filename) Sorts a covering by means of the greedy heuristic.
java.lang.String	toGML() Generates the GML-graph representation of the Bipartite Graph A recommended viewer for GML files is yED
void	toGML(java.lang.String filename)
void	toSetCoverCPLEXStream(java.lang.String filename, int mincover) Writes the linear program in CPLEX LP format for the set sovering problem represented by the bipartite graph directly to a file.
java.lang.String	toSetCoverGPML(int mincover) Deprecated.
void	toSetCoverGPML(java.lang.String filename, int mincover) Deprecated.
void	toSetCoverGPMLStream(java.lang.String filename, int mincover) Writes the linear program in Mathprog format for the set sovering problem represented by the bipartite graph directly to a file.
void	toSetCoverOPBStream(java.lang.String filename, int mincover) Writes the linear program in OPB format for the set sovering problem represented by the bipartite graph directly to a file.
java.lang.String	toTKZLatex(int minimumnodesize, int xrightnodes, double distance, java.lang.String leftnodecolor, java.lang.String rightnodecolor)

Methods inherited from class scpsolver.graph.Graph

activateAllEdges, addGraph, addNode, clone, getAdjMatrix, getAdjMatrix, getAllComponentsDL, getComponentDL, getEdge, getNodeSetPipe, getNodeWithActiveCardinality, getNodeWithCardinality, getNumberEdges, isEmpty, removeCards, removeEdge, removeNode, toGML, toGMLwithGrouping, toMTX

Methods inherited from class java.lang.Object

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

Constructor Detail

BipartiteGraph

public BipartiteGraph()

Method Detail

getNodesleft

public java.util.HashMap<java.lang.String,Node> getNodesleft()

Returns:

the nodesleft

getNodesright

public java.util.HashMap<java.lang.String,Node> getNodesright()

Returns:

the nodesright

getNode

public Node getNode(java.lang.String label)

Specified by:

getNode in interface GraphInterface

Overrides:

getNode in class Graph

reset

public void reset()

Overrides:

reset in class Graph

addLeftNode

public Node addLeftNode(Node node)

addRightNode

public Node addRightNode(Node node)

getComponent

public java.util.HashSet<Node> getComponent(Node n)

Returns all nodes that are in the same graph component as n

Overrides:

getComponent in class Graph

Parameters:

n - Node

Returns:

getAllComponents

public java.util.ArrayList<java.util.HashSet<Node>> getAllComponents()

Returns all components of the graph

Overrides:

getAllComponents in class Graph

Returns:

toTKZLatex

public java.lang.String toTKZLatex(int minimumnodesize,
                                   int xrightnodes,
                                   double distance,
                                   java.lang.String leftnodecolor,
                                   java.lang.String rightnodecolor)

removeLeftNode

public void removeLeftNode(Node node)

Remove a left node

Parameters:

node -

getNumberOfLeftNodes

public int getNumberOfLeftNodes()

Returns the number of left nodes

Returns:

getNumberOfRightNodes

public int getNumberOfRightNodes()

Returns the number of rigth nodes

Returns:

hasEdge

public boolean hasEdge(java.lang.String leftlabel,
                       java.lang.String rightlabel)

Checks if there is a edge between left node labeled leftlabel and a right node labeled rightlabel

Specified by:

hasEdge in interface GraphInterface

Overrides:

hasEdge in class Graph

Parameters:

leftlabel -

rightlabel -

Returns:

addEdgeSecure

public Edge addEdgeSecure(java.lang.String leftlabel,
                          java.lang.String rightlabel,
                          boolean reverse)

Adds a directed edge between a left and right node. If reverse is true the edge is directed from right to left.,

Overrides:

addEdgeSecure in class Graph

Parameters:

leftlabel -

rightlabel -

reverse -

Returns:

addEdgeSecure

public Edge addEdgeSecure(java.lang.String leftlabel,
                          java.lang.String rightlabel)

adds a directed edge between a left and right node.

Specified by:

addEdgeSecure in interface GraphInterface

Overrides:

addEdgeSecure in class Graph

Parameters:

leftlabel -

rightlabel -

Returns:

addEdgeSecure

public Edge addEdgeSecure(java.lang.String leftlabel,
                          java.lang.String rightlabel,
                          java.lang.String edgelabel,
                          boolean reverse)

Adds a directed labeled edge between a left and right node. If reverse is true the edge is directed from right to left.,

Overrides:

addEdgeSecure in class Graph

Parameters:

leftlabel -

rightlabel -

edgelabel -

reverse -

Returns:

getDenseConveringWithSizeLinearProgram

public LinearProgram getDenseConveringWithSizeLinearProgram(int k)

solveSetCoveringProblemGreedy

public java.util.ArrayList<Node> solveSetCoveringProblemGreedy()

Greedy heuristic for the set covering problem represented by the bipartite graph. Subsets are on the left. Universe elements on the right.

Returns:

solveSetCoveringProblemGreedyActive

public java.util.ArrayList<Node> solveSetCoveringProblemGreedyActive(java.util.Comparator<Node> comp)

Greedy heuristic for the set covering problem represented by the bipartite graph. Subsets are on the left. Universe elements on the right. The comparator directly influences te result.

Parameters:

comp -

Returns:

solveSetCoveringProblemGreedyActive

public java.util.ArrayList<Node> solveSetCoveringProblemGreedyActive(java.util.Comparator<Node> comp,
                                                                     int max)

Greedy heuristic for the set covering problem represented by the bipartite graph. Subsets are on the left. Universe elements on the right. The comparator directly influences te result.

Parameters:

comp -

Returns:

getSetCoverLinearProgram

public LinearProgram getSetCoverLinearProgram(int mincover)

getDualCoverLinearProgram

public LinearProgram getDualCoverLinearProgram(int maxcost)

getSetCoverLinearProgramMulticover

public LinearProgram getSetCoverLinearProgramMulticover()

getSetCoverLinearProgramRelaxed

public LinearProgram getSetCoverLinearProgramRelaxed(int mincover)

solveCoveringProblemLPApproximation

public java.util.ArrayList<Node> solveCoveringProblemLPApproximation(LinearProgramSolver solver)

solveLinearProgramForSubProblem

public java.util.ArrayList<Node> solveLinearProgramForSubProblem(java.util.ArrayList<Node> proteinsublist,
                                                                 java.util.ArrayList<Node> epitopes,
                                                                 java.util.ArrayList<Node> solution,
                                                                 LinearProgramSolver solver)

solveDenseCoveringProblemLP

public java.util.ArrayList<Node> solveDenseCoveringProblemLP(LinearProgramSolver solver,
                                                             int max)

solveCoveringProblemLP

public java.util.ArrayList<Node> solveCoveringProblemLP(LinearProgramSolver solver,
                                                        int mincover)

solveDualCoveringProblemLP

public java.util.ArrayList<Node> solveDualCoveringProblemLP(LinearProgramSolver solver,
                                                            int maxcost)

solveCoveringProblemLPMulticover

public java.util.ArrayList<Node> solveCoveringProblemLPMulticover(LinearProgramSolver solver)

toSetCoverGPML

public java.lang.String toSetCoverGPML(int mincover)

Deprecated.

Writes the linear program in Mathprog format for the set sovering problem represented by the bipartite graph to a string. Subsets are on the left. Universe elements on the right.

Parameters:

mincover -

Returns:

toGML

public java.lang.String toGML()

Generates the GML-graph representation of the Bipartite Graph A recommended viewer for GML files is yED

Overrides:

toGML in class Graph

Returns:

toSetCoverGPML

public void toSetCoverGPML(java.lang.String filename,
                           int mincover)

Deprecated.

Writes the linear program in Mathprog format for the set sovering problem represented by the bipartite graph to a file. Subsets are on the left. Universe elements on the right.

Parameters:

filename -

mincover -

toSetCoverGPMLStream

public void toSetCoverGPMLStream(java.lang.String filename,
                                 int mincover)

Writes the linear program in Mathprog format for the set sovering problem represented by the bipartite graph directly to a file. Subsets are on the left. Universe elements on the right.

Parameters:

filename -

mincover -

toSetCoverOPBStream

public void toSetCoverOPBStream(java.lang.String filename,
                                int mincover)

Writes the linear program in OPB format for the set sovering problem represented by the bipartite graph directly to a file. Subsets are on the left. Universe elements on the right. See http://www.mpi-inf.mpg.de/departments/d2/software/opbdp/README

Parameters:

filename -

mincover -

toSetCoverCPLEXStream

public void toSetCoverCPLEXStream(java.lang.String filename,
                                  int mincover)

Writes the linear program in CPLEX LP format for the set sovering problem represented by the bipartite graph directly to a file. Subsets are on the left. Universe elements on the right.

Parameters:

filename -

mincover -

isValidCovering

public boolean isValidCovering(java.util.ArrayList<Node> set)

Checks if a set of left nodes (subset) covers all right nodes (universe elements).

Parameters:

set -

Returns:

sortCovering

public java.util.ArrayList<Node> sortCovering(java.util.ArrayList<Node> pset,
                                              java.lang.String filename)

Sorts a covering by means of the greedy heuristic.

Parameters:

set -

Returns:

getLeftNodeWithCardinality

public java.util.ArrayList<Node> getLeftNodeWithCardinality(int min,
                                                            int max)

Returns all nodes on left side that have a cardinality bigger than min and lower than max.

Parameters:

min -

max -

Returns:

getRightNodeWithCardinality

public java.util.ArrayList<Node> getRightNodeWithCardinality(int min,
                                                             int max)

Returns all nodes on right side that have cardinality bigger than min and lower than max.

Parameters:

min -

max -

Returns:

getLeftNodeWithActiveCardinality

public java.util.ArrayList<Node> getLeftNodeWithActiveCardinality(int min,
                                                                  int max)

Returns all nodes on left side that have active cardinality bigger than min and lower than max.

Parameters:

min -

max -

Returns:

getRightNodeWithActiveCardinality

public java.util.ArrayList<Node> getRightNodeWithActiveCardinality(int min,
                                                                   int max)

Returns all nodes on right side that have active cardinality bigger than min and lower than max.

Parameters:

min -

max -

Returns:

findSimilarLeftNodes

public java.util.ArrayList<Node> findSimilarLeftNodes(Node node)

Parameters:

node -

Returns:

toGML

public void toGML(java.lang.String filename)

Overrides:

toGML in class Graph

Parameters:

filename -

getNodeSet

public java.util.ArrayList<Node> getNodeSet(java.lang.String nodestring)

Overrides:

getNodeSet in class Graph

Parameters:

nodestring -

Returns:

getNodeSet

public java.util.ArrayList<Node> getNodeSet(java.util.ArrayList<java.lang.String> nodelist)

getIndex

public int getIndex(Node node)

getNode

public Node getNode(int index)

main

public static void main(java.lang.String[] args)

getNodes

public java.util.HashMap<java.lang.String,Node> getNodes()

Specified by:

getNodes in interface GraphInterface

Overrides:

getNodes in class Graph

Returns:

the nodesright

getNumberNodes

public int getNumberNodes()

Specified by:

getNumberNodes in interface GraphInterface

Overrides:

getNumberNodes in class Graph