Re: [boost] [bgl] Graph class, an idea

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. 
> 
> 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