N_vertices = 13 # the maximal number of vertices we consider
N_Ramsey = 7 # all graphs with Ramsey number at most N_Ramsey
statistic_dict = dict()
def statistic(G):
    return statistic_dict.get(G.canonical_label().copy(immutable=True))

"""
The Ramsey number of a graph.

This is the smallest integer $n$ such that every two-colouring of the
$n$ vertices of the complete graph $K_n$ contains a (not necessarily
induced) monochromatic copy of the given graph. [1]

Thus, the Ramsey number of the complete graph $K_n$ is the ordinary Ramsey number $R(n,n)$.  Very few of these numbers are known. [2,3]

[1] Chvatál,Rödl,Szemerédi,Trotter, The Ramsey number of a graph with bounded maximum degree. doi:10.1016/0095-8956(83)90037-0

[2] Radziszowski, Stanisław P. "Small Ramsey numbers." Electron. J. Combin 1.7 (1994).

[3] [[wikipedia:Ramsey's theorem#Ramsey numbers]]

[4] Hendry, G. R. T. Ramsey numbers for graphs with five vertices

"""
def check_Ramsey(n, already_found=[]):
    r"""
    Colour the complete graph on n vertices with two colours, and
    return the subgraphs which appear in all colourings.

    EXAMPLES::

        sage: L = dict()
        sage: n = 2; L[n] = check_Ramsey(n)
        sage: n = 3; L[n] = check_Ramsey(n, sum(L.values(), []))
        sage: n = 4; L[n] = check_Ramsey(n, sum(L.values(), []))
        sage: n = 5; L[n] = check_Ramsey(n, sum(L.values(), []))
        sage: n = 6; L[n] = check_Ramsey(n, sum(L.values(), []))
        sage: n = 7; L[n] = check_Ramsey(n, sum(L.values(), []))

        sage: n=6; graphics_array([H.plot() for H in L[n] if H.is_connected()])
    """
    def has_copy(H1, H2, H):
        r"""
        Return True if there is a copy of H in H1=s or H2=E\s.
        """
        S1 = H1.subgraph_search(H)
        if not S1 is None:
            return True
        S2 = H2.subgraph_search(H)
        if not S2 is None:
            return True
        return False

    candidates = [H.canonical_label() for k in range(n+1) for H in graphs(k)]
    candidates = [H for H in candidates if H not in already_found]
    G = graphs.CompleteGraph(n)
    E = Set(G.edges(labels=False))
    V = G.vertices()
    for size in range(1+len(E)//2):
        print("check subgraphs of size", size)
        tested = []
        for s in E.subsets(size):
            H1 = Graph(n)
            H1.add_edges(s)
            H1 = H1.canonical_label()
            H2 = Graph(n)
            H2.add_edges(E.difference(s))
            H2 = H2.canonical_label()
            if (H1, H2) not in tested:
                tested += [(H1, H2)]
                candidates = [H for H in candidates if has_copy(H1, H2, H)]

    return candidates

def add_to_dict(G, v):
    H = G.canonical_label().copy(immutable=True)
    if H in statistic_dict:
        assert statistic_dict[H] == v, "The graph %s should have Ramsey number %s, got %s instead"%(repr(H), statistic_dict[H], v)
        print("%s already known to have Ramsey value %s"%(repr(H), v))
    else:
        statistic_dict[H] = v

Ramsey_small = dict()
for n in range(N_Ramsey+1):
    Ramsey_small[n] = check_Ramsey(n, sum(Ramsey_small.values(), []))

for v, lG in Ramsey_small.items():
    for G in lG:
        add_to_dict(G, v)

# table IIIa
Ramsey_almost_complete = dict()
Ramsey_almost_complete[3] = 3
Ramsey_almost_complete[4] = 10
Ramsey_almost_complete[5] = 22

for n, v in Ramsey_almost_complete.items():
    G = graphs.CompleteGraph(n)
    G.delete_edge(G.edges()[0])
    add_to_dict(G, v)

# G8 - G20 are from Table 1 in
# Hendry, G. R. T. Ramsey numbers for graphs with five vertices

G8 = Graph([(1,2),(2,3),(3,4),(4,5),(3,5)]).canonical_label().copy(immutable=True)
G9 = Graph([(1,2),(2,3),(3,4),(4,5),(2,4)]).canonical_label().copy(immutable=True)
G10 = Graph([(1,2),(1,3),(1,4),(1,5),(2,3)]).canonical_label().copy(immutable=True)
G12 = Graph([(1,2),(2,3),(3,4),(4,5),(1,3),(3,5)]).canonical_label().copy(immutable=True)
G13 = Graph([(1,2),(1,3),(1,4),(1,5),(2,3),(3,4)]).canonical_label().copy(immutable=True)
G14 = Graph([(1,2),(1,3),(1,4),(2,5),(2,3),(3,4)]).canonical_label().copy(immutable=True)
G15 = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)]).canonical_label().copy(immutable=True)
G16 = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(1,3),(1,4)]).canonical_label().copy(immutable=True)
G17 = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(1,3),(2,4)]).canonical_label().copy(immutable=True)
G19 = Graph([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(1,5)]).canonical_label().copy(immutable=True)
G20 = Graph([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(1,5),(2,5)]).canonical_label().copy(immutable=True)

Ramsey_Hendry = [(G8, 9), (G9, 9), (G10, 9), (G12, 9), (G13, 10), (G14, 10), (G15, 9), (G16, 10), (G17, 10), (G19, 18), (G20, 18)]

for G, v in Ramsey_Hendry:
    add_to_dict(G, v)

# table IVa and IVb
Ramsey_bipartite = dict()
Ramsey_bipartite[3, 3] = 18
Ramsey_bipartite[2, 2] = 6
Ramsey_bipartite[2, 3] = 10
Ramsey_bipartite[2, 4] = 14
Ramsey_bipartite[2, 5] = 18
Ramsey_bipartite[2, 6] = 21
Ramsey_bipartite[2, 7] = 26
Ramsey_bipartite[2, 8] = 30
Ramsey_bipartite[2, 9] = 33
Ramsey_bipartite[2, 10] = 38
Ramsey_bipartite[2, 11] = 42
Ramsey_bipartite[2, 12] = 46
Ramsey_bipartite[2, 13] = 50
Ramsey_bipartite[2, 14] = 54
Ramsey_bipartite[2, 15] = 57
Ramsey_bipartite[2, 16] = 62

for (n,m), v in Ramsey_bipartite.items():
    add_to_dict(graphs.CompleteBipartiteGraph(n,m), v)

# section 3.3.2 a
def Ramsey_star(n):
    m = n-1
    assert m > 0
    if is_even(m):
        return 2*m-1
    else:
        return 2*m

for n in range(2, N_vertices+1):
    add_to_dict(graphs.StarGraph(n-1), Ramsey_star(n))

# section 3.3.2, n
def Ramsey_m_4_star(n):
    assert n % 4 == 0, "The number of vertices, %s, should be divisible by 4"%n
    m = n//4
    assert m >= 2, "There must be at least 2 copies of the star, but there are only %s"%m
    return 5*m-1

for n in range(8, N_vertices+1, 4):
    add_to_dict(sum([graphs.StarGraph(3) for k in range(n//4)], Graph()), Ramsey_m_4_star(n))

# section 4.1, a,b,c
def Ramsey_cycle(n):
    assert n > 2
    if is_odd(n) and n > 3:
        return 2*n-1
    elif is_even(n) and n > 4:
        return n-1+(n//2)
    elif n == 3 or n == 4:
        return 6

for n in range(3, N_vertices+1):
    add_to_dict(graphs.CycleGraph(n), Ramsey_cycle(n))

# section 4.1, e
def Ramsey_m_triangles(n):
    assert n % 3 == 0, "The number of vertices, %s, should be divisible by 3"%n
    m = n // 3
    assert m >= 2, "There must be at least 2 copies of the triangle, but there are only %s"%m
    return 5*m

for n in range(6, N_vertices+1, 3):
    add_to_dict(sum([graphs.CycleGraph(3) for k in range(n//3)], Graph()), Ramsey_m_triangles(n))

# section 4.1, f
def Ramsey_m_squares(n):
    assert n % 4 == 0, "The number of vertices, %s, should be divisible by 4"%n
    m = n // 4
    assert m >= 2, "There must be at least 2 copies of the square, but there are only %s"%m
    return 6*m-1

for n in range(8, N_vertices+1, 4):
    add_to_dict(sum([graphs.CycleGraph(4) for k in range(n//4)], Graph()), Ramsey_m_squares(n))

# section 5.1
def Ramsey_paths(m):
    assert m >= 2
    return m + (m//2) - 1

for n in range(2, N_vertices+1):
    add_to_dict(graphs.PathGraph(n), Ramsey_paths(n))

# section 5.13 b
def Ramsey_union_K2(m):
    assert is_even(m) and m >= 2
    return 3*(m//2) - 1

for n in range(2, N_vertices+1, 2):
    add_to_dict(sum([graphs.CompleteGraph(2) for k in range(n//2)], Graph()), Ramsey_union_K2(n))

Ramsey_wheel = dict()
# table VIII
Ramsey_wheel[3] = 6
Ramsey_wheel[4] = 18
Ramsey_wheel[5] = 15
Ramsey_wheel[6] = 17

for n, v in Ramsey_wheel.items():
    add_to_dict(graphs.WheelGraph(n), v)

Ramsey_book = dict()
# table IX
Ramsey_book[1] = 6
Ramsey_book[2] = 10
Ramsey_book[3] = 14
Ramsey_book[4] = 18
Ramsey_book[5] = 21
Ramsey_book[6] = 26

for n, v in Ramsey_book.items():
    add_to_dict(Graph(1).join(graphs.StarGraph(n)), v)

# R.J. Faudree and R.H. Schelp, Ramsey Numbers for All Linear Forests, Discrete Mathematics, 16 (1976) 149-155.

def Ramsey_linear_forest(n, j):
    assert is_even(n-j)
    return n + (n-j)//2 - 1

for n in range(2, N_vertices+1):
    for la in Partitions(n):
        if min(la) > 1:
            G = sum([graphs.PathGraph(p) for p in la], Graph())
            add_to_dict(G, Ramsey_linear_forest(n, sum(1 for p in la if is_odd(p))))

# J.W. Grossman, The Ramsey Numbers of the Union of Two Stars, Utilitas Mathematica, 16 (1979) 271-279.

def Ramsey_two_stars(n, m):
    assert n >= m, "Ramsey_two_stars only valid for n >= m, but n = %s and m = %s"%(n,m)
    return max(n+2*m, 2*n+1, n+m+3)

for n in range(2, N_vertices+1):
    for m in range(2,(n-1)//2+1):
        G = graphs.StarGraph(m-1) + graphs.StarGraph(n-m-1)
        add_to_dict(G, Ramsey_two_stars(n-m-1, m-1))

# Yu, P., & Li, Y. (2016). All Ramsey numbers for brooms in graphs. The Electronic Journal of Combinatorics, 23(3), 3-29.
def Ramsey_broom(k, l):
    assert k >= 2
    n = k+l
    if l == 1 or l == 2:
        return Ramsey_star(n)
    if l == 3:
        return Ramsey_star(n-1)
    if l >= 2*k - 1:
        return n + (l+1)//2 - 1
    if 4 <= l <= 2*k - 2:
        return 2*n - 2*((l+1)//2) - 1

def BroomGraph(k, l):
    G = graphs.StarGraph(k)
    assert G.degree(0) == k
    G.add_path([0] + [k+1+i for i in range(l-1)])
    G.layout("tree", save_pos=True)
    return G

for n in range(2, N_vertices+1):
    for k in range(2,n-1):
        G = BroomGraph(k, n-k)
        add_to_dict(G, Ramsey_broom(k, n-k))

# Jerrold W. Grossman, Frank Harary, Maria Klawe, Generalized Ramsey theory for graphs, X: double stars
        
def Ramsey_double_star(k, l):
    assert k >= 2
    n = k+l+2
    if is_odd(k) and l <= 2:
        return max(2*k+1, k+2*l+2)
    if (is_even(k) or l >= 3) and (k^2 <= 2*l or k >= 3*l):
        return max(2*k+2, k+2*l+2)
        
def DoubleStarGraph(k, l):
    assert k >= l, "DoubleStarGraph only defined for k >= l"
    G = graphs.StarGraph(k)
    H = G.disjoint_union(graphs.StarGraph(l), "pairs")
    H.add_edge((0,0),(1,0))
    return H

for n in range(2, N_vertices+1):
    for l in range(2,n//2):
        k = n-l-2
        G = DoubleStarGraph(k, l)
        assert G.num_verts() == n
        if (is_odd(k) and l <= 2) or ((is_even(k) or l >= 3) and (k^2 <= 2*l or k >= 3*l)):
            add_to_dict(G, Ramsey_double_star(k, l))


######################################################################
# finally, add isolated vertices
for G, v in list(statistic_dict.items()):
    for k in range(N_vertices-G.num_verts()):
        add_to_dict(G.disjoint_union(Graph(k)), max(G.num_verts()+k, v))