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

Bug in the strongly connected component algorithm #21

Closed mmuesly closed 6 years ago

mmuesly commented 6 years ago

Due to incorrect backtracking on the stack, wrong components are put together using TarjanSCCVisitor.

The initial bug triggering example was the following graph:

nodes: a,b,c,d,e

edges: a -> b b -> c b -> e c -> d d -> b

I expected the following three sccs: {a}, {b,c,d} {e}, but got {a}, {b, e}, {c, d}.

mmuesly commented 6 years ago

I suggest pr #22 as solution.

mtf90 commented 6 years ago

PR #22 merged