################################################################################
#
# This file is part of Gato (Graph Algorithm Toolbox)
#
# file: PlanarityTest.py
# author: Ramazan Buzdemir (buzdemir@zpr.uni-koeln.de)
#
# Copyright (C) 1998-2005, Alexander Schliep, Winfried Hochstaettler and
# Copyright 1998-2001 ZAIK/ZPR, Universitaet zu Koeln
#
# Contact: schliep@molgen.mpg.de, wh@zpr.uni-koeln.de
#
# Information: http://gato.sf.net
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Library General Public
# License as published by the Free Software Foundation; either
# version 2 of the License, or (at your option) any later version.
#
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Library General Public License for more details.
#
# You should have received a copy of the GNU Library General Public
# License along with this library; if not, write to the Free
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
#
#
#
# This file is version $Revision: 1.14 $
# from $Date: 2005/02/22 11:12:59 $
# last change by $Author: schliep $.
#
################################################################################
###############################################################################
###############################################################################
###############################################################################
# #
# AN IMPLEMENTATION OF #
# THE HOPCROFT AND TARJAN #
# PLANARITY TEST AND EMBEDDING ALGORITHM #
# #
###############################################################################
# #
# References: #
# #
# [Meh84] K.Mehlhorn. #
# "Data Structures and Efficient Algorithms." #
# Springer Verlag, 1984. #
# [MM94] K.Mehlhorn and P.Mutzel. #
# "On the embedding phase of the Hopcroft and Tarjan planarity #
# testing algorithm." #
# Technical report no. 117/94, mpi, Saarbruecken, 1994 #
# #
###############################################################################
#=============================================================================#
from copy import deepcopy
from DataStructures import Stack
from tkMessageBox import showinfo
#=============================================================================#
#=============================================================================#
class List:
def __init__(self,el=[]):
elc=deepcopy(el)
self.elements=elc
# a) Access Operations
def length(self):
return len(self.elements)
def empty(self):
if self.length()==0:
return 1
else:
return 0
def head(self):
return self.elements[0]
def tail(self):
return self.elements[-1]
# b)Update Operations
def push(self,x):
self.elements.insert(0,x)
return x
def Push(self,x):
self.elements.append(x)
return x
def append(self,x):
self.Push(x)
def pop(self):
x=self.elements[0]
self.elements=self.elements[1:]
return x
def Pop(self):
x=self.elements[-1]
self.elements=self.elements[:-1]
return x
def clear(self):
self.elements=[]
def conc(self,A):
self.elements=self.elements+A.elements
A.elements=[]
#=============================================================================#
#=============================================================================#
class pt_graph:
def __init__(self):
self.V = []
self.E = []
self.adjEdges = {}
# a) Access operations
def source(self,e):
return e[0]
def target(self,e):
return e[1]
def number_of_nodes(self):
return len(self.V)
def number_of_edges(self):
return len(self.E)
def all_nodes(self):
return self.V
def all_edges(self):
return self.E
def adj_edges(self,v):
return self.adjEdges[v]
def adj_nodes(self,v):
nodelist=[]
for e in self.adj_edges(v):
nodelist.append(e[1])
return nodelist
def first_node(self):
return self.V[0]
def last_node(self):
return self.V[-1]
def first_edge(self):
return self.E[0]
def last_edge(self):
return self.E[-1]
def first_adj_edge(self,v):
if len(self.adj_edges(v))>0:
return self.adj_edges(v)[0]
else:
return None
def last_adj_edge(self,v):
if len(self.adj_edges(v))>0:
return self.adj_edges(v)[-1]
else:
return None
# b) Update operations
def new_node(self,v):
self.V.append(v)
self.adjEdges[v]=[]
return v
def new_edge(self,v,w):
if v==w: # Loop
raise GraphNotSimpleError
if (v,w) in self.E: # Multiple edge
raise GraphNotSimpleError
self.E.append((v,w))
self.adjEdges[v].append((v,w))
return (v,w)
def del_node(self,v):
try:
for k in self.V:
for e in self.adj_edges(k):
if source(e)==v or target(e)==v:
self.adjEdges[k].remove(e)
self.V.remove(v)
for e in self.E:
if source(e)==v or target(e)==v:
self.E.remove(e)
except KeyError:
raise NoSuchVertexError
def del_edge(self,e):
try:
self.E.remove(e)
self.adjEdges[source(e)].remove((source(e),target(e)))
except KeyError:
raise NoSuchEdgeError
def del_nodes(self,node_list): # deletes all nodes in list L from self
L=deepcopy(node_list)
for l in L:
self.del_node(l)
def del_edges(self,edge_list): # deletes all edges in list L from self
L=deepcopy(edge_list)
for l in L:
self.del_edge(l)
def del_all_nodes(self): # deletes all nodes from self
self.del_nodes(self.all_nodes())
def del_all_edges(self): # deletes all edges from self
self.del_edges(self.all_edges())
def sort_edges(self, cost):
def up(x,y):
if x[1]<y[1]: return -1
if x[1]==y[1]: return 0
return 1
sorted_list=cost.items()
sorted_list.sort(up)
self.del_all_edges()
for i in sorted_list:
self.new_edge(source(i[0]),target(i[0]))
def source(e):
return e[0]
def target(e):
return e[1]
def reversal(e):
return (e[1],e[0])
#=============================================================================#
#=============================================================================#
class block:
# The constructor takes an edge and a list of attachments and creates
# a block having the edge as the only segment in its left side.
#
# |flip| interchanges the two sides of a block.
#
# |head_of_Latt| and |head_of_Ratt| return the first elements
# on |Latt| and |Ratt| respectively
# and |Latt_empty| and |Ratt_empty| check these lists for emptyness.
#
# |left_interlace| checks whether the block interlaces with the left
# side of the topmost block of stack |S|.
# |right_interlace| does the same for the right side.
#
# |combine| combines the block with another block |Bprime| by simply
# concatenating all lists.
#
# |clean| removes the attachment |w| from the block |B| (it is
# guaranteed to be the first attachment of |B|).
# If the block becomes empty then it records the placement of all
# segments in the block in the array |alpha| and returns true.
# Otherwise it returns false.
#
# |add_to_Att| first makes sure that the right side has no attachment
# above |w0| (by flipping); when |add_to_Att| is called at least one
# side has no attachment above |w0|.
# |add_to_Att| then adds the lists |Ratt| and |Latt| to the output list
# |Att| and records the placement of all segments in the block in |alpha|.
def __init__(self,e,A):
self.Latt=List(); self.Ratt=List() # list of attachments "ints"
self.Lseg=List(); self.Rseg=List() # list of segments represented by
# their defining "edges"
self.Lseg.append(e)
self.Latt.conc(A) # the other two lists are empty
def flip(self):
ha=List() # "ints"
he=List() # "edges"
# we first interchange |Latt| and |Ratt| and then |Lseg| and |Rseg|
ha.conc(self.Ratt); self.Ratt.conc(self.Latt); self.Latt.conc(ha);
he.conc(self.Rseg); self.Rseg.conc(self.Lseg); self.Lseg.conc(he);
def head_of_Latt(self):
return self.Latt.head()
def empty_Latt(self):
return self.Latt.empty()
def head_of_Ratt(self):
return self.Ratt.head()
def empty_Ratt(self):
return self.Ratt.empty()
def left_interlace(self,S):
# check for interlacing with the left side of the
# topmost block of |S|
if (S.IsNotEmpty() and not((S.contents[-1]).empty_Latt()) and
self.Latt.tail()<(S.contents[-1]).head_of_Latt()):
return 1
else:
return 0
def right_interlace(self,S):
# check for interlacing with the right side of the
# topmost block of |S|
if (S.IsNotEmpty() and not((S.contents[-1]).empty_Ratt()) and
self.Latt.tail()<(S.contents[-1]).head_of_Ratt()):
return 1
else:
return 0
def combine(self,Bprime):
# add block Bprime to the rear of |this| block
self.Latt.conc(Bprime.Latt)
self.Ratt.conc(Bprime.Ratt)
self.Lseg.conc(Bprime.Lseg)
self.Rseg.conc(Bprime.Rseg)
del Bprime
def clean(self,dfsnum_w,alpha,dfsnum):
# remove all attachments to |w|; there may be several
while not(self.Latt.empty()) and self.Latt.head()==dfsnum_w:
self.Latt.pop()
while not(self.Ratt.empty()) and self.Ratt.head()==dfsnum_w:
self.Ratt.pop()
if not(self.Latt.empty()) or not(self.Ratt.empty()):
return 0
# |Latt| and |Ratt| are empty;
# we record the placement of the subsegments in |alpha|.
for e in self.Lseg.elements:
alpha[e]=left
for e in self.Rseg.elements:
alpha[e]=right
return 1
def add_to_Att(self,Att,dfsnum_w0,alpha,dfsnum):
# add the block to the rear of |Att|. Flip if necessary
if not(self.Ratt.empty()) and self.head_of_Ratt()>dfsnum_w0:
self.flip()
Att.conc(self.Latt)
Att.conc(self.Ratt)
# This needs some explanation.
# Note that |Ratt| is either empty or {w0}.
# Also if |Ratt| is non-empty then all subsequent
# sets are contained in {w0}.
# So we indeed compute an ordered set of attachments.
for e in self.Lseg.elements:
alpha[e]=left
for e in self.Rseg.elements:
alpha[e]=right
#=============================================================================#
#=============================================================================#
# GLOBALS:
left=1
right=2
G=pt_graph()
reached={}
dfsnum={}
parent={}
dfs_count=0
lowpt={}
Del=[]
lowpt1={}
lowpt2={}
alpha={}
Att=List()
cur_nr=0
sort_num={}
tree_edge_into={}
#=============================================================================#
#=============================================================================#
def planarity_test(Gin):
# planarity_test decides whether the InputGraph is planar.
# it also order the adjecentLists in counterclockwise.
### SaveGmlGraph(Gin,"/home/ramazan/Leda/Graphs/rama.gml")
n=Gin.Order() # number of nodes
if n<3: return 1
if not(Gin.QDirected()) and Gin.Size()>3*n-6: return 0 # number of edges
if Gin.QDirected() and Gin.Size()>6*n-12: return 0
#--------------------------------------------------------------
# make G a copy of Gin and make G bidirected
global G,cur_nr
G=pt_graph()
for v in Gin.vertices:
G.new_node(v)
for e in Gin.Edges():
G.new_edge(source(e),target(e))
cur_nr=0
nr={}
cost={}
n=G.number_of_nodes()
for v in G.all_nodes():
nr[v]=cur_nr
cur_nr=cur_nr+1
for e in G.all_edges():
if nr[source(e)] < nr[target(e)]:
cost[e]=n*nr[source(e)] + nr[target(e)]
else:
cost[e]=n*nr[target(e)] + nr[source(e)]
G.sort_edges(cost)
L=List(G.all_edges())
while not(L.empty()):
e=L.pop()
if (not(L.empty()) and source(e)==target(L.head())
and source(L.head())==target(e)):
L.pop()
else:
G.new_edge(target(e),source(e))
#--------------------------------------------------------------
#--------------------------------------------------------------
# make G biconnected
Make_biconnected_graph()
#--------------------------------------------------------------
#--------------------------------------------------------------
# make H a copy of G
#
# We need the biconnected version of G (G will be further modified
# during the planarity test) in order to construct the planar embedding.
# So we store it as a graph H.
H=deepcopy(G)
#--------------------------------------------------------------
#--------------------------------------------------------------
# test planarity
global dfsnum,parent,alpha,Att
dfsnum={}
parent={}
for v in G.all_nodes():
parent[v]=None
reorder()
alpha={}
for e in G.all_edges():
alpha[e]=0
Att=List()
alpha[G.first_adj_edge(G.first_node())] = left
if not(strongly_planar(G.first_adj_edge(G.first_node()),Att)):
return 0
#--------------------------------------------------------------
#--------------------------------------------------------------
# construct embedding
global sort_num,tree_edge_into
T=List()
A=List()
cur_nr=0
sort_num={}
tree_edge_into={}
embedding(G.first_adj_edge(G.first_node()),left,T,A)
# |T| contains all edges incident to the first node except the
# cycle edge into it.
# That edge comprises |A|.
T.conc(A)
for e in T.elements:
sort_num[e]=cur_nr
cur_nr=cur_nr+1
H.sort_edges(sort_num)
#--------------------------------------------------------------
return H.all_edges() # ccwOrderedEges
#=============================================================================#
#=============================================================================#
def pt_DFS(v):
global G,reached
S=Stack()
if reached[v]==0:
reached[v]=1
S.Push(v)
while S.IsNotEmpty():
v=S.Pop()
for w in G.adj_nodes(v):
if reached[w]==0:
reached[w]=1
S.Push(w)
#=============================================================================#
#=============================================================================#
def 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.
global G,reached,dfsnum,parent,dfs_count,lowpt
#--------------------------------------------------------------
# We first make G connected by linking all roots of the DFS-forest.
reached={}
for v in G.all_nodes():
reached[v]=0
u=G.first_node()
for v in G.all_nodes():
if not(reached[v]):
# explore the connected component with root v
pt_DFS(v)
if u!=v:
# link v's component to the first component
G.new_edge(u,v)
G.new_edge(v,u)
#--------------------------------------------------------------
#--------------------------------------------------------------
# We next make G biconnected.
for v in G.all_nodes():
reached[v]=0
dfsnum={}
parent={}
for v in G.all_nodes():
parent[v]=None
dfs_count=0
lowpt={}
dfs_in_make_biconnected_graph(G.first_node())
#--------------------------------------------------------------
#=============================================================================#
#=============================================================================#
def dfs_in_make_biconnected_graph(v):
# This procedure determines articulation points and adds appropriate
# edges whenever it discovers one.
global G,reached,dfsnum,parent,dfs_count,lowpt
dfsnum[v]=dfs_count
dfs_count=dfs_count+1
lowpt[v]=dfsnum[v]
reached[v]=1
if not(G.first_adj_edge(v)): return # no children
u=target(G.first_adj_edge(v)) # first child
for e in G.adj_edges(v):
w=target(e)
if not(reached[w]):
# e is a tree edge
parent[w]=v
dfs_in_make_biconnected_graph(w)
if lowpt[w]==dfsnum[v]:
# v is an articulation point. We now add an edge.
# If w is the first child and v has a parent then we
# connect w and parent[v], if w is a first child and v
# has no parent then we do nothing.
# If w is not the first child then we connect w to the
# first child.
# The net effect of all of this is to link all children
# of an articulation point to the first child and the
# first child to the parent (if it exists).
if w==u and parent[v]:
G.new_edge(w,parent[v])
G.new_edge(parent[v],w)
if w!=u:
G.new_edge(u,w)
G.new_edge(w,u)
lowpt[v]=min(lowpt[v],lowpt[w])
else:
lowpt[v]=min(lowpt[v],dfsnum[w]) # non tree edge
#=============================================================================#
#=============================================================================#
def 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.
global G,dfsnum,parent,reached,dfs_count,Del,lowpt1,lowpt2
reached={}
for v in G.all_nodes():
reached[v]=0
dfs_count = 0
Del=[]
lowpt1={}
lowpt2={}
dfs_in_reorder(G.first_node())
#--------------------------------------------------------------
# remove forward and reversals of tree edges
for e in Del:
G.del_edge(e)
#--------------------------------------------------------------
#--------------------------------------------------------------
# we now reorder adjacency lists
cost={}
for e in G.all_edges():
v = source(e)
w = target(e)
if dfsnum[w]<dfsnum[v]:
cost[e]=2*dfsnum[w]
elif lowpt2[w]>=dfsnum[v]:
cost[e]=2*lowpt1[w]
else:
cost[e]=2*lowpt1[w]+1
G.sort_edges(cost)
#--------------------------------------------------------------
#=============================================================================#
#=============================================================================#
def dfs_in_reorder(v):
global G,dfsnum,parent,reached,dfs_count,Del,lowpt1,lowpt2
#--------------------------------------------------------------
dfsnum[v]=dfs_count
dfs_count=dfs_count+1
lowpt1[v]=lowpt2[v]=dfsnum[v]
reached[v]=1
for e in G.adj_edges(v):
w = target(e);
if not(reached[w]):
# e is a tree edge
parent[w]=v
dfs_in_reorder(w)
lowpt1[v]=min(lowpt1[v],lowpt1[w])
else:
lowpt1[v]=min(lowpt1[v],dfsnum[w]) # no effect for forward edges
if dfsnum[w]>=dfsnum[v] or w==parent[v]:
# forward edge or reversal of tree edge
Del.append(e)
#--------------------------------------------------------------
#--------------------------------------------------------------
# we know |lowpt1[v]| at this point and now make a second pass over all
# adjacent edges of |v| to compute |lowpt2|
for e in G.adj_edges(v):
w = target(e)
if parent[w]==v:
# tree edge
if lowpt1[w]!=lowpt1[v]:
lowpt2[v]=min(lowpt2[v],lowpt1[w])
lowpt2[v]=min(lowpt2[v],lowpt2[w])
else:
# all other edges
if lowpt1[v]!=dfsnum[w]:
lowpt2[v]=min(lowpt2[v],dfsnum[w])
#--------------------------------------------------------------
#=============================================================================#
#=============================================================================#
def 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.
global G,alpha,dfsnum,parent
#--------------------------------------------------------------
# DETERMINE THE CYCLE C(e0)
# We determine the cycle "C(e0)" by following first edges until a back
# edge is encountered.
# |wk| will be the last node on the tree path and |w0|
# is the destination of the back edge.
x=source(e0)
y=target(e0)
e=G.first_adj_edge(y)
wk=y
while dfsnum[target(e)]>dfsnum[wk]: # e is a tree edge
wk=target(e)
e=G.first_adj_edge(wk)
w0=target(e)
#--------------------------------------------------------------
#--------------------------------------------------------------
# PROCESS ALL EDGES LEAVING THE SPINE
# The second phase of |strongly_planar| constructs the connected
# components of the interlacing graph of the segments emananating
# from the the spine of the cycle "C(e0)".
# We call a connected component a "block".
# For each block we store the segments comprising its left and
# right side (lists |Lseg| and |Rseg| contain the edges defining
# these segments) and the ordered list of attachments of the segments
# in the block;
# lists |Latt| and |Ratt| contain the DFS-numbers of the attachments;
# high DFS-numbers are at the front of the list.
#
# We process the edges leaving the spine of "S(e0)" starting at
# node |wk| and working backwards.
# The interlacing graph of the segments emanating from
# the cycle is represented as a stack |S| of blocks.
w=wk
S=Stack()
while w!=x:
count=0
for e in G.adj_edges(w):
count=count+1
if count!=1: # no action for first edge
# TEST RECURSIVELY
# Let "e" be any edge leaving the spine.
# We need to test whether "S(e)" is strongly planar
# and if so compute its list |A| of attachments.
# If "e" is a tree edge we call our procedure recursively
# and if "e" is a back edge then "S(e)" is certainly strongly
# planar and |target(e)| is the only attachment.
# If we detect non-planarity we return false and free
# the storage allocated for the blocks of stack |S|.
A=List()
if dfsnum[w]<dfsnum[target(e)]:
# tree edge
if not(strongly_planar(e,A)):
while S.IsNotEmpty(): S.Pop()
return 0
else:
A.append(dfsnum[target(e)]) # a back edge
# UPDATE STACK |S| OF ATTACHMENTS
# The list |A| contains the ordered list of attachments
# of segment "S(e)".
# We create an new block consisting only of segment "S(e)"
# (in its L-part) and then combine this block with the
# topmost block of stack |S| as long as there is interlacing.
# We check for interlacing with the L-part.
# If there is interlacing then we flip the two sides of the
# topmost block.
# If there is still interlacing with the left side then the
# interlacing graph is non-bipartite and we declare the graph
# non-planar (and also free the storage allocated for the
# blocks).
# Otherwise we check for interlacing with the R-part.
# If there is interlacing then we combine |B| with the topmost
# block and repeat the process with the new topmost block.
# If there is no interlacing then we push block |B| onto |S|.
B=block(e,A)
while 1:
if B.left_interlace(S): (S.contents[-1]).flip()
if B.left_interlace(S):
del B
while S.IsNotEmpty(): S.Pop()
return 0
if B.right_interlace(S): B.combine(S.Pop())
else: break
S.Push(B)
# PREPARE FOR NEXT ITERATION
# We have now processed all edges emanating from vertex |w|.
# Before starting to process edges emanating from vertex
# |parent[w]| we remove |parent[w]| from the list of attachments
# of the topmost
# block of stack |S|.
# If this block becomes empty then we pop it from the stack and
# record the placement for all segments in the block in array
# |alpha|.
while (S.IsNotEmpty() and
(S.contents[-1]).clean(dfsnum[parent[w]],alpha,dfsnum)):
S.Pop()
w=parent[w]
#--------------------------------------------------------------
#--------------------------------------------------------------
# TEST STRONG PLANARITY AND COMPUTE Att
# We test the strong planarity of the segment "S(e0)".
# We know at this point that the interlacing graph is bipartite.
# Also for each of its connected components the corresponding block
# on stack |S| contains the list of attachments below |x|.
# Let |B| be the topmost block of |S|.
# If both sides of |B| have an attachment above |w0| then
# "S(e0)" is not strongly planar.
# We free the storage allocated for the blocks and return false.
# Otherwise (cf. procedure |add_to_Att|) we first make sure that
# the right side of |B| attaches only to |w0| (if at all) and then
# add the two sides of |B| to the output list |Att|.
# We also record the placements of the subsegments in |alpha|.
Att.clear()
while S.IsNotEmpty():
B = S.Pop()
if (not(B.empty_Latt()) and not(B.empty_Ratt()) and
B.head_of_Latt()>dfsnum[w0] and B.head_of_Ratt()>dfsnum[w0]):
del B
while S.IsNotEmpty(): S.Pop()
return 0
B.add_to_Att(Att,dfsnum[w0],alpha,dfsnum)
del B
# Let's not forget that "w0" is an attachment
# of "S(e0)" except if w0 = x.
if w0!=x: Att.append(dfsnum[w0])
return 1
#--------------------------------------------------------------
#=============================================================================#
#=============================================================================#
def 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|.
global G,dfsnum,cur_nr,sort_num,tree_edge_into,parent
x=source(e0)
y=target(e0)
tree_edge_into[y]=e0
e=G.first_adj_edge(y)
wk=y
while (dfsnum[target(e)]>dfsnum[wk]): # e is a tree edge
wk=target(e)
tree_edge_into[wk]=e
e=G.first_adj_edge(wk)
w0=target(e)
back_edge_into_w0=e
# process the subsegments
w=wk
Al=List()
Ar=List()
Tprime=List()
Aprime=List()
T.clear()
T.append(e) # |e=(wk,w0)| at this point
while w!=x:
count=0
for e in G.adj_edges(w):
count=count+1
if count!=1: # no action for first edge
# embed recursively
if dfsnum[w]<dfsnum[target(e)]:
# tree edge
if t==alpha[e]:
tprime=left
else:
tprime=right
embedding(e,tprime,Tprime,Aprime)
else:
# back edge
Tprime.append(e)
Aprime.append(reversal(e))
# update lists |T|, |Al|, and |Ar|
if t==alpha[e]:
Tprime.conc(T)
T.conc(Tprime) # T = Tprime conc T
Al.conc(Aprime) # Al = Al conc Aprime
else:
T.conc(Tprime) # T = T conc Tprime
Aprime.conc(Ar)
Ar.conc(Aprime) # Ar = Aprime conc Ar
# compute |w|'s adjacency list and prepare for next iteration
T.append(reversal(tree_edge_into[w])) # (w_j-1,w_j)
for e in T.elements:
sort_num[e]=cur_nr
cur_nr=cur_nr+1
# |w|'s adjacency list is now computed; we clear |T| and
# prepare for the next iteration by moving all darts incident
# to |parent[w]| from |Al| and |Ar| to |T|.
# These darts are at the rear end of |Al| and at the front end
# of |Ar|.
T.clear()
while not(Al.empty()) and source(Al.tail())==parent[w]:
# |parent[w]| is in |G|, |Al.tail| in |H|
T.push(Al.Pop()) # Pop removes from the rear
T.append(tree_edge_into[w]) # push would be equivalent
while not(Ar.empty()) and source(Ar.head())==parent[w]:
T.append(Ar.pop()); # pop removes from the front
w=parent[w]
# prepare the output
A.clear()
A.conc(Ar)
A.append(reversal(back_edge_into_w0))
A.conc(Al)
#=============================================================================#
###############################################################################
# DEBUG #
###############################################################################
#=============================================================================#
def PrintGraph(G):
print "============================================================"
print "V : "
for v in G.all_nodes():
print "[%i]" %(v-1)
print
print "E : "
for e in G.all_edges():
print "[%i]---->[%i]" %((source(e)-1),(target(e)-1))
print
for v in G.all_nodes():
print "[%i] : " %(v-1)
for e in G.adj_edges(v):
print " [%i]---->[%i]" %((source(e)-1),(target(e)-1))
print
#=============================================================================#
#=============================================================================#
def SaveGmlGraph(G, fileName):
file = open(fileName, 'w')
file.write("graph [ \n")
file.write(" directed 1 \n \n")
for v in G.vertices:
file.write(" node [ id ")
n=str(v)
file.write(n)
file.write(" ] \n")
file.write("\n")
for e in G.Edges():
file.write(" edge [ \n")
file.write(" source ")
k=str(e[0])
file.write(k)
file.write("\n")
file.write(" target ")
k=str(e[1])
file.write(k)
file.write("\n")
file.write(" ] \n")
file.write("] \n")
#=============================================================================#