1 # Copyright (C) 2006-2008 CEA/DEN, EDF R&D
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.
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.
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
17 # See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
19 # -*- coding: iso-8859-1 -*-
22 This module contains graph utilities
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)
34 """Construit le graphe inverse de G en inversant les liens de voisinage"""
39 I.setdefault(v,Set()).add(n)
43 """Construit le set de noeuds atteignables depuis le noeud n
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)
53 def InducedSubgraph(V,G,adjacency_list_type=Set):
54 """ Construit un sous graphe de G avec les noeuds contenus dans V """
59 return dict([(x,adjacency_list_type(neighbors(x))) for x in G if x in V])
61 def write_dot(stream,G):
62 """Ecrit la representation (au format dot) du graphe G dans le fichier stream"""
64 stream.write('digraph %s {\nnode [ style="filled" ]\n' % name)
67 label = "%s:%s"% (node.name,node.__class__.__name__)
71 stream.write(' %s [fillcolor="%s" label=< %s >];\n' % ( id(node), color, label))
74 stream.write(' %s -> %s;\n' % (id(src), id(dst)))
77 def display(G,suivi="sync"):
78 """Affiche le graphe G avec l'outil dot"""
79 f=file("graph.dot", 'w')
82 cmd="dot -Tpng graph.dot |display" + (suivi == "async" and "&" or "")
99 print reachable(G,2) & reachable(I,6)
101 if __name__ == "__main__":