src/salomeloader/graph.py

   1 # -*- coding: iso-8859-1 -*-
   2 """
   3   This module contains graph utilities
   4
   5   Following functions : invert, reachable,InducedSubgraph,write_dot,display operate on a graph.
   6   A graph is an object G which supports following operations:
   7     - iteration on nodes (for n in G gives all nodes of the graph)
   8     - iteration on next nodes (for v in G[n] gives all next nodes of node n)
   9 """
  10
  11 import os
  12 from sets import Set
  13
  14 def invert(G):
  15   """Construit le graphe inverse de G en inversant les liens de voisinage"""
  16   I={}
  17   for n in G:
  18     I.setdefault(n,Set())
  19     for v in G[n]:
  20       I.setdefault(v,Set()).add(n)
  21   return I
  22
  23 def reachable(G,n):
  24   """Construit le set de noeuds atteignables depuis le noeud n
  25
  26      Le noeud n n'est pas dans le set retourné sauf en cas de boucles
  27      Ce cas n'est pas traité ici (limitation)
  28   """
  29   s=G[n]
  30   for v in G[n]:
  31     s=s|reachable(G,v)
  32   return s
  33
  34 def InducedSubgraph(V,G,adjacency_list_type=Set):
  35   """ Construit un sous graphe de G avec les noeuds contenus dans V  """
  36   def neighbors(x):
  37     for y in G[x]:
  38       if y in V:
  39         yield y
  40   return dict([(x,adjacency_list_type(neighbors(x))) for x in G if x in V])
  41
  42 def write_dot(stream,G):
  43   """Ecrit la representation (au format dot) du graphe G dans le fichier stream"""
  44   name="toto"
  45   stream.write('digraph %s {\nnode [ style="filled" ]\n' % name)
  46   for node in G :
  47     try:
  48       label = "%s:%s"% (node.name,node.__class__.__name__)
  49     except:
  50       label=str(node)
  51     color='green'
  52     stream.write('   %s [fillcolor="%s" label=< %s >];\n' % ( id(node), color, label))
  53   for src in G:
  54     for dst in G[src]:
  55       stream.write('   %s -> %s;\n' % (id(src), id(dst)))
  56   stream.write("}\n")
  57
  58 def display(G,suivi="sync"):
  59   """Affiche le graphe G avec l'outil dot"""
  60   f=file("graph.dot", 'w')
  61   write_dot(f,G)
  62   f.close()
  63   cmd="dot -Tpng graph.dot |display" + (suivi == "async" and "&" or "")
  64   os.system(cmd)
  65
  66
  67 def test():
  68   G={
  69   1:Set([2,3]),
  70   2:Set([4]),
  71   3:Set([5]),
  72   4:Set([6]),
  73   5:Set([6]),
  74   6:Set(),
  75   }
  76   display(G)
  77   I=invert(G)
  78   print reachable(G,2)
  79   print reachable(I,6)
  80   print reachable(G,2) & reachable(I,6)
  81
  82 if __name__ == "__main__":
  83   test()