CarnivalFlow bfs_heuristic bug

[stefanhannie]

I might be in a bit of an edge case here, but I'm hitting a bug where solving the problem is immediately returned as infeasible, yet a solution should exist. I've got a small repro example, and I think it has to do with the bfs_heuristic implementation.

# %%
import corneto as cn
from corneto.methods.future import CarnivalFlow

# %%
G = cn.Graph()
G.add_edges([("A", "B"), ("A", "C"), ("C", "D")])
G.plot()

# %%
data = cn.Data.from_cdict(
    {
        "sample_1": {
            "A": {"value": 1, "mapping": "vertex", "role": "input"},
            "B": {"value": 1, "mapping": "vertex", "role": "output"},
        },
        "sample_2": {
            "B": {"value": 1, "mapping": "vertex", "role": "input"},
            "C": {"value": 1, "mapping": "vertex", "role": "input"},
            "D": {"value": 1, "mapping": "vertex", "role": "output"},
        },
    }
)
data

# %%
carnival = CarnivalFlow()
P = carnival.build(G, data)

# %%
"B" in carnival.processed_graph.V

# %%
carnival.processed_graph.plot()

# %%
# Returns infeasible
P.solve(verbosity=1)

# %%
# Correctly finds solution
carnival_2 = CarnivalFlow(enable_bfs_heuristic=False)
P_2 = carnival_2.build(G, data)
P_2.solve(verbosity=1)

This issue is that in sample_1, B is reachable from A, so it's not dropped in the graph pruning, so it's present in the union graph of the samples. But then in create_flow_based_problem it's flagged as unreachable in sample_2, while simultaneously being an input vertex.

Now that I've diagnosed the problem, I can do the pre-filtering myself to drop B from my input vertices in sample_2, but could be a nice buff to handle this case internally.

Also, thanks for building this really cool tool.