给定指定DAG，如何编码/解码以生成其多种合法拓扑排序？

Got it, let's work through this problem together. We have a specific directed acyclic graph (DAG) to work with, and we need to build encoding/decoding logic that only spits out valid topological orders for it—no invalid sequences allowed.

First, Let's Map Out Our DAG #

Let's restate the graph clearly to avoid confusion:

• Vertex set: V = {1,2,3,4,5,6,7}
• Edge set: E = {(1,2),(1,3),(1,4),(2,5),(3,5),(4,6),(5,7),(6,7)}

It has a clean layered structure, which makes our job easier:

• Source layer: Only node 1 (no incoming edges)
• Middle layer 1: Nodes 2, 3, 4 (all depend solely on node 1)
• Middle layer 2: Node 5 (depends on 2 and 3), Node 6 (depends on 4)
• Sink layer: Only node 7 (depends on 5 and 6)

Encoding a Valid Topological Order #

The core idea here is to encode the choices we make when building the topological order, rather than the order itself. Since topological orders require picking only nodes with no pending dependencies (in-degree 0) at each step, we can track the valid options at each step and turn those choices into a compact code.

Step-by-Step Encoding Process #

1. Initialize: Start with the original in-degree values for each node:
   • in_degree = {1:0, 2:1, 3:1, 4:1, 5:2, 6:1, 7:2}
   • Collect all nodes with in-degree 0 (initially just [1]) as valid choices.
2. Iterate through the topological order:
   • For each node in the order (except the last one, which is always 7 and deterministic):
     • Find its index in the current list of valid choices (0-based, stick with this consistency).
     • Add this index to your encoding sequence.
     • Remove the node from the graph, decrement the in-degree of its neighbors, and add any neighbors whose in-degree drops to 0 to the valid choices list.
3. Optional Compactification: Convert the sequence of indices into a single integer using variable-base arithmetic (each step's base is the number of valid choices at that step).

Example Encoding

Take the valid order [1,2,3,5,4,6,7]:

• Step 1: Valid choices = [1], pick index 0 → encoding starts as [0]
• Step 2: Valid choices = [2,3,4], pick index 0 → encoding becomes [0,0]
• Step3: Valid choices = [3,4], pick index 0 → encoding [0,0,0]
• Step4: Valid choices = [5,4], pick index0 → encoding [0,0,0,0]
• Step5: Valid choices = [4], pick index0 → encoding [0,0,0,0,0]
• Step6: Valid choices = [6], pick index0 → encoding [0,0,0,0,0,0]

The total number of valid topological orders here is 1*3*2*2*1*1 =12, so this encoding can represent all 12 orders with a 6-element sequence (or a single integer between 0 and 11).

Decoding an Encoding Back to a Topological Order #

Decoding is just the reverse of encoding—we start with the original DAG state and use the encoded indices to pick the correct valid node at each step.

Step-by-Step Decoding Process #

1. Initialize: Reset to the original in-degree values and valid choices list ([1]).
2. Iterate through the encoded indices:
   • For each index in the encoding:
     • Pick the node at that index from the current valid choices list.
     • Add it to the output topological order.
     • Decrement the in-degree of its neighbors, adding any that hit 0 to the valid choices list.
     • Remove the picked node from valid choices.
3. Final Step: Add the last remaining node (7) to the order.

Example Python Implementation #

Here's a quick, working code snippet to demonstrate this logic:

# Define our DAG structure
adjacency_list = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [6],
    5: [7],
    6: [7],
    7: []
}
original_in_degree = {1:0, 2:1, 3:1, 4:1, 5:2, 6:1, 7:2}
all_nodes = {1,2,3,4,5,6,7}

def encode_top_order(top_order):
    in_degree = original_in_degree.copy()
    valid_nodes = [n for n in all_nodes if in_degree[n] == 0]
    encoding = []
    # Skip the last node (always 7, no choice)
    for node in top_order[:-1]:
        idx = valid_nodes.index(node)
        encoding.append(idx)
        # Update dependencies
        for neighbor in adjacency_list[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                valid_nodes.append(neighbor)
        valid_nodes.remove(node)
    return encoding

def decode_encoding(encoding):
    in_degree = original_in_degree.copy()
    valid_nodes = [n for n in all_nodes if in_degree[n] == 0]
    top_order = []
    for idx in encoding:
        node = valid_nodes[idx]
        top_order.append(node)
        # Update dependencies
        for neighbor in adjacency_list[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                valid_nodes.append(neighbor)
        valid_nodes.remove(node)
    # Add the final sink node
    top_order.append(valid_nodes[0])
    return top_order

# Test the code
test_order = [1,3,2,4,5,6,7]
encoded = encode_top_order(test_order)
print(f"Encoded sequence: {encoded}")  # Output: [0,1,0,0,0,0]
decoded = decode_encoding(encoded)
print(f"Decoded order: {decoded}")  # Output: [1,3,2,4,5,6,7]

Key Takeaways #

• This method guarantees only valid topological orders because we never pick a node with pending dependencies.
• The encoding is efficient: we only need to store the choices made at each step, which is far more compact than storing the full order for larger graphs.
• You can extend this logic to any DAG by adjusting the adjacency list and in-degree values.

内容的提问来源于stack exchange，提问作者WillEnsaba