Subversion Repositories programming

#!/usr/bin/env python

__author__    = "Ira W. Snyder (devel@irasnyder.com)"
__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"
__license__   = "GNU GPL v2 (or, at your option, any later version)"

# Fix for old version on school computers
from PyCompat import *

import Graph
if have_yapgvb():
        import yapgvb

class Key (object):
        """A class that makes a unique key for each pair of vertices."""

        def __init__ (self, v1, v2):
                self.__key = [v1, v2]
                self.__key.sort ()

        def __eq__ (self, rhs):
                return (self.__key[0] == rhs.__key[0]) and (self.__key[1] == rhs.__key[1])


class DrawGraph (object):
        """A class that will draw an unweighted, undirected graph given the vertices and
        edges in the same form that is used for the Graph class."""

        def __init__ (self, name, graph):
                """Constructor"""
                self.__name = str(name)
                self.__graph = graph

        def render_stupid (self, prop=None):
                """Print the graph using the not very good method of telling whether
                we go up,down,left,right between every node.
                NOTE: This tells us HOW each node was generated, not the path taken
                through the graph. Use render_graphviz() for a MUCH improved visualization"""
                if prop == None:
                        raise ValueError # no propery given

                g = self.__graph

                # Get the vertices sorted in the order in which they were added to
                # the graph.
                sorted_vertices = [(int (g.get_vertex_value (v)), g.vertices[v].raw_obj)
                                        for v in g.vertices.keys()]
                sorted_vertices.sort()

                for v in sorted_vertices:
                        print getattr (v[1], prop),

                print
                print '%d nodes in the solution\n' % (len(g.vertices), )

        def render_graphviz (self, filename, layout_engine=yapgvb.engines.neato):
                """Draw the graph given into the file given. This will render
                to SVG, PNG, and JPG."""

                if not have_yapgvb():
                        raise ValueError # must have yapgvb installed

                dg = yapgvb.Graph (self.__name)
                g = self.__graph

                visited = []

                for v in g.vertices.keys():
                        node = dg.add_node (str(v), label=str(v),
                                        shape=g.get_vertex_shape(v), fontsize=14)

                        for c in g.get_children (v):
                                k = Key (v, c)

                                if k not in visited:
                                        node_c = dg.add_node (str(c), label=str(c),
                                                        shape=g.get_vertex_shape (c),
                                                        fontsize=14)
                                        edge = dg.add_edge (node, node_c)
                                        edge.color = g.get_edge_color (v, c)
                                        edge.label = g.get_edge_label (v, c)
                                        visited.append (k)

                # Do the rendering
                dg.layout (layout_engine)
                dg.render (filename)


def main ():

        vertices = ['a', 'b', 'c', 'd', 'e']
        edges = ( ['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'a'], ['b', 'c'],
                        ['b', 'e'], ['e', 'b'], ['e', 'c'], ['e', 'd'],
                        ['d', 'a'], ['d', 'c'], ['d', 'e'], ['c', 'a'],
                        ['c', 'b'], ['c', 'd'], ['c', 'e'] )

        print 'Drawing graph g1.svg'
        g1 = Graph.Graph (vertices, edges)
        DrawGraph ('g1', g1).render_graphviz ('g1.svg')

        vertices = range (11)
        edges = ( [0, 1], [0, 9], [0, 8], [8, 10], [8, 7], [9, 6], [9, 5],
                        [6, 7], [1, 4], [1, 3], [1, 2], [2, 0] )

        print 'Drawing graph g2.svg'
        g2 = Graph.Graph (vertices, edges)
        DrawGraph ('g2', g2).render_graphviz ('g2.svg')

        vertices = range (3)
        edges = ( [0, 1], [1, 2], [2, 0] )

        print 'Drawing graph g3.svg'
        g3 = Graph.Graph (vertices, edges)
        DrawGraph ('g3', g3).render_graphviz ('g3.svg')


if __name__ == '__main__':
        main ()