suvi.alg.util
Class NodeRankingPolicies

java.lang.Object
  |
  +--javautils.collections.Algs
        |
        +--javautils.graph.Graphs
              |
              +--suvi.alg.util.NodeRankingPolicies
Direct Known Subclasses:
ExplicitNodeRankingPolicy, OptimalNodeRankingPolicy, SimplisticNodeRankingPolicy

public class NodeRankingPolicies
extends javautils.graph.Graphs

Utilities for node ranking policies.


Nested Class Summary
static class NodeRankingPolicies.SpanningTree
          A mutable spanning tree for a graph.
 
Field Summary
 
Fields inherited from class javautils.collections.Algs
EMPTY_ARRAY, EMPTY_LIST, EMPTY_MAP, EMPTY_SEQUENCE, EMPTY_SET
 
Constructor Summary
NodeRankingPolicies()
           
 
Method Summary
static javautils.maps.ObjectToIntMap edgeToMinLengthMap(javautils.graph.adt.AugmentedGraph preprocessed, GraphTopology topology, EdgeMinLengthAttr edgeMinLengthAttr)
           
static javautils.maps.ObjectToDoubleMap edgeToWeightMap(javautils.graph.adt.AugmentedGraph preprocessed, GraphTopology topology, EdgeWeightAttr edgeWeightAttr)
           
static void feasibleTree(NodeRankingPolicies.SpanningTree tree, javautils.maps.ObjectToDoubleMap graphEdgeToWeightMap, javautils.maps.ObjectToIntMap edgeToMinLengthMap, javautils.maps.ObjectToIntMap nodeToRankMap)
          Computes an initial feasible spanning tree for the network simplex algorithm.
static javautils.maps.ObjectToIntMap initialRanking(javautils.graph.adt.AugmentedGraph graph, javautils.maps.ObjectToIntMap edgeToMinLengthMap)
           
static void networkSimplex(NodeRankingPolicies.SpanningTree initialFeasibleTree, javautils.maps.ObjectToDoubleMap graphEdgeToWeightMap, javautils.maps.ObjectToIntMap edgeToMinLengthMap, javautils.maps.ObjectToIntMap nodeToRankMap)
          The network-simplex algorithm [Gansner1993].
static NodeRanking newNodeRanking(javautils.maps.ObjectToIntMap nodeToRankMap)
           
static void normalize(javautils.maps.ObjectToIntMap nodeToRankMap)
           
 
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

NodeRankingPolicies

public NodeRankingPolicies()
Method Detail

feasibleTree

public static void feasibleTree(NodeRankingPolicies.SpanningTree tree,
                                javautils.maps.ObjectToDoubleMap graphEdgeToWeightMap,
                                javautils.maps.ObjectToIntMap edgeToMinLengthMap,
                                javautils.maps.ObjectToIntMap nodeToRankMap)

Computes an initial feasible spanning tree for the network simplex algorithm.


networkSimplex

public static void networkSimplex(NodeRankingPolicies.SpanningTree initialFeasibleTree,
                                  javautils.maps.ObjectToDoubleMap graphEdgeToWeightMap,
                                  javautils.maps.ObjectToIntMap edgeToMinLengthMap,
                                  javautils.maps.ObjectToIntMap nodeToRankMap)

The network-simplex algorithm [Gansner1993].


initialRanking

public static javautils.maps.ObjectToIntMap initialRanking(javautils.graph.adt.AugmentedGraph graph,
                                                           javautils.maps.ObjectToIntMap edgeToMinLengthMap)

normalize

public static void normalize(javautils.maps.ObjectToIntMap nodeToRankMap)

newNodeRanking

public static NodeRanking newNodeRanking(javautils.maps.ObjectToIntMap nodeToRankMap)

edgeToMinLengthMap

public static javautils.maps.ObjectToIntMap edgeToMinLengthMap(javautils.graph.adt.AugmentedGraph preprocessed,
                                                               GraphTopology topology,
                                                               EdgeMinLengthAttr edgeMinLengthAttr)

edgeToWeightMap

public static javautils.maps.ObjectToDoubleMap edgeToWeightMap(javautils.graph.adt.AugmentedGraph preprocessed,
                                                               GraphTopology topology,
                                                               EdgeWeightAttr edgeWeightAttr)