y.layout.router.polyline
Class ChannelBasedPathRouting

java.lang.Object
  y.layout.router.polyline.ChannelBasedPathRouting

public class ChannelBasedPathRouting
extends java.lang.Object

This class routes edges using their pre-calculated Path information.

The concept of this algorithm is to bundle edge segments into so-called Channels and route each Channel individually.

This class is initialized using initialize(PathSearchConfiguration) which must have been called before the edges are routed.

After a ChannelBasedPathRouting instance is no longer in use, the Channel information and the reference to the configuration must be reset using method cleanup().

See Also:

EdgeInfo.getSegmentInfo(int), LayoutGraph.setPath(Edge, YList)

Constructor Summary

ChannelBasedPathRouting()
Creates a new instance of ChannelBasedPathRouting.

Method Summary

protected void	adjustSegmentLocations(Channel channel) Adjusts the location assigned to a segment info in the channel considering the preferred alignment of the segment.
protected void	calculateSegmentLocations(Channel channel) Calculates the locations of the segment infos in the given channel.
void	cleanup() Resets all channel information and the reference to the configuration.
protected java.util.Comparator	createSegmentInfoComparator(YList channels, PathSearchResult pathSearchResult, PathSearchConfiguration configuration) Creates a comparator for sorting the SegmentInfos in a Channel from left to right (for vertical segments) or top to bottom (for horizontal segments), respectively.
protected PathSearchConfiguration	getConfiguration() Returns the path search configuration with which the ChannelBasedPathRouting has been initialized.
void	initialize(PathSearchConfiguration configuration) Initializes this ChannelBasedPathRouting instance for routing paths that have been found with the given configuration.
protected void	optimizeSegmentOrder(Channel channel) Optimizes the order of the segments in the given channel.
void	route(EdgeList edges, PathSearchResult pathSearchResult) Routes the given edges.
protected void	sortSegmentInfos(java.util.List segmentInfos, java.util.Comparator segmentInfoComparator) Sorts the given list of SegmentInfos using the given comparator.

Methods inherited from class java.lang.Object

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

Constructor Detail

ChannelBasedPathRouting

public ChannelBasedPathRouting()

Creates a new instance of ChannelBasedPathRouting.

Method Detail

initialize

public void initialize(PathSearchConfiguration configuration)

Initializes this ChannelBasedPathRouting instance for routing paths that have been found with the given configuration.

This method must be called before the edges are routed.

Parameters:

configuration - the configuration used for the following path routing

See Also:

route(EdgeList, PathSearchResult)

cleanup

public void cleanup()

Resets all channel information and the reference to the configuration.

Afterwards, ChannelBasedPathRouting is ready to calculate paths for a new layout.

getConfiguration

protected PathSearchConfiguration getConfiguration()

Returns the path search configuration with which the ChannelBasedPathRouting has been initialized.

Returns:

the configuration of this ChannelBasedPathRouting instance

See Also:

initialize(PathSearchConfiguration)

route

public void route(EdgeList edges,
                  PathSearchResult pathSearchResult)

Routes the given edges.

Before calling this method, method initialize(PathSearchConfiguration) must have been called.

As a first step, the SegmentInfos of all edge paths are distributed to Channels. After that, the segments in each of these Channels are sorted and locations are assigned respecting the segments' location ranges by calling the subsequent methods:

1. optimizeSegmentOrder(Channel)
2. calculateSegmentLocations(Channel)
3. adjustSegmentLocations(Channel)

Finally, the control points for the paths are calculated.

Parameters:

edges - the list of edges to be routed

pathSearchResult - the path search result containing the Path objects for the edges

Throws:

java.lang.IllegalStateException - if the locations are not within the segment's location range

See Also:

PathSearchResult.getPath(Edge), AbstractSegmentInfo.getLocationRange(), AbstractSegmentInfo.setLocation(double)

createSegmentInfoComparator

protected java.util.Comparator createSegmentInfoComparator(YList channels,
                                                           PathSearchResult pathSearchResult,
                                                           PathSearchConfiguration configuration)

Creates a comparator for sorting the SegmentInfos in a Channel from left to right (for vertical segments) or top to bottom (for horizontal segments), respectively.

This method is called in route(EdgeList, PathSearchResult) before edge segments are distributed within the channels.

Parameters:

channels - the channels whose segments will be sorted by the comparator

pathSearchResult - the path search result containing the EdgeInfos with the SegmentInfos for which the comparator will be used

configuration - the configuration used during this path search

Returns:

a comparator used for sorting the SegmentInfos in a channel

sortSegmentInfos

protected void sortSegmentInfos(java.util.List segmentInfos,
                                java.util.Comparator segmentInfoComparator)

Sorts the given list of SegmentInfos using the given comparator.

This method is called in route(EdgeList, PathSearchResult) when the edge segments are distributed within the channels.

Parameters:

segmentInfos - the list of SegmentInfos to be sorted

segmentInfoComparator - the comparator used for sorting the list of SegmentInfos

optimizeSegmentOrder

protected void optimizeSegmentOrder(Channel channel)

Optimizes the order of the segments in the given channel.

After the segments in the channel have been sorted using the comparator created by method createSegmentInfoComparator(YList, PathSearchResult, PathSearchConfiguration), segments having a common SegmentGroup are replaced by their common representative segment info.

This method further improves the order of the resulting segment info list to make sure that the subsequent location calculation is able to respect the location ranges of the SegmentInfos and, if possible, the minimum edge to edge distances and possible grid constraints for the segments.

Parameters:

channel - the channel for which the order of the SegmentInfos is optimized

calculateSegmentLocations

protected void calculateSegmentLocations(Channel channel)

Calculates the locations of the segment infos in the given channel.

This method is called after the order of the segment infos within a channel has been optimized.

Precondition:

The locations of the segments are stored in the channel. They should respect minimum edge to edge distances and grid constraints and must lie in the respective location ranges.

Parameters:

channel - the channel that contains the segment infos for which the locations will be calculated

See Also:

Channel.setCurrentLocation(SegmentInfo, double)

adjustSegmentLocations

protected void adjustSegmentLocations(Channel channel)

Adjusts the location assigned to a segment info in the channel considering the preferred alignment of the segment.

This method is called after the segments have been distributed in the channel but before the final locations of the segments are assigned to the segment infos.

Parameters:

channel - the channel that contains the segment infos for which the alignment should be considered

See Also:

Channel.getCurrentLocation(SegmentInfo), AbstractSegmentInfo.getPreferredAlignment()