Improve performance of `SugiyamaAlgorithm` about graphview HOT 18 CLOSED

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

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

from graphview.

I am about 30% with the new EiglspergerAlgorithm

from graphview.

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

from graphview.

Any luck with the bugfix? @nabil6391

from graphview.

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.

from graphview.

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

from graphview.

Did you make any progress? :)

from graphview.

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

from graphview.

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

from graphview.

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

from graphview.

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

from graphview.

@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.

from graphview.

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.

from graphview.

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

from graphview.

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

from graphview.

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:

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

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

... 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:

  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:

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.

from graphview.

Pinging @nabil6391 @JulianBissekkou

from graphview.

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

from graphview.