Homer's profile - activity

Code for generating collections of cells I have written the following code in SageMath to generate all collections of ce

I tested it and it is consistent with the output that I obtained for all the other digraphs, that I tested so far. Thank

I tested it and it is consistent with the output that I obtained for all the other digraphs, that I tested so far. Thank

I'd like to share an algorithm in Sage to compute minimal directed cuts and minimal dijoins of a digraph and to ask for feedback regarding its correctness and efficiency.

I firstly recall some basic definitions.

Definition. Let $G = (V(G),E(G))$ be a directed graph (abbreviated to digraph throughout).

• A non-empty set of edges $C^* \subseteq E(G)$ is called a cut if there is a partition $V_0 \sqcup V_1 = V(G)$ of the vertex set such that $C^*$ is the set of edges connecting a vertex of $V_0$ and a vertex of $V_1$.

• A cut $C^* $ is directed if either each edge of $C^* $ leads from $V_0$ to $V_1$, or each edge of $C^*$ leads from $V_1$ to $V_0$.

• A cut $C^* $ is minimal if there does not exist any cut properly contained in $C^* $.
• A dijoin is a subset $E$ of the edge set $E(G)$ such that $E\cap K\neq \emptyset$, for every directed cut $K$ of $G$.
• A dijoin $E$ is minimal if there does not exist any dijoin properly contained in $E$.

The code. The Sage code (with an example) can be found here:

from itertools import chain, combinations

def all_subsets(edges):
    """Returns all subsets of the set of edges."""
    edges_list = list(edges)
    return [set(comb) for r in range(1, len(edges_list)+1) for comb in combinations(edges_list, r)]


def directed_edge_cuts(D):
    """
    Given a directed graph D, returns the list of minimal directed cuts.
    Each cut is a list of directed edges that disconnect the graph into two
    parts, with all edges going in one direction between them.
    """
    from itertools import combinations

    # Convert the directed graph to an undirected one
    G = D.to_undirected()
    edges = list(G.edges(labels=False))
    n = len(edges)

    minimal_cuts = []

    for r in range(1, n + 1):
        for subset in combinations(edges, r):
            subset_set = set(subset)

        # Skip supersets of already found cuts
        if any(set(cut).issubset(subset_set) for cut in minimal_cuts):
            continue

        # Remove edges from a copy of the undirected graph
        H = G.copy()
        H.delete_edges(subset)

        if not H.is_connected():
            # Get components
            components = H.connected_components()
            if len(components) != 2:
                continue  # Only consider binary cuts

            from_set = set(components[0])
            to_set = set(components[1])

            # Classify directed edges in the subset
            forward_cut = []
            backward_cut = []
            other = []

            for (u, v) in subset:
                if D.has_edge(u, v) and u in from_set and v in to_set:
                    forward_cut.append((u, v))
                elif D.has_edge(u, v) and u in to_set and v in from_set:
                    backward_cut.append((u, v))
                else:
                    other.append((u, v))  # not a valid directed edge

            # Keep only pure forward or pure backward cuts
            if len(forward_cut) == len(subset):
                minimal_cuts.append(forward_cut)
            elif len(backward_cut) == len(subset):
                minimal_cuts.append(backward_cut)

return minimal_cuts


def find_dijoins(D):
    """
    Finds all minimal-cardinality dijoins in a digraph D.
    A dijoin is a set of edges that intersects all minimal directed cuts.
    """
    E = set(D.edges(labels=False))
    S = all_subsets(E)
    C = [set(cut) for cut in directed_edge_cuts(D)]

    L = []
    Visited = []

    for Si in S:
        # Skip supersets already visited
        if any(v.issubset(Si) for v in Visited):
            continue

        # Check if Si intersects all cuts
        test = all(len(Si & c) > 0 for c in C)
        if test:
            L.append(Si)
            Visited.append(Si)

# Convert to list for manipulation
L = [list(subset) for subset in L]

if not L:
    return []

min_size = min(len(x) for x in L)
FinalList = [x for x in L if len(x) == min_size]

return FinalList


#############################################

# Build the directed graph
D = DiGraph([
    (1,4), (1,5),
    (2,4), (2,5), (2,6),
    (3,4), (3,5), (3,6)
])

cuts = directed_edge_cuts(D)

# Print the minimal directed cuts
for i, cut in enumerate(cuts, 1):
    print(f"Directed Cut {i}: {cut}")

# Find the minimal dijoins
dijoins = find_dijoins(D)
print("Minimal dijoins:")
for i, dj in enumerate(dijoins, 1):
    print(f"Dijoin {i}: {dj}")

Question. This algorithm is quite slow; for example, it took about 30 minutes to process the following graph before I stopped it:

D = DiGraph([
    (1,13), (1,14),
    (2,13), (2,14), (2,15),
    (3,10), (3,11), (3,12), (3,13), (3,14), (3,15), (3,17), (3,19), (3,20),
    (4,10), (4,11), (4,12), (4,13), (4,14), (4,15), (4,17), (4,19), (4,20),
    (5,19), (5,20), 
    (6,13), (6,14), (6,16), (6,18),
    (7,10), (7,11), (7,12),  
    (8,13), (8,14), (8,16), (8,18),
])

Can the current implementation be significantly optimised to improve computational efficiency and runtime?

The problem I have is that I cannot share link because I don't have enough karma :( In that case, I would share the link

The problem I have is that I cannot share link because I don't have enough karma :( In that case, I would share the link

Algorithm for listing minimal directed cuts and minimal dijoins I'd like to share an algorithm in Sage to compute minima