[R] cycle in a directed graph

[rex.dwyer at syngenta.com]

If the graph has n nodes and is represented by an adjacency matrix, you can square the matrix (log_2 n)+1 times.  Then you can multiply the matrix element-wise by its transpose.  The positive entries in the 7th row will tell you all nodes sharing a cycle with node 7.  This assumes all edge weights are positive.
Are you sure we're not doing your graph theory homework?  You asked about MSTs yesterday.

-----Original Message-----
From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On Behalf Of amir
Sent: Friday, February 11, 2011 10:11 AM
To: r-help at r-project.org
Subject: [R] cycle in a directed graph

Hi,

I have a directed graph and wants to find is there any cycle in it? If
it is, which nodes or edges are in the cycle.
Is there any way to find the cycle in a directed graph in R?

Regards,
Amir

______________________________________________
R-help at r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.




message may contain confidential information. If you are not the designated recipient, please notify the sender immediately, and delete the original and any copies. Any use of the message by you is prohibited.