CODEWITHSUNDEEP
algorithmsortinggraph-algorithm
user2585677
user2585677

Reputation: 149

topology sorting

Given a DAG with N nodes, each node has a value (e.g., 0.2, 0.5, 1.3, 0.1...). I want to sort the vertices into a chain. The difficulty is that there is an objective function when sorting the nodes.

For example, the chain is x---> y --->z ---> w. Each link has a weight, for (x,y) weight= x, link (y,z) weight = xy, link (z,w) weight = xyz and so on.

The objective function is to minimize the sum (here for the chain : x+xy+xyz) of all links weight.

I have been thinking about it. But I have no idea now. Is anyone can give some ideas on the algorithm design or the complexity proof of the problem? Thanks.

Upvotes: 2

Views: 221

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

This is the algorithm to which kevmo314 alluded, implemented in Python. Probably it should be reimplemented in C, with bit-wise operations replacing the set operations.

We can rewrite the objective

x + x*y + x*y*z = x*(1 + y*(1 + z)),

so assuming that all of the weights are positive, the overall objective is monotone in the subproblem objectives, which allows dynamic programming.

def optimal_order(predecessors_map, weight_map):
    vertices = frozenset(predecessors_map.keys())
    memo_map = {frozenset(): (0, [])}
    return optimal_order_helper(predecessors_map, weight_map, vertices, memo_map)


def optimal_order_helper(predecessors_map, weight_map, vertices, memo_map):
    if vertices in memo_map:
        return memo_map[vertices]
    possibilities = []
    for v in vertices:
        if any(u in vertices for u in predecessors_map[v]):
            continue
        sub_obj, sub_order = optimal_order_helper(predecessors_map, weight_map, vertices - frozenset({v}), memo_map)
        possibilities.append((weight_map[v] * (1.0 + sub_obj), [v] + sub_order))
    best = min(possibilities)
    memo_map[vertices] = best
    return best


print(optimal_order({'u': [], 'v': ['u'], 'w': [], 'x': ['w']}, {'u': 1.2, 'v': 0.5, 'w': 1.1, 'x': 1.001}))

Upvotes: 2

Related Questions