|
»
»
graph search algorithm
|
View:
New views
3 Messages
—
Rating Filter:
Alert me
|
 |
graph search algorithm
by George Kelly
::
Rate this Message:
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@... http://lists.boost.org/mailman/listinfo.cgi/boost-users |
|
|
Re: graph search algorithm
by Saul Spatz
::
Rate this Message:
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.
|
|
|
Re: graph search algorithm
by Alejandro Aragón-2
::
Rate this Message:
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@... >> 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 _______________________________________________ Boost-users mailing list Boost-users@... http://lists.boost.org/mailman/listinfo.cgi/boost-users |
| Free embeddable forum powered by Nabble | Forum Help |
