search

graphstream / gs-core

Graphstream core
http://graphstream-project.org/
Other
402 stars 109 forks source link

org.graphstream.util.GraphDiff events order bug #186

Closed hhromic closed 6 years ago

hhromic commented 8 years ago

Hello,

First of all, thanks a lot for this wonderful dynamic graphs library. My research is strongly focused on longitudinal networks and after being very frustrated by the lack of decent software built around this type of graphs, yours is by far the best implemented and designed. Kudos for that.

I discovered a small bug with the org.graphstream.util.GraphDiff utility class. The order in which the changed events are computed does matter if you use the apply() or reverse() methods and the destination graph is using strict checking. The ordering problem exists because of one assumption being ignored: if you delete a node from the graph, the edges associated with it are also automatically deleted. This means that if you have the following changes to apply:

dn "A" de "AB"

The apply() method throws an exception with a strict-enabled graph because the edge "AB" is tried to be deleted after it no longer exists because of the automatic underlying deletion after we removed the node "A". To fix this, it's just a matter of re-ordering the events before applying them. In this case the right order should have been:

de "AB" dn "A"

I fixed the order in which the changed events are computed in the GraphDiff class constructor so the aforementioned methods don't fail to execute, no matter if the target graph is in strict mode or not. I'm attaching the patch here for you to apply on the next GraphStream version.

Cheers! Hugo.

graphdiff-events-order.patch.txt

hhromic commented 6 years ago

Didn't realise this was applied, thanks! closing now.