Below is the file 'ancestry.py' from this revision. You can also download the file.

# Copyright (C) 2005 Grahame Bowland <grahame@angrygoats.net>
#
# This program is made available under the GNU GPL version 2.0 or
# greater. See the accompanying file COPYING for details.
#
# This program is distributed WITHOUT ANY WARRANTY; without even the
# implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
# PURPOSE.

import rfc822, string, sha, os
import mtn
from colorsys import hls_to_rgb
import config

def ancestry_dot(ctxt, revision):
    def dot_escape(s):
        # TODO: kind of paranoid, should probably revise
        permitted = string.digits + string.letters + ' -<>-:,*@!$%^&.+_~?/'
        return ''.join([t for t in s if t in permitted])
    revision = mtn.Revision(revision)
    original_branches = []
    for cert in ctxt.ops.certs(revision):
        if cert[4] == 'name' and cert[5] == 'branch':
            original_branches.append(cert[7])

    # strategy: we want to show information about this revision's place
    # in the overall graph, both forward and back, for revision_count
    # revisions in both directions (if possible)
    #
    # we will show propogates as dashed arcs
    # otherwise, a full arc
    #
    # we'll show the arcs leading away from the revisions at either end,
    # to make it clear that this is one part of a larger picture
    #
    # it'd be neat if someone wrote a google-maps style browser; I have
    # some ideas as to how to approach this problem.

    # revision graph is prone to change; someone could commit anywhere
    # any time. so we'll have to generate this dotty file each time;
    # let's write it into a temporary file (save some memory, no point
    # keeping it about on disk) and sha1 hash the contents.
    # we'll then see if <revision_id>.<sha1>.png exists; if not, we'll
    # generate it from the dot file

    # let's be general, it's fairly symmetrical in either direction anyway
    # I think we want to show a consistent view over a depth vertically; at the
    # very least we should always show the dangling arcs
    arcs = set()
    nodes = set()
    visited = set()

    def visit_node(revision):
        for node in ctxt.ops.children(revision):
            arcs.add((revision, node))
            nodes.add(node)
        for node in ctxt.ops.parents(revision):
            arcs.add((node, revision))
            nodes.add(node)
        visited.add(revision)

    def graph_build_iter():
        for node in (nodes - visited):
            visit_node(node)

    # stolen from monotone-viz
    def colour_from_string(str):
        def f(off):
            return ord(hashval[off]) / 256.0
        hashval = sha.new(str).digest()
        hue = f(5)
        li = f(1) * 0.15 + 0.55
        sat = f(2) * 0.5 + .5
        return ''.join(["%.2x" % int(x * 256) for x in hls_to_rgb(hue, li, sat)])

    # for now, let's do three passes; seems to work fairly well
    nodes.add(revision)
    for i in xrange(3):
        graph_build_iter()

    graph = '''\
digraph ancestry {
    ratio=compress
    nodesep=0.1
    ranksep=0.2
    edge [dir=forward];
'''

    # for each node, let's figure out it's colour, whether or not it's in our branch,
    # and the label we'd give it; we need to look at all the nodes, as we need to know
    # if off-screen nodes are propogates

    node_colour = {}
    node_label = {}
    node_in_branch = {}

    for node in nodes:
        author, date = '', ''
        branches = []
        for cert in ctxt.ops.certs(node):
            if cert[4] == 'name' and cert[5] == 'date':
                date = cert[7]
            elif cert[4] == 'name' and cert[5] == 'author':
                author = cert[7]
            elif cert[4] == 'name' and cert[5] == 'branch':
                branches.append(cert[7])
        name, email = rfc822.parseaddr(author)
        if name:
            brief_name = name
        else:
            brief_name = author
        node_label[node] = '%s on %s\\n%s' % (node.abbrev(),
                                             dot_escape(date),
                                             dot_escape(brief_name))
        node_colour[node] = colour_from_string(author)
        for branch in original_branches:
            if branch in branches:
                node_in_branch[node] = True
                break

    # draw visited nodes; other nodes are not actually shown
    for node in visited:
        line = '    "%s" ' % (node)
        options = []
        nodeopts = config.graphopts['nodeopts']
        for option in nodeopts:
            if option == 'fillcolor' and node_colour.has_key(node):
                value = '#'+node_colour[node]
            elif option == 'shape' and node == revision:
                value = 'hexagon'
            else:
                value = nodeopts[option]
            options.append('%s="%s"' % (option, value))
        options.append('label="%s"' % (node_label[node]))
        options.append('href="%s"' % ctxt.link(node).uri())
        line += '[' + ','.join(options) + ']'
        graph += line + '\n'

    for node in (nodes - visited):
        graph += '    "%s" [style="invis",label=""]\n' % (node)

    for (from_node, to_node) in arcs:
        if node_in_branch.has_key(from_node) and node_in_branch.has_key(to_node):
            style = "solid"
        else:
            style = "dashed"
        graph += '    "%s"->"%s" [style="%s"]\n' % (from_node, to_node, style)
    graph += '}'
    return graph

def ancestry_graph(ctxt, revision):
    dot_data = ancestry_dot(ctxt, revision)
    # okay, let's output the graph
    graph_sha = sha.new(dot_data).hexdigest()
    if not os.access(config.graphopts['directory'], os.R_OK):
        os.mkdir(config.graphopts['directory'])
    output_directory = os.path.join(config.graphopts['directory'], revision)
    if not os.access(output_directory, os.R_OK):
        os.mkdir(output_directory)
    dot_file = os.path.join(output_directory, graph_sha+'.dot')
    output_png = os.path.join(output_directory, 'graph.png')
    output_imagemap = os.path.join(output_directory, 'imagemap.txt')
    must_exist = (output_png, output_imagemap, dot_file)
    if filter(lambda fname: not os.access(fname, os.R_OK), must_exist):
        open(dot_file, 'w').write(dot_data)
        command = "%s -Tcmapx -o %s -Tpng -o %s %s" % (config.graphopts['dot'],
                                                       output_imagemap,
                                                       output_png,
                                                       dot_file)
        os.system(command)
    return output_png, output_imagemap