]> SALOME platform Git repositories - modules/yacs.git/blob - src/salomeloader/graph.py
Salome HOME
Deleted deprecated code
[modules/yacs.git] / 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()