Directed acyclic graph profit sorting

[mXSCNT]

Suppose we have a directed acyclic graph. The nodes are labeled with integers (which may be negative). Imagine that the labels represent payoffs or costs of taking an action associated with each node. In order to perform an action you must perform prerequisite actions indicated by the graph.

The question is whether there is a topological sort on this graph, such that at some point during the ordering, the sum of the labels on all the nodes up to that point becomes positive. This would represent a net profit from taking all actions up to that point.

Example:

[PLAIN]http://img535.imageshack.us/img535/5395/graph1f.png

If we have the topological sort ABCED, the labels on ABCE sum to a positive number (1). So this graph does meet the criteria for being profitable - if you take actions A B C E in that order, you make a profit of 1. Note that if you also took action D, the sum would be -6, so you should stop after E. ABCED is a "profitable topological sort" because it has the prefix ABCE which is profitable. ABCDE is an example of a non-profitable topological sort.

The problem is to find an algorithm to determine whether a directed acyclic graph in general has a profitable topological sort.

 

[mXSCNT]

Here's what I think may be a solution. I haven't figured out a proof of correctness, but it does work at least for simple examples, and it has some ideas.

First, when seeking to maximize the profit in the graph, we only need to consider including or excluding positive nodes; we only want to include the negative nodes that are prerequisites for our positive nodes. Including extra negative nodes beyond that would only decrease the profit.

So we maintain a set S of positive nodes and all their negative prerequisites, and consider a positive node x in S. If we remove x from S, then we also remove:
- The set of all nodes y in S with a path x -> y (call this set Descendents(x,S)). If we take out x then anything that x is a prerequisite for has to go as well.
- The set of all negative nodes z in S with a path z -> x, and no path from z to any other positive node w in S, unless w is in Descendents(x,S). Call this set Support(x,S). If we take out x, then we get to greedily remove the negative "support" for x that we aren't using elsewhere.

Define Family(x,S) = {x} u Support(x,S) u Descendents(x,S).

Define Level(x,S) for positive nodes to be 0 if Descendents(x,S) = {}, and otherwise Level(x,S) is one plus the highest level of any positive node y with a path x -> y. Level(x,S) measures how "deep" x is away from the front of the set. Level(x,S) is infinite for negative nodes.

Here is a graph to illustrate these definitions.

[PLAIN]http://img687.imageshack.us/img687/2971/graph2an.png

If S is the entire graph, then:
The nodes at level 0 are H, E, and F
The only node at level 1 is B
Family(E,S) = {E} u Support(E,S) = {E} - doesn't include C because C supports F
Family(F,S) = {F} u Support(F,S) = {F, D}
Family(H) = {H}
Family(B,S) = {B} u Support(B,S) u Descendents(B,S) = {B} u {A} u {E, C, D, F} = {A, B, C, D, E, F} - omitting G because G supports H

Also define LabelSum(A) to be the sum of the labels of each node in a set A.

The idea is to start with a set S that includes all positive nodes and their negative prerequisites, and greedily delete positive nodes and their families from S to increase the profit. Note that LabelSum(Family(F,S)) = -1 < 0 in the example, and since F is level 0 we can remove it and increase the profit for S (or in this case just decreasing the loss).

We want to work backwards trying to delete nodes with level 0 first, then level 1, etc. This is because, suppose you have a level 1 node x, and y is a positive level 0 descendent of x where LabelSum(Support(y,S)) < 0. Now perhaps LabelSum(Family(x,S)) is also less than 0. We don't want to delete x right away, because if we try deleting y first, it would change the evaluation of LabelSum(Family(x,S)) and we might end up not deleting x after all.

So here is the algorithm.

Initialize S to include all positive nodes and their negative prerequisites
Done = False
while not Done:
  for L = 0 to infinity:
    Lvl = {x in S: Level(x,S) = L}
    If Lvl = {} then Done = True and exit the for loop
    If there are any nodes x in Lvl where LabelSum(Family(x,S)) < 0:
      Delete Family(x,S) from S
      Exit the for loop
If LabelSum(S) > 0:
  print "The maximum profit to be had from the graph is ", LabelSum(S)
Else:
  print "The graph is not profitable"

 

[Stephen Tashi]

if you take actions A B C E in that order, you make a profit of 1.

I don't understand what defines an allowed sequence of actions. The diagram doesn't show a path directly from C to E. Should there be one? If not, to perform ABCE, it looks like to you have to go from C back to B and then to E. However, what's the point of the direction in the graph, if you can do that?

 

[mXSCNT]

I don't understand what defines an allowed sequence of actions. The diagram doesn't show a path directly from C to E. Should there be one? If not, to perform ABCE, it looks like to you have to go from C back to B and then to E. However, what's the point of the direction in the graph, if you can do that?

The rule is that you can't visit node x until you've visited all nodes y with an edge (y, x). In other words you just have to visit nodes in an order corresponding to some topological sort. It's OK to visit E in the diagram because we already visited B, the only parent of E. A topological sort can jump around, not always following the edges, as long as we don't visit a node before visiting its parents.