#!/usr/bin/env python

class Graph:
    def __init__(self, N):
        self.N = N                     # number of vertices
        
        # maps a vertex number to the list of (vertices, edge value)
        # to which it is connected by edges.
        self.adjacent = [[] for n in xrange(N)]
    
    def connect(self, vertex1, vertex2, edge_value):
        """
        Connect 'vertex1' and 'vertex2' with an edge, with associated
        value 'value'
        """
        # Add vertices to each other's adjacent list
        self.adjacent[vertex1].append( (vertex2, edge_value) )
        self.adjacent[vertex2].append( (vertex1, edge_value) )

    def check(self):
        """
        See if vertex values add up to edge values (mod N).
        """
        for vertex in xrange(self.N):
            for neighbor, edge_value in self.adjacent[vertex]:
                assert (self.vertex_values[vertex] +
                        self.vertex_values[neighbor]) % self.N == edge_value
    
    def calc_tree_sizes(self):
        """
        After running this method, the attribute size will contain a list,
        which maps the vertices to the size of the tree that vertex belongs
        to.
        """
        visited = self.N * [-1]  # -1 unvisited, otherwise the number of tree
        treenum = 0
        
        # Loop over all vertices, taking unvisited ones as roots.
        for root in xrange(self.N):
            if visited[root] >= 0:
                continue
            
            # explore tree starting at 'root'
            # Stack of vertices to visit, a list of tuples (parent, vertex)
            tovisit = [ (None, root) ]
            while tovisit:
                parent, vertex = tovisit.pop()
                visited[vertex] = treenum
                
                # Loop over adjacent vertices, but skip the vertex we arrived
                # here from the first time it is encountered.
                skip = True
                for neighbor, edge_value in self.adjacent[vertex]:
                    if skip and neighbor == parent:
                        skip = False
                        continue
                    
                    if visited[neighbor] >= 0:
                        # We visited here before, so the graph is cyclic.
                        exit('Hmm, graph is cyclic.')
                    
                    tovisit.append( (vertex, neighbor) )
                    
            treenum += 1
        
        # maps the tree number to number of vertices within that tree
        treesizes = treenum * [0]
        for tree in visited:
            treesizes[tree] += 1
        
        self.size = [treesizes[visited[v]] for v in xrange(self.N)]
        
        if verbose:
            freq = (self.N+1) * [0]
            for size in treesizes:
                freq[size] += 1
        
            sys.stderr.write(' Size   Trees\n')
            for i, f in enumerate(freq):
                if f:
                    sys.stderr.write('%5i %5i\n' % (i, f))
                if i == minsize-1:
                    sys.stderr.write('--------------\n')
        
    def write(self, fo, labels = False):
        self.calc_tree_sizes()
        
        fo.write('graph G {\n'
                 '  size = "8,8";\n'
                 '  edge [color="#ff0000"]\n')
        if labels:
            fo.write('  node [color="#a0e0ee", style=filled];\n')
            
            for vertex, value in enumerate(self.vertex_values):
                if self.size[vertex] < minsize: continue
                fo.write('  { node [label="%i: %i"] v%i }\n' % (
                    vertex, value, vertex))
        else:
            fo.write('  node [color="#3377a0", label="",\n'
                     '        style=filled, shape=circle]\n')
            
        for vertex in xrange(self.N):          # edges
            if self.size[vertex] < minsize: continue
            for neighbor, edge_value in self.adjacent[vertex]:
                if neighbor > vertex:  continue
                fo.write('  v%i -- v%i%s;\n' %
                         (vertex, neighbor,
                          (' [label="%s: %i"]' % (K[edge_value], edge_value))
                          if labels else ''))
        fo.write('}\n')
        fo.close()


if __name__ == '__main__':
    import sys
    from optparse import OptionParser
    
    usage = "usage: %prog [options] [PYCODE]"
    
    description = """\
Given the python code for a perfect hash function which was generated by
perfect_hash.py, e.g. by '$ ../perfect_hash.py animals.txt >animals.py',
this program will create the graph which was used in determining the
perfect hash function.  The input python code may also be given to stdin.
The output is saved as in the .dot format which is used by the Graphviz
tools (see http://www.graphviz.org/) to generate a picture of the graph.
"""

    parser = OptionParser(usage = usage,
                          description = description,
                          prog = sys.argv[0])

    parser.add_option("-l", "--labels",
                      action  = "store_true",
                      help    = "Be verbose")

    parser.add_option("-m", "--minsize",
                      action  = "store",
                      default = 1,
                      type    = "int",
                      help    = "Include only trees in the output which "
                                "have at least INT vertices. "
                                "Default is %default, i.e. all trees are "
                                "included within the output.",
                      metavar = "INT")

    parser.add_option("-o", "--output",
                      action  = "store",
                      help    = "Specify output FILE explicitly. "
                                "Default, is stdout. ",
                      metavar = "FILE")

    parser.add_option("-v", "--verbose",
                      action  = "store_true",
                      help    = "Be verbose")
    
    options, args = parser.parse_args()
    
    if options.minsize > 0:
        minsize = options.minsize
    else:
        parser.error("minimal size of trees has to be larger than zero")
    
    verbose = options.verbose
    
    if len(args) > 1:
        parser.error("incorrect number of arguments")

    # --------------------- end parsing and checking -----------------------
    
    if verbose:
        sys.stderr.write('minsize (of trees): %i\n' % minsize)
        sys.stderr.write('labels (in output): %s\n' % options.labels)

    # ------------ input filehandle
    
    if len(args)==1:
        try:
            fi = file(args[0])
        except IOError :
            exit("Error: Can't open `%s' for reading." % args[0])
    else:
        fi = sys.stdin

    # ------------ read input, i.e. execute code
    
    exec(fi.read())
    
    # ------------ make graph
    
    g = Graph(len(G))
    g.vertex_values = G
    for key, hashval in zip(K, H):
        g.connect(hash_f(key, S1),
                  hash_f(key, S2),
                  hashval)
    g.check()

    # ------------ output filehandle
    
    if options.output:
        try:
            fo = file(options.output, 'w')
        except IOError :
            exit("Error: Can't open `%s' for writing." % options.output)
    else:
        fo = sys.stdout

    # ------------ write output, i.e. generate .dot output

    g.write(fo, options.labels)


# Local Variables:
# mode: python
# End: