Need help understanding this problem on max connecting graphs

Question

I was wondering if anyone could help me understand this problem. I prepared a small diagram because it is easier to explain visually.

alt text http://img179.imageshack.us/img179/4315/pon.jpg

The problem I'm trying to solve is:

1. Building a dependency graph Given the connectivity of the graph and the metric that determines how well a node depends on another, order the dependencies. For example, I can give a few rules saying that

• node 3 depends on node 4
• node 2 depends on node 3
• node 3 depends on node 5

But since the last rule is not “valuable” (again based on the same metric), I will not add this rule to my system.

2. Executing the order of queries After I have built the dependency graph, execute the list in the order that maximizes the final connection. I'm not sure if this is really a problem, but I have a feeling that there may be more than one order, in which case you need to choose the best order.

First of all, I wonder if I built the problem correctly, and if I need to know about any cases in the corner. Secondly, is there a close algorithm that I can look at? I am currently thinking of something like Arc Arc Arc or Secretary Problem , but I'm a little confused at the moment. Any suggestions?

PS: I am a little confused about the problem, so please do not cry for me for this. If any clarification is needed, I will try to update the question.

Answer 1

, , ( " " google) .

" ", , , .

, , ; AKA.

Answer 2

, : . , , (A B, ) . , NP-hard, , , DFS, , .

Answer 3

node, .

, ... :)

:

def buildLayers(nodes):
  layers = []
  n = nodes[:] # copy the list
  while not len(n) == 0:
    layer = _buildRec(layers, n)

    if len(layer) == 0: raise RuntimeError('Cyclic Dependency')

    for l in layer: n.remove(l)
    layers.append(layer)
  return layers

def _buildRec(layers, nodes):
  """Build the next layer by selecting nodes whose dependencies
     already appear in `layers`
  """
  result = []
  for n in nodes:
    if n.dependencies in flatten(layers): result.append(n) # not truly python
  return result

, .

If you save a set of already selected nodes, and the dependencies are also presented as a set, the check is more effective. Other implementations will use event propagation to avoid all of these nested loops ...

Note that in the worst case you have O (n ³ ), but I only had thirty components and they are not THAT related: p