#!/usr/bin/env python
# coding: utf-8

# # Two adjacent vertices and their combined neighbourhoods
# 
# Suppose there exists a Conway-99 graph G, that is, an SRG(99,14,1,2). Let a and b be vertices of G such that a and b are neighbours. Then:
# * a has 14 neighbours, one of which is b
# * b has 14 neighbours, one of which is a
# * By lambda = 1, precisely one of these neighbours is a mutual neighbour of both a and b
# 
# Thus the graph G' on a,b and their neighbours consists of 27 vertices (a, b, their mutual neighbour, 12 neighbours of a but not b, and 12 neighbours of b but not a). In this workbook, we determine (up to isomorphism) the possibilities for this graph induced by the lambda = 1, mu = 2 constraints on G. 
# 
# For convenience, we fix a numbering:
# * a is vertex 0
# * b is vertex 1
# * Their mutual neighbour is vertex 2
# * The remaining neighbours of vertex a are vertices 3 through 14
# * The remaining neighbours of vertex b are vertices 15 through 26
# 
# Moreover, we introduce these vertices sequentially using the 'fanblade' structures centred at vertices 0 and 1:
# * For i,j in 1...14 we have i,j adjacent iff j = i + 1 and i is odd
# * For i,j in 15...26 we have i,j adjacent iff j = i + 1 and i is odd
# * (The seventh blade for vertex 1 consists of vertices 0 and 2)
# 
# Finally, we note that each of the vertices i = 15...26 is not adjacent to vertex 0, thus (by mu = 2) there must be two mutual neighbours of 0,i in G. But as all neighbours of 0 are in G', namely vertices 1...14, we know that each vertex i = 15...26 is adjacent to precisely 2 of the vertices 1...14.
# 
# * By assumption, vertex 1 is adjacent to vertex i
# * Hence vertex 2 is not adjacent to vertex i (else 0 and i and are mutual neighbours of adjacent vertices 1 and 2, which violates lambda = 1)
# * So for each i = 15...26 there is a unique j in 3...14 such that i and j are neighbours.
# * For the first such i=15, all choices of j give equivalent graphs on vertices 0...15. Wlog, we set j=3.
# 
# Our task then essentially reduces to determining j for each i=16...26, whilst satisfying all our other conditions.

# In[1]:


get_ipython().run_line_magic('pylab', 'inline')
import numpy as np
from conway99 import *
import pydot
from networkx.drawing.nx_pydot import write_dot


# ## The neighbourhood of vertex 0
# We start from an arbitrary vertex and its neighbours. These can necessarily be arranged as 7 blades of a fan; we fix a numbering with vertex 0 the centre, 1-14 its neighbours, and blade edges 1-2, 3-4, 5-6, 7-8, 9-10, 11-12, 13-14

# In[2]:


seed15 = np.empty((15,15), dtype='int')
for i in range(15):
    for j in range(15):
        seed15[i,j] = 0

# 1-14 all nhbrs of 0
for i in range(1,15):
    seed15[0,i] = 1
    seed15[i,0] =1
    
# By fixing an ordering, a single representative suffices
for i in [1,3,5,7,9,11,13]:
    seed15[i,i+1] = 1
    seed15[i+1,i] = 1


# In[3]:


# review
print(seed15)
plot_given_edges(seed15)


# In[4]:


# Verify some details
assert len(seed15)*len(seed15) == num_known_zeros(seed15) + num_known_ones(seed15) + num_unknowns(seed15)
assert not(has_unknown_values(seed15))
assert lambda_compatible(seed15)
assert mu_compatible(seed15)
assert meets_adjacency_requirements(seed15, debug=True)
assert graph_is_valid(seed15)


# ## Adding vertex 15
# (NB, as we started numbering at 0, this is our 16th vertex)
# 
# wlog (see intro, or consider how the plot below would be equivalent for any alternative choice for second neighbour amongst 3...14), we may assume this is a neighbour of vertices 1 and 3.

# In[5]:


get_ipython().run_line_magic('time', 'rep16 = find_valid_supergraphs([seed15], forced_edges=[(1,15), (15,3)])')


# In[6]:


# confirm this is what we expected:
plot_given_edges(rep16[0])


# ## Adding vertices 16...26
# _Note that we no longer make any direct assumptions about the second neighbour j in 3...14; we determine representatives of the possibilities dictated by the lambda, mu conditions._ 

# ### Vertex 16
# 
# We know one of the blades centred at vertex 1; namely 1-0-2-1.
# 
# We also have part of another, containing vertex 15.
# 
# wlog, let vertex 16 be the other vertex of that blade (_so we force 1-16, and 15-16_)

# In[7]:


get_ipython().run_line_magic('time', 'rep17 = find_valid_supergraphs(rep16, forced_edges=[(1,16),(15,16)], verbose=False)')


# ### Vertex 17
# 
# Vertex 17 necessarily starts a new blade, so only forcing 1-17

# In[8]:


get_ipython().run_line_magic('time', 'rep18 = find_valid_supergraphs(rep17, forced_edges=[(1,17)], verbose=False)')


# ### Vertex 18
# 
# However, we can then force vertex 18 to be the other vertex of that blade

# In[9]:


get_ipython().run_line_magic('time', 'rep19 = find_valid_supergraphs(rep18, forced_edges=[(1,18),(17,18)], verbose=False)')


# ### Vertices 19...26
# 
# Continue in this fashion until we have all nhbrs of vertex 1, with forced fan pattern 0-2, 15-16, 17-18, 19-20, 21-22, 23-24, 25-26

# In[10]:


get_ipython().run_line_magic('time', 'rep20 = find_valid_supergraphs(rep19, forced_edges=[(1,19)], verbose=False)')


# In[11]:


get_ipython().run_line_magic('time', 'rep21 = find_valid_supergraphs(rep20, forced_edges=[(1,20), (19,20)], verbose=False)')


# In[12]:


get_ipython().run_line_magic('time', 'rep22 = find_valid_supergraphs(rep21, forced_edges=[(1,21)], verbose=False)')


# In[13]:


get_ipython().run_line_magic('time', 'rep23 = find_valid_supergraphs(rep22, forced_edges=[(1,22), (21,22)], verbose=False)')


# In[14]:


get_ipython().run_line_magic('time', 'rep24 = find_valid_supergraphs(rep23, forced_edges=[(1,23)], verbose=False)')


# In[15]:


get_ipython().run_line_magic('time', 'rep25 = find_valid_supergraphs(rep24, forced_edges=[(1,24), (23,24)], verbose=False)')


# In[16]:


get_ipython().run_line_magic('time', 'rep26 = find_valid_supergraphs(rep25, forced_edges=[(1,25)], verbose=False)')


# In[17]:


get_ipython().run_line_magic('time', 'rep27 = find_valid_supergraphs(rep26, forced_edges=[(1,26),(25,26)], verbose=False)')


# # Review
# 
# Up to equivalence, we have 11 possibilities. We first review an arbitrary example, then consider how the others differ.

# In[18]:


plot_given_edges(rep27[0])


# In[19]:


def describe_differences(rep1, rep2):
    order = min(len(rep1),len(rep2))
    for i in range(order):
        for j in range(i, order):
            if rep1[i,j] > rep2[i,j]:
                print('First graph has edge {}-{} absent from second'.format(i,j))
            if rep1[i,j] < rep2[i,j]:
                print('First graph lacks edge {}-{} present in second'.format(i,j))


# In[20]:


for i in range(1, 11):
    print('Comparing rep 0 to rep {}'.format(i))
    describe_differences(rep27[0],rep27[i])
    print('\n------\n')


# Which edges are consistent across all reps?

# In[21]:


for i in range(27):
    for j in range(i,27):
        if min([r[i,j] for r in rep27]) == 1:
            print('Edge {}-{} appears in all representatives'.format(i,j))


# This is just our assumed numbering of:
# * The neighbours of vertex 0
# * The neighbours of vertex 1
# * The fan structure centred at 0 (1-2, 3-4 etc.)
# * Vertex 3 chosen as the second mutual neighbour of vertices 0 and 15 amongst 3...14
# * The fan structure centred at 1 (15-16, 17-18 etc.)
# 
# So these assumptions do not inevitably force any other edges; various branches arise as each succesive vertex 16..26 is considered.

# In[22]:


# Export base example for plotting


# In[23]:


G = graph_from_mat(rep27[0])
write_dot(G, "rep27_0.dot")


# Note that rep 0 has a particularly pleasing pattern - for each i = 15...26, the neighbour j from 3...14 satisfies i = j + 12 
# 
# (i.e. consistent throughout with our choice of vertex 3 as neighbour of vertex 15.)
# 

# In[24]:


G.edges


# In[ ]: