"""
 graph_play_v0.py

 playing around with graphs & trees

 vocabulary :
   tree  : made up of nodes, each with children & parent
   graph : made up of vertices, each with neighbors, connected by edges
   search: visiting each node or vertex, doing something with each
   static: put everything into memory before searching
   dynamic: generate tree or graph elements as needed 

 API choices :
   * put nodes or edges or something into a list or dictionary or whatever
   * or wrap the whole Graph into an object with an API
   * or put individual Node or Vertex or Edge components into objects
   * or some combination

 tasks : 
   * create image from graph edges using graphviz.org "dot" shell utility
   * store graph as
     - collection of edges
     - neighbors 
   * store tree as
     - children of nodes
   * recursively search tree, using node children API
   * breadth-first or depth-first search graph with 
     "fringe" idea, using Stack, Queue, and vertex neighbors API

 version 0 :
   - edges for graph_example_1
   - created graph_example_1.dot and graph_example_1.png image

 Jim Mahoney | April 2021 | cs.bennington.college | MIT License
"""

# -- utility function ---

def make_graph_png(edges, filename='graph'):
    """ Given graph edges, create an image file graph.png """
    run_graphviz(edges_to_dot(edges), filename)

def run_graphviz(dot_text, filename):
    """ Run the graphviz 'dot' command line function
        to create an image file graph.png given a graphviz 'dot' string """
    import subprocess
    dot_file = filename + '.dot'
    png_file = filename + '.png'
    with open(dot_file, 'w') as dot:
        dot.write(dot_text)
    command = f'/usr/bin/env dot -Tpng {dot_file}'.split()
    png_image = subprocess.check_output(command)
    with open(png_file, 'wb') as png:  # open in write binary mode
        png.write(png_image)

def edges_to_dot(edges, graph_or_digraph='graph', arrow='--', lined_up=[]):
    """ Return string giving .dot representation of graph given its edges. """
    # See graphviz.org for the "dot" command line program which makes
    # graph images.
    # The arguments are :
    #  * edges is a sequence of pairs of names, where each pair is an edge,
    #          for example [('a','b'), ('a', 'c')].
    #  * lined_up is e.g. [('a','b'), ('c','d')] which would line those up.
    #  * graph_or_digraph is 'graph' or 'digraph' (directed graph)
    #  * arrow is '--' or '->' (for directed graph)
    dot_text = '/* -- .dot file - see graphviz.org  */\n'
    dot_text = '{} {{\n'.format(graph_or_digraph)
    for (parent, child) in edges:
        dot_text += ' {} {} {} ;\n'.format(parent, arrow, child)
    for same in lined_up:
        dot_text += '{{rank=same; {}}};\n'.format(' '.join(same))
    dot_text += '}\n'
    return dot_text

# --- stupid python tricks ---

# Set A, B, C, ... to 'A', 'B', 'C' for shorter typing.
a='A'; b='B'; c='C'; d='D'; e='E'; f='F'; g='G'; h='H'; i='I'; j='J'; k='K'

# Uncommment the next three lines for another way to do that.
#import string
#def setglobal(name,value): eval("globals().__setitem__(name,value)")
#for letter in string.ascii_uppercase: setglobal(letter, letter)

# --- define the edges of a graph ---

# graph_example_1
edges_1 = ( (a, b),
            (a, c),
            (b, d),
            (b, e),
            (c, f),
            (c, g),
            (d, h),
            (d, i),
            (e, j),
            (e, k)
           )

# -- do something with the graph --

def main():
    make_graph_png(edges_1, filename='graph_example_1')

if __name__ == '__main__':
    main()