Skip to content

Instantly share code, notes, and snippets.

@kgourgou
Created March 26, 2018 23:02
Show Gist options
  • Save kgourgou/168f59e006223c567cd88214efbdfcc9 to your computer and use it in GitHub Desktop.
Save kgourgou/168f59e006223c567cd88214efbdfcc9 to your computer and use it in GitHub Desktop.
Converts a tree to cherry tree -- needs review.
def tree_to_cherry_tree(A):
"""
Given the adj matrix of a tree,
produces a cherry t-tree that includes it.
Arguments:
- adj: numpy array or sparse array, the adjacency matrix of the tree.
Returns:
- new_adj: numpy array or sparse array, the adjacency matrix of the cherry tree.
"""
new_A = A.copy()
n,m = new_A.shape
for i in range(n):
new_A[i,i] = -5
V = set([i for i in range(len(A))])
node1 = V.pop()
node2 = next((i for i, x in enumerate(list(A[node1, :])) if x), None) # x!= 0 for strict match
V.remove(node2)
for i in V:
other_node = next((j for j, x in enumerate(list(A[i, :])) if x), None)
not_connected = next((j for j, x in enumerate(list(new_A[i, :])) if x == 0), None)
new_A[i,not_connected] = 1
new_A[not_connected,i] = 1
for i in range(n):
new_A[i,i] = 0
return new_A
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment