'''
Input for the base algorithms:
- M is a matroid.
- T_0 is an initial base of M
'''
def greedy_base_closest(M,T_0):
# Greedy-base with closest tiebreak.
# We begin by imposing a linear order on the elements
E = sorted(M.groundset())
m = len(E)
# Setting initial states
active = E
T = set(T_0)
# Visiting first base
yield(T)
while True:
visited = False
# We check all pairs e,f such that e is active, and take the smallest possible e.
for i in range(1,m,1):
e = E[i]
if e in active:
for j in range(i-1,-1,-1):
f = E[j]
if M.is_basis(T.symmetric_difference({e,f})) and not visited:
T = T.symmetric_difference({e,f})
active = [a for a in E if a<e] + [a for a in active if a>e]
yield(T)
visited = True
if not visited:
break
def greedy_base_furthest(M,T_0):
# Greedy-base with furthest tiebreak.
# We begin by imposing a linear order on the elements
E = sorted(M.groundset())
m = len(E)
# Initializing variables
T = set(T_0)
T_star = {e for e in E if e not in T_0}
stack = []
visit = []
# Initialization of the stack:
# add elements f whose f-prefix minor has a branching in the colexico tree.
for i in range(m-1,-1,-1):
e=E[i]
partial_T = [g for g in E if g in T and g>e]
partial_T_star = [g for g in E if g in T_star and g>e]
if M.is_independent(partial_T+[e]) and M.is_coindependent(partial_T_star+[e]):
stack.append(e)
# Output first basis
yield T
# Loop while stack is nonempty
while stack:
e = stack.pop()
j = E.index(e)
T = T.symmetric_difference({e})
T_star = T_star.symmetric_difference({e})
# We descend to respect the furthest tie breaker rule by delaying and to add into the stack
for i in range(j-1,-1,-1):
f = E[i]
partial_T = [g for g in E if g in T and g>f]
partial_T_star = [g for g in E if g in T_star and g>f]
# If there is a branching add to the stack
if M.is_independent(partial_T+[f]) and M.is_coindependent(partial_T_star+[f]):
stack.append(f)
# Otherwise, choose f if we are forced to
elif (M.is_independent(partial_T+[f]) and f not in T) or (M.is_coindependent(partial_T_star+[f]) and f in T):
T = T.symmetric_difference({f})
T_star = T_star.symmetric_difference({f})
yield T