Hi guy,
If i remember, this algorithm check for each edge if there is a circuit. It
returns for each edge the smallest circuit.
It seems to have a bug somewhere, because in your result, the value (1,5)
should appaers only one time, and the value (1,3,2) must be present.
About the value (1,5,2,3), this algorithm will never return it because it
is a bigger circuit.
Cheers,
Jannik
2014-11-27 22:23 GMT+01:00 Alexandre Bergel <alexandre.bergel(a)me.com>om>:
Hello,
The truth is that I am not familiar with this code. I can hardly provide
any justification about the result. I advice you to subscribe to the Moose
mailing list (
http://moosetechnology.org)
Alexandre
Begin forwarded message:
*From: *Bledar Aga <bledar.aga(a)students.unibe.ch>
*Subject: **MalCyclesCoverage*
*Date: *November 27, 2014 at 1:09:45 PM GMT-4
*To: *abergel(a)dcc.uchile.cl, alexandre.bergel(a)me.com
Dear Prof. Bergel,
I’m a master student at Bern University and I am working for my master
thesis about dependency cycles.
I am using your implementation of Tarjan algorithm MalCyclesCoverage
(Moose) for detecting the cycles. I tried to understand your implementation
but it is a bit hard to follow the execution and I can’t find the
documentation.
I want kindly to ask: Is there any reason that given a certain input it
does not provide all the circuits of a strongly connected components?
Removing the dependencies (edges) from a cyclic graph at the end I obtain
the acyclic graph and this is what I want, but I need to understand how the
single circuits are obtained.
Example:
Considering the following input:
|tarjan|
tarjan := MalCyclesCoverage new.
tarjan nodes: #(1 2 3 4 5).
tarjan edges: #((1 3) (3 1) (1 5) (5 1) (4 1) (2 1) (2 5) (5 2) (2 3) (3
2) (3 4) (5 4)) from:#first to:#second.
tarjan run.
self halt.
It returns the following output: ((1 3 4)(1 5) (1 5)(2 3) (1 3) (1 5 4)
(2 5)). In practice there are more circuits, example (1 3 2) (1 5 2 3)...?
To have a clear idea of the input I attached the graph.
Thank you very much in advance for your time.
Best regards,
Bledar Aga.
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel
http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
_______________________________________________
Moose-dev mailing list
Moose-dev(a)iam.unibe.ch
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
--
~~Jannik Laval~~
École des Mines de Douai
Enseignant-chercheur
http://www.jannik-laval.eu
http://www.phratch.com
http://www.approchealpes.info
http://car.mines-douai.fr/