Closed JulianBissekkou closed 1 year ago
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
Thanks for the PR, I will publish to pub.dev soon.
I have also started looking into the New Algorithm you shared.
Did you make any progress? :)
I am about 30% with the new EiglspergerAlgorithm
@JulianBissekkou Highly suggest you to update to 1.1.0. There are some major improvements to Sugiyama Algorithm. Do have a look
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
That sucks. Need to improve my test cases, thanks for exporting this . Will try in the week end
Thanks a lot. If you need any help then let me know :)
Any luck with the bugfix? @nabil6391
@JulianBissekkou try out 1.1.1. Should be ok now but let me know if there are any other issues or not
@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.
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.
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.
@nabil6391 Did you have the time to check into that issue?
I did sat one day, found the place which should have taken into account the width (placeBlockWidth) but could not solve it yet
Today I had a go at tackling the issue of overlapping nodes, with almost no success.
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}')),
),
);
}
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:
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).
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.
Pinging @nabil6391 @JulianBissekkou
Try out 1.2.0 , fixed overlapping nodes and the tests are not failing as well
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
andassignX
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.