################################################################################ # # 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.22 $ # from $Date: 2006/09/03 14:44:11 $ # last change by $Author: schliep $. # ################################################################################ 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 nmax_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()]