Imported modules
|
|
from DataStructures import Stack
from copy import deepcopy
from tkMessageBox import showinfo
|
Functions
|
|
|
|
Make_biconnected_graph
|
Make_biconnected_graph ()
We first make it connected by linking all roots of a DFS-forest.
Assume now that G is connected.
Let a be any articulation point and let u and v be neighbors
of a belonging to different biconnected components.
Then there are embeddings of the two components with the edges
{u,a} and {v,a} on the boundary of the unbounded face.
Hence we may add the edge {u,v} without destroying planarity.
Proceeding in this way we make G biconnected.
|
|
PrintGraph
|
PrintGraph ( G )
|
|
SaveGmlGraph
|
SaveGmlGraph ( G, fileName )
|
|
dfs_in_make_biconnected_graph
|
dfs_in_make_biconnected_graph ( v )
This procedure determines articulation points and adds appropriate
edges whenever it discovers one.
|
|
dfs_in_reorder
|
dfs_in_reorder ( v )
|
|
embedding
|
embedding (
e0,
t,
T,
A,
)
embed: determine the cycle "C(e0)"
We start by determining the spine cycle.
This is precisley as in |strongly_planar|.
We also record for the vertices w_r+1, ...,w_k, and w_0 the
incoming cycle edge either in |tree_edge_into| or in the local
variable |back_edge_into_w0|.
|
|
planarity_test
|
planarity_test ( Gin )
planarity_test decides whether the InputGraph is planar.
it also order the adjecentLists in counterclockwise.
|
|
pt_DFS
|
pt_DFS ( v )
|
|
reorder
|
reorder ()
The procedure reorder first performs DFS to compute dfsnum, parent
lowpt1 and lowpt2, and the list Del of all forward edges and all
reversals of tree edges.
It then deletes the edges in Del and finally reorders the edges.
|
|
reversal
|
reversal ( e )
|
|
source
|
source ( e )
|
|
strongly_planar
|
strongly_planar ( e0, Att )
We now come to the heart of the planarity test: procedure strongly_planar.
It takes a tree edge e0=(x,y) and tests whether the segment S(e0) is
strongly planar.
If successful it returns (in Att) the ordered list of attachments of S(e0)
(excluding x); high DFS-numbers are at the front of the list.
In alpha it records the placement of the subsegments. strongly_planar operates in three phases.
It first constructs the cycle C(e0) underlying the segment S(e0).
It then constructs the interlacing graph for the segments emanating >from the
spine of the cycle.
If this graph is non-bipartite then the segment S(e0) is non-planar.
If it is bipartite then the segment is planar.
In this case the third phase checks whether the segment is strongly planar
and, if so, computes its list of attachments.
|
|
target
|
target ( e )
|
Classes
|
|
List | |
block |
The constructor takes an edge and a list of attachments and creates
|
pt_graph | |
|