import itertools
import random
# Date: 04/12/2016
# Licence: Please feel free to copy and reuse for whatever purpose.
# Description:
# Code related to Ahmad Abu-Khazneh's thesis "Matchings and Covers of Multipartite Hypergraphs."
# link: http://etheses.lse.ac.uk/3360/1/Abu-Khazneh_Matchings_and_Covers.pdf
# This file includes a self-contained implementation of the algorithms presented in Chapter 3 of the thesis.
# It includes the hypergraphs presented in the thesis in chapter 5, 6 and 7.
# It also implements method to check the properties claimed in the thesis about the aforementioned hypergraphs.
# This includes claims made about their covering number, and claims made about the number of edge-minimal extremals they contain.
# The final method in the file "verify_ahmad_thesis()" verifies all computational claims in the thesis sequentially.
# This code has been optimised for readability rather than efficiency.
# Structure:
# SECTION 1: General helper methods.
# SECTION 2: Covering methods.
# SECTION 3: Isomorphism methods.
# SECTION 4: Edge-minimality methods.
# SECTION 5: Ryser-stability methods.
# SECTION 6: Hypergraphs from the thesis.
# Data structure & Idioms:
# r-partite hypergraphs are represented as a list of tuples each with r elements.
# For example, the 3-partite sunflower with three edges meeting in one vertex, is represented as follow:
# [ (0,0,0), (0,1,1), (0,2,2) ]
# To get the partite-ness of a given r-partite hypergraph, hg, we use:
# len(hg[0])
# That is get the number of the vertices in the first edge of the graph.
# To get the set of vertices of an edge, e, of a hypergraph, we use:
# set(enumerate(e))
# SECTION 1: General helper method:
def hg_intersects_edge(hg_in, edge_in):
""" Returns True if edge_in intersects all the edges in hg_in, False otherwise. """
edge_in_vertices = set(enumerate(edge_in))
for e in hg_in:
temp_set = set(enumerate(e))
if not temp_set.intersection(edge_in_vertices):
return False
return True
def is_intersecting_hg(hg_in):
""" Returns True if hg_in is intersecting hypergraph, False otherwise."""
for e in hg_in:
if not hg_intersects_edge(hg_in, e):
return False
return True
def gen_edges(hg_in):
""" Outputs all possible edges that you can add to hg_in, and are not already contained in hg_in. """
edges_out = []
r = len(hg_in[0]) # Get the parity of hg_in.
widths_temp = [max( [e[r] + 1 for e in hg_in] ) for r in range(0,r)]
widths_list = [list(range(0, w + 1)) for w in widths_temp]
# width_list[r] contains the list [1, ..., v+1] where v is the number of vertices in side r of hg_in.
# To generate all intersecting edges:
# Take the cross product of widths_list, and
# Filter out any edge in the product, that doesn't intersect all edges of hg_in
for e in itertools.product(*widths_list):
if e in hg_in:
continue
if not hg_intersects_edge(hg_in, e):
continue
edges_out.append(e)
return edges_out
def create_sunflower(r, core_in, petals_in):
""" Creates an r-partite sunflower with a core of size n, and m petals. """
hg_out = []
for e in range(0, petals_in):
new_edge = []
for c in range(0, core_in):
new_edge.append(0)
for l in range(0, r - core_in):
new_edge.append(e)
hg_out.append(tuple(new_edge))
return hg_out
# SECTION 2: Covering methods
def get_cover_depth(hg_in, edges_in, max_cap):
""" Finds a cover of size at most max_cap for hg_in AND edges_in, using ONLY vertices from hg_in. Otherwise returns [] if no such cover exists. """
# The method works by a depth first search on the vertices of hg, using the auxiliary recursive method get_cover_depth_rec
hg_in_vertices = []
for e in hg_in:
for v in enumerate(e):
if v not in hg_in_vertices:
hg_in_vertices.append(v)
edges_to_cover = list(hg_in)
edges_to_cover.extend(edges_in)
return get_cover_depth_rec(hg_in_vertices, edges_to_cover, max_cap, [], [])
def get_cover_depth_rec(vertices_pool, uncovered_edges, max_cap, current_cover, cross_list):
""" The recursive auxiliary method used by get_cover_depth. """
# Parameters:
# vertices_pool: the allowed pool of vertices from which to construct a cover.
# uncovered_edges: The edges that are not yet covered by current_cover.
# max_cap: The maximum size allowed for the cover being constructed.
# current_cover: The vertices that are in the cover in this current iteration.
# cross_list: Contains vertices which have already been used (unsuccessfully) to construct a cover, so that they are not included again.
if len(current_cover) >= max_cap:
return []
new_cross_list = list(cross_list)
current_edge = uncovered_edges[0] # Get the first uncovered edge.
for v in enumerate(current_edge):
# if v is not in the vertices_pool or it is already crossed, then try another vertex of current_edge
if (v not in vertices_pool) or (v in cross_list):
continue
# create new cover that contains v
new_cover = list(current_cover)
new_cover.append(v)
# filter out all edges that are now covered due to v's inclusion.
new_uncovered_edges = [e for e in uncovered_edges if v not in enumerate(e)]
if not new_uncovered_edges:
# all edges are now covered, so new_cover is what we are looking for.
return new_cover
else:
sub_cover = get_cover_depth_rec(vertices_pool, new_uncovered_edges, max_cap, new_cover, new_cross_list)
if sub_cover:
return sub_cover
else:
new_cross_list.append(v)
# All allowed vertices of the first uncovered edge have been tried, but no cover was constructed, so return [] as no cover can be constructed
return []
# SECTION 3: Isomorphism methods
# Overview on isomorphism methods:
# 1. To test if two r-partite hypergraphs are isomorphic we define a "canonical representation" of an r-partite hypergraph.
# 2. The canonical representation involves indexing the vertices from zero for each partition, and incrementing by 1 for each new vertex in the partition.
# then the partitions are sorted.
# 3. To test if two hypergraphs are isomorphic we first get the canonical representation of one of them,
# then for the other we obtain the canonical representation for each possible permutation of its edges,
# if any of theses representation is equal to the canonical representation of the first hypergraph, they are isomophic.
def get_canonical(hg_in):
""" Gets the canonical representation of hg_in. """
r = len(hg_in[0])
widths_list = [0 for x in range(0, r)]
vertex_map = {}
new_hg = [ ]
for edge in hg_in:
new_edge = []
for v in list(enumerate(edge)):
if v not in vertex_map.keys():
new_v = (v[0], widths_list[v[0]])
widths_list[v[0]] = widths_list[v[0]] + 1
vertex_map[v] = new_v
else:
new_v = vertex_map[v]
new_edge.append(new_v)
new_edge = tuple([x[1] for x in new_edge])
new_hg.append(new_edge)
hg_can = [ [e[r] for e in new_hg] for r in range(0,r)]
hg_can.sort()
return hg_can
def is_iso(hg1, hg2):
""" Returns True if hg1 is isomorphic to hg2, False otherwise. See above comment for more explanation."""
hg1_can = get_canonical(hg1)
for hg2_perm in itertools.permutations(hg2):
hg2_can = get_canonical(hg2_perm)
if (hg1_can == hg2_can):
return True
return False
def is_sub_iso(hg1, hg2):
""" Returns True if hg2 is isomorphic to a subgraph of hg1. """
if len(hg2) > len(hg1):
return False
for sub_hg in itertools.combinations(hg1, len(hg2)):
if is_iso(sub_hg, hg2):
return True
return False
def get_all_unique(hgs_in):
""" Takes a list of graphs hgs_in, outputs a smallest set of graphs, such that each graph in hgs_in is isomorphic to one of the graphs in the output set. """
hgs_out = []
for hg1 in hgs_in:
is_already_seen = False
for hg2 in hgs_out:
if is_iso(hg1, hg2):
is_already_seen = True
break
if is_already_seen == False:
hgs_out.append(hg1)
return hgs_out
# SECTION 4: Edge-minimality methods.
def is_edge_min(hg_in, c):
""" Returns True if hg_in is a c-edge-minimal hypergraph, False otherwise."""
r = len(hg_in[0])
for e in hg_in:
sub_hg = [h for h in hg_in if not h == e]
is_extremal = not get_cover_depth(sub_hg, [], c -1)
if is_extremal:
return False
return True
def get_all_edge_min(hg_in, c):
""" Returns all c-edge-minimal exremals contained in hg_in by a recursive depth first search."""
# Parameters: hg_in must be a hypergraph with a cover number c.
if len(hg_in) == 1:
return [hg_in]
edge_min_out = get_all_edge_min_rec(hg_in, c, [])
return edge_min_out
def get_all_edge_min_rec(hg_in,c, cross_list):
""" Recursive auxiliary method used by get_all_edge_min."""
# parameter cross_list is used to keep track of which edges have already been checked in the search tree so as not to try them again, which gives a slight efficiency gain.
edge_min_out = []
new_cross_list = [x for x in cross_list]
r = len(hg_in[0])
is_edge_min = True
for e in hg_in:
new_hg = [h for h in hg_in if not h == e]
if not get_cover_depth(new_hg, [], c - 1):
is_edge_min = False
if e in cross_list:
continue
new_edge_min = get_all_edge_min_rec(new_hg,c, new_cross_list)
edge_min_out.extend(new_edge_min)
new_cross_list.append(e)
if is_edge_min == True:
edge_min_out.append(hg_in)
return edge_min_out
def get_all_nu1_edge_min(nu2_extremal):
""" Given a nu2_extremal r-partite hypergraph, returns all the nu1_edge_minimal hypergraphs contained inside of it."""
r = len(nu2_extremal[0])
sub_ext_out = []
for i in range(1, len(nu2_extremal)):
for hg in itertools.combinations(nu2_extremal, i):
if is_intersecting_hg(hg):
if not get_cover_depth(hg, [], r - 2):
if is_edge_min(hg, r - 1):
sub_ext_out.append(hg)
return sub_ext_out
# SECTION 5: Ryser-stability methods
def get_ryser_stable_cover(hg_in, ryser_seq, c):
""" Given an r-partite hypergraph hg_in, a Ryser-sequence ryser_seq, and an integer c, returns True, if hg_in is c-Ryser-stable relative to the graphs in ryser_seq."""
intersecting_edges = gen_edges(hg_in)
filtered_edges = []
# Filter out all edges that are already contained in the sequence
for e in intersecting_edges:
temp_hg = [h for h in hg_in]
temp_hg.append(e)
is_relative_stable = False
for seq_hg in ryser_seq:
if is_sub_iso(temp_hg, seq_hg):
is_relative_stable = True
break
if not is_relative_stable:
filtered_edges.append(e)
is_relative_stable = get_cover_depth(hg_in, filtered_edges, c)
return is_relative_stable
def create_uset(r, c):
""" Creates the uset of sunflowers described in the thesis needed to run the compute-sequence method. """
if c == 0:
return []
uset_out = []
temp_hg = []
for i in range(1, r):
temp_hg = create_sunflower(r, i, c + 1)
uset_out.append(temp_hg)
return uset_out
def compute_ryser_seq(hg_in, ryser_seq, x_set, c):
""" This is an implementation of the algorithm described in Chapter 2 of the thesis with the same name."""
# Parameters:
# hg_in: hypergraph
# ryser_seq: a list of hypergraphs
# x_set: a set of hypergraphs.
# c: integer
# Output:
# Returns a c-Ryser-stable sequence of hg_in relative to (x_set union uset), but if no such sequence, return
# a hypergraph that contains hg_in that has a covering number more than c.
# We tag a graph by the string "graph" at the beginning, so as to distinguish when a graph is returned, as opposed to a sequence.
r = len(hg_in[0])
uset = create_uset(r, c+1)
# The set all_hg_set will contain all hypergraphs in the sequence, x_set and uset.
all_hg_set = [hg_pair[1] for hg_pair in ryser_seq]
all_hg_set.extend(x_set)
all_hg_set.extend(uset)
ryser_stable_cover = get_ryser_stable_cover(hg_in, all_hg_set, c)
if ryser_stable_cover:
new_seq = [g for g in ryser_seq]
new_seq.insert(0, (ryser_stable_cover, hg_in) )
return new_seq
cover = get_cover_depth(hg_in, [], c)
if not cover:
return ("graph", hg_in)
intersecting_edges = gen_edges(hg_in)
# we randomly sort the edges to iterate on
random.shuffle(intersecting_edges)
itr_hgs = [] # We will fill this with the graphs we need to iterate on.
for e in intersecting_edges:
# This loop is to filter out any of the edges that lead to a graph already contained in sequence.
# This step is not mentioned in the thesis but leads to a slight efficiency gain.
new_hg = [h for h in hg_in]
new_hg.append(e)
is_current_sub = False
for x_hg in x_set:
if is_sub_iso(new_hg, x_hg):
is_current_sub = True
break
if is_current_sub:
continue
itr_hgs.append(new_hg)
for itr_hg in itr_hgs:
# This loop is to check if any of the graphs we need to iterate on is already a graph that would halt the algorithm,
# so that we can halt it straight away without doing any unnecessary iterations.
# This step is not mentioned in the thesis but leads to a slight efficiency gain.
itr_cover = get_cover_depth(itr_hg, [], c)
if not itr_cover:
return ("graph", itr_hg)
for itr_hg in itr_hgs:
# Now all the remaining graphs in itr_hgs are the ones we need to iterate on as described in the thesis.
temp_seq = compute_ryser_seq(itr_hg, ryser_seq, x_set, c)
if temp_seq[0] == "graph":
return temp_seq
ryser_seq = temp_seq
ryser_seq.insert( 0, (cover, hg_in))
return ryser_seq
def enumerate_edge_min(r, c):
""" The algorithm described in chapter 3 of the thesis with the same name. """
# Inputs: r and c are integers.
# Outputs: A set of graphs x_set that contain (upto isomorphism) all r-partite c-cover edge-minimal hypergraphs,
# and a sequence proving it as described in the thesis.
ryser_seq = []
edge = tuple( [0 for x in range(0, r)] )
init_hg = [edge]
x_set = []
temp_seq = compute_ryser_seq(init_hg, ryser_seq, x_set, c-1)
if c == 1:
return init_hg
while (temp_seq[0] == "graph"):
new_edge_mins = get_all_edge_min(temp_seq[1],c)
new_edge_mins = get_all_unique(new_edge_mins)
x_set.extend(new_edge_mins)
temp_seq = compute_ryser_seq(init_hg, ryser_seq, x_set, c -1)
print "Ryser-stable sequence:"
for s in temp_seq:
print s
print "\n%d-paritte %d-cover edge-minimal:" %(r, c)
for x in x_set:
print x
print "\n"
return (temp_seq, x_set)
# SECTION 6: Hypergraphs from the thesis.
# 4-partite, edge-minimal, nu2, extremal hypergraphs presented in chapter 5:
G1 = [ (1,1,1,1), (2,2,2,2), (1,3,3,3), (2,1,5,5), (1,4,4,4), (2,5,6,2), (3,1,6,2), (4,6,5,2), (5,3,1,4), (4,2,6,5), (6,3,4,1), (2,6,6,6), (6,4,1,3), (1,2,1,1)]
G2 = [ (1,1,1,1), (2,2,2,2), (1,3,3,3), (2,4,4,4), (1,5,5,5), (2,2,6,6), (3,1,3,5), (4,4,2,6), (5,5,3,1), (6,2,2,4), (5,1,5,3), (2,6,2,4), (1,1,4,1), (4,2,1,4)]
G3 = [ (1,1,1,1), (2,2,2,2), (1,3,3,3), (2,4,4,4), (1,5,5,5), (2,2,6,6), (3,1,3,5), (4,4,2,6), (5,5,3,1), (6,2,2,4), (5,1,5,3), (2,6,2,4), (1,1,4,1), (4,2,6,4)]
# {6,7,11}-partite hypergraphs, intersecting, hypergraphs presented in chapter 7:
hg6 = [(1,4,4,5,3,5), (2,5,2,5,5,3), (3,4,5,3,4,3), (4,1,5,4,5,5), (4,5,4,2,4,4), (5,2,5,5,1,4), (5,5,1,3,2,5), (5,4,3,2,5,2), (5,3,4,4,3,3), (6,2,4,3,5,1), (6,4,2,4,2,4), (6,5,5,1,3,2), (6,3,3,5,4,5)]
hg7 = [ (1,1,1,1,1,1,1), (1,2,2,2,2,2,2), (1,3,1,3,3,3,3), (1,3,3,3,4,3,4), (1,4,4,4,5,4,5), (1,5,5,5,6,5,3), (2,1,2,3,5,6,3), (2,3,4,1,6,2,6), (2,6,4,5,2,3,1), (3,1,1,5,5,2,4), (3,1,2,6,6,3,5), (3,3,6,2,5,5,1), (3,5,4,3,1,3,2), (3,5,4,3,2,1,7), (3,6,3,1,2,4,3), (4,1,4,2,4,4,3), (4,2,5,1,5,3,7), (4,3,1,3,2,5,5), (4,5,2,1,5,3,1), (5,3,1,4,2,3,3), (5,3,2,5,1,4,7), (6,2,1,3,6,4,1)]
hg11 = [ (0,0,0,0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0,1,1,1), (0,0,0,0,0,0,0,1,0,1,2), (0,0,0,0,0,1,0,0,0,1,4), (0,0,0,0,1,0,0,0,0,1,5), (0,0,0,1,0,0,0,0,0,1,6), (0,1,2,2,2,2,2,2,2,2,8), (0,2,3,3,3,3,3,3,3,3,8), (0,3,4,4,4,4,4,4,4,4,8), (0,5,0,0,0,0,0,0,0,1,9), (1,3,3,6,6,0,6,5,2,6,4), (1,4,2,7,3,4,7,0,6,7,2), (2,1,5,7,0,7,8,3,4,6,5), (2,2,4,6,5,2,7,7,0,8,1), (2,3,6,3,7,5,9,0,7,2,2), (2,7,3,4,2,6,0,8,6,5,3), (3,0,3,7,8,2,9,6,5,4,9), (3,2,7,0,4,8,8,5,6,2,6), (3,7,5,8,3,0,4,2,7,8,4), (3,8,6,5,0,6,7,4,2,3,5), (4,3,8,2,3,6,8,7,5,1,0), (4,7,9,5,4,2,3,0,9,6,2), (4.,9,3,0,5,7,2,4,7,7,6), (5,1,3,8,4,5,7,9,8,1,0), (5,8,2,3,5,0,8,8,9,4,4), (5,9,6,9,3,2,0,5,4,9,3), (6,1,9,3,8,6,4,5,0,7,1), (6,3,5,0,2,3,7,6,9,9,6), (6,4,0,4,6,2,8,9,7,3,7), (6,8,3,2,9,8,5,0,4,8,2), (7,2,8,5,2,0,9,9,4,7,4), (7,7,0,2,7,7,7,5,3,4,7), (7,9,4,8,8,3,8,0,2,5,2), (8,3,7,8,0,2,5,8,3,7,5), (8,4,8,3,4,7,0,6,2,8,3), (8,6,3,5,7,4,8,2,0,9,1), (8,8,4,7,2,9,3,5,7,1,0), (8,9,9,4,9,0,7,3,5,2,4), (9,0,0,0,0,0,0,0,0,1,8), (0,0,0,0,0,0,1,0,0,1,3), (0,0,1,0,0,0,0,0,0,1,7), (0,4,5,5,5,5,5,5,5,5,8), (1,6,0,8,5,6,3,6,4,2,7), (2,4,7,2,8,0,3,4,8,9,4), (3,3,2,9,9,7,3,9,0,5,1), (4,4,6,8,2,8,6,3,0,4,1), (5,7,8,7,6,3,5,4,0,2,1), (6,2,2,8,7,9,0,4,5,6,3), (7,1,6,0,6,4,3,8,5,8,6), (8,2,5,9,6,6,2,0,8,4,2), (8,7,2,0,8,5,6,7,4,3,6)]
def verify_ahmad_thesis():
# Test which edge-minimal intersecting hypergraphs are contained in G1, G2, G3
# (claims made in chapter 5).
print "\nTesting claims made in chapter 5:"
G1_min_subgraphs = get_all_nu1_edge_min(G1)
print "\n G1 has the following intersecting edge-minimal hypergraphs:"
for hg in G1_min_subgraphs:
print hg
G2_min_subgraphs = get_all_nu1_edge_min(G2)
print "\n G2 has the following intersecting edge-minimal hypergraphs:"
for hg in G2_min_subgraphs:
print hg
G3_min_subgraphs = get_all_nu1_edge_min(G3)
print "\n G3 has the following intersecting edge-minimal hypergraphs:"
for hg in G3_min_subgraphs:
print hg
# Test that claims made about extremality made in chap7 of the thesis are correct.
print "\n\nTesting claims made in chapter 7:"
if is_edge_min(hg6, 5):
print "\thg6 is extremal."
if is_edge_min(hg7, 6):
print "\thg7 is extremal."
# The following takes around 10 hours on a standard desktop, so commented out.
#if is_edge_min(hg11, 10):
# print "hg11 is extremal."
return