GraphCreator.py :  » Development » Leo » Leo-4.7.1-final » leo » extensions » Gato » Python Open Source

Home
Python Open Source
1.3.1.2 Python
2.Ajax
3.Aspect Oriented
4.Blog
5.Build
6.Business Application
7.Chart Report
8.Content Management Systems
9.Cryptographic
10.Database
11.Development
12.Editor
13.Email
14.ERP
15.Game 2D 3D
16.GIS
17.GUI
18.IDE
19.Installer
20.IRC
21.Issue Tracker
22.Language Interface
23.Log
24.Math
25.Media Sound Audio
26.Mobile
27.Network
28.Parser
29.PDF
30.Project Management
31.RSS
32.Search
33.Security
34.Template Engines
35.Test
36.UML
37.USB Serial
38.Web Frameworks
39.Web Server
40.Web Services
41.Web Unit
42.Wiki
43.Windows
44.XML
Python Open Source » Development » Leo 
Leo » Leo 4.7.1 final » leo » extensions » Gato » GraphCreator.py
################################################################################
#
#       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()]
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.