################################################################################
#
#       This file is part of Gato (Graph Animation Toolbox) 
#
#	file:   GraphCreator.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.1 $ 
#                       from $Date: 2007/10/04 14:36:39 $
#             last change by $Author: edream $.
#
################################################################################

from Graph import *
from Embedder import *
import random
from tkMessageBox import askokcancel

class Creator:
    """ This class provides an abstract Creator as
        a base for actual Creator implementations """
    
    def Name(self):
        """ Return a short descriptive name for the creator e.g. usable as 
            a menu item """
        return "none"
        
    def Create(self, theGraphEditor):
        """ Create a new graph. """
        return none

    def CheckDirtyAndCreate(self, theGraphEditor):
        """ Create a new graph. """

        if theGraphEditor.dirty == 1:
            if not askokcancel("Open Graph",
                               "Graph changed since last saved. Do you want to overwrite it?"):
                return            
        self.Create(theGraphEditor)
        
        
def DrawNewGraph(theGraphEditor,G,direction):

    theGraphEditor.dirty = 0
    theGraphEditor.NewGraph(direction,1,0,'None',0,'One',0)
    
    for v in G.vertices:
        theGraphEditor.AddVertex(G.xCoord[v],G.yCoord[v])
        
    for e in G.Edges():
        theGraphEditor.AddEdge(e[0],e[1])
    theGraphEditor.dirty = 1
    
        
#----------------------------------------------------------------------
from Tkinter import *
import tkSimpleDialog 
import string
from tkMessageBox import showwarning

class Dialog(tkSimpleDialog.Dialog):

    def __init__(self, master, planar, visible, Text):
        self.planar=planar
        self.visible=visible
        tkSimpleDialog.Dialog.__init__(self, master, Text)
        
        
    def body(self, master):
        self.resizable(0,0)
        
        self.number_of_nodes=StringVar()
        self.number_of_nodes.set("1")
        label = Label(master, text="number of nodes :", anchor=W)
        label.grid(row=0, column=0, padx=0, pady=2, sticky="w")
        entry=Entry(master, width=6, exportselection=FALSE,
                    textvariable=self.number_of_nodes)
        entry.selection_range(0,1)
        entry.focus_set()
        entry.grid(row=0,column=1, padx=2, pady=2, sticky="w")
        
        self.number_of_edges=StringVar()
        self.number_of_edges.set("0")
        if self.visible:
            label = Label(master, text="number of edges :", anchor=W)
            label.grid(row=1, column=0, padx=0, pady=2, sticky="w")
            entry=Entry(master, width=6, exportselection=FALSE,
                        textvariable=self.number_of_edges)
            entry.selection_range(0,1)
            entry.focus_set()
            entry.grid(row=1,column=1, padx=2, pady=2, sticky="w")
            
        self.direction=IntVar()
        self.direction.set(0)
        radio=Radiobutton(master, text="Undirected", variable=self.direction,
                          value=0)
        radio.grid(row=0, column=2, padx=2, pady=2, sticky="w") 
        radio=Radiobutton(master, text="Directed", variable=self.direction,
                          value=1)
        radio.grid(row=1, column=2, padx=2, pady=2, sticky="w")
        
        label = Label(master, text=" ")
        label.grid(row=0, column=3, padx=5, pady=2) 
        
        self.layout=IntVar()
        self.layout.set(0)
        radio=Radiobutton(master, text="Randomize Layout",
                          variable=self.layout, value=0,
                          width=23, indicatoron=0, selectcolor="white")
        radio.grid(row=0, column=4, padx=3, pady=2, sticky="w")  
        radio=Radiobutton(master, text="Circular Layout",
                          variable=self.layout, value=1,
                          width=23, indicatoron=0, selectcolor="white")
        radio.grid(row=1, column=4, padx=3, pady=2, sticky="w") 
        if self.planar:
            radio=Radiobutton(master, text="Planar Layout (FPP)",
                              variable=self.layout, value=2,
                              width=23, indicatoron=0, selectcolor="white")
            radio.grid(row=3, column=4, padx=3, pady=2, sticky="w") 
            radio=Radiobutton(master, text="Planar Layout (Schnyder)",
                              variable=self.layout, value=3,
                              width=23, indicatoron=0, selectcolor="white")
            radio.grid(row=4, column=4, padx=3, pady=2, sticky="w")
            
    def validate(self):
        try:
            n=string.atoi(self.number_of_nodes.get())
            if n<1 or n>200:
                raise nodeError
        except:
            showwarning("Please try again !",
                        "min. number of nodes = 1\n" 
                        "max. number of nodes = 200")
            return 0            
            
        try:
            m=string.atoi(self.number_of_edges.get())
            
            if self.planar:
                if n==1: max_m=0
                else: max_m=6*n-12
            else:
                max_m=n*n-n
                
            if self.direction.get()==0:
                max_m = max_m/2
                
            if m<0 or m>max_m:
                raise edgeError
                
        except:
            showwarning("Please try again !",
                        "min. number of edges = 0\n"
                        "max. number of edges = %i" %max_m)
            return 0
            
        self.result=[]
        self.result.append(n)
        self.result.append(m)
        self.result.append(self.direction.get())
        self.result.append(self.layout.get())
        return self.result
        
        #----------------------------------------------------------------------
def CompleteEdges(G,n,direction):
    Edges=[]
    for i in range(0,n):
        source=G.vertices[i]
        for j in range(i+1,n):   
            target=G.vertices[j]
            Edges.append((source,target))
            if direction==1: Edges.append((target,source))
    return Edges
    
def MaximalPlanarEdges(G,n,direction):
    Edges=[] #6*n
    
    AdjEdges={}
    for v in G.vertices:
        AdjEdges[v]=[]
        
    index=0
    a=G.vertices[index]
    index=index+1
    b=G.vertices[index]
    index=index+1
    
    Edges.append((a,b))
    AdjEdges[a].append((a,b))
    Edges.append((b,a))
    AdjEdges[b].append((b,a))
    
    m=2
    while index < n:
        e=Edges[random.randint(0,m-1)]
        v=G.vertices[index]
        index=index+1
        
        while e[1]!=v:
            x=(v,e[0])
            Edges.append(x)
            m=m+1
            AdjEdges[v].append(x)
            
            y=(e[0],v)
            Edges.append(y)
            m=m+1
            AdjEdges[e[0]].insert(AdjEdges[e[0]].index(e)+1,y)
            
            index2=AdjEdges[e[1]].index((e[1],e[0]))
            if index2==0:
                e=AdjEdges[e[1]][-1]
            else:
                e=AdjEdges[e[1]][index2-1]
                
    if direction==0: # undirected
        m=m-1
        while m>0:
            del Edges[m]
            m=m-2
            
    return Edges
    
    #----------------------------------------------------------------------
class completeGraphCreator(Creator):

    def Name(self):
        return "Create Complete Graph" 
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        dial = Dialog(theGraphEditor, 0, 0, "Create Complete Graph")
        if dial.result is None:
            theGraphEditor.config(cursor="")	    
            return
        
        n=dial.result[0]
        direction=dial.result[2]
        layout=dial.result[3]
        
        G=Graph()
        G.directed=direction
        
        for v in range(0,n):
            G.AddVertex()
            
        Edges=CompleteEdges(G,n,direction)
        
        for e in Edges:
            G.AddEdge(e[0],e[1])
            
        if layout==0:
            if RandomCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        else:
            if CircularCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
                
        theGraphEditor.config(cursor="")
        
        #----------------------------------------------------------------------
class randomGraphCreator(Creator):

    def Name(self):
        return "Create Random Graph" 
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        dial = Dialog(theGraphEditor, 0, 1, "Create Random Graph")
        if dial.result is None:
            theGraphEditor.config(cursor="")
            return
            
        n=dial.result[0]
        m=dial.result[1]
        direction=dial.result[2]
        layout=dial.result[3]
        
        G=Graph()
        G.directed=direction
        
        for v in range(0,n):
            G.AddVertex()
            
        Edges=CompleteEdges(G,n,direction)
        
        for i in range(0,m):
            pos=random.randint(0,len(Edges)-1)
            G.AddEdge(Edges[pos][0],Edges[pos][1])
            del Edges[pos]
            
        if layout==0:
            if RandomCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        else:
            if CircularCoords(G):
                DrawNewGraph(theGraphEditor,G,direction) 
                
        theGraphEditor.config(cursor="")          
        
        #----------------------------------------------------------------------
class maximalPlanarGraphCreator(Creator):

    def Name(self):
        return "Create Maximal Planar Graph" 
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        dial = Dialog(theGraphEditor, 1, 0, "Create Maximal Planar Graph")
        if dial.result is None:
            theGraphEditor.config(cursor="")
            return
            
        n=dial.result[0]
        if n<=1: return
        direction=dial.result[2]
        layout=dial.result[3]
        
        G=Graph()
        G.directed=direction
        
        for v in range(0,n):
            G.AddVertex()
            
        Edges=MaximalPlanarEdges(G,n,direction)
        
        for e in Edges:
            G.AddEdge(e[0],e[1])
            
        if layout==0:
            if RandomCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        elif layout==1:
            if CircularCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        elif layout==2:
            if FPP_PlanarCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        else:
            if Schnyder_PlanarCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)  
                
        theGraphEditor.config(cursor="")
        
        #----------------------------------------------------------------------
from math import log10

class randomPlanarGraphCreator(Creator):

    def Name(self):
        return "Create Random Planar Graph" 
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        dial = Dialog(theGraphEditor, 1, 1, "Create Random Planar Graph")
        if dial.result is None:
            theGraphEditor.config(cursor="")
            return
            
        n=dial.result[0]
        if n<=1: return
        m=dial.result[1]
        direction=dial.result[2]
        layout=dial.result[3]
        
        G=Graph()
        G.directed=direction
        
        for v in range(0,n):
            G.AddVertex()
            
        Edges=MaximalPlanarEdges(G,n,direction)
        
        for i in range(0,m):
            pos=random.randint(0,len(Edges)-1)
            G.AddEdge(Edges[pos][0],Edges[pos][1])
            del Edges[pos]
            
        if layout==0:
            if RandomCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        elif layout==1:
            if CircularCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        elif layout==2:
            if FPP_PlanarCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)
        else:
            if Schnyder_PlanarCoords(G):
                DrawNewGraph(theGraphEditor,G,direction)   
                
        theGraphEditor.config(cursor="")         
        
        #----------------------------------------------------------------------
class TreeDialog(tkSimpleDialog.Dialog):

    def __init__(self, master, visible, Text):
        self.visible=visible
        tkSimpleDialog.Dialog.__init__(self, master, Text)
        
        
    def body(self, master):
        self.resizable(0,0)
        
        self.degree=StringVar()
        self.degree.set("2")
        label = Label(master, text="degree  :", anchor=W)
        label.grid(row=0, column=0, padx=0, pady=2, sticky="w")
        entry=Entry(master, width=6, exportselection=FALSE,
                    textvariable=self.degree)
        entry.selection_range(0,1)
        entry.focus_set()
        entry.grid(row=0,column=1, padx=2, pady=2, sticky="w")
        
        self.height=StringVar()
        self.height.set("0")
        label = Label(master, text="height   :", anchor=W)
        label.grid(row=1, column=0, padx=0, pady=2, sticky="w")
        entry=Entry(master, width=6, exportselection=FALSE,
                    textvariable=self.height)
        entry.selection_range(0,1)
        entry.focus_set()
        entry.grid(row=1,column=1, padx=2, pady=2, sticky="w")
        
        self.number_of_nodes=StringVar()
        self.number_of_nodes.set("1")
        if self.visible:
            label = Label(master, text="#nodes :", anchor=W)
            label.grid(row=2, column=0, padx=0, pady=2, sticky="w")
            entry=Entry(master, width=6, exportselection=FALSE,
                        textvariable=self.number_of_nodes)
            entry.selection_range(0,1)
            entry.focus_set()
            entry.grid(row=2,column=1, padx=2, pady=2, sticky="w")
            
        self.direction=IntVar()
        self.direction.set(0)
        radio=Radiobutton(master, text="Undirected", variable=self.direction,
                          value=0)
        radio.grid(row=0, column=2, padx=2, pady=2, sticky="w") 
        radio=Radiobutton(master, text="Directed", variable=self.direction,
                          value=1)
        radio.grid(row=1, column=2, padx=2, pady=2, sticky="w")
        
        label = Label(master, text=" ")
        label.grid(row=0, column=3, padx=5, pady=2) 
        
        self.layout=IntVar()
        self.layout.set(0)
        radio=Radiobutton(master, text="Randomize Layout",
                          variable=self.layout, value=0,
                          width=17, indicatoron=0, selectcolor="white")
        radio.grid(row=0, column=4, padx=3, pady=2, sticky="w") 
        radio=Radiobutton(master, text="Circular Layout",
                          variable=self.layout, value=1,
                          width=17, indicatoron=0, selectcolor="white")
        radio.grid(row=1, column=4, padx=3, pady=2, sticky="w")
        radio=Radiobutton(master, text="Tree Layout",
                          variable=self.layout, value=2,
                          width=17, indicatoron=0, selectcolor="white")
        radio.grid(row=2, column=4, padx=3, pady=2, sticky="w") 
        radio=Radiobutton(master, text="BFS-Tree Layout",
                          variable=self.layout, value=3,
                          width=17, indicatoron=0, selectcolor="white")
        radio.grid(row=3, column=4, padx=3, pady=2, sticky="w")
        
    def validate(self):
        try:
            d=string.atoi(self.degree.get())
            if d<1 or d>20:
                raise degreeError   
        except:
            showwarning("Please try again !",
                        "min. degree = 1\n"
                        "max. degree = 20")
            return 0
            
        try:
            h=string.atoi(self.height.get())
            if h<0 or h>50:
                raise heightError   
        except:
            showwarning("Please try again !",
                        "min. height = 0\n"
                        "max. height = 50")
            return 0
            
        try:
            n=string.atoi(self.number_of_nodes.get())
        except:
            showwarning("Invalid value !",
                        "Please enter an integer\n"
                        "value for #nodes !")
            return 0
            
        if self.visible:
            if n>1000:
                showwarning("Please try again !",
                            "max. #nodes = 1000")
                return 0
            min_nodes=h+1
            if d==1:
                max_nodes=h+1
            else:
                max_nodes=(float(d)**(h+1)-1)/float(d-1)
            if min_nodes>max_nodes:
                max_nodes=min_nodes
            if max_nodes>1000:
                max_nodes=1000
            if n<min_nodes or n>max_nodes:
                showwarning("Please try again !",
                            "min. #nodes = %i\n"
                            "max. #nodes = %i" %(min_nodes,max_nodes))
                return 0
        else:
            if d==1:
                max_height=100
            else:
                max_height=int(log10(1000)/log10(d))
            if h>max_height:
                showwarning("Please try again !",
                            "max. height = %i" %max_height)
                return 0
                
        self.result=[]
        self.result.append(d)
        self.result.append(h)
        self.result.append(n)
        self.result.append(self.direction.get())
        self.result.append(self.layout.get())
        return self.result
        
        #----------------------------------------------------------------------
class completeTreeCreator(Creator):

    def Name(self):
        return "Create Complete Tree"
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        dial = TreeDialog(theGraphEditor, 0, "Create Complete Tree")
        if dial.result is None:
            theGraphEditor.config(cursor="")
            return
            
        degree=dial.result[0]
        height=dial.result[1]
        direction=dial.result[3]
        layout=dial.result[4]
        
        G=Graph()
        G.directed=direction
        
        nodes={}
        nodes[0]=[]
        G.AddVertex()
        nodes[0].append(G.vertices[0])
        for h in range(0,height):
            nodes[h+1]=[]
            for v in nodes[h]:
                for d in range(0,degree):
                    new_v=G.AddVertex()
                    if direction==0: 
                        G.AddEdge(v,new_v)
                    else:
                        if random.randint(0,1):
                            G.AddEdge(v,new_v)
                        else:
                            G.AddEdge(new_v,v)
                    nodes[h+1].append(new_v)
                    
        if layout==0:
            if RandomCoords(G):
                DrawNewGraph(theGraphEditor,G,direction) 
        elif layout==1:
            if CircularCoords(G):
                DrawNewGraph(theGraphEditor,G,direction) 
        elif layout==2:
            if TreeCoords(G,G.vertices[0],"vertical"):
                DrawNewGraph(theGraphEditor,G,direction) 
        else:
            if BFSTreeCoords(G,G.vertices[0],"forward"):
                DrawNewGraph(theGraphEditor,G,direction) 
                
        theGraphEditor.config(cursor="")
        
        #----------------------------------------------------------------------
from math import ceil

class randomTreeCreator(Creator):

    def Name(self):
        return "Create Random Tree"
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        dial = TreeDialog(theGraphEditor, 1, "Create Random Tree")
        if dial.result is None:
            theGraphEditor.config(cursor="")
            return
            
        degree=dial.result[0]
        height=dial.result[1]
        n=dial.result[2]
        direction=dial.result[3]
        layout=dial.result[4]
        
        G=Graph()
        G.directed=direction
        
        nodes={}
        nodes[0]=[]
        new_v=G.AddVertex()
        nodes[0].append(new_v)
        children_nr={}
        children_nr[new_v]=0
        for h in range(0,height):
            nodes[h+1]=[]
            if degree==1:
                min_nodes=1
                max_nodes=1
            else:
                min_nodes=max(1,ceil(float(n-G.Order())/
                                     float((float(degree)**(height-h)-1)/
                                           (degree-1))))
                max_nodes=min(n-G.Order()-height+h+1,len(nodes[h])*degree)     
            nodes_nr=random.randint(min_nodes,max_nodes)
            for i in range(0,nodes_nr):
                pos=random.randint(0,len(nodes[h])-1)
                v=nodes[h][pos]
                children_nr[v]=children_nr[v]+1
                if children_nr[v]==degree:
                    del nodes[h][pos]
                new_v=G.AddVertex()
                children_nr[new_v]=0
                if direction==0:
                    G.AddEdge(v,new_v)
                else:
                    if random.randint(0,1):
                        G.AddEdge(v,new_v)
                    else:
                        G.AddEdge(new_v,v)
                nodes[h+1].append(new_v)
                
        if layout==0:
            if RandomCoords(G):
                DrawNewGraph(theGraphEditor,G,direction) 
        elif layout==1:
            if CircularCoords(G):
                DrawNewGraph(theGraphEditor,G,direction) 
        elif layout==2:
            if TreeCoords(G,G.vertices[0],"vertical"):
                DrawNewGraph(theGraphEditor,G,direction) 
        else:
            if BFSTreeCoords(G,G.vertices[0],"forward"):
                DrawNewGraph(theGraphEditor,G,direction) 
                
        theGraphEditor.config(cursor="")
        
        #----------------------------------------------------------------------
from math import ceil

class rectangularGridGraph(Creator):

    def Name(self):
        return "Create Rectangular Grid Graph"
        
    def Create(self, theGraphEditor):
        theGraphEditor.config(cursor="watch")
        
        
        print " FIXME XXX Dialog for #x, #y, delta_x, delta_y is missing"
        ##         dial = TreeDialog(theGraphEditor, 1, "create random tree")
        ##         if dial.result is None:
        ## 	    theGraphEditor.config(cursor="")
        ##             return
        
        G=Graph()
        G.directed=0
        G.xCoord={}
        G.yCoord={}
        
        maxI = 10
        maxJ = 8
        
        nodes = {}
        count = 1
        for i in xrange(maxI):
            for j in xrange(maxJ):
                v = G.AddVertex()
                nodes[(i,j)] = v
                G.xCoord[v] = j * 40 + 40
                G.yCoord[v] = i * 40 + 40
                count += 1
                
        for i in xrange(maxI-1):
            for j in xrange(maxJ-1):
                G.AddEdge(nodes[(i,j)], nodes[(i+1,j)])
                G.AddEdge(nodes[(i,j)], nodes[(i,j+1)])
            G.AddEdge(nodes[(i,maxJ-1)], nodes[(i+1,maxJ-1)])
        for  j in xrange(maxJ-1):
            G.AddEdge(nodes[(maxI-1,j)], nodes[(maxI-1,j+1)])
            
        DrawNewGraph(theGraphEditor,G,G.directed) 
        theGraphEditor.config(cursor="")
        
        #----------------------------------------------------------------------
        
""" Here instantiate all the creators you want to make available to
    a client."""
creator = [completeGraphCreator(),
           randomGraphCreator(),
           maximalPlanarGraphCreator(),
           randomPlanarGraphCreator(),
           completeTreeCreator(),
           randomTreeCreator(),
           rectangularGridGraph()]
