Re: [boost] [BGL] isomorphism, filtered_graph problems

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-11-06 12:00:08

Jeremy Siek wrote:
> On Mon, 5 Nov 2001, Vladimir Prus wrote:
> ghost>
> ghost> I've got several problems with BGL:
> ghost> 1. 'isomorphism' has problems with directed graph. The following
> does not ghost> compile:
> ghost> 	[ includes skipped]
> ghost> 	int main()
> ghost> 	{
> ghost> 	    adjacency_list<vecS, vecS, directedS> g1, g2;
> ghost> 	    isomorphism(g1, g2);
> ghost> 	}
> ghost> When 'undirectedS' is used, it compiles. Is it my fault, or BGL's?
>
> As per the docs, the second graph has to be a BidirectionalGraph, so
> you need to use bidirectionS instead of directedS

I've missed that. But... is this requirement present due to the algorithm 
used or for some other reason. The graphs which I'd like to compare are 
directed by definition.

> jsiek> Yes, I thought about this. I don't think the semantics can
> jsiek> change, though I will document them.
> jsiek>
> jsiek> We certainly do need a resizable-on-subscript container. Would you
> jsiek> be interested in writing one?

Alas, I don't have quite enough time to promise writing one. For now, we can 
at least discuss what precisely type of container it should be. In 
particular, should iteration be supported? GTL's node map does not support 
in, IIRC, and supporting it would require skipping elements while iterating.

Regards,
Vladimir