# Author        :   Paul Tabatabai
# Date          :   July 17th 2016
# Description   :   An exhaustive search is used
#                   to find a graph on 9 vertices and 16
#                   edges which contains all trees and to
#                   show that no such graph on 15 edges
#                   exists.

from sage.graphs.trees import TreeIterator
import itertools as it

def contains_all_trees(G, n):
    T = TreeIterator(n)
    for t in T:
        if G.subgraph_search(t) is None:
            return False
    return True


def find_graph_containing_all_trees(n, m):
    vertices = range(n)
    edges = [(i, j) for i in range(n) for j in range(i+1, n)]
    
    # without loss of generalization,
    # the graph we are looking for
    # contains the edges of the path 1,2,...,n.
    path_edges = [(i, i+1) for i in range(n-1)]
    
    # we only need to try adding edges
    # from the remaining edge set.
    rem_edges = [edge for edge in edges if edge not in path_edges]
    add = m - (n - 1) # we already have n-1 edges from path_edges

    # just for printing progress.
    max_iters = binomial(binomial(n, 2) - (n-1), add)
    count = 0

    for additional_edges in it.combinations(rem_edges, add):
        if count % 10000 == 0:
            print  "{:8.4f}".format(float(count)/max_iters * 100), "percent searched."
        G = Graph()
        G.add_vertices(vertices)
        G.add_edges(path_edges)
        G.add_edges(additional_edges)
        if contains_all_trees(G, n):
            return "Graph found! Edges: ", G.edges(labels = False)
        count = count + 1
    print "100.0000 percent searched."
    return "No such graph exists!", None


print "Finding Graph containing all trees on 9 vertices and 16 edges:"
print find_graph_containing_all_trees(9, 16)

print "Showing that no such Graph on 9 vertices and 15 edges exists:"
print find_graph_containing_all_trees(9, 15)