#!/usr/bin/python
#
# Interactive MST interface
# Chris Lawrence
# December 2, 1997
#

import mst, string
from string import atoi

while 1:
    print "To exit, press return at the nodes prompt."
    while 1:
        try:
            st = raw_input("How many nodes are in this graph (>= 2)? ")
            if not st:
                raise SystemExit
            try:
                n = atoi(st)
                if n >= 2:
                    break
            except ValueError:
                pass
            print "Invalid input.  Enter a number >= 2 or no input to quit."

        except EOFError:
            raise SystemExit

    # End of node count request loop

    edges = 0
    maxedges = (n * (n-1))/2

    print "Please enter up to %d edges, in the format:" % maxedges
    print "  v1, v2, weight"
    print "where v1 and v2 are integers from 0 to %d and the weight " % (n-1)
    print "is any positive real number.  When done, enter a blank line."
    
    al = mst.AdjacencyList(n)
    while edges < maxedges:
        try:
            edge = raw_input("Edge %d: " % edges)
            if not edge:
                break
        except EOFError:
            break
        bits = string.split(edge, ',')
        if len(bits) != 3:
            print 'Correct format is v1, v2, weight.'
        else:
            # Input line in valid format
            try:
                v1 = atoi(bits[0])
                v2 = atoi(bits[1])
                w = atoi(bits[2])
                if v1 < 0 or v2 < 0 or v1 >= n or v2 >= n or w <= 0:
                    print 'Vertex number or weight invalid.'
                else:
                    edges = edges+1
                    al.add_edge(v1, v2, w)
            except:
                print 'Vertex number or weight invalid.'

    # End of input while loop
    
    print "\nFinding the MST of this graph..."
    try:
        mintree = mst.Kruskal(al)
        print "Results in adjacency-list format:"
        print mintree
    except IndexError:
        print "Graph is not connected, so no MST exists."

# End of main loop