Module org.jgrapht.core

Package org.jgrapht.alg.drawing

Class MedianGreedyTwoLayeredBipartiteLayout2D<V,E>

java.lang.Object

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

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

LayoutAlgorithm2D<V,E>

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

The median 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: Eades, Peter, and Nicholas C. Wormald. "Edge crossings in drawings of bipartite graphs." Algorithmica 11.4 (1994): 379-403. The problem of minimizing edge crossings when drawing bipartite graphs as two layered graphs is NP-complete and the median heuristic is a 3-approximation algorithm.

Author:

Dimitrios Michail

Field Summary

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

partition, vertexComparator, vertical

Constructor Summary

Constructors

Constructor	Description
MedianGreedyTwoLayeredBipartiteLayout2D()	Create a new layout
MedianGreedyTwoLayeredBipartiteLayout2D(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

MedianGreedyTwoLayeredBipartiteLayout2D

public MedianGreedyTwoLayeredBipartiteLayout2D()

Create a new layout

MedianGreedyTwoLayeredBipartiteLayout2D

public MedianGreedyTwoLayeredBipartiteLayout2D(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>