Subject: Re: [boost] [bgl] Graph class, an idea
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-04-03 05:48:48
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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk