# This file with Sage commands is a modification of a file that was used in the
# paper ``A. Bishnoi and B. De Bruyn. On generalized hexagons of order (3,t) and
# (4,t) containing a subhexagon. European J. Combin. 62 (2017), 115--123 to
# compute the ovoids of some small generalized hexagons.
# It computes all T_1-blocking sets of size q^2-1 in a computer model of
# PG(3,q)\Q^+(3,q) where the point set coincides with [0..q^3-q-1].
# Such T_1-blocking sets intersect the truncated tangents in singletons (and so
# can be regarded as ovoids of a certain geometry). These truncated tangents
# are imported from a file that was generated by GeneralA.g.
def read_lines_from_file(name):
"""
Read a file containing the lines of the geometry.
Args:
name -- the file name (each line of the file should have integers
separated by a space)
Returns:
a list each element of which is a line of the geometry stored as a
list of points incident to the line
"""
L = []
f = open(name, 'r')
for l in f.readlines():
l = l.split()
L.append([int(x) for x in l])
f.close()
return L
def get_data(name):
"""
Get the necessary data regarding the geometry.
Args:
name -- the name of the file
Returns:
a tuple of points, lines, collinearity graph, distance function
"""
lines = read_lines_from_file(name)
edges = []
for l in lines:
edges.extend(Combinations(l,2))
T = Graph(edges)
points = T.vertices()
D = T.distance_all_pairs()
return (points, lines, T, D)
def ovoids(P,L):
"""
Find all exact hitting sets (ovoids) in the hypergraph (geometry)
using the Dancing Links algorithm.
Args:
P -- the vertices (points) of the hypergraph (geometry)
L -- the edges (lines) of the hypergraph (geometry)
Returns:
a list of all exact hitting sets (ovoids) in the hypergraph (geometry)
"""
map = dict()
for p in P:
map[p] = []
for i in range(len(L)):
for p in L[i]:
map[p].append(i)
E = [map[p] for p in P]
return list(DLXCPP(E))
points, lines, T, D = get_data("Desktop/lines")
ovs = ovoids(points, lines)
# All T_1-blocking sets are stored in ovs.