Sugiyama Layout reseting width/height of nodes in GraphAttributes

[acceptable-security]

I've recently run into an issue when trying to use ogdf::SugiyamaLayout for laying out a directed graph. The layout code in question is (where ogdfGraph is an ogdf::Graph and graphAttr is a ogdf::GraphAttributes with nodeGraphics, edgeGraphics, nodeStyle, and, edgeStyle enabled):

		for ( const auto& node : ogdfGraph.nodes ) {
			std::cout << "Found before node " << graphAttr.width(node) << "x" << graphAttr.height(node) << std::endl;
		}

		ogdf::SugiyamaLayout SL;
		SL.setRanking(new ogdf::OptimalRanking);
		SL.setCrossMin(new ogdf::MedianHeuristic);

		ogdf::OptimalHierarchyLayout *ohl = new ogdf::OptimalHierarchyLayout;
		ohl->layerDistance(30.0);
		ohl->nodeDistance(40.0);
		ohl->weightBalancing(0.8);
		SL.setLayout(ohl);

		SL.call(graphAttr);

		for ( const auto& node : ogdfGraph.nodes ) {
			std::cout << "Found after node " << graphAttr.width(node) << "x" << graphAttr.height(node) << std::endl;
		}

The output of this code is

Found before node 660x232
Found before node 625x154
Found before node 191x141
Found before node 681x154
Found before node 275x141
Found before node 681x167
Found before node 625x154
Found before node 275x141
Found before node 289x141
Found before node 632x167
Found before node 674x167
Found before node 660x167
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20
Found after node 20x20

I didn't see any documentation that SugiyamaLayout would have such behavior, and I didn't see in the code any indication that that should be that case. Am I misusing/misunderstanding the API somehow and causing this behavior, or is it a bug in OGDF itself? For reference, I'm using:

• Latest commit on master (commit acfb68a)
• Apple clang version 11.0.0 (clang-1100.0.33.16)

[milsen]

Thank you for your detailed bug report.
This is in fact a known bug of HierarchyLayoutModule. To quote the relevant issue in the development repository:

"In HierarchyLayoutModule::call(...), which probably every subclass calls in some way or another, the node height, width and shape are overwritten with default values before the subclass implementation is called, although their values are not altered by any subclass of that interface but only read."

We have a fix for this ready, it will be included in the next release. Here's a patch if you need one (copy it to a file named file.patch and use it with git am < file.patch):

From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
From: Max Ilsen <milsen@users.noreply.github.com>
Date: Wed, 11 Nov 2020 11:11:57 +0100
Subject: [PATCH] Fix HierarchyLayoutModule resetting attributes

---
 include/ogdf/layered/HierarchyLayoutModule.h | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/include/ogdf/layered/HierarchyLayoutModule.h b/include/ogdf/layered/HierarchyLayoutModule.h
index 0acde9974..3da9bdbe3 100644
--- a/include/ogdf/layered/HierarchyLayoutModule.h
+++ b/include/ogdf/layered/HierarchyLayoutModule.h
@@ -58,6 +58,20 @@ public:
 	 */
 	void call(const HierarchyLevelsBase &levels, GraphAttributes &GA) {
 		GraphAttributes AGC(levels.hierarchy());
+		// Copy over relevant nodeGraphics attributes that may be used by doCall or need to be preserved
+		// edgeGraphics' bend points need to be cleared and aren't copied over
+		if (GA.has(GraphAttributes::nodeGraphics)) {
+			const GraphCopy &GC = dynamic_cast<const GraphCopy&>(AGC.constGraph());
+			for (node vOrig: GA.constGraph().nodes)
+			{
+				node v = GC.copy(vOrig);
+				if (v != nullptr) {
+					AGC.height(v) = GA.height(vOrig);
+					AGC.width(v) = GA.width(vOrig);
+					AGC.shape(v) = GA.shape(vOrig);
+				}
+			}
+		}
 		doCall(levels,AGC);
 		AGC.transferToOriginal(GA);
 	}
-- 
2.29.2

[acceptable-security]

Awesome! That patch works like a charm, thank you so much for your help on this.

[andraantariksa]

Thank you for the solution, I previously using snap-2018-03-28 and got not problem. This issue appears when I'm using the Catalpa release.

[csware]

Is there a reason why this patch is not committed to master?

I wasted 4 hours of debugging until I found this issue for which a fix is available for more than one year...

[milsen]

Is there a reason why this patch is not committed to master?

I wasted 4 hours of debugging until I found this issue for which a fix is available for more than one year...

There is a private OGDF repository that is used to work on new scientific ideas. Once the scientific results are published, the respective code can also be made public, including all bug patches that were added in the meantime.

To that end, we normally have a somewhat "regular" release of the OGDF. However, nowadays, close to nobody is actively working on the OGDF anymore (even I just do this on the side when I have some spare minutes as my financing is not related to it anymore). That's why releases take ages.

However, I'll try to initiate a new release soon. It would definitely be helpful. Having a rolling release would be even better, but let's not get ahead of ourselves...

[csware]

Why not use another release model:

• Maintain all bugfixes directly on master and keep it on GitHub
• Develop new scintific ideas on a private repository and when finished merge to master or rebase (maybe with a sqaush commit) onto master and push to GitHub

Git is such a powerful tool, why not make use of it?

[milsen]

Why not use another release model: ...

Yes, that's what I mean by "rolling release". It's definitely something I'd want to have in the future–the repos would probably be on GitLab then because that's where the current development repo is, but the idea is the same.
I think the current release model was originally used because of licensing concerns (some parts of the code were not allowed to ever be published publicly). However, to my knowledge those concerns are not relevant anymore. Now transitioning to the new release model should just require some thought and time (and convincing of the boss). Which, however, is also kind of a problem because of our aforementioned limited capacities. But I'll try my best.