Package util

Class PartialScheduleGrph

java.lang.Object

grph.Grph

grph.in_memory.InMemoryGrph

util.ScheduleGrph

util.PartialScheduleGrph

All Implemented Interfaces:

java.lang.Comparable<PartialScheduleGrph>

public class PartialScheduleGrph
extends ScheduleGrph
implements java.lang.Comparable<PartialScheduleGrph>

The PartialScheduleGrph extends the Grph libraries graphing classes, and provides an object that represents a Partial schedule in the scheduling algorithm state space

Author:

Matt / Eugene

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class grph.Grph

grph.Grph.DIRECTION, grph.Grph.MaxIndependentSetAlgorithm, grph.Grph.MinVertexCoverAlgorithm, grph.Grph.TYPE

Field Summary

Fields

Modifier and Type	Field	Description
static long	time

Fields inherited from class grph.Grph

adjacencyMatrixAlgo, allClusteringCoefficientsAlgorithm, avgClusteringCoefficientAlgorithm, avgDegreeAlgorithm, bfsAlgorithm, bipartiteAlgorithm, branchingMinimumVertexCoverAlgorithm, bruteForceMinimumVertexCoverAlgorithm, centerAlgorithm, chordalAlgo, COMPILATION_DIRECTORY, complementAlgorithm, completenessAlgorithm, connectedComponentsAlg, connectednessAlgorithm, densityAlgorithm, diameterAlgorithm, FominGrandoniKratschMaximumindependentSetAlgorithm, girthAlgorithm, HOSTS, inacessibleVertices, incidenceMatrixAlgo, inNeighborsAlgorithm, inOutNeighborsAlgorithm, irreflexiveAlgorithm, isCyclicAlgorithm, isolatedVerticesAlgorithm, lineGraphAlg, logger, LPMaximumindependentSetAlgorithm, LPMaxMatchingAlgorithm, LPMinVertexCoverAlgorithm, maxInEdgeDegreeAlgorithm, maxInVertexDegreeAlgorithm, maxOutEdgeDegreeAlgorithm, maxOutVertexDegreeAlgorithm, minInEdgeDegreeAlgorithm, minInVertexDegreeAlgorithm, minOutEdgeDegreeAlgorithm, minOutVertexDegreeAlgorithm, multigraphnessAlgorithm, NiedermeierMinimumVertexCoverAlgorithm, outNeighborsAlgorithm, radiusAlgorithm, reflexivityAlgorithm, regularityAlgorithm, simplenessAlgorithm, tarjanSCC, topologicalSortingAlg, treenessAlgorithm, trianglesAlgorithm, twoSweepDiameterAlg, unweightedDistanceMatrixAlgorithm, unweightedPredecessorMatrixAlgorithm, useCache, vertexAdjacenciesAsIDSetsAlgorithm, vertexListAlgorithm

Constructor Summary

Constructors

Constructor	Description
PartialScheduleGrph(int score)	Constructor with specific score value, useful for cloning from a parent.

Method Summary

Modifier and Type	Method	Description
void	addFreeTask(ScheduleGrph init, int task, int pc)	Add a free task to the earliest possible time on this schedule on the specified processor
int	compareTo(PartialScheduleGrph g)	The compareTo method for ranking partial schedules.
PartialScheduleGrph	copy()	Create and return a copy of this schedule including data such as task starts, score, processor starts etc
boolean	equals(java.lang.Object o)
boolean	equivalenceCheck(ScheduleGrph input, int lastAdded, int numProcessors)	Checks whether or not a schedule has any equivalent schedules, and should therefore not be expanded.
java.util.TreeSet<java.lang.Integer>	getFixedFree(ScheduleGrph inputSaved)	Get the list of currently free tasks for this partial schedule using the Fixed Task Order pruning strategy.
java.util.HashSet<java.lang.Integer>	getFree(ScheduleGrph inputSaved)	Get the list of currently free tasks for this partial schedule
int	getLastFBottomLevel()	Get the last known bottom level cost of this schedule.
int	getLastIdleTime()	Get the last calculated idle time of this partial schedule, either an outdated value inherited from parent, or an iteratively calculated value usually set during the cost function
PartialScheduleGrph	getNormalizedCopy(int numProcessor)	Returns a normalized copy of this schedule, where processors are in a specific fixed order, to allow comparison between two schedules that are identical aside from processor names
int	getScheduleLength()	Get the overall finish time of this schedule
int	getScore()	Get the current score of this partial schedule, used for ranking in the algorithm
long	getTimeAdded()	Get the time this schedule was added to a list/set.
boolean	outgoingCommsOK(ScheduleGrph input, java.util.HashMap<java.lang.Integer,java.lang.Integer> newStarts, int numProcessors)	Helper method for equivalenceCheck which checks that all outgoing datatransfers of a set of tasks are unaffected by a change in order/position
MinimalScheduleGrph	serialize()	Serialize this schedule into a MinimalScheduleGrph for low memory saving
void	setFBottomLevel(int fbtw)	Set the bottom level time of this schedule
void	setIdleTime(int idleTime)	Set the idle time of this partial schedule
void	setScore(int score)	Set the score of this partial schedule, used for ranking in the algorithm
void	setSerialized(java.lang.String s)	Set the value of the serialized version of this schedule
void	setTimeAdded(long t)	Set the time this schedule was added to a list/set.

Methods inherited from class grph.Grph

addDirectedSimpleEdge, addGraph, addHyperEdge, addNVertices, addSimpleEdge, addSimpleEdge, addUndirectedSimpleEdge, addVertex, addVertices, areEdgesAdjacent, areVerticesAdjacent, bfs, bfs, bfsList, chain, clear, clearCache, clique, clique, clone, computeMaxFlow, connectToKClosestNeighbors, contains, containsAPath, contractEdge, contractVertices, contractVertices, createSwingRenderer, dgrid, disconnect, disconnectVertex, display, displayGraphstream_0_4_2, displayImg, displayReport, displaySVGSalamander, dring, ensureNVertices, equals, findAlgorithm, findPropertyByName, fromCaidaMap, fromGraphML, fromGraphML, fromGrphBinary, fromGrphText, fromGrphTextFile, getAdjacencyMatrix, getAllCycles, getAllInEdgeDegrees, getAllOutEdgeDegrees, getAllPaths, getAverageClusteringCoefficient, getAverageDegree, getAverageDegree, getBipartiteSubgraphInducedByVertices, getCenter, getCircleStar, getCliques, getClusteringCoefficient, getClusteringCoefficient, getClusteringCoefficientDistribution, getComplement, getConnectedComponentContaining, getConnectedComponents, getCutEdges, getCutSize, getDefaultNumberOfThreads, getDegreeDistribution, getDensity, getDescription, getDiameter, getDifference, getDistanceMatrix, getEccentricity, getEccentricity, getEdgeColorProperty, getEdgeDegree, getEdgeLabelProperty, getEdgeNature, getEdgePairs, getEdgesAdjacentToEdge, getEdgesConnecting, getEdgesIncidentTo, getEdgeStyleProperty, getEdgeWidthProperty, getFartestVertex, getFartestVertex, getFringes, getGirth, getGpmetisPartitionning, getGpmetisPartitionning, getInaccessibleVertices, getIncidenceMatrix, getInducedSubgraphIsomorphism, getInEdgeDegree, getInEdges, getInNeighborhoods, getInNeighbors, getInNeighbours, getInOnlyEdges, getInOutOnlyEdges, getInVertexDegree, getIsolatedVertices, getKClosestNeighbors, getKShortestPaths, getLargestConnectedComponent, getLineGraph, getLineGraph, getLocalClusteringCoefficients, getLoops, getMaximumClique, getMaximumIndependentSet, getMaximumIndependentSet, getMaximumMatching, getMaxInEdgeDegrees, getMaxInVertexDegrees, getMaxOutEdgeDegrees, getMaxOutVertexDegrees, getMinimumVertexCover, getMinimumVertexCover, getMinInEdgeDegrees, getMinInVertexDegrees, getMinOutEdgeDegrees, getMinOutVertexDegrees, getNeighborhoods, getNeighbors, getNeighborsAtMaxDistance, getNeighbours, getNeighbours, getNeighbours, getNeighboursAtMostKHops, getNumberOfDirectedEdges, getNumberOfEdges, getNumberOfHyperEdges, getNumberOfSimpleEdges, getNumberOfTriangles, getNumberOfUndirectedEdges, getNumberOfVertices, getOppositeEdges, getOrder, getOutEdgeDegree, getOutEdges, getOutNeighborhoods, getOutNeighbors, getOutOnlyEdges, getOutVertexDegree, getPageRanking, getPartialSubgraphIsomorphism, getProperties, getRadius, getShortestCycle, getShortestPath, getShortestPath, getSimplicialVertices, getSinks, getSize, getSomeEdgeConnecting, getSources, getSpanningTree, getStronglyConnectedComponents, getSubgraphInducedByEdges, getSubgraphInducedByVertices, getTopologyListeners, getTwoSweepBFSDiameterApproximatedDiameter, getVersion, getVertexColorProperty, getVertexDegree, getVertexDegree, getVertexLabelProperty, getVertexShapeProperty, getVertexSizeProperty, getVerticesAccessibleThrough, getVerticesAccessibleThrough, getVerticesIncidentToEdge, getVerticesOfDegree, getVerticesOfDegree, getVerticesOfDegreeAtLeast, glp, grid, grid, hasCycles, hasLoop, hasLoops, hasMultipleEdges, highlight, highlight, highlight, highlight, highlightEdges, highlightEdges, highlightVertex, highlightVertices, highlightVertices, highlightVertices, highlightVertices, isAntigraph, isBipartite, isChordal, isClique, isComplete, isConnected, isCut, isCut, isCyclic, isDirected, isDirectedSimpleEdge, isDirectedSimpleGraph, isDominatingSet, isHyperEdge, isHypergraph, isIndependentSet, isIrreflexive, isIsomorphicTo, isLeaf, isLoop, isMatching, isMixed, isNull, isReflexive, isRegular, isSimple, isSimpleEdge, isSimplicial, isSink, isSource, isStronglyConnected, isTree, isTrivial, isUndirectedSimpleEdge, isUndirectedSimpleGraph, isVertexCover, listCachingGraphAlgorithms, loadOnlineGrph, merge, performRandomTopologicalChange, postOnTheWeb, prune, removeEdges, removeVertices, removeVertices, removeVertices, report, revertEdge, ring, ring, ring, rnws, rnws, search, setEdgesColor, setEdgesLabel, setEdgesStyle, setEdgesWidth, setVerticesColor, setVerticesLabel, setVerticesShape, setVerticesSize, sortTopologically, sortVerticesByDegree, stepMonitor, toEdgeList, toGraphML, toGraphStream_0_4_2_AWTComponent, toGraphviz, toGraphviz, toGrphBinary, toGrphText, toString, toString_elements, toTextADJ, toUndirectedGraph, undirectionalizeEdge

Methods inherited from class grph.in_memory.InMemoryGrph

addDirectedHyperEdge, addDirectedSimpleEdge, addToDirectedHyperEdgeHead, addToDirectedHyperEdgeTail, addToUndirectedHyperEdge, addUndirectedHyperEdge, addUndirectedSimpleEdge, addVertex, containsEdge, containsVertex, getDirectedHyperEdgeHead, getDirectedHyperEdgeTail, getDirectedSimpleEdgeHead, getDirectedSimpleEdgeTail, getEdges, getID, getInOnlyElements, getInOutOnlyElements, getNavigation, getNextEdgeAvailable, getNextVertexAvailable, getNumberOfDirectedHyperEdges, getNumberOfDirectedSimpleEdges, getNumberOfUndirectedHyperEdges, getNumberOfUndirectedSimpleEdges, getOneVertex, getOutOnlyElements, getTheOtherVertex, getUndirectedHyperEdgeVertices, getVertices, isDirectedHyperEdge, isDirectedSimpleEdge, isUndirectedHyperEdge, isUndirectedSimpleEdge, main, removeEdge, removeEdge, removeFromDirectedHyperEdgeHead, removeFromDirectedHyperEdgeTail, removeFromHyperEdge, removeVertex, storeEdges

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from class util.ScheduleGrph

cloneSelf, dependenciesValid, getBottomLevel, getEdgeWeightProperty, getVertexProcessorProperty, getVertexStartProperty, getVertexWeightProperty, getVerticesForProcessor, setEdgeWeightProperty, setVertexProcessorProperty, setVertexStartProperty, setVertexWeightProperty, toDot

Field Detail

time

public static long time

Constructor Detail

PartialScheduleGrph

public PartialScheduleGrph(int score)

Constructor with specific score value, useful for cloning from a parent.

Parameters:

score - The score to assign to this partial schedule

Method Detail

getScore

public int getScore()

Get the current score of this partial schedule, used for ranking in the algorithm

Returns:

setScore

public void setScore(int score)

Set the score of this partial schedule, used for ranking in the algorithm

Parameters:

score - The score value to set

getLastIdleTime

public int getLastIdleTime()

Get the last calculated idle time of this partial schedule, either an outdated value inherited from parent, or an iteratively calculated value usually set during the cost function

Returns:

setIdleTime

public void setIdleTime(int idleTime)

Set the idle time of this partial schedule

Parameters:

idleTime - The total amount of Idle Time on this schedule

setTimeAdded

public void setTimeAdded(long t)

Set the time this schedule was added to a list/set. e.g closedSet, used in comparing between schedules with the same score.

Parameters:

t - The time value to set as

getTimeAdded

public long getTimeAdded()

Get the time this schedule was added to a list/set. e.g closedSet, used in comparing between schedules with the same score.

Returns:

getLastFBottomLevel

public int getLastFBottomLevel()

Get the last known bottom level cost of this schedule. Either an outdated value inherited from parent, or an iteratively calculated value usually set during the cost function

Returns:

setFBottomLevel

public void setFBottomLevel(int fbtw)

Set the bottom level time of this schedule

Parameters:

fbtw - The bottom level cost to set for this schedule

getScheduleLength

public int getScheduleLength()

Get the overall finish time of this schedule

Returns:

copy

public PartialScheduleGrph copy()

Create and return a copy of this schedule including data such as task starts, score, processor starts etc

Returns:

getNormalizedCopy

public PartialScheduleGrph getNormalizedCopy(int numProcessor)

Returns a normalized copy of this schedule, where processors are in a specific fixed order, to allow comparison between two schedules that are identical aside from processor names

Parameters:

numProcessor - The number of processors available for this schedule

Returns:

serialize

public MinimalScheduleGrph serialize()

Serialize this schedule into a MinimalScheduleGrph for low memory saving

Returns:

getFree

public java.util.HashSet<java.lang.Integer> getFree(ScheduleGrph inputSaved)

Get the list of currently free tasks for this partial schedule

Parameters:

inputSaved - The graph read as input used to calculate this partial schedule

Returns:

getFixedFree

public java.util.TreeSet<java.lang.Integer> getFixedFree(ScheduleGrph inputSaved)

Get the list of currently free tasks for this partial schedule using the Fixed Task Order pruning strategy.

Parameters:

inputSaved - The graph read as input used to calculate this partial schedule

Returns:

setSerialized

public void setSerialized(java.lang.String s)

Set the value of the serialized version of this schedule

Parameters:

s - The string to store as the serialized schedule

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class grph.Grph

addFreeTask

public void addFreeTask(ScheduleGrph init,
                        int task,
                        int pc)

Add a free task to the earliest possible time on this schedule on the specified processor

Parameters:

init - The schedule graph read as input used to generate this partial schedule

task - The task to add

pc - The processor to add the task to

equivalenceCheck

public boolean equivalenceCheck(ScheduleGrph input,
                                int lastAdded,
                                int numProcessors)

Checks whether or not a schedule has any equivalent schedules, and should therefore not be expanded. i.e leaves it to the last equivalentschedule to be expanded. RELIES ON THE ALGORITHM EVENTUALLY CHECKING THE EQUIVALENT SCHEDULE WITH ALL TASKS THAT ARE ON THE SAME PROCESSOR AS LASTADDED BEING IN THE INDEX ORDER WHERE POSSIBLE

Parameters:

input - The schedule graph read as input used to generate this partial schedule

lastAdded - The most recently added task on this partial schedule

numProcessors - The number of processors available to schedule tasks on

Returns:

outgoingCommsOK

public boolean outgoingCommsOK(ScheduleGrph input,
                               java.util.HashMap<java.lang.Integer,java.lang.Integer> newStarts,
                               int numProcessors)

Helper method for equivalenceCheck which checks that all outgoing datatransfers of a set of tasks are unaffected by a change in order/position

Parameters:

input - The schedule graph read as input used to generate this partial schedule

newStarts - A map of task id to start time, after the change

numProcessors - The number of processors available to schedule tasks on

Returns:

compareTo

public int compareTo(PartialScheduleGrph g)

The compareTo method for ranking partial schedules. Based on score, otherwise based on time added if scores are equal

Specified by:

compareTo in interface java.lang.Comparable<PartialScheduleGrph>