Hi,

2014-11-28 11:52 GMT+01:00 Bledar Aga <bledar.aga@students.unibe.ch>:
Hello,

Thank you for your answers.

Good to know, I’m using it for the same scope, I can compare with my tool.

I missed a value it’s not 1-5 but 1-5-2. Still I don’t get want do you mean with smallest circuit, and what is the purpose to return the smallest one? Considering the node 1 it returns the circuit 1-5 but also 1-5-2.

Ok, if it is 1-5-2, the algorithm is ok.
As I explained, the algorithm is not based on nodes, but on edges.

It means that for the edge 1-5, it find the circuit 1-5.
For the edge 2-1, it find the circuit 1-5-2. This is why it return both.

But, for the edge 2-1, it could return 1-3-2 too. The algorithm returns only one value, the first value it find.

Jannik

 

Cheers,
Bledar. 
  

On 28 Nov 2014, at 09:26, Christophe Demarey <christophe.demarey@inria.fr> wrote:

just to let you know, there is also this tool available for Pharo 4: http://www.baptistequide.fr/packagedependencies.php
It also uses the Tarjan algorithm

Christophe.

Le 28 nov. 2014 à 09:20, jannik laval a écrit :

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@me.com>:
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@students.unibe.ch>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4

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.



<IMG_2837.jpeg>

-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.




_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch
https://www.iam.unibe.ch/mailman/listinfo/moose-dev




-- 
_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch
https://www.iam.unibe.ch/mailman/listinfo/moose-dev


_______________________________________________
Moose-dev mailing list
Moose-dev@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/