suvi.alg.policies
Class OptimalNodeRankingPolicy

java.lang.Object
  |
  +--javautils.collections.Algs
        |
        +--javautils.graph.Graphs
              |
              +--suvi.alg.util.NodeRankingPolicies
                    |
                    +--suvi.alg.policies.OptimalNodeRankingPolicy

All Implemented Interfaces:

GraphLayoutAttrConsumer, NodeRankingPolicy

public class OptimalNodeRankingPolicy

extends NodeRankingPolicies

implements NodeRankingPolicy

Assigns optimal ranks minimizing the sum of edge weights (EdgeWeightAttr) while respecting minimum edge length constraints (EdgeMinLengthAttr). Uses the network-simplex algorithm described in [Gansner1993].

Note: This policy assumes that the preprocessed graph is acyclic. If your graphs may contain cycles, you must use an appropriate node ranking policy decorator to make the preprocessed graph acyclic.

Nested Class Summary

Nested classes inherited from class suvi.alg.util.NodeRankingPolicies

NodeRankingPolicies.SpanningTree

Field Summary

Fields inherited from class javautils.collections.Algs

EMPTY_ARRAY, EMPTY_LIST, EMPTY_MAP, EMPTY_SEQUENCE, EMPTY_SET

Constructor Summary

OptimalNodeRankingPolicy()

Method Summary

GraphLayoutAttr[]	defaultAttrs() This policy uses the following attributes: EdgeMinLengthAttr EdgeWeightAttr
NodeRanking	nodeRanking(javautils.graph.adt.AugmentedGraph original, javautils.graph.adt.AugmentedGraph preprocessed, GraphTopology topology, GraphLayoutAttrMap attrMap) A node ranking for the graph.

Methods inherited from class suvi.alg.util.NodeRankingPolicies

edgeToMinLengthMap, edgeToWeightMap, feasibleTree, initialRanking, networkSimplex, newNodeRanking, normalize

Methods inherited from class javautils.graph.Graphs

asSourceTargetPair, asString, asString, augmented, connectedComponents, edges, edgeSet, forEachEdge, forEachNode, inducedByEdgesAndContainingNodes, invariant, isAcyclic, isIncoming, isSelf, nodesByDecreasingDfsFinishingTime, nodesByIncreasingIndegree, nodesByIncreasingOutdegree, nodeSet, nodesReachableFrom, nodesReachableFrom, nodesReachableFrom, otherNode, randomGraph, restrictedToNodes, restrictedToNodes, restrictedToNodes, sameNodesAndEdges, stronglyConnectedComponents, transitiveIrreflexiveClosure, transposed, transposed, undirected

Methods inherited from class javautils.collections.Algs

addAll, allSuperInterfaces, asArray, asArray, asComparator, asUnmodifiableList, collect, collectMap, collectSet, collectUnmodifiable, concat, concat, concat, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOfArray, ensureLength, exists, exists, exists, filter, filter, filter, find, find, find, flatten, flatten, flatten, fold, fold, fold, foldRight, foldRight, foldRight, forAll, forAll, forAll, forEach, forEach, forEach, forEach, forEach, forEach, forEachInProduct, forEachInProduct, forEachInProduct, forEachInProduct, genAddAll, genConcat, genConcat, genForEach, genForEach, getOrIfNull, integersInRange, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iteratorOverArray, map, map, map, map, map, map, mapMorphism, mapMorphismTo, mapTransform, max, max, max, max, max, max, max, min, min, min, min, min, min, min, newMap, newShapedArray, newUnmodifiableList, putAll, putAll, reverseIterator, reverseIterator, select, select, select, sign, singletonIterator, sort, sort, sorted, sorted, transform, transform, transform

Methods inherited from class java.lang.Object

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

Constructor Detail

OptimalNodeRankingPolicy

public OptimalNodeRankingPolicy()

Method Detail

defaultAttrs

public GraphLayoutAttr[] defaultAttrs()

This policy uses the following attributes:

• EdgeMinLengthAttr
• EdgeWeightAttr

Specified by:

defaultAttrs in interface GraphLayoutAttrConsumer

nodeRanking

public NodeRanking nodeRanking(javautils.graph.adt.AugmentedGraph original,
                               javautils.graph.adt.AugmentedGraph preprocessed,
                               GraphTopology topology,
                               GraphLayoutAttrMap attrMap)

Description copied from interface: NodeRankingPolicy

A node ranking for the graph.

Specified by:

nodeRanking in interface NodeRankingPolicy