Weighted Directed Acyclic Graphs: algorithm to find edge weights such that they define a distance function?

3
votes

I have this technical problem that can be formuated with a Directed Acyclic Graph (DAG). Nodes represent events (with unknown timing), with directed edges encoding the relation ship: "I'm younger than you/I happened before you".

I need to estimate edge weights (i.e. "dynamic weights") such that the Weighted DAG (WDAG) implies a distance function on the DAG. In other words the sum of weights for paths between nodes A and B should be equal for all paths.

This is an undetermined problem, even if the weights are integers (same underlying reason that topological sorting is not unique, I suppose). In all generality, the edge weights, which represent timeintervals between nodes/events, are real numbers. Therefore I'm introducing some preset objective function C=J(WDAG) on the weighted DAG, here unspecified.

My question is: is there an algorithm that distributes positive definite weights on the WDAG, subject to the constraint 1) that the weights form a distance function of the DAG and 2) minimizing the objective function cost C.

This seems unrelated to the shortest-path or minimum-spanning-tree problems classically associated to WDAG's. Any ideas to a formal or heuristic solution to the above problem?

Regards,

Stephane

1
algorithmgraphgraph-algorithm

1 Answers

1
votes

I think all you need is topological sorting.

  1. Sort the nodes according to a topological sort.
  2. Distribute them in the [0,1] interval in the order you got.
  3. Now the distance of node-pairs on the [0,1] line will give you the weight of the edge connecting them.

This is one possible solution. If you have more constraints on the weights than what you describe in the question, the problem might be more difficult.