Finding the width of a directed acyclic graph ... with the ability to search only parents

Question

I am trying to find the width of a directed acyclic graph ... as represented by an arbitrarily ordered list of nodes, even without an adjacency list.

The graph / list is intended for the GNU Make-like parallel workflow manager, which uses files as criteria for the execution order. Each node has a list of source files and destination files. We have a hash table in place, so given the file name, we can determine the node that produces it. Thus, we can find out the parents of node by examining the nodes that each of their source files generate using this table.

This is the only ability I have at the moment, without major code changes. The code has been in public use for some time, and the last thing we want to do is significantly change the structure and have a bad version. And no, we don’t have time for rigorous testing (I am in the academic environment). Ideally, we hope that we can do this without doing anything more dangerous than adding fields to the node.

I will post a response from the wiki community outlining my current approach and its weaknesses. If someone wants to edit this or use it as a starting point, feel free to. If I can do something to clarify the situation, I can answer questions or send a code if necessary.

Thank!

EDIT: for anyone who cares, it will be in C. Yes, I know that my pseudo-code is in some terribly bad Python. I kind of hope that the language does not really matter.

Answer 1

I think the “width” that you are considering here is not really what you want - the width depends on how you assign levels to each node where you have a choice. You noticed this when you made a decision about whether to assign all sources to level 0 or all receivers to the maximum level.

" ", . parallelism . , , .

, , - - , .

Answer 2

(Platinum Azure, ) .

/:

• "" ( "DAG" ) node
• "" "DAG" node
• "children_left" "DAG" node. , , , ( ).

:

• ; , , == 0 .

  for l in L:
    l.children = 0
  
  
  for l in L:
    l.level = 0
    for p in l.parents:
      ++p.children
  
  Leaves = []
  for l in L:
    l.children_left = l.children
    if l.children == 0:
      Leaves.append(l)
  

• node " ". depth = 0 . , , , = 0, . , , node, " " ( " " ).

  max_level = 0
  while !Leaves.empty():
    l = Leaves.pop()
    for p in l.parents:
      --p.children_left
      if p.children_left == 0:
        /* we only want to append parents with for sure correct level */
        Leaves.append(p)
      p.level = Max(p.level, l.level + 1)
      if p.level > max_level:
        max_level = p.level
  

• , node , , , .

  level_count = new int[max_level+1]
  for l in L:
    ++level_count[l.level]
  
  width = Max(level_count)
  

---

, . ? , , , , . , - - node .

?

Answer 3

-, , , . , , .

• , ( )
• . ( tsort, )
• , , , node.
• node:
  • node , 0
  • + 1.
• .

, , , ?