[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] finding the most negaitve (weighted) cycle in a graph
From: |
Tamas Nepusz |
Subject: |
[igraph] finding the most negaitve (weighted) cycle in a graph |
Date: |
Sat, 22 May 2010 17:51:14 +0100 |
> I want to find the most negative (weighted) cycle in a graph. Can I do that
> using igraph package in R.
[Please do not reply to an existing thread if your question is unrelated to
that thread (it makes the mailing list archive harder to follow).]
Anyway, of course you can do that, but there is no built-in function for that
as this is not a very common problem. You will have to implement the algorithm
yourself. You can use a depth-first search to find all the cycles in the graph
(every time you see a back-edge during DFS, you have found a cycle), and then
keep only the one with the most negative weight.
--
Tamas