On 04/02/2010 07:14 PM, Alexander Golec wrote:
Hey all,
I have recently been working on a project that has led me to some interesting ideas for a graph class.
Chief among them is the structure of the cycle matrix. This is a matrix representing the fundamental cycles of a graph. With this matrix, one can easily determine if, given an arbitrary set of vertices, if there is a cycle that passes through all of them. Whats more, it can easily provide that cycle if it exists.
I'd like to ask if this sounds like something that would be useful in Boost's Graph class.
Thanks, Alex
Hi Alex! There are a number of questions arising when I read your message that might or might not be interesting for an implementation: 1. Does the cycle matrix uniquely represent a given graph, or does one need further information such as adjacency information? 2. If yes, which existing concepts does it provide? 3. I guess the problem you described cannot be solved (more efficiently) with the existing datastructures? Are there further problems? What are the running times / space for the matrix + it's algorithms? A short overview / reference to literature would do. best regards Matthias Walter