/usr/share/pyshared/ferari/graph.py is in python-ferari 1.0.0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 | # Copyright (C) 2006 Robert C. Kirby
#
# This file is part of FErari.
#
# FErari is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# FErari is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with FErari. If not, see <http://www.gnu.org/licenses/>.
#
# First added: 2005-04-01
# Last changed: 2006-04-01
import copy, os
def argmin( a ):
"""a is a dictionary, returns the key for which the value
is minimal"""
am = a.keys()[0]
minval = a[a.keys()[0]]
for (k,ak) in a.iteritems():
if ak < minval:
am = k
minval = ak
return am
def prim( G ):
"""G is a dictionary whose keys are nodes in a graph. The values
are dictionaries mapping neighbors to (weight,label) pairs/
Returns a directed graph rooted at the first node in G"""
start = G.iterkeys().next()
weights = { start: 0 }
parents = { start: None }
done = set()
while weights:
u = argmin( weights )
weights.pop( u )
done.add( u )
for v in G[u]:
if v not in done:
if v not in weights or \
G[u][v][0] < weights[v]:
weights[v] = G[u][v][0]
parents[v] = (u,G[u][v][0],G[u][v][1])
pgraph = dict( [ (u,{}) for u in parents ] )
for u in parents:
if parents[u]: #not a root
(p,w,l) = parents[u]
pgraph[u][p] = (w,l)
return pgraph
def topsort( p ):
"""p is a digraph with nodes pointing from u to v if u depends on
v. We produce an ordering such that u comes after v. This is the
reverse of a typical topological sort."""
g = copy.deepcopy( p )
order = []
while g:
found_u = False
for u in g:
if len( g[u] ) == 0:
found_u = True
break
if not found_u:
raise RuntimeError, "not acyclic"
order.append( u )
for v in g:
if u in g[v]:
g[v].pop( u )
g.pop( u )
return order
def bfs( g ):
order = []
found = set()
Q = set()
u = g.iterkeys().next()
def bfs( g , start ):
"""returns a list that is a breadth-first ordering of the nodes of
g reachable from start"""
Q = [ start ]
found = set( (start,) )
done = set()
order = []
while Q:
u = Q.pop( 0 )
done.add( u )
order.append( u )
for v in g[u]:
if v not in found:
found.add( v )
Q.append( v )
return order
def connectedComponents( g ):
"""takes an undirected graph g and returns a list of graphs that are
the connected components."""
components = []
found = set()
while len( found ) != len( g ):
# pick a member of g that is not found yet
for u in g:
if u not in found:
break
order = bfs( g , u )
component_cur = dict( [ (v , g[v] ) for v in order ] )
found.update( order )
components.append( component_cur )
return components
def merge_disjoint( g1 , g2 ):
g3 = copy.deepcopy( g1 )
for u in g2:
if u in g3:
raise RuntimeError, "graphs not disjoint"
g3[u] = copy.deepcopy( g2[u] )
return g3
# mooched/modified from pygraphlib.
class Dot:
'''
A class that creates a B{graphviz} (dot language) representation
of the graph. To make use of the image generation features
If the C{dot} and C{dotty} programs must be either be in the
system path or their location needs to be specified in the
L{constructor<__init__>}. Download and install the graphviz
programs then either set the
See the L{pydot} module level documentation for
usage examples.
'''
def __init__(self, graph, name="G", dot='dot', dotty='dotty', neato='neato'):
self.graph = graph
self.temp_file = 'pydot_temp.dot'
self.name, self.style = name, {}
self.dot , self.dotty, self.neato = dot, dotty, neato
self.node_style, self.edge_style = {}, {}
def set_style(self, **kwargs):
'Changes the overall style'
self.style = kwargs
def set_node_style(self, node, **kwargs):
'Sets the style for a node.'
self.node_style[node] = kwargs
def set_all_node_style(self, **kwargs):
'Sets the styles for all nodes'
for node in self.graph:
self.set_node_style(node, **kwargs)
def set_edge_style(self, head, tail, **kwargs):
'Sets the stye for a single edge'
key1, key2 = (head, tail), (tail, head)
self.edge_style.setdefault(key1, kwargs).update(kwargs)
def set_all_edge_style(self, **kwargs):
'Sets the styles for all edges'
for u in self.graph:
for v in self.graph[u]:
self.set_edge_style(u,v, **kwargs)
def save_dot(self, file_name=None):
'Saves the current graph represenation as a C{dot} file '
if not file_name:
file_name = self.temp_file
fp = open(file_name, "w")
header = "digraph %s {\n" % self.name
fp.write(header)
# write overall graph style
for attr_name, attr_value in self.style.items():
fp.write('%s="%s"; ' % (attr_name, attr_value))
fp.write("\n")
# shortcuts to some reusable patterns
beg_patt = '\t"%s" [' # to begin attributes
mid_patt = '"%s"="%s",' # to write attributes
end_patt = '];\n' # to end attributes
edg_patt = '\t"%s" -> "%s" [' # to begin edges
# write the node attributes
for node in self.graph:
fp.write( beg_patt % (node,))
if self.node_style.has_key(node):
for attr_name, attr_value in self.node_style[node].items():
fp.write(mid_patt % (attr_name, attr_value))
fp.write(end_patt)
seen = {}
# write edge attributes
for u in self.graph:
for v in self.graph[u]:
edge = (u, v)
fp.write(edg_patt % edge )
if self.edge_style.has_key(edge):
for attr_name, attr_value in self.edge_style[edge].items():
fp.write(mid_patt % (attr_name, attr_value))
fp.write(end_patt)
fp.write("}\n")
fp.close()
def show(self):
'Displays the current graph via dotty'
self.save_dot(self.temp_file)
show_cmd = "%s %s&" % (self.dotty, self.temp_file)
os.system(show_cmd)
def save_image(self, file_name="out", mode="gif"):
'Saves the dot file as an image file'
self.save_dot(self.temp_file)
save_cmd = "%s -T%s %s -o %s" % (self.dot, mode, self.temp_file, file_name)
os.system(save_cmd)
|