src/salomeloader/graph.py

   1 #  Copyright (C) 2006-2008  CEA/DEN, EDF R&D
   2 #
   3 #  This library is free software; you can redistribute it and/or
   4 #  modify it under the terms of the GNU Lesser General Public
   5 #  License as published by the Free Software Foundation; either
   6 #  version 2.1 of the License.
   7 #
   8 #  This library is distributed in the hope that it will be useful,
   9 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 #  Lesser General Public License for more details.
  12 #
  13 #  You should have received a copy of the GNU Lesser General Public
  14 #  License along with this library; if not, write to the Free Software
  15 #  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 #
  17 #  See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 #
  19 # -*- coding: iso-8859-1 -*-
  20 #
  21 """
  22   This module contains graph utilities
  23
  24   Following functions : invert, reachable,InducedSubgraph,write_dot,display operate on a graph.
  25   A graph is an object G which supports following operations:
  26     - iteration on nodes (for n in G gives all nodes of the graph)
  27     - iteration on next nodes (for v in G[n] gives all next nodes of node n)
  28 """
  29
  30 import os
  31 from sets import Set
  32
  33 def invert(G):
  34   """Construit le graphe inverse de G en inversant les liens de voisinage"""
  35   I={}
  36   for n in G:
  37     I.setdefault(n,Set())
  38     for v in G[n]:
  39       I.setdefault(v,Set()).add(n)
  40   return I
  41
  42 def reachable(G,n):
  43   """Construit le set de noeuds atteignables depuis le noeud n
  44
  45      Le noeud n n'est pas dans le set retourné sauf en cas de boucles
  46      Ce cas n'est pas traité ici (limitation)
  47   """
  48   s=G[n]
  49   for v in G[n]:
  50     s=s|reachable(G,v)
  51   return s
  52
  53 def InducedSubgraph(V,G,adjacency_list_type=Set):
  54   """ Construit un sous graphe de G avec les noeuds contenus dans V  """
  55   def neighbors(x):
  56     for y in G[x]:
  57       if y in V:
  58         yield y
  59   return dict([(x,adjacency_list_type(neighbors(x))) for x in G if x in V])
  60
  61 def write_dot(stream,G):
  62   """Ecrit la representation (au format dot) du graphe G dans le fichier stream"""
  63   name="toto"
  64   stream.write('digraph %s {\nnode [ style="filled" ]\n' % name)
  65   for node in G :
  66     try:
  67       label = "%s:%s"% (node.name,node.__class__.__name__)
  68     except:
  69       label=str(node)
  70     color='green'
  71     stream.write('   %s [fillcolor="%s" label=< %s >];\n' % ( id(node), color, label))
  72   for src in G:
  73     for dst in G[src]:
  74       stream.write('   %s -> %s;\n' % (id(src), id(dst)))
  75   stream.write("}\n")
  76
  77 def display(G,suivi="sync"):
  78   """Affiche le graphe G avec l'outil dot"""
  79   f=file("graph.dot", 'w')
  80   write_dot(f,G)
  81   f.close()
  82   cmd="dot -Tpng graph.dot |display" + (suivi == "async" and "&" or "")
  83   os.system(cmd)
  84
  85
  86 def test():
  87   G={
  88   1:Set([2,3]),
  89   2:Set([4]),
  90   3:Set([5]),
  91   4:Set([6]),
  92   5:Set([6]),
  93   6:Set(),
  94   }
  95   display(G)
  96   I=invert(G)
  97   print reachable(G,2)
  98   print reachable(I,6)
  99   print reachable(G,2) & reachable(I,6)
 100
 101 if __name__ == "__main__":
 102   test()