################################################################################
#
# This file is part of Gato (Graph Animation Toolbox)
# You can find more information at
# http://gato.sf.net
#
# file: Embedder.py
# author: Ramazan Buzdemir
#
# 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.25 $
# from $Date: 2006/09/03 14:44:10 $
# last change by $Author: schliep $.
#
################################################################################
from GatoGlobals import *
class Embedder:
""" This class provides an abstract Embedder as
a base for actual Embedder implementations """
def Name(self):
""" Return a short descriptive name for the embedder e.g. usable as
a menu item """
return "none"
def Embed(self, theGraphEditor):
""" Compute the Embedding. Changed display through theGraphEditor.
Return value != none designates error/warning message """
return none
def RedrawGraph(theGraphEditor):
theGraphEditor.SetGraphMenuGrid(0)
for v in theGraphEditor.G.vertices:
theGraphEditor.MoveVertex(v, theGraphEditor.G.xCoord[v],
theGraphEditor.G.yCoord[v], 1)
#----------------------------------------------------------------------
import random
def RandomCoords(G):
G.xCoord={}
G.yCoord={}
for v in G.vertices:
G.xCoord[v]=random.randint(10,990)
G.yCoord[v]=random.randint(10,990)
return 1
class RandomEmbedder(Embedder):
def Name(self):
return "Randomize Layout"
def Embed(self, theGraphEditor):
if theGraphEditor.G.Order()==0:
return
theGraphEditor.config(cursor="watch")
theGraphEditor.update()
if RandomCoords(theGraphEditor.G):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
#----------------------------------------------------------------------
from math import pi, sin, cos
def CircularCoords(G):
G.xCoord={}
G.yCoord={}
distance = 2*pi/G.Order()
degree = 0
xMiddle=500; yMiddle=500; radius=450
for v in G.vertices:
G.xCoord[v]=radius*cos(degree)+xMiddle
G.yCoord[v]=radius*sin(degree)+yMiddle
degree=degree+distance
return 1
class CircularEmbedder(Embedder):
def Name(self):
return "Circular Layout"
def Embed(self, theGraphEditor):
if theGraphEditor.G.Order()==0:
return
theGraphEditor.config(cursor="watch")
theGraphEditor.update()
if CircularCoords(theGraphEditor.G):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
#----------------------------------------------------------------------
from PlanarEmbedding import *
class FPP_PlanarEmbedder(Embedder):
def Name(self):
return "Planar Layout (FPP)"
def Embed(self, theGraphEditor):
theGraphEditor.config(cursor="watch")
theGraphEditor.update()
if theGraphEditor.G.Order()==0:
return
if FPP_PlanarCoords(theGraphEditor.G):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
class Schnyder_PlanarEmbedder(Embedder):
def Name(self):
return "Planar Layout (Schnyder)"
def Embed(self, theGraphEditor):
if theGraphEditor.G.Order()==0:
return
theGraphEditor.config(cursor="watch")
theGraphEditor.update()
if Schnyder_PlanarCoords(theGraphEditor.G):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
#----------------------------------------------------------------------
from Tkinter import *
import tkSimpleDialog
import string
from tkMessageBox import showwarning
from DataStructures import Stack
"""
def center(G):
# Floyd-Algorithm
INFTY=9999999
dist={}
for v in G.vertices:
for w in G.vertices:
if w in G.InOutNeighbors(v):
dist[v,w]=1
elif v==w:
dist[v,w]=0
else:
dist[v,w]=INFTY
for u in G.vertices:
for v in G.vertices:
for w in G.vertices:
if dist[v,u]+dist[u,w]<dist[v,w]:
dist[v,w]=dist[v,u]+dist[u,w]
max1=INFTY
center=G.vertices[0]
for u in G.vertices:
max2=0
for v in G.vertices:
if dist[u,v]>max2:
max2=dist[u,v]
if max2<max1:
center=u
max1=max2
return center
"""
class TreeLayoutDialog(tkSimpleDialog.Dialog):
def __init__(self, master):
self.G = master.G
tkSimpleDialog.Dialog.__init__(self, master, "Tree Layout")
def body(self, master):
self.resizable(0,0)
self.root=StringVar()
self.root.set(self.G.vertices[0])
#self.root.set(center(self.G))
label = Label(master, text="root :", anchor=W)
label.grid(row=0, column=0, padx=0, pady=2, sticky="w")
entry=Entry(master, width=6, exportselection=FALSE,textvariable=self.root)
entry.selection_range(0,"end")
entry.focus_set()
entry.grid(row=0,column=1, padx=2, pady=2, sticky="w")
self.orientation=StringVar()
self.orientation.set("vertical")
radio=Radiobutton(master, text="vertical", variable=self.orientation,
value="vertical")
radio.grid(row=0, column=2, padx=2, pady=2, sticky="w")
radio=Radiobutton(master, text="horizontal", variable=self.orientation,
value="horizontal")
radio.grid(row=1, column=2, padx=2, pady=2, sticky="w")
def validate(self):
try:
if (string.atoi(self.root.get())<0 or
string.atoi(self.root.get()) not in self.G.vertices):
raise rootError
self.result=[]
self.result.append(string.atoi(self.root.get()))
self.result.append(self.orientation.get())
return self.result
except:
showwarning("Warning",
"Invalid root !!!\n"
"Please try again !")
return 0
def TreeCoords(G, root, orientation):
S = Stack()
visited = {}
d = {}
leaves = []
number_of_leaves = 0
height = 0
nodes = {}
children = {}
father = {}
for v in G.vertices:
visited[v] = 0
visited[root] = 1
S.Push(root)
d[root] = 0
nodes[0] = []
children[root] = []
father[root] = None
while S.IsNotEmpty():
v = S.Pop()
if orientation=="vertical":
nodes[d[v]].insert(0,v)
if v!=root: children[father[v]].insert(0,v)
else:
nodes[d[v]].append(v)
if v!=root: children[father[v]].append(v)
isleaf = 1
for w in G.InOutNeighbors(v):
if visited[w] == 0:
isleaf = 0
visited[w] = 1
d[w] = d[v] + 1
children[w] = []
father[w] = v
if d[w]>height:
height = d[w]
nodes[height] = []
S.Push(w)
if isleaf:
number_of_leaves = number_of_leaves + 1
if orientation=="vertical":
leaves.insert(0,v)
else:
leaves.append(v)
# Test whether the graph is connected and
# acyclic.(=test whether the graph is a tree)
for v in G.vertices:
if visited[v]==0:
showwarning("Warning",
"Graph is not a tree,\n"
"not connected !!!")
return 0
ch_len = len(children[v])
if v!=root: ch_len = ch_len + 1
if ch_len<len(G.InOutNeighbors(v)):
showwarning("Warning",
"Graph is not a tree,\n"
"contains cycles !!!")
return 0
if number_of_leaves<=19:
dist1 = 50
else:
dist1 = 900 / (number_of_leaves-1)
if height+1<=19:
dist2 = 50
else:
dist2 = 900 / height
if dist1<25 or dist2<30:
showwarning("Warning",
"Tree-Layout not possible,\n"
"the tree is too large !!!")
return 0
Coord1 = {}
Coord2 = {}
i = 0
for v in leaves:
Coord1[v] = 50 + i * dist1
Coord2[v] = 50 + d[v] * dist2
i = i + 1
i = height - 1
while i>=0:
for v in nodes[i]:
if children[v]!=[]:
Coord2[v] = 50 + d[v] * dist2
if len(children[v])==1:
Coord1[v] = Coord1[children[v][0]]
else:
Coord1[v] = ( Coord1[children[v][0]] +
(Coord1[children[v][-1]] -
Coord1[children[v][0]]) / 2)
i=i-1
if orientation=="vertical":
G.xCoord=Coord1
G.yCoord=Coord2
else:
G.xCoord=Coord2
G.yCoord=Coord1
return 1
class TreeEmbedder(Embedder):
def Name(self):
return "Tree Layout"
def Embed(self, theGraphEditor):
if theGraphEditor.G.Order()==0:
return
theGraphEditor.config(cursor="watch")
dial = TreeLayoutDialog(theGraphEditor)
if dial.result is None:
theGraphEditor.config(cursor="")
return
if TreeCoords(theGraphEditor.G, dial.result[0], dial.result[1]):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
#----------------------------------------------------------------------
from GraphUtil import BFS
class BFSLayoutDialog(tkSimpleDialog.Dialog):
def __init__(self, master):
self.G = master.G
tkSimpleDialog.Dialog.__init__(self, master, "BFS Layout")
def body(self, master):
self.resizable(0,0)
self.root=StringVar()
self.root.set(self.G.vertices[0])
label = Label(master, text="root :" , anchor=W)
label.grid(row=0, column=0, padx=0, pady=2, sticky="w")
entry=Entry(master, width=6, exportselection=FALSE,textvariable=self.root)
entry.selection_range(0,"end")
entry.focus_set()
entry.grid(row=0,column=1, padx=2, pady=2, sticky="w")
self.direction=StringVar()
self.direction.set("forward")
if self.G.QDirected():
radio=Radiobutton(master, text="forward", variable=self.direction,
value="forward")
radio.grid(row=0, column=2, padx=2, pady=2, sticky="w")
radio=Radiobutton(master, text="backward", variable=self.direction,
value="backward")
radio.grid(row=1, column=2, padx=2, pady=2, sticky="w")
def validate(self):
try:
if (string.atoi(self.root.get())<0 or
string.atoi(self.root.get()) not in self.G.vertices):
raise rootError
self.result=[]
self.result.append(string.atoi(self.root.get()))
self.result.append(self.direction.get())
return self.result
except:
showwarning("Warning",
"Invalid root !!!\n"
"Please try again !")
return 0
def BFSTreeCoords(G, root, direction):
BFSdistance = BFS(G,root,direction)[0]
maxDistance=0
maxBreadth=0
list = {}
for v in G.vertices:
list[BFSdistance[v]] = []
for v in G.vertices:
list[BFSdistance[v]].append(v)
maxDistance=len(list)
for d in list.values():
if len(d)>maxBreadth: maxBreadth=len(d)
if maxDistance > 1:
xDist=900/(maxDistance-1)
else:
xDist=0
if maxBreadth > 1:
yDist=900/(maxBreadth-1)
else:
yDist=0
Coord1=950
G.xCoord={}
G.yCoord={}
for d in list.values():
Coord2=500-(len(d)-1)*yDist/2
for v in d:
G.xCoord[v]=Coord1+random.randint(-20,20)
G.yCoord[v]=Coord2
Coord2=Coord2+yDist
Coord1=Coord1-xDist
return 1
class BFSTreeEmbedder(Embedder):
def Name(self):
return "BFS-Tree Layout"
def Embed(self, theGraphEditor):
if theGraphEditor.G.Order()==0:
return
theGraphEditor.config(cursor="watch")
dial = BFSLayoutDialog(theGraphEditor)
if dial.result is None:
theGraphEditor.config(cursor="")
return
if BFSTreeCoords(theGraphEditor.G, dial.result[0], dial.result[1]):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
from math import *
from DataStructures import Queue
def RadialTreeBFS(G,root,direction='forward'):
""" Calculate BFS distances and predecessor without showing animations.
Also compute angles for a radial layout
If G is directed, direction does matter:
- 'forward' BFS will use outgoing edges
- 'backward' BFS will use incoming edges
It uses gInfinity (from GatoGlobals.py) as infinite distance.
returns (dist,pred) """
Q = Queue()
d = {}
pred = {}
angle = {}
childrenrange = {}
for v in G.vertices:
d[v] = gInfinity
d[root] = 0
pred[root] = None
angle[root] = 0
childrenrange[root] = (0, 2 * pi)
Q.Append(root)
while Q.IsNotEmpty():
v = Q.Top()
if G.QDirected() == 1 and direction == 'backward':
nbh = G.InNeighbors(v)
else:
nbh = G.Neighborhood(v)
# Compute size of unseen Nbh
unseen = 0
for w in nbh:
if d[w] == gInfinity:
unseen += 1
if unseen > 0:
range = childrenrange[v][1] - childrenrange[v][0]
delta = range / float(unseen)
delta2 = delta * 0.5
left = childrenrange[v][0] + delta2
for w in nbh:
if d[w] == gInfinity:
angle[w] = left + delta2
childrenrange[w] = (left,left+delta)
left += delta
d[w] = d[v] + 1
#print (v,w), "angle = ", angle[w]," range = ", childrenrange[w]
Q.Append(w)
return (d,pred,angle)
def RadialToXY(degree, r, offset):
return (r*sin(degree) + offset[0], r*cos(degree) + offset[1])
def BFSRadialTreeCoords(G, root, direction):
(BFSdistance,pred,angle) = RadialTreeBFS(G,root,direction)
maxdist = max(max(BFSdistance.values()),1)
G.xCoord={}
G.yCoord={}
offset = (500,500)
d = 450 / maxdist
for v in G.vertices:
try:
(G.xCoord[v], G.yCoord[v]) = RadialToXY(angle[v], BFSdistance[v] * d, offset)
except:
return 0
return 1
class BFSRadialTreeEmbedder(Embedder):
def Name(self):
return "BFS-Radial Tree Layout"
def Embed(self, theGraphEditor):
if theGraphEditor.G.Order()==0:
return
theGraphEditor.config(cursor="watch")
dial = BFSLayoutDialog(theGraphEditor)
if dial.result is None:
theGraphEditor.config(cursor="")
return
if BFSRadialTreeCoords(theGraphEditor.G, dial.result[0], dial.result[1]):
RedrawGraph(theGraphEditor)
theGraphEditor.dirty = 1
theGraphEditor.config(cursor="")
#----------------------------------------------------------------------
""" Here instantiate all the embedders you want to make available to
a client. """
embedder = [RandomEmbedder(),
CircularEmbedder(),
FPP_PlanarEmbedder(),
Schnyder_PlanarEmbedder(),
TreeEmbedder(),
BFSTreeEmbedder(),
BFSRadialTreeEmbedder()]
syntax highlighted by Code2HTML, v. 0.9.1