On 03/08/2010 17:51, Anders Wallin wrote:
I was thinking to reset the filtered graph at every source vertex. Roughly equivalent to keeping track of depth, without having to write the code.
thanks for all replies, I will try writing an exception-throwing visitor or my own depth-limited bfs.
I should probably describe my application, since there might be a much better solution than the one I am trying. As part of a computer-aided-manufacturing toolpath calculation I am producing planar graphs like this: http://tinyurl.com/377lvt8 red edges go in the X-direction, blue edges in the Y-direction. the vertices I am interested in are drawn as blue/red dots(the color does not matter here), and the problem is to find the correct order of these vertices which creates a "silhouette" or "contour" of the graph. A naive solution would just hop from one dot to the closest one, but in more complicated cases this is not correct, so I would prefer traversing the graph to the next dot.
sometimes the graph has many disconnected components: (no colored dots in this pic, and nevermind the white triangulated surface...) http://tinyurl.com/3aefpgn and note that the donut-shaped component of the graph has two of these "loops" I am interested in, one on the outside, one on the inside.
I've been thinking about two approaches: 1) start at one vertex, search in the neighbourhood of this vertex for the next one, figure out which one of the found points is the correct next vertex. iterate. 2) something based on the idea of surface tension, or some kind of relaxation/removal/addition of edges. start in the middle of the graph and work your way towards the outside and when we are finished only the correct edges remain.
any ideas?
Yes. 1. Remove (or filter out) all vtx of deg 1 together with their edges. 2. Mark all vtx of deg < 4 with p. 3. Starting at, and working away from, the p vtxs of deg 2[1], join with the adjacent p vtx. 4. Now any p vtx of pdeg < 2 will be adjacent to a non p vtx that is adjacent to another p vtx of pdeg < 2, make the non p vertex a p vertex and join with the two adjacent p vtxs. (pdeg is the number of adjacent p vtxs, of course). 5. That's it, bar sticking the loose threads back on etc. No shadow of a proof, so may contain bugs! Louis. [1] Looks like you need to move away from the deg 2 vtxs in step, in case you're on a strip 2 vtxs wide, in which case there'll be two adjacent p vtxs you could join with.