TreeLayout only handles TreeLayout::RootSelectionType::Source

[milsen]

In GitLab by @N-Coder on Mar 22, 2021, 10:44

TreeLayout claims to support three modes for finding the root of the tree to layout: the source, the sink or by coordinates (i.e. select the topmost node if orientation is topToBottom).
But actually, if you pass in any tree where the root is a sink and not a source, the algorithm fails because isArborescenceForest will return false:

void TreeLayout::call(GraphAttributes &AG)
{
	const Graph &tree = AG.constGraph();
	if(tree.numberOfNodes() == 0) return;

	OGDF_ASSERT(isArborescenceForest(tree));

For an example see also here (and note the flipped direction of the edges to the root in the second cell). The example can be fixed by calling G.reverseAllEdges(), but this kind of makes the RootSelectionType parameter superflous.

Additionally, I didn't find the requirement that the root needs to be the source for isArborescenceForest mentioned anywhere in documentation. The docs for isTree actually claim the opposite.

[milsen]

This could be fixed as follows:

• add and document new parameter pointAwayFromRoot = true for isArborescence and isArborescenceForest, this parameter should determine whether the arborescences are out-arborescences or in-arborescences (per default out-arborescences)
• change assertion to

#ifdef OGDF_DEBUG
if (m_selectRoot == RootSelectionType::Source) {
	OGDF_ASSERT(isArborescenceForest(tree, true)));
else if (m_selectRoot == RootSelectionType::Sink) {
	OGDF_ASSERT(isArborescenceForest(tree, false)));
} else {
	OGDF_ASSERT(isAcyclicUndirected(tree));
}
#endif

• check whether the actual root selection code works then