Module org.jgrapht.core

Package org.jgrapht.alg.drawing

Class BarycenterGreedyTwoLayeredBipartiteLayout2D<V,E>

java.lang.Object

org.jgrapht.alg.drawing.TwoLayeredBipartiteLayout2D<V,E>

org.jgrapht.alg.drawing.BarycenterGreedyTwoLayeredBipartiteLayout2D<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

LayoutAlgorithm2D<V,E>

public class BarycenterGreedyTwoLayeredBipartiteLayout2D<V,E>
extends TwoLayeredBipartiteLayout2D<V,E>

The barycenter heuristic greedy algorithm for edge crossing minimization in two layered bipartite layouts. The algorithm draws a bipartite graph using straight edges. Vertices are arranged along two vertical or horizontal lines, trying to minimize crossings. This algorithm targets the one-sided problem where one of the two layers is considered fixed and the algorithm is allowed to adjust the positions of vertices in the other layer. The algorithm is described in the following paper: K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transaction on Systems, Man, and Cybernetics, 11(2):109–125, 1981. The problem of minimizing edge crossings when drawing bipartite graphs as two layered graphs is NP-complete. If the coordinates of the nodes in the fixed layer are allowed to vary wildly, then the barycenter heuristic can perform badly. If the coordinates of the nodes in the fixed layer are $1, 2, 3, \ldots, ...$ then it is an $\mathcal{O}(\sqrt{n})$-approximation algorithm.

Author:

Dimitrios Michail

Field Summary

Fields inherited from class org.jgrapht.alg.drawing.TwoLayeredBipartiteLayout2D

partition, vertexComparator, vertical

Constructor Summary

Constructors

Constructor	Description
BarycenterGreedyTwoLayeredBipartiteLayout2D()	Create a new layout
BarycenterGreedyTwoLayeredBipartiteLayout2D(Set<V> partition, Comparator<V> vertexComparator, boolean vertical)	Create a new layout

Method Summary

Modifier and Type	Method	Description
protected void	drawSecondPartition(Graph<V,E> graph, List<V> partition, LayoutModel2D<V> model)

Methods inherited from class org.jgrapht.alg.drawing.TwoLayeredBipartiteLayout2D

computePartitions, drawFirstPartition, layout, withFirstPartition, withVertexComparator, withVertical

Methods inherited from class java.lang.Object

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

Constructor Detail

BarycenterGreedyTwoLayeredBipartiteLayout2D

public BarycenterGreedyTwoLayeredBipartiteLayout2D()

Create a new layout

BarycenterGreedyTwoLayeredBipartiteLayout2D

public BarycenterGreedyTwoLayeredBipartiteLayout2D(Set<V> partition,
                                                   Comparator<V> vertexComparator,
                                                   boolean vertical)

Create a new layout

Parameters:

partition - one of the two partitions, can be null

vertexComparator - vertex order, can be null

vertical - draw on two vertical or horizontal lines

Method Detail

drawSecondPartition

protected void drawSecondPartition(Graph<V,E> graph,
                                   List<V> partition,
                                   LayoutModel2D<V> model)

Overrides:

drawSecondPartition in class TwoLayeredBipartiteLayout2D<V,E>