Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.DirectedCycle
r1.1 - 09 Aug 2005 - 12:05 - Main.guest
topic end
Start of topic |
Skip to actions
In the picture below, we have wedge triangles to the left and right of "diagonal edge" _e_ with Schnyder label _i_ + 1. The triangle to the left of _e_ involves the edge _e.inc_ with label _i_ + 2 and the triangle to the right of _e_ involves the edge _e.dec_ with label _i_. _e_ cannot be swapped with either _e.inc_ or _e.dec_ because all three edges are outgoing from the same vertex _v_. Either _e.inc_ or _e.dec_ will have to be reversed so that one of them is incoming to vertex _v_, then a swap with _e_ can be performed. <img src="%ATTACHURLPATH%/Capture8-8-2005-7.54.13PM.jpg " alt="Wedge Triangles "/> We can prove that there is always a directed cycle of edges through v that does not include edge e. By reversing this cycle and relabelling edges, we can make either f or g incoming to vertex v. This cycle will start at either _e.inc_ or _e.dec_ and end at an incoming edge to _v_ between _e.inc_ and _e.dec_ with label _i_ + 1. If the cycle starts from _e.inc_ with label _i_ + 2, you can traverse the cycle by starting from _e.inc_ then going to the outgoing edge from the vertex pointed to by e.inc (vertex _w_ in the picture below) with label _i_ (edge _f_ in the picture). Next, go to the outgoing edge from vertex _x_ with label _i_ + 1. Keep following outgoing edges with label _i_ + 1 until you get back to vertex _v_. <img src="%ATTACHURLPATH%/Capture8-8-2005-7.56.48PM.jpg " alt="Cycle including e.inc"/> If the cycle starts from _e.dec_ with label _i_, you can traverse the cycle by starting from _e.dec_ then going to the outgoing edge from the vertex pointed to by e.dec (vertex _w_ in the picture below) with label _i_ + 2 (edge _f_ in the picture). Next, go to the outgoing edge from vertex _x_ with label _i_ + 1. Keep following outgoing edges with label _i_ + 1 until you get back to vertex _v_. <img src="%ATTACHURLPATH%/Capture8-8-2005-7.55.10PM.jpg " alt="Cycle including e.dec"/> In general, if you let the label of _e.inc_ be _i_, a directed cycle of edges through v starting from _e.inc_ will have labels as follows: <blockquote> _i_ --> _i_ + 1 --> _i_ + 2 --> _i_ + 2 --> _i_ + 2 --> _i_ + 2... </blockquote> If you let the label of _e.dec_ be _i_, a directed cycle of edges through v starting from _e.dec_ will have labels as follows: <blockquote> _i_ --> _i_ + 2 --> _i_ + 1 --> _i_ + 1 --> _i_ + 1 --> _i_ + 1... </blockquote> Since we never know if the directed cycle will start from _e.dec_ or _e.inc_, we will start from both edges simultaneously and stop when one of the paths take us back to _v_. *[JSS: would you like to tackle the proof that one of these works?]* To actually construct the cycle, it helps to have a subroutine that, given an edge of label _i_ into a vertex _v_ returns the edge of label _i_ out of vertex _v_. <pre> edge FollowLabel(edge h) If triangle to the left of h is mouth Let h be h.ccw.ccw.inc If triangle to the left of h is cycle Let h be h.ccw.ccw.dec If triangle to the left of h is wedge Let h be h.inc.cw.dec return h </pre> Here is an algorithm for traversing the directed cycle starting from _e.dec_. If the directed cycle starts from e.inc, interchange _inc_ and _dec_, right and left, and cw and ccw. [Considerations: This algorithm doesn't test simultaneously as explained in the paragraph above. Also, I probably need a function that returns the edges of the cycle.] *[JSS: yes, you'll want to store the edges visited in arrays, and include the simultaneous exploration. Having a subroutine makes that easier.]* <pre> Step 1: Start from e.dec Step 2: If triangle to the right of e.dec is mouth or cycle Let h be e.cw.inc Else Error! since triangle to the right of e.dec can never be wedge Step 3: If triangle to the left of h is mouth Let h be h.ccw.ccw If triangle to the left of h is cycle Let h be h.ccw.ccw.inc If triangle to the left of h is wedge Let h be h.inc.cw.inc Step 4: while h <> e Let h = FollowLabel(h) </pre> -- Main.SisillaSookdeo - 05 Aug 2005 *Now for the fun part: reversing the cycle...* -- Main.JackSnoeyink - 09 Aug 2005
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
DirectedCycle
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback