This file is indexed.

/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)