src/salomeloader/graph.py

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