mingaleg/3d_matching.py

## 3d_matching.py
class Bitmasks:
    """
    do bitmasks operations in linear time
    """
    def __init__(self):
        pass

    def reverse_bit(self, mask):
        """
        expecting mask with exactly one '1'
        returns number of that '1' digit
        actually, this calculates log2 of power of 2
        examples:
            reverse_bit(1) == 0 # 1 == 2 ** 0
            reverse_bit(4) == 2 # 4 == 2 ** 2
            reverse_bit(1024) == 10 # 1024 == 2 ** 10
        """
        cur = 0
        while mask > 1:
            cur += 1
            mask //= 2
        return cur

    def lst2mask(self, lsts):
        """
        expecting iterable container of numbers
        returns mask with requested bits
        examples:
            lst2mask([0, 3, 5]) = 0b101001 == 2**0 + 2**3 + 2**5
        """
        return sum((1 << x) for x in set(lsts))

    def popbit(self, mask):
        """
        expecting nonzero mask
        returns tuple (number of lowest bit, mask without that bit)
        examples:
            popbit(11) == popbit(0b1011) == (0, 0b1010) == (0, 10)
            popbit(12) == popbit(0b1100) == (2, 0b1000) == (2, 8)
        """
        others = mask & (mask - 1)
        repmask = mask ^ others
        return self.reverse_bit(repmask), others

    def mask2seq(self, mask):
        """
        expecting mask
        yielding all mask's bits
        examples:
            list(mask2seq(11)) == list(mask2seq(0b1011)) == [0, 2, 3]
        """
        while mask:
            rep, mask = self.popbit(mask)
            yield rep

    def popcount(self, mask):
        """
        expecting mask
        returns total number of '1's
        examples:
            popcount(11) == popcount(0b1011) == 3
        """
        return sum(1 for _ in self.mask2seq(mask))

    def is_subset(self, left, right):
        """
        expecting two masks
        returns True if left is subset of right
        """
        return (left | right) == right


class FastBitmasks(Bitmasks):
    """
    do almost all bitmasks operations in constant time
    after precalculations
    """
    def __init__(self, n):
        """
        precalculate all masks with length = n
        """
        self.n = n
        self.build_reverse_bit()
        self.build_popcount()

    def build_reverse_bit(self):
        self._rb = [0] * (1 << self.n)
        for i in range(self.n):
            self._rb[1 << i] = i

    def reverse_bit(self, mask):
        return self._rb[mask]

    def build_popcount(self):
        self._pc = [0] * (1 << self.n)
        for mask in range(1, 1 << self.n):
            _, other = self.popbit(mask)
            self._pc[mask] = self._pc[other] + 1

    def popcount(self, mask):
        return self._pc[mask]


class Cliquer:
    """
    Find max clique in every subgraph
    """
    def __init__(self, G, bitmasks=None):
        """
        expecting list of masks G which represents adjacency matrix
        builds self.max_clique list, where for every mask max_clique[mask]
        stores information about maximal clique among vertecies in mask

        max_clique[mask] = (size of max clique among mask, submask of mask equal to that clique)
        """
        self.G = G
        self.n = len(G)
        self.bitmasks = bitmasks or Bitmasks(self.n)
        self.build_is_clique()
        self.build_max_clique()

    def build_is_clique(self):
        """
        builds self.is_clique
        self.is_clique[mask] = True if verticies from mask forms a clique
        """
        dp = self.is_clique = [None] * (1 << self.n)
        dp[0] = True # empty subgraph is clique
        for mask in range(1, 1 << self.n):
            # divide mask into one vertice `rep` and mask of other verticies in mask
            rep, others = self.bitmasks.popbit(mask)

            # `mask` is clique iff `others` is clique and `rep` is adjacent to all verticies from `other`
            dp[mask] = dp[others] and self.bitmasks.is_subset(others, self.G[rep])


    def build_max_clique(self):
        """
        builds max_clique
        read __init__ help for more info
        """
        dp = self.max_clique = [(0, 0)] * (1 << self.n)
        for mask in range(1, 1 << self.n):
            if self.is_clique[mask]:
                # if `mask` is clique then max subgraph which froms a clique is `mask` itself
                dp[mask] = (self.bitmasks.popcount(mask), mask)
                continue

            # divide mask into one vertice `rep` and mask of other verticies in mask
            rep, others = self.bitmasks.popbit(mask)

            # max clique in `mask` is at least as in `others` (`rep` is not in max clique)
            dp[mask] = dp[others]

            # check if `rep` is in max clique
            rep_adj_size, rep_adj_ans = dp[(self.G[rep] & mask) ^ (1 << rep)]
            if rep_adj_size >= dp[mask][0]:
                dp[mask] = (rep_adj_size + 1, rep_adj_ans | (1 << rep))


class FastCliquer:
    """
    Optimize Cliquer using Meet-in-the-middle trick
    """
    bitmasks = Bitmasks()
    def __init__(self, G):
        self.n = len(G)
        self.G = G
        self.n0 = self.n // 2
        self.n1 = self.n - self.n0
        self.fastbitmasks = FastBitmasks(self.n1)
        self.build_subgraphs()
        self.build_mid_grouped()
        self.c0 = Cliquer(self.g0, self.fastbitmasks)
        self.c1 = Cliquer(self.g1, self.fastbitmasks)
        self.find_max_clique()


    def __call__(self):
        ret = []
        for v0 in self.bitmasks.mask2seq(self.ans[1]):
            ret.append(v0)
        for v1 in self.bitmasks.mask2seq(self.ans[2]):
            ret.append(v1 + self.n0)
        return ret

    def find_max_clique(self):
        ans = (0, 0, 0)
        for mask0 in range(1 << self.n0):
            mask1 = self.mid_grouped[mask0]
            a0, mc0 = self.c0.max_clique[mask0]
            a1, mc1 = self.c1.max_clique[mask1]
            cur = (a0+a1, mc0, mc1)
            ans = max(ans, cur)
        self.ans = ans
        return ans

    def build_subgraphs(self):
        self.g0 = [[] for i in range(self.n0)]
        self.g1 = [[] for i in range(self.n1)]
        self.gs = [self.g0, self.g1]
        self.mid = [[] for i in range(self.n0)]
        for v in range(self.n):
            gv, av = self.assign_vertex(v)
            for u in self.bitmasks.mask2seq(self.G[v]):
                gu, au = self.assign_vertex(u)
                if gv == gu:
                    self.gs[gv][av].append(au)
                elif gv < gu:
                        self.mid[av].append(au)
        for gg in (self.g0, self.g1, self.mid):
            for i in range(len(gg)):
                gg[i] = self.bitmasks.lst2mask(gg[i])

    def build_mid_grouped(self):
        dp = self.mid_grouped = [0] * (1 << self.n0)
        dp[0] = (1 << self.n1) - 1
        for mask in range(1, 1 << self.n0):
            rep, others = self.fastbitmasks.popbit(mask)
            dp[mask] = dp[others] & self.mid[rep]

    def assign_vertex(self, v):
        if v < self.n0:
            return 0, v
        else:
            return 1, v - self.n0


def list_matching(lsts):
    n = len(lsts)
    G = [[i] for i in range(n)]
    for i in range(n):
        for j in range(i):
            if not (set(lsts[i]) & set(lsts[j])):
                G[i].append(j)
                G[j].append(i)
    G = [Bitmasks().lst2mask(x) for x in G]
    return FastCliquer(G)()


l = [[0, 1, 12], [0, 4, 11], [0, 7, 19], [0, 15, 17], [0, 16, 18], [1, 4, 16], [1, 13, 25], [2, 4, 23], [2, 10, 27], [2, 12, 19], [2, 14, 22], [2, 16, 20], [3, 6, 13], [3, 7, 22], [3, 10, 14], [3, 20, 26], [4, 7, 13], [4, 17, 22], [5, 7, 25], [5, 9, 22], [5, 10, 21], [5, 11, 23], [5, 12, 20], [5, 13, 16], [5, 14, 15], [6, 7, 17], [6, 10, 23], [7, 11, 20], [7, 14, 27], [7, 18, 23], [8, 12, 26], [8, 14, 17], [8, 22, 23], [11, 12, 18], [12, 17, 21], [12, 23, 25], [13, 19, 20], [13, 21, 24], [18, 20, 25], [18, 24, 26], [19, 24, 27]]


print(list_matching(l))
	class Bitmasks:
	"""
	do bitmasks operations in linear time
	"""
	def __init__(self):
	pass

	def reverse_bit(self, mask):
	"""
	expecting mask with exactly one '1'
	returns number of that '1' digit
	actually, this calculates log2 of power of 2
	examples:
	reverse_bit(1) == 0 # 1 == 2 ** 0
	reverse_bit(4) == 2 # 4 == 2 ** 2
	reverse_bit(1024) == 10 # 1024 == 2 ** 10
	"""
	cur = 0
	while mask > 1:
	cur += 1
	mask //= 2
	return cur

	def lst2mask(self, lsts):
	"""
	expecting iterable container of numbers
	returns mask with requested bits
	examples:
	lst2mask([0, 3, 5]) = 0b101001 == 20 + 23 + 2**5
	"""
	return sum((1 << x) for x in set(lsts))

	def popbit(self, mask):
	"""
	expecting nonzero mask
	returns tuple (number of lowest bit, mask without that bit)
	examples:
	popbit(11) == popbit(0b1011) == (0, 0b1010) == (0, 10)
	popbit(12) == popbit(0b1100) == (2, 0b1000) == (2, 8)
	"""
	others = mask & (mask - 1)
	repmask = mask ^ others
	return self.reverse_bit(repmask), others

	def mask2seq(self, mask):
	"""
	expecting mask
	yielding all mask's bits
	examples:
	list(mask2seq(11)) == list(mask2seq(0b1011)) == [0, 2, 3]
	"""
	while mask:
	rep, mask = self.popbit(mask)
	yield rep

	def popcount(self, mask):
	"""
	expecting mask
	returns total number of '1's
	examples:
	popcount(11) == popcount(0b1011) == 3
	"""
	return sum(1 for _ in self.mask2seq(mask))

	def is_subset(self, left, right):
	"""
	expecting two masks
	returns True if left is subset of right
	"""
	return (left \| right) == right


	class FastBitmasks(Bitmasks):
	"""
	do almost all bitmasks operations in constant time
	after precalculations
	"""
	def __init__(self, n):
	"""
	precalculate all masks with length = n
	"""
	self.n = n
	self.build_reverse_bit()
	self.build_popcount()

	def build_reverse_bit(self):
	self._rb = [0] * (1 << self.n)
	for i in range(self.n):
	self._rb[1 << i] = i

	def reverse_bit(self, mask):
	return self._rb[mask]

	def build_popcount(self):
	self._pc = [0] * (1 << self.n)
	for mask in range(1, 1 << self.n):
	_, other = self.popbit(mask)
	self._pc[mask] = self._pc[other] + 1

	def popcount(self, mask):
	return self._pc[mask]



	class Cliquer:
	"""
	Find max clique in every subgraph
	"""
	def __init__(self, G, bitmasks=None):
	"""
	expecting list of masks G which represents adjacency matrix
	builds self.max_clique list, where for every mask max_clique[mask]
	stores information about maximal clique among vertecies in mask

	max_clique[mask] = (size of max clique among mask, submask of mask equal to that clique)
	"""
	self.G = G
	self.n = len(G)
	self.bitmasks = bitmasks or Bitmasks(self.n)
	self.build_is_clique()
	self.build_max_clique()

	def build_is_clique(self):
	"""
	builds self.is_clique
	self.is_clique[mask] = True if verticies from mask forms a clique
	"""
	dp = self.is_clique = [None] * (1 << self.n)
	dp[0] = True # empty subgraph is clique
	for mask in range(1, 1 << self.n):
	# divide mask into one vertice `rep` and mask of other verticies in mask
	rep, others = self.bitmasks.popbit(mask)

	# `mask` is clique iff `others` is clique and `rep` is adjacent to all verticies from `other`
	dp[mask] = dp[others] and self.bitmasks.is_subset(others, self.G[rep])


	def build_max_clique(self):
	"""
	builds max_clique
	read __init__ help for more info
	"""
	dp = self.max_clique = [(0, 0)] * (1 << self.n)
	for mask in range(1, 1 << self.n):
	if self.is_clique[mask]:
	# if `mask` is clique then max subgraph which froms a clique is `mask` itself
	dp[mask] = (self.bitmasks.popcount(mask), mask)
	continue

	# divide mask into one vertice `rep` and mask of other verticies in mask
	rep, others = self.bitmasks.popbit(mask)

	# max clique in `mask` is at least as in `others` (`rep` is not in max clique)
	dp[mask] = dp[others]

	# check if `rep` is in max clique
	rep_adj_size, rep_adj_ans = dp[(self.G[rep] & mask) ^ (1 << rep)]
	if rep_adj_size >= dp[mask][0]:
	dp[mask] = (rep_adj_size + 1, rep_adj_ans \| (1 << rep))


	class FastCliquer:
	"""
	Optimize Cliquer using Meet-in-the-middle trick
	"""
	bitmasks = Bitmasks()
	def __init__(self, G):
	self.n = len(G)
	self.G = G
	self.n0 = self.n // 2
	self.n1 = self.n - self.n0
	self.fastbitmasks = FastBitmasks(self.n1)
	self.build_subgraphs()
	self.build_mid_grouped()
	self.c0 = Cliquer(self.g0, self.fastbitmasks)
	self.c1 = Cliquer(self.g1, self.fastbitmasks)
	self.find_max_clique()


	def __call__(self):
	ret = []
	for v0 in self.bitmasks.mask2seq(self.ans[1]):
	ret.append(v0)
	for v1 in self.bitmasks.mask2seq(self.ans[2]):
	ret.append(v1 + self.n0)
	return ret

	def find_max_clique(self):
	ans = (0, 0, 0)
	for mask0 in range(1 << self.n0):
	mask1 = self.mid_grouped[mask0]
	a0, mc0 = self.c0.max_clique[mask0]
	a1, mc1 = self.c1.max_clique[mask1]
	cur = (a0+a1, mc0, mc1)
	ans = max(ans, cur)
	self.ans = ans
	return ans

	def build_subgraphs(self):
	self.g0 = [[] for i in range(self.n0)]
	self.g1 = [[] for i in range(self.n1)]
	self.gs = [self.g0, self.g1]
	self.mid = [[] for i in range(self.n0)]
	for v in range(self.n):
	gv, av = self.assign_vertex(v)
	for u in self.bitmasks.mask2seq(self.G[v]):
	gu, au = self.assign_vertex(u)
	if gv == gu:
	self.gs[gv][av].append(au)
	elif gv < gu:
	self.mid[av].append(au)
	for gg in (self.g0, self.g1, self.mid):
	for i in range(len(gg)):
	gg[i] = self.bitmasks.lst2mask(gg[i])

	def build_mid_grouped(self):
	dp = self.mid_grouped = [0] * (1 << self.n0)
	dp[0] = (1 << self.n1) - 1
	for mask in range(1, 1 << self.n0):
	rep, others = self.fastbitmasks.popbit(mask)
	dp[mask] = dp[others] & self.mid[rep]

	def assign_vertex(self, v):
	if v < self.n0:
	return 0, v
	else:
	return 1, v - self.n0


	def list_matching(lsts):
	n = len(lsts)
	G = [[i] for i in range(n)]
	for i in range(n):
	for j in range(i):
	if not (set(lsts[i]) & set(lsts[j])):
	G[i].append(j)
	G[j].append(i)
	G = [Bitmasks().lst2mask(x) for x in G]
	return FastCliquer(G)()


	l = [[0, 1, 12], [0, 4, 11], [0, 7, 19], [0, 15, 17], [0, 16, 18], [1, 4, 16], [1, 13, 25], [2, 4, 23], [2, 10, 27], [2, 12, 19], [2, 14, 22], [2, 16, 20], [3, 6, 13], [3, 7, 22], [3, 10, 14], [3, 20, 26], [4, 7, 13], [4, 17, 22], [5, 7, 25], [5, 9, 22], [5, 10, 21], [5, 11, 23], [5, 12, 20], [5, 13, 16], [5, 14, 15], [6, 7, 17], [6, 10, 23], [7, 11, 20], [7, 14, 27], [7, 18, 23], [8, 12, 26], [8, 14, 17], [8, 22, 23], [11, 12, 18], [12, 17, 21], [12, 23, 25], [13, 19, 20], [13, 21, 24], [18, 20, 25], [18, 24, 26], [19, 24, 27]]


	print(list_matching(l))