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.