################################################################################
#
#       This file is part of Gato (Graph Algorithm Toolbox) 
#
#	file:   PlanarEmbedding.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.15 $ 
#                       from $Date: 2005/02/22 11:12:58 $
#             last change by $Author: schliep $.
#
################################################################################


###############################################################################
###############################################################################
###############################################################################
#                                                                             #
#                            AN IMPLEMENTATION OF                             #
#                    THE "DE FRAYSSEIX,PACH,POLLACK(FPP)"                     #
#                             AND THE "SCHNYDER"                              #
#                   PLANAR STRAIGHT-LINE EMBEDDING ALGORITHM                  #
#                                                                             #
###############################################################################
#                                                                             #
# References:                                                                 #
#                                                                             #
# [FPP90] H. de Fraysseix, J.Pach, and R.Pollack .                            #
#         "How to draw a planar graph on a grid."                             #
#         Combinatorian, 10:41-51,1990                                        #
# [Sch90] W.Schnyder.                                                         #
#         "Embedding planar graphs on the grid."                              #
#         In 1st Annual ACM-SIAM Symposium on Discrete Algorithms,            #
#         pages 138-14, San Francisco, 1990                                   #
#                                                                             #
###############################################################################



#=============================================================================#
from PlanarityTest import *
from copy import deepcopy
from DataStructures import Stack
from tkMessageBox import showinfo
#=============================================================================#



#=============================================================================#
class pe_Point:

    def __init__(self,xpos,ypos):
        self.x=xpos
        self.y=ypos
        #=============================================================================#
        
        
        
        #=============================================================================#
class pe_Node:

    def __init__(self,x,y):
        self.xpos=x
        self.ypos=y
        self.canOrder=None
        self.t1,self.t2,self.t3=None,None,None 
        self.p1,self.p2,self.p3=None,None,None 
        self.r1,self.r2,self.r3=None,None,None 
        self.xsch,self.ysch=None,None
        self.xfpp,self.yfpp=None,None
        self.adjacentEdges=[]
        self.adjacentNodes=[]
        self.M=[]
        self.oppositeNodes=[]
        self.outface=None
        
        self.path1=[]
        self.path2=[]
        self.path3=[]   
        
    def addEdge(self,e,v):
        self.adjacentEdges.append(e)
        self.adjacentNodes.append(v)
        #=============================================================================#
        
        
        
        #=============================================================================#
class pe_Edge: # directed from p1->p2

    def __init__(self,index_p1,index_p2,ep1,ep2,tf):
        self.p1=index_p1
        self.p2=index_p2
        self.label=None # normal labelling: 1,-1,2,-2,3,-3
        self.original=tf
        self.outface=None
        #=============================================================================#
        
        
        
        #=============================================================================#
class pe_Graph:

    #-------------------------------------------------------------------------
    def printGraph(self):
    
        for i in range(0,len(self.nodes)):
            n=self.nodes[i]
            print "--------Node:",i,"--------------"
            print "xpos=",n.xpos,"ypos=",n.ypos
            print "canOrder=",n.canOrder
            print "t1=",n.t1,"t2=",n.t2,"t3=",n.t3
            print "p1=",n.p1,"p2=",n.p2,"p3=",n.p3
            print "r1=",n.r1,"r2=",n.r2,"r3=",n.r3
            print "xsch=",n.xsch,"ysch=",n.ysch
            print "xfpp=",n.xfpp,"yfpp=",n.yfpp
            print "outface=",n.outface
            
        print
        for i in range(0,len(self.edges)):
            e=self.edges[i]
            print "-------Edge:",i,"---------------"
            print "p1=",e.p1,"p2=",e.p2
            print "label=",e.label
            print "original=",e.original,"outface=",e.outface
            
        print
        for i in range(0,len(self.nodes)):
            n=self.nodes[i]
            
            print "---------------------------"
            print i,":"
            
            print "adjacentEdges:",
            for j in range(0,len(n.adjacentEdges)):
                print n.adjacentEdges[j],
            print
            
            print "adjacentNodes:",
            for j in range(0,len(n.adjacentNodes)):
                print n.adjacentNodes[j],
            print
            
            print "M:",
            for j in range(0,len(n.M)):
                print n.M[j],
            print
            
            print "oppositeNodes:",
            for j in range(0,len(n.oppositeNodes)):
                print n.oppositeNodes[j],
            print
            
            print "path1:",
            for j in range(0,len(n.path1)):
                print n.path1[j],
            print
            
            print "path2:",
            for j in range(0,len(n.path2)):
                print n.path2[j],
            print
            
            print "path3:",
            for j in range(0,len(n.path3)):
                print n.path3[j],
            print
            #-------------------------------------------------------------------------
            
            
            #-------------------------------------------------------------------------
    def __init__(self):
        self.nodes=[]
        self.edges=[]
        
        self.orderK,self.orderIndexVk=None,None
        self.FPPk=None
        self.labelK=None
        self.indexV1,self.indexV2,self.indexV3=-1,-1,-1
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def checkIndex(self,index, p1):
        if index<0:
            tempNode1=pe_Node(p1.x,p1.y)
            self.nodes.append(tempNode1)
            return (len(self.nodes)-1)
        return index
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def storeEdge(self,indexP1,indexP2,p1,p2,tf):
        ep1=pe_Point(self.nodes[indexP1].xpos,self.nodes[indexP1].ypos)
        ep2=pe_Point(self.nodes[indexP2].xpos,self.nodes[indexP2].ypos)
        self.edges.append(pe_Edge(indexP1,indexP2,ep1,ep2,tf))
        #-------------------------------------------------------------------------
        
        
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # TRIANGULATION
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # Algorithm:
        # For each vertex v
        #     for v's each pair of consecutive neighbours u & w
        #             add the edge in
        #             add u into w's incident list in ccw order
        #             add w into u's incident list in ccw order
        #             repeat this procedure
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        #-------------------------------------------------------------------------
    def isEdge(self,u,w):
        # check if w is in u's adjacentEdges
        if w in u.adjacentNodes: return 1
        return 0
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def adjacentVertex(self,v,e):
        return v.adjacentNodes[e]
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def consider(self):
        for indexV in range(0,len(self.nodes)):
            v=self.nodes[indexV]
            
            if len(v.adjacentEdges)<2: continue
            
            for j in range(0,len(v.adjacentEdges)):
                # get two consective neighbours of v
                indexU=self.adjacentVertex(v,j)
                u=self.nodes[indexU]
                k=j+1
                if k==len(v.adjacentEdges): k=0
                indexW=self.adjacentVertex(v,k)
                w=self.nodes[indexW]
                
                # check if (u, w) is an edge
                if not(self.isEdge(u,indexW)):
                    pointu=pe_Point(u.xpos,u.ypos)
                    pointw=pe_Point(w.xpos,w.ypos)
                    self.storeEdge(indexU,indexW,pointu, pointw,0)
                    
                    tempi1=indexV
                    tempe1=len(self.edges)-1
                    
                    # add u to w's adjacentEdges (with ordering)
                    # add u after v in w's adjacentEdges
                    indexVinW=w.adjacentNodes.index(tempi1)+1
                    w.adjacentEdges.insert(indexVinW,tempe1)
                    w.adjacentNodes.insert(indexVinW,indexU)
                    
                    # add w to u's incitentList (with ordering)
                    # add w before v in u's adjacentEdges
                    indexVinU=u.adjacentNodes.index(tempi1)
                    u.adjacentEdges.insert(indexVinU,tempe1)
                    u.adjacentNodes.insert(indexVinU,indexW)
                    
                    # Don't forget to set original=0
                    self.edges[-1].original=0
                    
                    return 1
        return 0
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def triangulate(self):
        finish=1
        while finish:
            finish=self.consider()
            #-------------------------------------------------------------------------
            
            #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
            
            
            
            #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
            # CANONICAL ORDERING
            #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
            # Algorithm:
            # Pick up a face as outface
            # Assign its vertices with canonical ordering 1,2, and n
            #
            # For k from n-1 to 3 
            #     remove Vk+1 from graph
            #     find all Vk+1's neighbours in the new graph Gk
            #     update the vertices on the outface
            #     assign Vk to one of these neighbours on Ck that
            #                                              is not V1
            #                                              is not V2
            #                                              is not incident to a chord
            #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
            
            #-------------------------------------------------------------------------
    def ordering(self):
        self.orderK=len(self.nodes)
        
        # Now, remove Vn from the graph, and let Vn-1 be the vertex 
        # that is on the outerface and not incident to a chord.
        k=len(self.nodes)
        while k>3:
            self.orderIndexVk=self.order()
            k=k-1
            #-------------------------------------------------------------------------
            
            
            #-------------------------------------------------------------------------
    def initOrder(self):
        # NOTE: initially, all the canOrder are 0
        for i in range(0,len(self.nodes)):
            self.nodes[i].canOrder=0
            
            # Base: find v1, v2, and vn, which define a outerface
        if self.indexV1<0:
            self.indexV1=0
            v1=self.nodes[self.indexV1]
            
            self.indexV2=v1.adjacentNodes[0]
            v2=self.nodes[self.indexV2]
            
            self.indexVn=v1.adjacentNodes[1]
            vk=self.nodes[self.indexVn]
        else:
            v1=self.nodes[self.indexV1]
            v2=self.nodes[self.indexV2]
            vk=self.nodes[self.indexVn]
            
        v1.canOrder=1
        v2.canOrder=2
        vk.canOrder=len(self.nodes)
        
        # initialize all the outface to 0
        for j in range(0,len(self.nodes)): 
            self.nodes[j].outface=0
            
        self.orderK=len(self.nodes)
        self.orderIndexVk=self.indexVn
        return self.indexVn
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
        # Now, remove Vn from the graph, and let Vn-1 be the vertex 
        # that is on the outerface and not incident to a chord
    def order(self):
        if self.orderK>3:
            v1=self.nodes[self.indexV1]
            v2=self.nodes[self.indexV2]
            vk=self.nodes[self.orderIndexVk]
            # "remove" Vk from the graph
            # find the neighbours of Vk, that have canOrder number < k
            # define they are on the outface
            for i in range(0,len(vk.adjacentNodes)):
                neighbour=self.nodes[vk.adjacentNodes[i]]
                
                if neighbour.canOrder<self.orderK:
                    neighbour.outface=1
                    
                    # find the node that is not v1, v2, and not incident to any chord,
                    # let it be Vk-1
            found=0
            j=0
            while not(found) and j<len(self.nodes):
                candidate=self.nodes[j]
                if (candidate.outface and candidate!=v1 and
                    candidate!=v2 and candidate.canOrder<self.orderK):
                    # if it only has 2 neighbours on the outface,
                    # we set it to be Vk-1
                    count=0
                    for i in range(0,len(candidate.adjacentNodes)):
                        checkIndex=candidate.adjacentNodes[i]
                        checkNode=self.nodes[checkIndex]
                        if (checkNode.outface and
                            (checkNode.canOrder<self.orderK)):
                            count=count+1
                    if count==2:
                        found=1
                        vk=candidate
                        candidate.canOrder=self.orderK-1
                        
                        self.orderK=self.orderK-1
                        self.orderIndexVk=j
                        return j
                j=j+1
        return -1
        #-------------------------------------------------------------------------
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # EDGE LABELLING 
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # Algorithm:
        # In triangle V1, V2, V3 (canonical order)
        #     label V3->V1 with 1
        #     label V3->V2 with 2
        #
        # For k from 3 to n-1   
        #     add Vk+1 to graph Gk
        #     find all Vk+1's neighbours in Gk in order
        #     label the left most edge from top to bottom with 1
        #     label the right most edge from top to bottom with 2
        #     label the rest from bottom to top with 3
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        #-------------------------------------------------------------------------
    def labelling(self):
        self.initLabel()
        #steps
        for k in range(3,len(self.nodes)):
            self.labelK=k
            self.labelStep()
            # looking for v4, v5, ..., vn
            #-------------------------------------------------------------------------
            
            
            #-------------------------------------------------------------------------
            # label  label if the edge is indexP1 -> indexP2
            #       -label if the edge is indexP2 -> indexP1
    def labelEdge(self,indexP1,indexP2,label):
        e=self.edges[0]
        
        if e.p1==indexP1 and e.p2==indexP2:
            self.edges[0].label=label
            return
        if e.p1==indexP2 and e.p2==indexP1:
            self.edges[0].label=-label 
            return
            
        for i in range(1,len(self.edges)):
            e=self.edges[i]
            if e.p1==indexP1 and e.p2==indexP2:
                e.label=label
                return
            if e.p1==indexP2 and e.p2==indexP1:
                e.label=-label
                return
                #-------------------------------------------------------------------------
                
                
                #-------------------------------------------------------------------------
    def findIndexOfVk(self,k):
        indexVk=-1
        i=0
        
        while indexVk<0:
            if self.nodes[i].canOrder==k:
                return i
            i=i+1
        return -1
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def initLabel(self):
        for j in range(0,len(self.edges)):
            self.edges[j].label=0
            
        self.indexV3=self.findIndexOfVk(3)
        
        # find v1, v2, v3
        v1=self.nodes[self.indexV1]
        v2=self.nodes[self.indexV2]
        v3=self.nodes[self.indexV3]
        
        # labelling should be done at the same time as FPP is running
        # (because we need the outface information)
        # but we are doing this separately, for the sak of clearness
        
        # label V3 -> V1 by 1
        self.labelEdge(self.indexV3,self.indexV1,1)
        
        # label V3 -> V2 by 2
        self.labelEdge(self.indexV3,self.indexV2,2)
        
        self.labelK = 3
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def labelStep(self):
        k=self.labelK
        n=len(self.nodes)
        
        if k<n:
            indexVkplus1=self.findIndexOfVk(k+1)
            vkplus1=self.nodes[indexVkplus1]
            
            # labelling should be done at the same time as FPP is running
            # (because we need the outface information)
            # case 1: vk+1 is "to the right" of vk
            # case 2: vk+1 is "to the left" of vk
            # case 3: vk+1 "covers" vk
            # all make the first element in Vk+1's oppositeNodes label 1, 
            #   	   last                                        2,
            #  		   rest        	   			       3.
            # oppositeNodes is done in FPP
            
            first=vkplus1.oppositeNodes[0]
            self.labelEdge(indexVkplus1,first,1)
            
            last=vkplus1.oppositeNodes[-1]
            self.labelEdge(indexVkplus1,last,2)
            
            if len(vkplus1.oppositeNodes)>2:
                for l in range(1,len(vkplus1.oppositeNodes)-1):
                    self.labelEdge(indexVkplus1,vkplus1.oppositeNodes[l],-3)
                    
            self.labelK=self.labelK+1
        return self.labelK
        #-------------------------------------------------------------------------
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # FPP
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # Algorithm:
        # 3. Initialize x,y coordinates and M for V1,V2, and V3
        #                               v1.M={v1,v2,v3}
        #                               v2.M={v2}
        #                               v3.M={v2,v3}
        # 4. In the canonical order, for each vertex
        #       1. find the vertices on the outface in order
        #       2. shift vertices in the subset M of Wp+1 and Wq
        #       3. calculate the x,y coordinates of Vk+1
        #       4. updating M for all the outface vertices
        #                               wi.M=wi.M+{vk+1}  for i<=p
        #                               vk+1.M=wp+1.M+{vk+1}
        #                               wj.M=wj.M  for j>=q
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        #-------------------------------------------------------------------------
    def FPP(self):
        self.initFPP()
        
        # steps
        for k in range(3,len(self.nodes)):
            self.FPPk=k
            self.FPPstep()
            #-------------------------------------------------------------------------
            
            
            #-------------------------------------------------------------------------
    def initFPP(self):
        self.indexV3=self.findIndexOfVk(3)
        
        # initialize all the outface to 0
        for j in range(0,len(self.nodes)):
            self.nodes[j].outface=0
            self.nodes[j].xfpp=0
            self.nodes[j].yfpp=0
            self.nodes[j].M=[]
            self.nodes[j].oppositeNodes=[]
            
            # find v1, v2, v3
        v1=self.nodes[self.indexV1]
        v2=self.nodes[self.indexV2]
        v3=self.nodes[self.indexV3] 
        
        # basic
        v1.xfpp=0; v1.yfpp=0
        v2.xfpp=2; v2.yfpp=0
        v3.xfpp=1; v3.yfpp=1
        
        # v1.M={v1,v2,v3} v2.M={v2} v3.M={v2,v3}
        v1.M.append(self.indexV1)
        v1.M.append(self.indexV2)
        v1.M.append(self.indexV3)
        
        v2.M.append(self.indexV2)
        
        v3.M.append(self.indexV2)
        v3.M.append(self.indexV3) 
        
        self.nodes[self.indexV1].outface=1
        self.nodes[self.indexV2].outface=1
        self.nodes[self.indexV3].outface=1
        
        self.FPPk=3
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def FPPstep(self):
        k=self.FPPk
        n=len(self.nodes)
        
        if k<n:
            indexVkplus1=self.findIndexOfVk(k+1)
            vkplus1=self.nodes[indexVkplus1]
            
            # find the vertices on the outerface of Gk,
            # and in order of p, p+1, ..., q
            # find the neighbours of v(k+1) with CanOrder <= k,
            # and sort them according to their xfpp
            for i in range(0,len(vkplus1.adjacentNodes)):
                neighbour=self.nodes[vkplus1.adjacentNodes[i]]
                if neighbour.canOrder<=k:
                    insertPlace=-1
                    j=0
                    while insertPlace<0 and j<len(vkplus1.oppositeNodes):
                        if (neighbour.xfpp <
                            self.nodes[vkplus1.oppositeNodes[j]].xfpp):
                            insertPlace=j
                        j=j+1
                        
                    if insertPlace==-1:
                        vkplus1.oppositeNodes.append(
                            self.nodes.index(neighbour))
                    else:
                        vkplus1.oppositeNodes.insert(insertPlace,
                                                 self.nodes.index(neighbour))
                        
                        # find the vertices on the outface
            self.nodes[indexVkplus1].outface=1
            if len(vkplus1.oppositeNodes)>2:
                for i in range(1,len(vkplus1.oppositeNodes)-1):
                    temp=vkplus1.oppositeNodes[i]
                    self.nodes[temp].outface=0
                    
                    # shift all vertices in w(p+1).M right by 1 unit
            indexWpplus1=vkplus1.oppositeNodes[1]
            w=self.nodes[indexWpplus1]
            for i in range(0,len(w.M)):
                temp=w.M[i]
                self.nodes[temp].xfpp=self.nodes[temp].xfpp+1
                
                # shift all vertices in w(q).M right by 1 unit
            Wq=self.nodes[vkplus1.oppositeNodes[-1]]
            for i in range(0,len(Wq.M)): 
                self.nodes[Wq.M[i]].xfpp=self.nodes[Wq.M[i]].xfpp+1
                
                # add in v(k+1)
                
            Wp=self.nodes[vkplus1.oppositeNodes[0]]
            x1=Wp.xfpp
            y1=Wp.yfpp
            x2=Wq.xfpp
            y2=Wq.yfpp
            
            vkplus1.xfpp=(x1+x2+y2-y1)/2
            vkplus1.yfpp=(x2-x1+y2+y1)/2
            
            # update M
            # wi.M = wi.M + v(k+1)  for i<=p
            for i in range(0,n):
                wi=self.nodes[i]
                if wi.outface  and  wi.xfpp<w.xfpp and i!=indexVkplus1:
                    wi.M.append(indexVkplus1)
                    
                    # v(k+1).M = w(p+1).M + v(k+1)
            vkplus1.M.append(indexVkplus1)
            for i in range(0,len(w.M)):
                vkplus1.M.append(w.M[i])
                
                
            self.FPPk=self.FPPk+1
            
        return self.FPPk
        #-------------------------------------------------------------------------
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        
        
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # SCHNYDER
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        # Algorithm:
        # 4. Calculate for each interior vertex v
        #              pathi : vertices on the i-path from v to v1, v2, or vn
        #              pn : number of vertices on the i-path starting at v
        #              ti : number of vertices in the subtree of Ti rooted at v
        #              ri : number of vertices in region Ri(v) for v
        # 5. Calculate barycentric representation for each v: vi'=ri - pi-1
        #                                            v->(v1',v2',v3')/(n-1)
        #    A barycentric representation of a graph G is 
        #    an injective function v->(v1,v2,v3) that satisfies:
        #      a.) v1+v2+v3=1 for all v
        #      b.) for each edge (x,y) and each vertex z not x or y,
        #          there is some k (k=1,2 or 3) such that xk < zk and yk < zk   
        #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        
        #-------------------------------------------------------------------------
    def calculateP(self,path123):
        for i in range(0,len(self.nodes)):
            v=self.nodes[i] 
            finalNode=0
            
            if (v.canOrder!=1 and v.canOrder!=2 and 
                v.canOrder!=len(self.nodes)):
                # v is an interior vertex
                if path123==1:
                    v.p1=1
                    v.path1.append(i)
                    finalNode=1
                if path123==2:
                    v.p2=1
                    v.path2.append(i)
                    finalNode=2
                if path123==3:
                    v.p3=1
                    v.path3.append(i)
                    finalNode=len(self.nodes)
                    
                vNext=v
                while vNext.canOrder!=finalNode:
                    j=0
                    found=0
                    while (not(found) and j<len(vNext.adjacentEdges)):
                        curEdge=self.edges[vNext.adjacentEdges[j]]
                        curLabel=curEdge.label
                        # HIER IST IRGENDWO EIN FEHLER !!!!!!
                        if ( ((curLabel==path123) and 
                              (curEdge.p1==self.nodes.index(vNext))) or 
                             ((curLabel==-path123) and
                              (curEdge.p2==self.nodes.index(vNext))) ):
                            found=1
                            vNextIndex=vNext.adjacentNodes[j]
                            vNext=self.nodes[vNextIndex]
                            
                            if path123==1:
                                v.p1=v.p1+1
                                v.path1.append(vNextIndex)
                            if path123==2:
                                v.p2=v.p2+1
                                v.path2.append(vNextIndex)
                            if path123==3:
                                v.p3=v.p3+1
                                v.path3.append(vNextIndex)
                        j=j+1
                        #-------------------------------------------------------------------------
                        
                        
                        #-------------------------------------------------------------------------
    def traverse(self,label,v,count):
        for j in range(0,len(v.adjacentEdges)):
            curEdge=self.edges[v.adjacentEdges[j]]
            curLabel=curEdge.label
            if ( ((curLabel==-label) and 
                  (curEdge.p1==self.nodes.index(v))) or
                 ((curLabel==label) and
                  (curEdge.p2==self.nodes.index(v))) ):
                vNextIndex=v.adjacentNodes[j]
                vNext=self.nodes[vNextIndex]
                count=count+1
                count=self.traverse(label,vNext,count)
        return count
        #-------------------------------------------------------------------------
        
        
        #-------------------------------------------------------------------------
    def Schnyder(self):
        # we need to compute p1, p2, p3 and t1, t2, t3 and
        # r1, r2, r3 for each vertex
    
        # Initialize the data
        for i in range(0,len(self.nodes)):
            tempnn1=self.nodes[i]
            tempnn1.p1=0
            tempnn1.p2=0
            tempnn1.p3=0
            tempnn1.t1=0
            tempnn1.t2=0
            tempnn1.t3=0
            tempnn1.r1=0
            tempnn1.r2=0
            tempnn1.r3=0
            tempnn1.xsch=0
            tempnn1.ysch=0
            tempnn1.path1=[]
            tempnn1.path2=[]
            tempnn1.path3=[]
            
            # find those for v1, v2, and vn
        v1=self.nodes[self.indexV1]
        v2=self.nodes[self.indexV2]
        vn=self.nodes[self.indexVn]
        v1.t1=0; v1.t2=1; v1.t3=1;
        v2.t1=1; v2.t2=0; v2.t3=1;
        vn.t1=1; vn.t2=1; vn.t3=0;
        v1.p1=0; vn.p1=1;
        v2.p2=0; vn.p2=1;
        
        v1.xsch=len(self.nodes)-1; v1.ysch=0;
        v2.xsch=0; v2.ysch=len(self.nodes)-1;
        vn.xsch=0; vn.ysch = 0;
        
        
        # can we get p1/p2/p3 while doing ordering or labelling???
        # Not really!!! We cannot get p3 easily
        
        # calculate p1, p2, p3 by going through path1, path2, path3
        self.calculateP(1)
        self.calculateP(2)
        self.calculateP(3)
        
        # calculate t1, t2, t3
        # exterior vertices are done in ordering
        # for each interior vertex v
        for i in range(0,len(self.nodes)):
            v=self.nodes[i]
            
            if (v.canOrder!=1 and v.canOrder!=2 and
                v.canOrder!=len(self.nodes)):
                # v is an interior vertex
                v.t1=self.traverse(1,v,1) # Itself is in the subtree
                v.t2=self.traverse(2,v,1) # Itself is in the subtree
                v.t3=self.traverse(3,v,1) # Itself is in the subtree
                
                # calculate r1, r2, r3
                # we need 3 vectors in each vertex to store the path 1,2,3
                # v.ri = ti of all vertices on P(i+1)+ti of all vertices on P(i-1)-ti
        for i in range(0,len(self.nodes)):
            v=self.nodes[i]
            
            if (v.canOrder!=1 and v.canOrder!=2 and
                v.canOrder!=len(self.nodes)):
                # v is an interior vertex
                v.r1=0; v.r2=0; v.r3=0;
                
                # r1
                for j in range(0,len(v.path2)):
                    onPath=self.nodes[v.path2[j]]
                    v.r1=v.r1+onPath.t1
                for j in range(0,len(v.path3)):
                    onPath=self.nodes[v.path3[j]]
                    v.r1=v.r1+onPath.t1
                v.r1=v.r1-v.t1
                
                # r2
                for j in range(0,len(v.path1)):
                    onPath=self.nodes[v.path1[j]]
                    v.r2=v.r2+onPath.t2
                for j in range(0,len(v.path3)):
                    onPath=self.nodes[v.path3[j]]
                    v.r2=v.r2+onPath.t2
                v.r2=v.r2-v.t2
                
                # r3
                for j in range(0,len(v.path1)):
                    onPath=self.nodes[v.path1[j]]
                    v.r3=v.r3+onPath.t3
                for j in range(0,len(v.path2)):
                    onPath=self.nodes[v.path2[j]]
                    v.r3=v.r3+onPath.t3
                v.r3=v.r3-v.t3
                
                
                # The coordinates of each vertex is (v'1, v'2), 
                # where v'i = ri - p(i-1)
                # exterior vertices are done in ordering
                # for each interior vertex v
        for i in range(0,len(self.nodes)):
            v=self.nodes[i]
            
            if (v.canOrder!=1 and v.canOrder!=2 and
                v.canOrder!=len(self.nodes)):
                # v is an interior vertex
                v.xsch=(v.r1-v.p3)
                v.ysch=(v.r2-v.p1)
                #-------------------------------------------------------------------------
                
                #+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
                
                
                #=============================================================================#
                # LOAD GRAPH
                
def load_graph(InGraph):

    if InGraph.Order()<3:
        return 0
        
    ccwOrderedEdges=planarity_test(InGraph)
    if not(ccwOrderedEdges):
        showinfo("Planarity Test", "Graph is NOT PLANAR!")
        return 0
        
    graph1=pe_Graph()
    
    i=0
    NodeIndex={}
    for v in InGraph.vertices:
        NodeIndex[v]=i
        i=i+1
        
    for i in range(0,InGraph.Order()):
        graph1.nodes.append(pe_Node(i,i))
        
    EdgeIndex={}
    for i in range(0,len(ccwOrderedEdges)):
        n1=NodeIndex[ccwOrderedEdges[i][0]]
        n2=NodeIndex[ccwOrderedEdges[i][1]]
        ccwOrderedEdges[i]=(n1,n2)
        EdgeIndex[(n1,n2)]=None
        
    i=0
    for e in ccwOrderedEdges:
        if EdgeIndex[e]==None:
            EdgeIndex[e]=i
            EdgeIndex[(e[1],e[0])]=i
            i=i+1
            p1=pe_Point(e[0],e[0])
            p2=pe_Point(e[1],e[1])
            tempe1=pe_Edge(e[0],e[1],p1,p2,1)
            graph1.edges.append(tempe1)
            
        graph1.nodes[e[0]].addEdge(EdgeIndex[e],e[1])
        
    return graph1
    #=============================================================================#
    
    
    
    #=============================================================================#
def FPP_PlanarCoords(G): # (2n-4)*(n-2) GRID
# Algorithm: 
# 1. Triangulate orginal graph
# 2. Canonical order all vertices
# 3. Initialize x,y coordinates and M for V1,V2, and V3
#                               v1.M={v1,v2,v3}
#                               v2.M={v2}
#                               v3.M={v2,v3}
# 4. In the canonical order, for each vertex
#       1. find the vertices on the outface in order
#       2. shift vertices in the subset M of Wp+1 and Wq
#       3. calculate the x,y coordinates of Vk+1
#       4. updating M for all the outface vertices
#                               wi.M=wi.M+{vk+1}  for i<=p
#                               vk+1.M=wp+1.M+{vk+1}
#                               wj.M=wj.M  for j>=q

    #-------------------------------------------------------------------------
    # LOAD GRAPH
    graph=load_graph(G)
    if graph==0: return 0
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 1.TRIANGULATION
    graph.triangulate()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 2.CANONICAL ORDERING
    graph.initOrder()
    graph.ordering()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 3+4. FPP 
    graph.FPP()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # COORDINATES
    G.xCoord={}
    G.yCoord={}
    n=len(graph.nodes)
    for i in range(0,n):
        G.xCoord[G.vertices[i]]=graph.nodes[i].xfpp*float(900/(2*n-4))+50
        G.yCoord[G.vertices[i]]=1000-(graph.nodes[i].yfpp*float(900/(n-2))+50)
    return 1
    #-------------------------------------------------------------------------
    
    #=============================================================================#
    
    
    
    #=============================================================================#
def Schnyder_PlanarCoords(G): # (n-1)*(n-1) GRID
# Algorithm: 
# 1. Triangulate orginal graph
# 2. Canonical order all vertices
# 3. Normal label interior edges of G to i->Ti (i=1,2,3)
# 4. Calculate for each interior vertex v
#              pathi : vertices on the i-path from v to v1, v2, or vn
#              pn : number of vertices on the i-path starting at v
#              ti : number of vertices in the subtree of Ti rooted at v
#              ri : number of vertices in region Ri(v) for v
# 5. Calculate barycentric representation for each v: vi'=ri - pi-1
#                                            v->(v1',v2',v3')/(n-1)
#    A barycentric representation of a graph G is 
#    an injective function v->(v1,v2,v3) that satisfies:
#      a.) v1+v2+v3=1 for all v
#      b.) for each edge (x,y) and each vertex z not x or y,
#          there is some k (k=1,2 or 3) such that xk < zk and yk < zk       

    #-------------------------------------------------------------------------
    # LOAD GRAPH
    graph=load_graph(G)
    if graph==0: return 0
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 1.TRIANGULATION
    graph.triangulate()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 2.CANONICAL ORDERING
    graph.initOrder()
    graph.ordering()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 3. EDGE LABELLING 
    graph.FPP() # outfaces
    graph.labelling()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # 4+5. Schnyder
    graph.Schnyder()
    #-------------------------------------------------------------------------
    
    
    #-------------------------------------------------------------------------
    # COORDINATES
    G.xCoord={}
    G.yCoord={}
    n=len(graph.nodes)
    for i in range(0,n):
        G.xCoord[G.vertices[i]]=graph.nodes[i].xsch*float(900/(n-1))+50
        G.yCoord[G.vertices[i]]=1000-(graph.nodes[i].ysch*float(900/(n-1))+50)
    return 1
    #-------------------------------------------------------------------------
    
    #=============================================================================#