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-boun...@r-project.org [mailto:r-help-boun...@r-project.org] On Behalf Of amir Sent: Friday, February 11, 2011 10:11 AM To: r-help@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@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. ______________________________________________ R-help@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.
