Improve performance of SugiyamaAlgorithm

[JulianBissekkou]

Thanks again for taking the time to hop on a call with me and discuss potential performance fixes.
I reduced the iterations in nodeOrdering to 3 and then I did some research to see what else takes the most time.

As you can see crossingb and assignX takes most of the time.
I checked the graphview android lib to see if they made any performance adjustments, but there are none.

I tried to optimize both methods but I don't have enough knowledge about the algorithm so I need some help here.
@nabil6391 It would be a help if you could explain what the implementation exactly does and how a fix could look like so I can help.

[JulianBissekkou]

I found some performance optimizations in this paper. Might be interesting.

https://jgaa.info/accepted/2005/EiglspergerSiebenhallerKaufmann2005.9.3.pdf

And it looks like this project implemented this:
https://github.com/tomnelson/jungrapht-visualization

[nabil6391]

Thanks for the PR, I will publish to pub.dev soon.

I have also started looking into the New Algorithm you shared.

[JulianBissekkou]

Did you make any progress? :)

[nabil6391]

I am about 30% with the new EiglspergerAlgorithm

[nabil6391]

@JulianBissekkou Highly suggest you to update to 1.1.0. There are some major improvements to Sugiyama Algorithm. Do have a look

[JulianBissekkou]

Thanks! Improvements are looking really good, but we saw some nodes that are overlapping horizontally.

I exported the tree as JSON so you can easily reproduce this issue.
https://gist.github.com/JulianBissekkou/9e2a6a7dccb437b0e781352f7665b99d

[nabil6391]

That sucks. Need to improve my test cases, thanks for exporting this . Will try in the week end

[JulianBissekkou]

Thanks a lot. If you need any help then let me know :)

[JulianBissekkou]

Any luck with the bugfix? @nabil6391

[nabil6391]

@JulianBissekkou try out 1.1.1. Should be ok now but let me know if there are any other issues or not

[JulianBissekkou]

@nabil6391 I checked out 1.1.1 and I found some overlapping issues. I also added some tests that are failing so you have some data to work with.
You can find that data in my PR #63

If you need some more details let me know. I can also improve the test suite to include more examples and details.

[nabil6391]

Thanks for the tests, I had a brief look. looks like the issues is not with the new code as the tests failed for Old Sugiyama Algorithm as well. I will have to dig deeper to see how to fix that.

[JulianBissekkou]

I went through the sources of the java lib and found no change that would be a potential bugfix. Maybe you can take a look as well.
The java lib has a few issues about overlapping that are still open. I send an E-Mail to the maintainers of that lib. Let's see if they fix this issue then we can add the fix to your lib as well.

It would still be good if you can analyze the problem because I don't know if and when they are going to respond.

[JulianBissekkou]

@nabil6391
Did you have the time to check into that issue?

[nabil6391]

I did sat one day, found the place which should have taken into account the width (placeBlockWidth) but could not solve it yet

[CicadaCinema]

Today I had a go at tackling the issue of overlapping nodes, with almost no success.

Minimal test cases

I produced two minimal test cases - small graphs which result in overlapping nodes. Substitute these in place of this object.

This graph is disconnected:

var json = {
  'edges': [
    {'from': '1', 'to': '2'},
    {'from': '1', 'to': '3'},
    {'from': '4', 'to': '7'},
    {'from': '4', 'to': '5'},
    {'from': '9', 'to': '6'},
    {'from': '6', 'to': '4'},
    {'from': '8', 'to': '1'},
  ],
};

This graph is connected:

var json = {
  'edges': [
    {'from': '1', 'to': '2'},
    {'from': '1', 'to': '3'},
    {'from': '7', 'to': '8'},
    {'from': '7', 'to': '9'},
    {'from': '10', 'to': '6'},
    {'from': '6', 'to': '7'},
    {'from': '5', 'to': '1'},
    {'from': '5', 'to': '10'},
    {'from': '4', 'to': '1'},
  ],
};

I made the nodes translucent to be able to see overlaps more clearly:

 Widget rectangleWidget(String? a, Node node) {
   return Container(
-    color: Colors.amber,
     child: InkWell(
       onTap: () {
         print('clicked');
       },
       child: Container(
           padding: EdgeInsets.all(16),
           decoration: BoxDecoration(
             borderRadius: BorderRadius.circular(4),
             boxShadow: [
-              BoxShadow(color: Colors.blue[100]!, spreadRadius: 1),
+              BoxShadow(color: Colors.blue[500]!.withOpacity(0.3), spreadRadius: 1),
             ],
           ),
           child: Text('${a}')),
     ),
   );
 }

Debugging

It was difficult to debug this issue, and I found it difficult to make any sense of the data structures in the SugiyamaAlgorithm class. Without any evidence I claim that the bug might lie in one of these two methods:

graphview/lib/layered/SugiyamaAlgorithm.dart

Line 364 in f1ac307

void coordinateAssignment() {

graphview/lib/layered/SugiyamaAlgorithm.dart

Line 374 in f1ac307

void assignX() {

By the time they are populated, the following data structures...

graphview/lib/layered/SugiyamaAlgorithm.dart

Lines 375 to 384 in f1ac307

	// each node points to the root of the block.;
	final root = <Map<Node, Node>>[];
	// each node points to its aligned neighbor in the layer below.;
	final align = <Map<Node, Node>>[];
	final sink = <Map<Node, Node>>[];
	final x = <Map<Node, double>>[];
	// minimal separation between the roots of different classes.;
	final shift = <Map<Node, double>>[];
	// the width of each block (max width of node in block);
	final blockWidth = <Map<Node?, double>>[];

...are arrays of 4 elements, which might correspond to the 'alignment' of nodes in 4 directions. Here...

graphview/lib/layered/SugiyamaAlgorithm.dart

Line 408 in f1ac307

final k = 2 * downward + leftToRight;

... k ranges between 0 and 3 (inclusive) due to the two nested loops.

I claim that a logic error could arise at index 3 (k=3).

I experimented with making the following modification to this block of code:

graphview/lib/layered/SugiyamaAlgorithm.dart

Lines 490 to 495 in f1ac307

	for (var i = 0; i < 4; i++) {
	values[i] = x[i][n]!;
	}
	values.sort();
	var average = (values[1] + values[2]) * 0.5;
	coordinates[n] = average;

  for (var i = 0; i < 4; i++) {
    values[i] = x[i][n]!;
  }
  values.sort();
  var average = (values[1] + values[2]) * 0.5;
- coordinates[n] = average;
+ if (values[1] != x[3][n]! && values[2] != x[3][n]!) {
+   coordinates[n] = average;
+ } else if (values[1] != x[3][n]!) {
+   coordinates[n] = values[1];
+ } else {
+   // here, values[2] != x[3][n]! is true
+   coordinates[n] = values[2];
+ }

It looks like this location in the algorithm is where the x coordinates of the nodes are set, and my logic above "avoids" x[3][n]! while attempting to retain the original behaviour if possible.

This change produces the following renderings of my test cases above:

This approach performs poorly for other examples, such as this one:

This modification fails the following tests:

Click to expand

PS C:\Users\Atom\Downloads\graphview> flutter test
00:02 +0: C:\Users\Atom\Downloads\graphview\test\buchheim_walker_algorithm_test.dart: Buchheim Graph Buchheim Node positions are correct for Top_Bottom
Timetaken 8
00:02 +1: C:\Users\Atom\Downloads\graphview\test\buchheim_walker_algorithm_test.dart: Buchheim Graph Buchheim Performance for 100 nodes to be less than 2.5s
Timetaken 21 12
00:02 +3: C:\Users\Atom\Downloads\graphview\test\graph_test.dart: Graph Node Hash Implementation is performant
Timetaken 5 Node{position: Offset(0.0, 0.0), key: [<5.6>], _size: Size(0.0, 0.0)}
00:02 +4: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama Graph Sugiyama Node positions are correct for Top_Bottom
Timetaken 37
00:02 +4 -1: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama Graph Sugiyama Node positions are correct for Top_Bottom [E]
  Expected: Offset:<Offset(1045.0, 815.0)>
    Actual: Offset:<Offset(2195.0, 815.0)>
  
  package:test_api                                    expect
  package:flutter_test/src/widget_tester.dart 460:16  expect
  test\sugiyama_algorithm_test.dart 112:7             main.<fn>.<fn>
  

To run this test again: C:\Software\flutter\bin\cache\dart-sdk\bin\dart.exe test C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart -p vm --plain-name 'Sugiyama Graph Sugiyama Node positions are correct for Top_Bottom'
00:02 +4 -1: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama Graph Sugiyama Node positions correct for LEFT_RIGHT
Timetaken 10
00:02 +4 -2: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama Graph Sugiyama Node positions correct for LEFT_RIGHT [E]
  Expected: Offset:<Offset(815.0, 745.0)>
    Actual: Offset:<Offset(815.0, 1595.0)>

  package:test_api                                    expect
  package:flutter_test/src/widget_tester.dart 460:16  expect
  test\sugiyama_algorithm_test.dart 142:7             main.<fn>.<fn>


To run this test again: C:\Software\flutter\bin\cache\dart-sdk\bin\dart.exe test C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart -p vm --plain-name 'Sugiyama Graph Sugiyama Node positions correct for LEFT_RIGHT'
00:02 +6 -3: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama Graph Sugiyama for a cyclic graph [E]
  Expected: Offset:<Offset(10.0, 17.5)>
    Actual: Offset:<Offset(10.0, 10.0)>

  package:test_api                                    expect
  package:flutter_test/src/widget_tester.dart 460:16  expect
  test\sugiyama_algorithm_test.dart 239:7             main.<fn>.<fn>


To run this test again: C:\Software\flutter\bin\cache\dart-sdk\bin\dart.exe test C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart -p vm --plain-name 'Sugiyama Graph Sugiyama for a cyclic graph'
00:02 +6 -3: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama for a complex graph with 140 nodes
Timetaken 37 140
00:02 +6 -4: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama for a complex graph with 140 nodes [E]
  Expected: Offset:<Offset(10.0, 397.5)>
    Actual: Offset:<Offset(10.0, 210.0)>

  package:test_api                                    expect
  package:flutter_test/src/widget_tester.dart 460:16  expect
  test\sugiyama_algorithm_test.dart 276:5             main.<fn>


To run this test again: C:\Software\flutter\bin\cache\dart-sdk\bin\dart.exe test C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart -p vm --plain-name 'Sugiyama for a complex graph with 140 nodes'
00:05 +7 -4: C:\Users\Atom\Downloads\graphview\test\sugiyama_algorithm_test.dart: Sugiyama Performance for 100 nodes to be less than 2.5s
Timetaken 2013 200
00:05 +8 -4: Some tests failed.

The good news is that all these look like golden tests, and that the tests for overlapping actually pass. The bad news is that the graphs resulting from this algorithm are probably wildly space-inefficient (like the example above).

Conclusion

This is all I know. Oh well, I can't be bothered to work on this issue any longer, maybe someone else can pick up the torch. It looks like this is the most fully-fledged graph-drawing package on pub.dev, which is a shame because it was very difficult for me to work with something which is essentially a twice-translated Java library.

[CicadaCinema]

Pinging @nabil6391 @JulianBissekkou

[nabil6391]

Try out 1.2.0 , fixed overlapping nodes and the tests are not failing as well