Package org.jungrapht.visualization.layout.algorithms.eiglsperger

Class EiglspergerSteps<V,​E>

  • Type Parameters:
    V - vertex type
    E - edge type
    Direct Known Subclasses:
    EiglspergerStepsBackward, EiglspergerStepsForward
    public class EiglspergerSteps<V,​E>
extends Object
    The five steps of the Eiglsperger optimization of the Sugiyama Layout Algorithm

    Javadoc text includes descriptions from the Eiglsperger paper

    See Also:
    "Methods for Visual Understanding Hierarchical System Structures. KOZO SUGIYAMA, MEMBER, IEEE, SHOJIRO TAGAWA, AND MITSUHIKO TODA, MEMBER, IEEE", "An E log E Line Crossing Algorithm for Levelled Graphs. Vance Waddle and Ashok Malhotra IBM Thomas J. Watson Research Center", "Simple and Efficient Bilayer Cross Counting. Wilhelm Barth, Petra Mutzel, Institut für Computergraphik und Algorithmen Technische Universität Wien, Michael Jünger, Institut für Informatik Universität zu Köln", "Fast and Simple Horizontal Coordinate Assignment, Ulrik Brandes and Boris Köpf, Department of Computer & Information Science, University of Konstanz", "An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing. Markus Eiglsperger, Martin Siebenhaller, Michael Kaufman"

    • Field Detail

      • svGraph

        protected org.jgrapht.Graph<LV<V>,​LE<V,​E>> svGraph
        The delegate Graph to layout

      • neighborCache

        protected org.jgrapht.alg.util.NeighborCache<LV<V>,​LE<V,​E>> neighborCache

      • layersArray

        protected LV<V>[][] layersArray
        the result of layering the graph vertices and introducint synthetic vertices and edges

      • joinVertexPredicate

        protected Predicate<LV<V>> joinVertexPredicate
        when sweeping top to bottom, this is a PVertex, bottom to top, this is a QVertex

      • splitVertexPredicate

        protected Predicate<LV<V>> splitVertexPredicate
        when sweeping top to bottom, this is a QVertex, bottom to top this is a PVertex

      • neighborFunction

        protected Function<LV<V>,​Set<LV<V>>> neighborFunction
        When sweeping top to bottom, this function returns predecessors When sweeping bottom to top, this function returns sucessors

      • edgeSourceFunction

        protected Function<LE<V,​E>,​LV<V>> edgeSourceFunction

      • edgeTargetFunction

        protected Function<LE<V,​E>,​LV<V>> edgeTargetFunction

      • transpose

        protected boolean transpose

      • compactionGraph

        protected org.jgrapht.Graph<LV<V>,​Integer> compactionGraph

      • typeOneConflicts

        protected Set<LE<V,​E>> typeOneConflicts

    • Constructor Detail

      • EiglspergerSteps

        protected EiglspergerSteps​(org.jgrapht.Graph<LV<V>,​LE<V,​E>> svGraph,
                           LV<V>[][] layersArray,
                           Predicate<LV<V>> joinVertexPredicate,
                           Predicate<LV<V>> splitVertexPredicate,
                           Function<LE<V,​E>,​LV<V>> edgeSourceFunction,
                           Function<LE<V,​E>,​LV<V>> edgeTargetFunction,
                           Function<LV<V>,​Set<LV<V>>> neighborFunction,
                           Function<List<LE<V,​E>>,​List<LE<V,​E>>> edgeEndpointSwapOrNot,
                           boolean transpose)
        Parameters:
        svGraph - the delegate graph
        layersArray - layered vertices
        joinVertexPredicate - vertices to join with Containers
        splitVertexPredicate - vertices to split from Containers
        neighborFunction - predecessors or successors in the Graph

    • Method Detail

      • clearGraph

        protected static <V,​E> void clearGraph​(org.jgrapht.Graph<V,​E> graph)

      • getTypeOneConflicts

        public Set<LE<V,​E>> getTypeOneConflicts()

      • stepOne

        public void stepOne​(List<LV<V>> currentLayer)
        "In the first step we append the segment s(v) for each p-vertex v in layer L i to the container preceding v. Then we join this container with the succeeding container. The result is again an alternating layer (p-vertices are omitted). for any PVertex (QVertex) that is in the list, take that vertex's segment and append it to the any prior Container in the list (creating the Container as needed), and do not append the PVertex (QVertex) in the list to be returned. Finally, scan the list to join any sequential Containers into one and to insert empty Containers between sequential vertices.
        Parameters:
        currentLayer - the rank of vertices to operate over

      • stepTwo

        public void stepTwo​(List<LV<V>> currentLayer,
                    List<LV<V>> downstreamLayer)
        "In the second step we compute the measure values for the elements in L i+1 . First we assign a position value pos(v i j ) to all vertices v i j in L i . pos(v i 0 ) = size(S i 0 ) and pos(v i j ) = pos(v i j−1 ) + size(S i j ) + 1. Note that the pos values are the same as they would be in the median or barycenter heuristic if each segment was represented as dummy vertex. Each non- empty container S i j has pos value pos(v i j −1 ) + 1. If container S i 0 is non- empty it has pos value 0. Now we assign the measure to all non-q-vertices and containers in L i+1 . The initial containers in L i+1 are the resulting containers of the first step. Recall that the measure of a container in L i+1 is its position in L i ." Assign positions to the currentLayerVertices and use those posisions to calculate the measure for vertices in the downstreamLayer. The measure here is the median of the positions of neghbor vertices
        Parameters:
        currentLayer -
        downstreamLayer -

      • stepThree

        public void stepThree​(List<LV<V>> downstreamLayer)
        "In the third step we calculate an initial ordering of L i+1 . We sort all non-q-vertices in L i+1 according to their measure in a list L V . We do the same for the containers and store them in a list L S . We use the following operations on these sorted lists:"
        • ◦ l = pop(L) : Removes the first element l from list L and returns it.
        • ◦ push(L, l) : Inserts element l at the head of list L.
        We merge both lists in the following way: if m(head(L V )) ≤ pos(head(L S )) then v = pop(L V ), append(L i+1 , v) if m(head(L V )) ≥ (pos(head(L S )) + size(head(L S )) − 1) then S = pop(L S ), append(L i+1 , S) else S = pop(L S ), v = pop(L V ), k = ⌈m(v) − pos(S)⌉, (S 1 ,S 2 ) = split(S, k), append(L i+1 ,S 1 ), append(L i+1 , v), pos(S 2 ) = pos(S) + k, push(L S ,S 2 ).
        Parameters:
        downstreamLayer -

      • stepFour

        public void stepFour​(List<LV<V>> downstreamLayer,
                     int downstreamRank)
        In the fourth step we place each q-vertex v of L i+1 according to the position of its corresponding segment s(v). We do this by calling split(S, s(v)) for each q-vertex v in layer L i+1 and placing v between the resulting containers (S denotes the container that includes s(v)).
        Parameters:
        downstreamLayer -
        downstreamRank -

      • stepFive

        public int stepFive​(List<LV<V>> currentLayer,
                    List<LV<V>> downstreamLayer,
                    int currentRank,
                    int downstreamRank)
        In the fifth step we perform cross counting according to the scheme pro- posed by Barth et al (see Section 1.2). During the cross counting step between layer L i and L i+1 we therefore consider all layer elements as ver- tices. Beside the common edges between both layers, we also have to handle virtual edges, which are imaginary edges between a container ele- ment in L i and the resulting container elements or q-vertices in L i+1 (see Figure 5). In terms of the common approach each virtual edge represents at least one edge between two dummy vertices. The number of represented edges is equal to the size of the container element in L i+1 . We have to consider this fact to get the right number of edge crossings. We therefore introduce edge weights. The weight of a virtual edge ending with a con- tainer element S is equal to size(S). The weight of the other edges is one. So a crossing between two edges e 1 and e 2 counts as weight(e 1 )·weight(e 2 ) crossings.
        Parameters:
        currentLayer - the Li layer
        downstreamLayer - the Li+1 (or Li-1 for backwards) layer
        currentRank - the value of i for Li
        downstreamRank - the value of i+1 (or i-1 for backwards)
        Returns:
        count of edge crossing weight

      • swapEdgeEndpoints

        protected static <V,​E> List<LE<V,​E>> swapEdgeEndpoints​(List<LE<V,​E>> list)

      • stepSix

        public void stepSix​(List<LV<V>> downstreamLayer)
        In the sixth step we perform a scan on L i+1 and insert empty containers between two consecutive vertices, and call join(S 1 , S 2 ) on two consecutive containers in the list. This ensures that L i+1 is an alternating layer.
        Parameters:
        downstreamLayer -