Re: [Boost-users] graph search algorithm

From: Alejandro Aragon (aaragon2_at_[hidden])
Date: 2006-09-05 23:30:12

Saul Spatz wrote:
> This description of the algorithm comes from the documentation for the
> computer algebra system magma
> http://magma.maths.usyd.edu.au/magma/htmlhelp/text1472.htm#14914
> 
> Face(u, v) : GrphVert, GrphVert -> SeqEnum
> 
>     Returns the face of the planar graph G bordered by the directed edge [u,
> v] as an ordered list of edges of G.
> 
>     Note that a directed edge and an orientation determine a face uniquely:
> We can assume without loss of generality that the plane is given a clockwise
> orientation. Then given a directed edge e = [u_1, v_1], the face defined by
> e is the ordered set of edges [u_1, v_1], [u_2, v_2], ..., [u_m, v_m] such
> that v_i = u_(i + 1) for all i, 1 <= i < m, v_m = u_1, and for each v_i =
> u_(i + 1), the neighbours of v_i, u_i and v_(i + 1), are consecutive
> vertices in v_i's adjacency list whose order is anti-clockwise. 
> 
> 
> George Kelly wrote:
>> I have a undirected graph set on a 2D plane.
>>
>> Imagine the graph looking something like the USA where the edges form 
>> the borders of the states.
>>
>> I would like to automatically recognise all of the enclosed regions (the 
>> states) by searching the graph and store each state as a subgraph.
>>
>> How can I search the graph returning only the enclosed regions?
>>
>> Thanks, any suggestions appreciated.
>>
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
>>
> 

If you read the boost graph library book, there is a section where it
describes how to detect cycles.  I think that may help.

Alejandro Aragon