Implements a constrained force-directed layout algorithm. More...

#include <cola.h>

Collaboration diagram for cola::ConstrainedFDLayout:

Public Member Functions
	ConstrainedFDLayout (const vpsc::Rectangles &rs, const std::vector< cola::Edge > &es, const double idealLength, const EdgeLengths &eLengths=StandardEdgeLengths, TestConvergence doneTest=nullptr, PreIteration preIteration=nullptr)
	Constructs a constrained force-directed layout instance. More...

void	run (bool x=true, bool y=true)
	Implements the main layout loop, taking descent steps until stress is no-longer significantly reduced. More...

void	runOnce (bool x=true, bool y=true)
	Same as run(), but only applies one iteration. More...

void	setConstraints (const cola::CompoundConstraints &ccs)
	Specify a set of compound constraints to apply to the layout. More...

void	setAvoidNodeOverlaps (bool avoidOverlaps, ListOfNodeIndexes listOfNodeGroups=ListOfNodeIndexes())
	Specifies whether non-overlap constraints should be automatically generated between all nodes, as well as any exemptions to this. More...

void	setTopology (TopologyAddonInterface *topology)
	Set an addon for doing topology preserving layout. More...

void	setClusterHierarchy (RootCluster *hierarchy)
	Specifies an optional hierarchy for clustering nodes. More...

void	setUnsatisfiableConstraintInfo (UnsatisfiableConstraintInfos unsatisfiableX, UnsatisfiableConstraintInfos unsatisfiableY)
	Register to receive information about unsatisfiable constraints. More...

void	makeFeasible (double xBorder=1, double yBorder=1)
	Finds a feasible starting position for nodes that satisfies the given constraints. More...

void	freeAssociatedObjects (void)
	A convenience method that can be called from Java to free the memory of nodes (Rectangles), CompoundConstraints, etc. More...

void	outputInstanceToSVG (std::string filename=std::string())
	Generates an SVG file containing debug output and code that can be used to regenerate the instance. More...

void	setUseNeighbourStress (bool useNeighbourStress)
	Specifies whether neighbour stress should be used. More...

std::vector< double >	readLinearD (void)
	Retrieve a copy of the "D matrix" computed by the computePathLengths method, linearised as a vector. More...

std::vector< unsigned >	readLinearG (void)
	Retrieve a copy of the "G matrix" computed by the computePathLengths method, linearised as a vector. More...

Detailed Description

Implements a constrained force-directed layout algorithm.

This method is based on a non-linear gradient projection technique. Conceptually it's similar to a force directed method like Fruchterman-Reingold—but using a more principled goal function and optimisation techniques.

Constructor & Destructor Documentation

◆ ConstrainedFDLayout()

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

Constructs a constrained force-directed layout instance.

If an empty edges (es) vector is passed to the constructor, then constraint satisfaction will be performed, but no force-directed layout. In this case, idealLength and eLengths have no effect.

Conversely, if no constraints or clusters are specified and no overlap prevention is enabled, but edge info is given, then pure force-directed layout will be performed.

Parameters

[in]	rs	Bounding boxes of nodes at their initial positions.
[in]	es	Simple pair edges, giving indices of the start and end nodes in rs.
[in]	idealLength	A scalar modifier of ideal edge lengths in eLengths or of 1 if no ideal lengths are specified.
[in]	eLengths	Individual ideal lengths for edges. The actual ideal length used for the ith edge is idealLength*eLengths[i], or if eLengths is nullptr a then just idealLength is used (i.e., eLengths[i] is assumed to be 1).
[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 called before each iteration (optional).

Member Function Documentation

◆ freeAssociatedObjects()

void cola::ConstrainedFDLayout::freeAssociatedObjects ( void )

A convenience method that can be called from Java to free the memory of nodes (Rectangles), CompoundConstraints, etc.

This assumes that the ConstrainedFDLayout instance takes ownership of all the objects passed to it.

This is useful because in SWIG we have problems with Java wrapper classes going out of scope and causing objects like Rectanges to sometimes be freed when the layout instance still needs them. For this reason we prevent the Java wrappers from deleting the internal C++ instances, and let them be cleaned up later via this method.

◆ makeFeasible()

void cola::ConstrainedFDLayout::makeFeasible	(	double	xBorder = `1`,
		double	yBorder = `1`
	)

Finds a feasible starting position for nodes that satisfies the given constraints.

Starts with an initial position (x, y) for the nodes. This position is then iteratively updated with a greedy heuristic that tries adding additional constraints based on compound constraint priority to the satisfiable set, so as to satisfy as many of the placement constraints as possible. This includes automatically generated constraints for non-overlap and cluster containment.

Parameters

[in]	xBorder	Optional border width to add to left and right sides of rectangles. Defaults to 1.
[in]	yBorder	Optional border width to add to top and bottom sides of rectangles. Defaults to 1.

Note: This method doesn't do force-directed layout. All forces are ignored and it merely satisfies the constraints with minimal movement to nodes.

References vpsc::IncSolver::addConstraint(), cola::generateVariables(), and vpsc::IncSolver::satisfy().

Here is the call graph for this function:

◆ outputInstanceToSVG()

void cola::ConstrainedFDLayout::outputInstanceToSVG ( std::string filename = std::string() )

Generates an SVG file containing debug output and code that can be used to regenerate the instance.

This method can be called before or after run() or makeFeasible() have been called.

Parameters

[in] filename A string indicating the filename (without extension) for the output file. Defaults to "libcola-debug.svg" if no filename is given.

◆ readLinearD()

std::vector< double > cola::ConstrainedFDLayout::readLinearD ( void )

Retrieve a copy of the "D matrix" computed by the computePathLengths method, linearised as a vector.

This is especially useful for projects in SWIG target languages that want to do their own computations with stress.

D is the required euclidean distances between pairs of nodes based on the shortest paths between them (using m_idealEdgeLength*eLengths[edge] as the edge length, if eLengths array is provided otherwise just m_idealEdgeLength).

Returns: vector representing the D matrix.

◆ readLinearG()

std::vector< unsigned > cola::ConstrainedFDLayout::readLinearG ( void )

Retrieve a copy of the "G matrix" computed by the computePathLengths method, linearised as a vector.

This is especially useful for projects in SWIG target languages that want to do their own computations with stress.

G is a matrix of unsigned ints such that G[u][v]= 0 if there are no forces required between u and v (for example, if u and v are in unconnected components) 1 if attractive forces are required between u and v (i.e. if u and v are immediately connected by an edge and there is no topology route between u and v (for which an attractive force is computed elsewhere)) 2 if no attractive force is required between u and v but there is a connected path between them.

Returns: vector representing the G matrix.

◆ run()

void cola::ConstrainedFDLayout::run	(	bool	x = `true`,
		bool	y = `true`
	)

Implements the main layout loop, taking descent steps until stress is no-longer significantly reduced.

Parameters

[in]	x	If true, layout will be performed in x-dimension (default: true).
[in]	y	If true, layout will be performed in y-dimension (default: true).

Referenced by dialect::ACALayout::layoutWithCurrentConstraints().

Here is the caller graph for this function:

◆ runOnce()

void cola::ConstrainedFDLayout::runOnce	(	bool	x = `true`,
		bool	y = `true`
	)

Same as run(), but only applies one iteration.

This may be useful here it's too hard to implement a call-back (e.g., in java apps).

Parameters

[in]	x	If true, layout will be performed in x-dimension (default: true).
[in]	y	If true, layout will be performed in y-dimension (default: true).

◆ setAvoidNodeOverlaps()

void cola::ConstrainedFDLayout::setAvoidNodeOverlaps	(	bool	avoidOverlaps,
		ListOfNodeIndexes	listOfNodeGroups = `ListOfNodeIndexes()`
	)

Specifies whether non-overlap constraints should be automatically generated between all nodes, as well as any exemptions to this.

The optional second parameter indicates groups of nodes that should be exempt from having non-overlap constraints generated between each other. For example, you might want to do this for nodes representing ports, or the child nodes in a particular cluster.

Parameters

[in]	avoidOverlaps	New boolean value for this option.
[in]	listOfNodeGroups	A list of groups of node indexes which will not have non-overlap constraints generated between each other.

Referenced by dialect::ACALayout::layoutWithCurrentConstraints().

Here is the caller graph for this function:

◆ setClusterHierarchy()

void cola::ConstrainedFDLayout::setClusterHierarchy ( RootCluster * hierarchy )

inline

Specifies an optional hierarchy for clustering nodes.

Parameters

[in] hierarchy A pointer to a RootCluster object defining the the cluster hierarchy (optional).

Referenced by dialect::ACALayout::layoutWithCurrentConstraints().

Here is the caller graph for this function:

◆ setConstraints()

void cola::ConstrainedFDLayout::setConstraints ( const cola::CompoundConstraints & ccs )

Specify a set of compound constraints to apply to the layout.

Parameters

[in] ccs The compound constraints.

Referenced by dialect::ACALayout::layoutWithCurrentConstraints().

Here is the caller graph for this function:

◆ setTopology()

void cola::ConstrainedFDLayout::setTopology ( TopologyAddonInterface * topology )

Set an addon for doing topology preserving layout.

It is expected that you would use the topology::ColaTopologyAddon() from libtopology rather than write your own. This is done so that libcola does not have to depend on libtopology.

Parameters

[in] topology Instance of a class implementing the TopologyAddonInterface.

See also: topology::ColaTopologyAddon

◆ setUnsatisfiableConstraintInfo()

void cola::ConstrainedFDLayout::setUnsatisfiableConstraintInfo	(	UnsatisfiableConstraintInfos *	unsatisfiableX,
		UnsatisfiableConstraintInfos *	unsatisfiableY
	)

inline

Register to receive information about unsatisfiable constraints.

In the case of unsatisifiable constraints, the solver will drop unsatisfiable constraints of lowest priority. Information about these will be written to these lists after each iteration of constrained layout.

param[out] unsatisfiableX A pointer to a UnsatisfiableConstraintInfos object that will be used to record unsatisfiable constraints in the x-dimension. param[out] unsatisfiableY A pointer to a UnsatisfiableConstraintInfos object that will be used to record unsatisfiable constraints in the y-dimension.

Referenced by dialect::ACALayout::layoutWithCurrentConstraints().

Here is the caller graph for this function:

◆ setUseNeighbourStress()

void cola::ConstrainedFDLayout::setUseNeighbourStress ( bool useNeighbourStress )

Specifies whether neighbour stress should be used.

Under neighbour stress, only the terms representing neighbouring nodes contribute to the stress function. This can help to distribute nodes more evenly, eliminating long-range forces.

Default value is false.

Parameters

[in] useNeighbourStress New boolean value for this option.

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

libcola/cola.h
libcola/colafd.cpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ConstrainedFDLayout()

Member Function Documentation

◆ freeAssociatedObjects()

◆ makeFeasible()

◆ outputInstanceToSVG()

◆ readLinearD()

◆ readLinearG()

◆ run()

◆ runOnce()

◆ setAvoidNodeOverlaps()

◆ setClusterHierarchy()

◆ setConstraints()

◆ setTopology()

◆ setUnsatisfiableConstraintInfo()

◆ setUseNeighbourStress()