python-ferari 1.0.0-1 / usr / share / pyshared / ferari / graph.py

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