def ant_colony_optimization(g, verbose=True, iterations = 100, ants_per_iteration = 50, q = 10, degradation_factor = .9, use_inertia = False):
    best_cycle = best_so_far # can be pre set or set to None
    best_length = cycle_length(g, best_so_far) #hardcoded instance. Else use None
    if use_inertia: #this is adding pheromones everywhere if the process stagnates. This did not improve my results and is left off.
      old_best = None
      inertia = 0
      patience = 100

    for iteration in range(iterations):
        cycles = [traverse_graph(g, random.randint(0, g.nodes -1)) for _ in range(ants_per_iteration)] # could be trivially parallelized if not on Mac through multiprocessing
        cycles.sort(key = lambda x: x[1])
        cycles = cycles[: ants_per_iteration//2] #optionally keep best half.

        if best_cycle: #elitism
            cycles.append((best_cycle, best_length))
            if use_inertia:
                old_best = best_length

        for cycle, total_length in cycles: # pheromone update
            total_length = cycle_length(g, cycle)
            if total_length < best_length:
                best_length = total_length
                best_cycle = cycle

            delta = q/total_length
            i = 0
            while i < len(cycle) -1:
                g.intensity[cycle[i]][cycle[i+1]]+= delta
                i+=1
            g.intensity[cycle[i]][cycle[0]] += delta
            g.intensity *= degradation_factor
        
        if use_inertia and best_cycle:        
            if old_best == best_length:
                    inertia+=1
            else:
                inertia = 0
            if inertia > patience:
                g.intensity += g.intensity.mean() # applying shake

    return best_cycle