Source Code for Module teamwork.widgets.fsa

  1  # Natural Language Toolkit: Finite State Automota Visualization 
  2  # 
  3  # Copyright (C) 2001 University of Pennsylvania 
  4  # Author: Edward Loper <edloper@gradient.cis.upenn.edu> 
  5  # 
  6  # URL: <http://nltk.sf.net> 
  7  # For license information, see LICENSE.TXT 
  8  # 
  9  # $Id: fsa.py 2455 2007-03-02 00:23:07Z pynadath $ 
 10   
 11  """ 
 12  Graphically display a finite state automaton. 
 13   
 14  This module may be renamed to nltk.draw.graph at some point in the 
 15  future, since it actually supports arbitrary graphs. 
 16  """ 
 17   
 18  import math 
 19  from bigwidgets import * 
 20  from teamwork.shell.PsychShell import * 
 21   
 22  #from teamwork.examples.PsychSim.PsychScenario import * 
 23   
 24  # from nltk.draw import * 
 25   
 26 -class GraphEdgeWidget(CanvasWidget): 
 27      """ 
 28      Display an edge of a graph. 
 29      """ 
 30 -    def __init__(self, canvas, x1, y1, x2, y2, label=None, **attribs): 
 31          self._curve = 0 
 32          coords = self._line_coords((x1, y1), (x2, y2)) 
 33          self._line = canvas.create_line(arrow='last', smooth=1, *coords) 
 34          canvas.lower(self._line) 
 35          self._label = label 
 36          if label is not None: 
 37              self._add_child_widget(label) 
 38   
 39          CanvasWidget.__init__(self, canvas, **attribs) 
 40   
 41 -    def __setitem__(self, attr, value): 
 42          if attr == 'curve': 
 43              self._curve = value 
 44              coords = self._line_coords(self.start(), self.end()) 
 45              self.canvas().coords(self._line, *coords) 
 46          elif attr == 'color': 
 47              self.canvas().itemconfig(self._line, fill=value) 
 48          elif attr == 'width': 
 49              self.canvas().itemconfig(self._line, width=value) 
 50          else: 
 51              CanvasWidget.__setitem__(self, attr, value) 
 52           
 53 -    def __getitem__(self, attr): 
 54          if attr == 'curve': 
 55              return self._curve 
 56          elif attr == 'color': 
 57              return self.canvas().itemcget(self._line, fill) 
 58          elif attr == 'width': 
 59              return self.canvas().itemcget(self._line, width) 
 60          else: 
 61              return CanvasWidget.__getitem__(self, attr) 
 62   
 63 -    def _tags(self): return [self._line] 
 64   
 65 -    def start(self): 
 66          return self.canvas().coords(self._line)[:2] 
 67       
 68 -    def end(self): 
 69          return self.canvas().coords(self._line)[-2:] 
 70   
 71 -    def set_start(self, x, y): 
 72          coords = self._line_coords((x, y), self.end()) 
 73          self.canvas().coords(self._line, *coords) 
 74          self.update(self._label) 
 75   
 76 -    def set_end(self, x, y): 
 77          coords = self._line_coords(self.start(), (x, y)) 
 78          self.canvas().coords(self._line, *coords) 
 79          self.update(self._label) 
 80   
 81 -    def _update(self, child): 
 82          # The label moved? 
 83          (x1, y1, x2, y2) = child.bbox() 
 84          (x, y) = self._label_coords() 
 85          child.move(x-(x1+x2)/2, y-(y1+y2)/2) 
 86   
 87 -    def _manage(self): 
 88          if self._label is not None: 
 89              self._update(self._label) 
 90   
 91 -    def _label_coords(self): 
 92          line_coords = self.canvas().coords(self._line) 
 93          (x1, y1) = line_coords[:2] 
 94          (x2, y2) = line_coords[-2:] 
 95          if (x1, y1) == (x2, y2): 
 96              # Self-loops.  Emperically, this formula seems about 
 97              # right, but it wasn't derived mathmatically. 
 98              radius = 0 
 99              return (x1, y1 + 0.81*(150*self._curve+radius) + 10) 
100          elif self._curve >= 0: 
101              # Normal edges. 
102              r = max(math.sqrt((x1-x2)**2 + (y1-y2)**2), 1) 
103              labelx = (x1+x2)*0.5 + (y2-y1)*(self._curve*.6) 
104              labely = (y1+y2)*0.5 - (x2-x1)*(self._curve*.6) 
105              return (int(labelx), int(labely)) 
106          else: 
107              # Normal edges. 
108              r = max(math.sqrt((x1-x2)**2 + (y1-y2)**2), 1) 
109              labelx = (x1+x2)*0.5 + (y2-y1)*(self._curve/2 + 8/r) 
110              labely = (y1+y2)*0.5 - (x2-x1)*(self._curve/2 + 8/r) 
111              return (int(labelx), int(labely)) 
112       
113 -    def _line_coords(self, (startx, starty), (endx, endy)): 
114          (x1, y1) = (startx, starty) 
115          (x2, y2) = (endx, endy) 
116          radius1 = 0 
117          radius2 = 0 
118           
119          if (x1, y1) == (x2, y2): 
120              # Self-loops 
121              x3 = x1 - 70*self._curve - radius1 
122              y3 = y1 + 70*self._curve + radius1 
123              x4 = x1 
124              y4 = y1 + 140*self._curve + radius1 
125              x5 = x1 + 70*self._curve + radius1 
126              y5 = y1 + 70*self._curve + radius1 
127              return (int(x1), int(y1), int(x3), int(y3), int(x4), 
128                      int(y4), int(x5), int(y5), int(x1), int(y1)) 
129          else: 
130              # Normal edges. 
131              x3 = (x1+x2)*0.5 + (y2-y1)*self._curve 
132              y3 = (y1+y2)*0.5 - (x2-x1)*self._curve 
133              # Adjust endpoints so they end at the node perimeter. 
134              r = max(math.sqrt((x1-x2)**2 + (y1-y2)**2), 0.001) 
135              (dx, dy) = (x2-x1, y2-y1) 
136              x1 += dx/r * radius1 
137              y1 += dy/r * radius1 
138              x2 -= dx/r * radius2 
139              y2 -= dy/r * radius2 
140              return (int(x1), int(y1), int(x3), int(y3), int(x2), int(y2)) 
141           
142 -class GraphWidget(CanvasWidget): 
143      """ 
144      Connect nodes and GraphEdgeWidgets into a graph. 
145      """ 
146 -    def __init__(self, canvas, nodes, edges, **attrs): 
147          """ 
148          @type edges: C{dictionary} from (node, node) to label. 
149          """ 
150          self._nodes = nodes 
151          self._edges = edges 
152   
153          # Management parameters.  I should add attributes for these.  
154          self._arrange = 'bfs' 
155          self._xspace = 150 
156          self._yspace = 250 
157          self._orientation = 'vertical' 
158   
159          # Attributes for edges. 
160   
161          # Out & in edges for a given node 
162          self._outedges = {} 
163          self._inedges = {} 
164   
165          # Start & end nodes for a given edge. 
166          self._startnode = {} 
167          self._endnode = {} 
168   
169          # Keep track of edge widgets. 
170          self._edgewidgets = {} 
171   
172          for node in self._nodes: 
173              self._add_child_widget(node) 
174          for (start, end, edgewidget) in self._edges: 
175              curve = 0.2 * (1+len(self._edgewidgets.get( (start, end), []))) 
176              edgewidget['curve'] = curve 
177   
178              # Add the edge to the outedge & inedge dictionaries 
179              self._outedges.setdefault(start, []).append(edgewidget) 
180              self._inedges.setdefault(end, []).append(edgewidget) 
181   
182              self._startnode[edgewidget] = start 
183              self._endnode[edgewidget] = end 
184                   
185              self._edgewidgets.setdefault((start, end),[]).append(edgewidget) 
186              self._add_child_widget(edgewidget) 
187   
188          CanvasWidget.__init__(self, canvas, **attrs) 
189   
190 -    def _tags(self): return [] 
191   
192 -    def _update(self, child): 
193          """ 
194          Make sure all edges/nodes are connected correctly. 
195          """ 
196          if isinstance(child, GraphEdgeWidget): 
197              # Moved an edge. 
198              pass 
199          else: 
200              (x1, y1, x2, y2) = child.bbox() 
201              x = (x1+x2)/2 
202              y = (y1+y2)/2 
203               
204              # Moved a node. 
205              for outedge in self._outedges.get(child, []): 
206                  outedge.set_start(x, y) 
207              for inedge in self._inedges.get(child, []): 
208                  inedge.set_end(x, y) 
209   
210 -    def _manage(self): 
211          self.arrange() 
212   
213      ##//////////////////////// 
214      ##  Graph Layout 
215      ##//////////////////////// 
216 -    def arrange(self, arrange_algorithm=None): 
217          """ 
218          Set the node positions.  This routine should attempt to 
219          minimize the number of crossing edges, in order to make the 
220          graph easier to read. 
221          """ 
222          if arrange_algorithm is not None: 
223              self._arrange = arrange_algorithm 
224               
225          self._arrange_into_levels() 
226          self._arrange_levels() 
227   
228          (old_left, old_top) = self.bbox()[:2] 
229          for node in self._nodes: 
230              (x1, y1) = node.bbox()[:2] 
231              node.move(-x1, -y1) 
232   
233          # Now we want to minimize crossing edges.. how, again? :) 
234          for i in range(len(self._levels)): 
235              for j in range(len(self._levels[i])): 
236                  if self._levels[i][j] is not None: 
237                      if self._orientation == 'horizontal': 
238                          self._levels[i][j].move(i*self._xspace, 
239                                                  j*self._yspace) 
240                      else: 
241                          self._levels[i][j].move(j*self._xspace, 
242                                                  i*self._yspace) 
243   
244          (left, top) = self.bbox()[:2] 
245          self.move(int(old_left-left), int(old_top-top)) 
246   
247 -    def _arrange_levels(self): 
248          """ 
249          Re-arrange each level to (locally) minimize the number of 
250          crossing edges. 
251          """ 
252          # For now, put nodes with more incoming edges further down. 
253          for levelnum in range(len(self._levels)): 
254              self._arrange_level(levelnum) 
255  ##        for level in self._levels: 
256  ##            level.sort(lambda n1,n2:cmp(len(n1.incoming()), len(n2.incoming()))) 
257   
258 -    def _arrange_level(self, levelnum): 
259          """ 
260          Arrange a given level..  This algorithm is simple and pretty 
261          heuristic.. 
262          """ 
263          if levelnum == 0: return 
264   
265          # For each position where we might want to put a node, create 
266          # a scores dictionary, mapping candidate nodes to scores.  We 
267          # will then use these scores to distribute nodes to level positions. 
268          scores = [{} for i in range(max(len(self._levels[levelnum]), 
269                                         len(self._levels[levelnum-1])))] 
270          for node in self._levels[levelnum]: 
271              # All else being equal, put nodes with more incoming 
272              # connections towards the end (=bottom) of the level. 
273              for pos in range(len(scores)): 
274                  scores[pos][node] = 1.0/len(self._inedges.get(node, [])) 
275                   
276              # Try to put a node at level position x if nodes 
277              # in previous levels at position x point to it. 
278              for edge in self._inedges.get(node, []): 
279                  from_node = self._startnode[edge] 
280                  from_levelnum = self._nodelevel[from_node] 
281                  if from_levelnum < levelnum: 
282                      from_pos = self._levels[from_levelnum].index(from_node) 
283                      score = (scores[from_pos].get(node, 0) + 1.0 / 
284                               (levelnum - from_levelnum)) 
285                      scores[from_pos][node] = score 
286   
287          # Get the list of nodes that we need to fill in, and empty the 
288          # level. 
289          nodes = self._levels[levelnum] 
290          self._levels[levelnum] = [None] * len(scores) 
291          level = self._levels[levelnum] 
292   
293          # Fill in nodes, picking the best first.. 
294          while len(nodes) > 0: 
295              best = (None, None, -1) # node, position, score. 
296              for pos in range(len(scores)): 
297                  for (node, score) in scores[pos].items(): 
298                      if score > best[2] and level[pos] is None and node in nodes: 
299                          best = (node, pos, score) 
300                      elif (score == best[2] and pos<best[1] and 
301                          level[pos] is None and node in nodes): 
302                          # Put higher scores at lower level positions 
303                          best = (node, pos, score) 
304              nodes.remove(best[0]) 
305              level[best[1]] = best[0] 
306   
307 -    def _arrange_into_levels(self): 
308          """ 
309          Assign a level to each node. 
310          """ 
311          # Mapping from node to level. 
312          self._nodelevel = {} 
313          self._levels = [] 
314   
315          # Find any nodes that have no incoming edges; put all of these 
316          # in level 0. 
317          toplevel = [] 
318          for node in self._nodes: 
319              if len(self._inedges.get(node, [])) == 0: 
320                  toplevel.append(node) 
321                  self._nodelevel[node] = 0 
322   
323          # Expand all of their children. 
324          self._levels = [toplevel] 
325          self._add_descendants(toplevel, 1) 
326   
327          # If we didn't get all the nodes, we'll have to start picking 
328          # nodes that do have incoming transitions.  Pick the ones that 
329          # have the most reachable nodes.  (n.b., this implementation 
330          # isn't terribly efficient, but we dont' expect to be 
331          # displaying huge FSAs, so it should be ok) 
332          while len(self._nodelevel) < len(self._nodes): 
333              expand_node = None 
334              max_reachable = -1 
335   
336              for node in self._nodes: 
337                  reachable = self._reachable(node) 
338                  if reachable >= max_reachable: 
339                      max_reachable = reachable 
340                      expand_node = node 
341               
342              # Expand the new node's children. 
343              self._levels[0].append(expand_node) 
344              self._nodelevel[expand_node] = 0 
345              self._add_descendants(toplevel, 1) 
346       
347 -    def _reachable(self, node, reached=None): 
348          """ 
349          How many *unexpanded* nodes can be reached from the given node? 
350          """ 
351          if self._nodelevel.has_key(node): return 0 
352          if reached is None: reached = {} 
353          if not reached.has_key(node): 
354              reached[node] = 1 
355              for edge in self._outedges.get(node, []): 
356                  self._reachable(self._endnode[edge], reached) 
357          return len(reached) 
358   
359 -    def _add_descendants(self, parent_level, levelnum): 
360          """ 
361          Add all the descendants of the nodes in the list parent_level 
362          to the structures self._level and self._nodelevel. 
363          """ 
364          if self._arrange == 'bfs': 
365              self._add_descendants_bfs(parent_level, levelnum) 
366          elif self._arrange == 'dfs': 
367              self._add_descendants_dfs(parent_level, levelnum) 
368          else: 
369              # Default to dfs 
370              self._add_descendants_dfs(parent_level, levelnum) 
371   
372 -    def _add_descendants_dfs(self, parent_level, levelnum): 
373          if levelnum >= len(self._levels): self._levels.append([]) 
374          for parent_node in parent_level: 
375              # Add the parent node 
376              if not self._nodelevel.has_key(parent_node): 
377                  self._levels[levelnum-1].append(parent_node) 
378                  self._nodelevel[parent_node] = levelnum-1 
379   
380              # Recurse to its children 
381              child_nodes = [self._endnode[edge] 
382                             for edge in self._outedges.get(parent_node, []) 
383                             if not self._nodelevel.has_key(self._endnode[edge])] 
384              if len(child_nodes) > 0: 
385                  self._add_descendants_dfs(child_nodes, levelnum+1) 
386   
387 -    def _add_descendants_bfs(self, parent_level, levelnum): 
388          frontier_nodes = [] 
389          if levelnum >= len(self._levels): self._levels.append([]) 
390          for parent_node in parent_level: 
391              child_nodes = [self._endnode[edge] 
392                             for edge in self._outedges.get(parent_node, [])] 
393              for node in child_nodes: 
394                  if not self._nodelevel.has_key(node): 
395                      self._levels[levelnum].append(node) 
396                      self._nodelevel[node] = levelnum 
397                      frontier_nodes.append(node) 
398          if len(frontier_nodes) > 0: 
399              self._add_descendants_bfs(frontier_nodes, levelnum+1) 
400   
401 -    def _add_descendants_bfs2(self, parent_level, levelnum): 
402          frontier_nodes = [] 
403          if levelnum >= len(self._levels): self._levels.append([]) 
404          for parent_node in parent_level: 
405              child_nodes = [self._endnode[edge] 
406                             for edge in self._outedges.get(parent_node, [])] 
407              child_nodes += [self._startnode[edge] 
408                             for edge in self._inedges.get(parent_node, [])] 
409              for node in child_nodes: 
410                  if not self._nodelevel.has_key(node): 
411                      self._levels[levelnum].append(node) 
412                      self._nodelevel[node] = levelnum 
413                      frontier_nodes.append(node) 
414          if len(frontier_nodes) > 0: 
415              self._add_descendants_bfs2(frontier_nodes, levelnum+1) 
416   
417   
418   
419  ##////////////////////////////////////////////////////// 
420  ##  Test code. 
421  ##////////////////////////////////////////////////////// 
422   
423 -def fsawindow(fsa): 
424      import random 
425      def manage(cw): cw.manage() 
426      def changetext(cw): 
427          from random import randint 
428          cw.set_text(5*('%d' % randint(0,999999))) 
429       
430      cf = CanvasFrame(width=300, height=300) 
431      c = cf.canvas() 
432   
433      nodes = {} 
434      for state in fsa.states(): 
435          if state in fsa.finals(): color = 'red3' 
436          else: color='green3' 
437          nodes[state] = StackWidget(c, TextWidget(c, `state`), 
438                                     OvalWidget(c, SpaceWidget(c, 12, 12), 
439                                                fill=color, margin=0)) 
440   
441      edges = [] 
442      for (s1, tlabels, s2) in fsa.transitions(): 
443          for tlabel in tlabels.elements(): 
444              if tlabel is None: 
445                  label = SymbolWidget(c, 'epsilon', color='gray40') 
446                  edge = GraphEdgeWidget(c, 0,0,0,0, label, color='gray50') 
447              else: 
448                  label = TextWidget(c, str(tlabel), color='blue4') 
449                  edge = GraphEdgeWidget(c, 0,0,0,0, label, color='cyan4') 
450              edges.append( (nodes[s1], nodes[s2], edge) ) 
451   
452      for node in nodes.values(): 
453          node['draggable'] = 1 
454   
455      graph = GraphWidget(c, nodes.values(), edges, draggable=1) 
456      graph.bind_click(manage) 
457      cf.add_widget(graph, 20, 20) 
458   
459      return nodes, graph 
460   
461   
462   
463   
464  # Test 
465