Implements the Adaptive Constrained Alignment (ACA) algorithm. More...

#include <aca.h>

Collaboration diagram for dialect::ACALayout:

Public Member Functions
	ACALayout (const vpsc::Rectangles &rs, const std::vector< cola::Edge > &es, cola::CompoundConstraints &ccs, const double idealLength, const cola::EdgeLengths &eLengths=cola::StandardEdgeLengths, cola::TestConvergence doneTest=nullptr, cola::PreIteration preIteration=nullptr)
	Constructs an adaptive constrained alignment layout instance. More...

	ACALayout (std::shared_ptr< dialect::Graph > G)
	Construct an ACALayout based on a Graph. More...

void	createAlignments (void)
	Creates alignments. More...

bool	createOneAlignment (void)
	Creates one alignment. More...

bool	applyOAsAllOrNothing (OrderedAlignments oas)
	Creates all the requested alignments, or none if any is infeasible. More...

void	layout (void)
	Do an initial stress-minimising layout, and then create alignments. More...

void	removeOverlaps (void)
	Do an FD layout with overlap prevention, then stop.

void	layoutWithCurrentConstraints (void)
	Run layout with current constraints, and with or without overlap prevention, as per the current settings.

void	updateGraph (void)
	For forward compatibility (i.e. with Graphs), we offer a convenience method to update the Graph (when we have one) with the positions and constraints chosen by this object.

void	updateSepMatrix (void)
	Update the SepMatrix of the Graph on which this ACALayout was built (if any).

void	updateSepMatrix (SepMatrix &M, const std::map< size_t, id_type > &ix2id)
	Update a given SepMatrix with all the ordered alignment constraints generated by this ACA layout. More...

void	addBendPointPenalty (bool b)
	Control whether we avoid making bend points. More...

void	favourLongEdges (bool b)
	Prefer long edges instead of ones that are close to aligned. More...

void	postponeLeaves (bool b)
	Say whether alignment of leaf edges should be saved for last. More...

void	useNonLeafDegree (bool b)
	Say whether leaves should be counted when computing node degrees. More...

void	allAtOnce (bool b)
	Say whether alignment choices should alternate with stress minimisation steps. More...

void	aggressiveOrdering (bool b)
	Say whether to consider changing orthogonal ordering of nodes. More...

void	setAvoidNodeOverlaps (bool avoidOverlaps)
	Specifies whether non-overlap constraints should be automatically generated between all nodes. More...

void	ignoreEdges (std::vector< bool > ignore)
	Specify that certain edges are never to be aligned. More...

void	ignoreNodesForOPWithOffsets (std::vector< bool > ignore)
	Say that certain nodes may be crossed by edges. More...

void	setNodeAliases (std::map< int, int > aliases)
	Set certain nodes to be used in place of others. More...

void	setAlignmentOffsetsForCompassDirection (ACASepFlag sf, EdgeOffsets offsets)
	Say how to offset nodes when edges are aligned in a certain direction. More...

void	setAllowedDirections (ACASepFlags seps)
	Say which separations are allowed for the source and target of each edge. More...

void	setClusterHierarchy (cola::RootCluster *rc)
	sets the cluster hierarchy of the underlying FDLayout.

bool	edgeIsAligned (int j) const
	Check whether an edge is aligned. More...

void	addGroupOfNonOverlapExemptRectangles (std::vector< unsigned > rs)
	Stop non-overlap constraints from being generated between certain nodes.

Detailed Description

Implements the Adaptive Constrained Alignment (ACA) algorithm.

See Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow. "Incremental grid-like layout using soft and hard constraints." In Graph Drawing 2013, pp. 448-459. Springer International Publishing, 2013.

Constructor & Destructor Documentation

◆ ACALayout() [1/2]

dialect::ACALayout::ACALayout	(	const vpsc::Rectangles &	rs,
		const std::vector< cola::Edge > &	es,
		cola::CompoundConstraints &	ccs,
		const double	idealLength,
		const cola::EdgeLengths &	eLengths = `cola::StandardEdgeLengths`,
		cola::TestConvergence *	doneTest = `nullptr`,
		cola::PreIteration *	preIteration = `nullptr`
	)

Constructs an adaptive constrained alignment layout instance.

Parameters are the same as for the ConstrainedFDLayout constructor, with the addition of a vector of constraints passed by reference.

If the vector of constraints is non-empty, these constraints will be applied throughout the ACA process, and the new constraints created by ACA will not conflict with any of these.

In any case, the new constraints generated by ACA are added to this vector.

Parameters

[in]	rs	The bounding boxes of the nodes at their initial positions.
[in]	es	The edges, given as simple pairs of indices (i, j) into the rectangle vector rs.
[in]	ccs	Vector of any pre-existing constraints, and the place where new constraints created by ACA will be recorded.
[in]	idealLength	The "ideal edge length" parameter for the stress function, i.e. the ideal separation between neighbouring nodes. If eLengths (see below) is specified, then this parameter becomes instead a scalar multiplier for the lengths given there.
[in]	preventOverlaps	Say whether non-overlap constraints should be generated for all rectangles.
[in]	eLengths	Individual ideal lengths for edges. The actual ideal length used for the ith edge is idealLength*eLengths[i]. If eLengths is not passed, then just idealLength is used (as if eLengths[i] were equal to 1 for all i).
[in]	done	A test of convergence operation called at the end of each iteration (optional). If not given, uses a default TestConvergence object.
[in]	preIteration	An operation to be called before each iteration (optional).

◆ ACALayout() [2/2]

dialect::ACALayout::ACALayout ( std::shared_ptr< dialect::Graph > G )

Construct an ACALayout based on a Graph.

Parameters

[in] G the Graph

Member Function Documentation

◆ addBendPointPenalty()

void dialect::ACALayout::addBendPointPenalty ( bool b )

Control whether we avoid making bend points.

We refer to a node of degree 2 as a "bend point" when one of its edges has been aligned horizontally and the other vertically.

The default value of addBendPointPenalty is true. In this case a penalty score is added when choosing the next alignment in order to postpone creating bend points until no other choices remain.

If set to false then there is no penalty score to postpone the creation of bend points.

When there is both bend point penalty and leaf penalty (see below), then bend points will be created before leaf edges are aligned. This can be reversed by altering the BP_PENALTY and LEAF_PENALTY constants.

◆ aggressiveOrdering()

void dialect::ACALayout::aggressiveOrdering ( bool b )

Say whether to consider changing orthogonal ordering of nodes.

The default value is false. In that case, consider a pair of nodes u, v where v currently lies to the southeast of u. Then when ACA considers aligning u and v it will only consider putting v east or south of u; it will not consider reversing their current ordering in either dimension.

In the same example, if you set aggressiveOrdering to true, then ACA will also consider putting v north and west of u.

In the exceptional case of a node v lying, say, precisely east of a node u despite not being constrained to that alignment, then ACA will consider placing v east, north, and south of u even with aggressiveOrdering set to false. (But it will consider west only with it set to true.)

◆ allAtOnce()

void dialect::ACALayout::allAtOnce ( bool b )

Say whether alignment choices should alternate with stress minimisation steps.

The default value of allAtOnce is false. In this case, after each new alignment is chosen, stress is again minimised before choosing the next one.

If you set allAtOnce to true, then all the alignments will be chosen based on the initial layout, and then they will all be applied at once.

◆ applyOAsAllOrNothing()

bool dialect::ACALayout::applyOAsAllOrNothing ( OrderedAlignments oas )

Creates all the requested alignments, or none if any is infeasible.

Returns: true if all alignments are successfully applied, else false.

Referenced by dialect::OrthoHubLayout::layout().

Here is the caller graph for this function:

◆ createAlignments()

void dialect::ACALayout::createAlignments ( void )

Creates alignments.

This is the main functionality of ACA. This function should be called on an existing layout in order to greedily align edges until any further alignments would create edge overlaps.

If the graph does not have an initial layout already, then the 'layout' function may be called instead.

Referenced by dialect::doHOLA(), and layout().

Here is the caller graph for this function:

◆ createOneAlignment()

bool dialect::ACALayout::createOneAlignment ( void )

Creates one alignment.

Call this function instead of createAlignments in order to create just one alignment and then stop. The return value is true if and only if a new alignment was actually created.

Thus, repeatedly calling this function until it returns false achieves the exact same result as simply calling createAlignments.

◆ edgeIsAligned()

bool dialect::ACALayout::edgeIsAligned ( int j ) const

Check whether an edge is aligned.

Pass the index of the edge. The returned boolean says whether ACA aligned this edge.

◆ favourLongEdges()

void dialect::ACALayout::favourLongEdges ( bool b )

Prefer long edges instead of ones that are close to aligned.

This defaults to 'false', in which case ACA prefers to align edges that are almost aligned already. When set to 'true' it will instead choose the longest edges first.

◆ ignoreEdges()

void dialect::ACALayout::ignoreEdges ( std::vector< bool > ignore )

Specify that certain edges are never to be aligned.

The number of booleans must equal the number of edges in the graph. Entry j should be 'true' if you want edge j to be ignored (never aligned); 'false' otherwise.

◆ ignoreNodesForOPWithOffsets()

void dialect::ACALayout::ignoreNodesForOPWithOffsets ( std::vector< bool > ignore )

Say that certain nodes may be crossed by edges.

When using the ACAOPWITHOFFSETS option, a potential alignment will /not/ be marked as creating an edge-node overlap if for all indices i such that the alignment would make an edge overlap node i, the ith entry in the vector passed to this function is true.

◆ layout()

void dialect::ACALayout::layout ( void )

Do an initial stress-minimising layout, and then create alignments.

This is a convenience function which first does a constrained force-directed layout of the given graph, and then calls the 'createAlignments' function.

References createAlignments(), and layoutWithCurrentConstraints().

Here is the call graph for this function:

◆ postponeLeaves()

void dialect::ACALayout::postponeLeaves ( bool b )

Say whether alignment of leaf edges should be saved for last.

The default value is true.

◆ setAlignmentOffsetsForCompassDirection()

void dialect::ACALayout::setAlignmentOffsetsForCompassDirection	(	ACASepFlag	sf,
		EdgeOffsets	offsets
	)

Say how to offset nodes when edges are aligned in a certain direction.

The number of offsets must equal the number of edges in the graph. For any edge e=(s,t), let o=(ds,dt) be the corresponding offset. Then if ACA aligns edge e so that sf is the separation from s to t, then s will be offset from the alignment guideline by ds, and t by dt.

If you do not set any offsets then offsets of zero will be used.

◆ setAllowedDirections()

void dialect::ACALayout::setAllowedDirections ( ACASepFlags seps )

Say which separations are allowed for the source and target of each edge.

The number of separation flags must equal the number of edges in the graph. For any edge e=(s,t), let f be the corresponding flag. Then when ACA considers aligning edge e it will only consider the directions whose bits are set in f.

If you do not set allowed separations then all are considered to be allowed.

Note that if aggressiveOrdering is false then even if you set ACAALLSEP as allowed direction, still only the two "natural" directions will be tried. (See aggressiveOrdering().)

◆ setAvoidNodeOverlaps()

void dialect::ACALayout::setAvoidNodeOverlaps ( bool avoidOverlaps )

Specifies whether non-overlap constraints should be automatically generated between all nodes.

Parameters

[in] avoidOverlaps New boolean value for this option.

◆ setNodeAliases()

void dialect::ACALayout::setNodeAliases ( std::map< int, int > aliases )

Set certain nodes to be used in place of others.

Pass a map m. Then for each computation that involves a node u, we will check whether u is a key in m, and if so will use m(u) instead.

◆ updateSepMatrix()

void dialect::ACALayout::updateSepMatrix	(	SepMatrix &	M,
		const std::map< size_t, id_type > &	ix2id
	)

Update a given SepMatrix with all the ordered alignment constraints generated by this ACA layout.

Parameters

[in]	M	the SepMatrix to be updated.
[in]	ix2id	a mapping from Rectangle indices back to the IDs of the Nodes they represent.

References dialect::EAST.

◆ useNonLeafDegree()

void dialect::ACALayout::useNonLeafDegree ( bool b )

Say whether leaves should be counted when computing node degrees.

The default value is true.

This setting matters only if addBendPointPenalty is set to true. In that case, if useNonLeafDegree is also true then the nodes identified as potential bend points will be those having exactly 2 /non-leaf/ neighbours.

When there is both leaf penalty and bend point penalty (see above), then bend points will be created before leaf edges are aligned. This can be reversed by altering the BP_PENALTY and LEAF_PENALTY constants.

The documentation for this class was generated from the following files:

libdialect/aca.h
libdialect/aca.cpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ACALayout() [1/2]

◆ ACALayout() [2/2]

Member Function Documentation

◆ addBendPointPenalty()

◆ aggressiveOrdering()

◆ allAtOnce()

◆ applyOAsAllOrNothing()

◆ createAlignments()

◆ createOneAlignment()

◆ edgeIsAligned()

◆ favourLongEdges()

◆ ignoreEdges()

◆ ignoreNodesForOPWithOffsets()

◆ layout()

◆ postponeLeaves()

◆ setAlignmentOffsetsForCompassDirection()

◆ setAllowedDirections()

◆ setAvoidNodeOverlaps()

◆ setNodeAliases()

◆ updateSepMatrix()

◆ useNonLeafDegree()