search

LearnLib / automatalib

A free, open-source Java library for modeling automata, graphs, and transition systems
http://automatalib.net
Apache License 2.0
92 stars 34 forks source link

Fixing issue #21 #22

Closed mmuesly closed 6 years ago

mmuesly commented 6 years ago

I found an error in the strong component tracing while debugging another project.

So, I suggest the following fix and added a few more examples, ensuring that the fix is working.

mmuesly commented 6 years ago

It seems like travis is checking the source code using pmd, but the codebase is not completely in shape for pmd checks. I fixed the util subproject as this is the area where my changes reside, but it seems like I would have to fix all automata lib modules to make pmd pass in the travis ci build. What do you recommend for solving the build errors?

mtf90 commented 6 years ago

It seems, you directly invoked the PMD maven-plugin from the CLI (which uses some default configuration). The Automatalib build process uses a specific configuration (and exclusions) file. To replicate what Travis does, you can invoke mvn clean install -Pcode-analysis (+ ,bundles for javadoc) in the util module.

From what I saw, after reverting 6cba2a5, it was mostly just formatting stuff. If you don't mind, you can grant me push access and I can look into this.

Also, I have to think about your changes to the SCCListener interface. Previously, when finding an SCC, you would receive all nodes at once and immediately know how many nodes (Collection.size()) a component contains. In your version, you would (at the end) receive for every node its component id (=lowLink?) but can't tell, when a component is full/finished until the n-th invocation. I think, the first version may be more convenient for users who want to use a custom listener (cf. SCCs#findSCCs). I'll probably look into the algorithm myself for this. But you already did the majority of the work by writing test cases and providing a working implementation, so thank you for that already :+1:.

mmuesly commented 6 years ago

I granted you push access. Feel free, to adapt the PR.

You are right about the SCCListener change. TheAlgorithm in the version as proposed in Tarjan's paper, needs a fine grained control about backtracking during DFS. Up to my understanding this is currently not supported sufficient well by the graph traversal infrastructure to maintain the old SCCListener interface. But I am open for discussions. Thanks for mentioning the -Pcode-analysis flag.

mmuesly commented 6 years ago

Thank you for locking into this and fixing the algorithm!