Smalltalk › Frameworks & Tools › Moose

Fwd: MalCyclesCoverage

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

6 messages Options

abergel

Fwd: MalCyclesCoverage

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 <[hidden email]>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4
To: [hidden email], [hidden email]

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
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

jannik laval

Re: Fwd: MalCyclesCoverage

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 <[hidden email]>:

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 <[hidden email]>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4
To: [hidden email], [hidden email]

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
[hidden email]
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/

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

demarey

Re: Fwd: MalCyclesCoverage

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 <[hidden email]>:
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 <[hidden email]>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4
To: [hidden email], [hidden email]

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
[hidden email]
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/

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

smime.p7s (5K) Download Attachment

Bledar Aga

Re: MalCyclesCoverage

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.

Cheers,

Bledar.

On 28 Nov 2014, at 09:26, Christophe Demarey <[hidden email]> 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 <[hidden email]>:
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 <[hidden email]>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4
To: [hidden email], [hidden email]

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
[hidden email]
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/
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

jannik laval

Re: MalCyclesCoverage

Hi,

2014-11-28 11:52 GMT+01:00 Bledar Aga <[hidden email]>:

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 <[hidden email]> 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 <[hidden email]>:
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 <[hidden email]>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4
To: [hidden email], [hidden email]

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
[hidden email]
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/
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
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/

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

Bledar Aga

Re: MalCyclesCoverage

Hi,

Good explanation.

Thank you very much.

Cheers,

Bledar.

On 28 Nov 2014, at 13:30, jannik laval <[hidden email]> wrote:

Hi,

2014-11-28 11:52 GMT+01:00 Bledar Aga <[hidden email]>:
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 <[hidden email]> 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 <[hidden email]>:
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 <[hidden email]>
Subject: MalCyclesCoverage
Date: November 27, 2014 at 1:09:45 PM GMT-4
To: [hidden email], [hidden email]

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
[hidden email]
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/
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
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/
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev