Need some help understanding this problem about maximizing graph connectivity

Question

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

Problem I am trying to solve:

1. Constructing the dependency graph Given the connectivity of the graph and a metric that determines how well a node depends on the other, order the dependencies. For instance, I could put in a few rules saying that

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

But because the final rule is not "valuable" (again based on the same metric), I will not add the rule to my system.

2. Execute the request order Once I built a dependency graph, execute the list in an order that maximizes the final connectivity. I am not sure if this is a really a problem but I somehow have a feeling that there might exist more than one order in which case, it is required to choose the best order.

First and foremost, I am wondering if I constructed the problem correctly and if I should be aware of any corner cases. Secondly, is there a closely related algorithm that I can look at? Currently, I am thinking of something like Feedback Arc Set or the Secretary Problem but I am a little confused at the moment. Any suggestions?

PS: I am a little confused about the problem myself so please don't flame on me for that. If any clarifications are needed, I will try to update the question.

Answer 1

It looks like you are trying to determine an ordering on requests you send to nodes with dependencies (or "partial ordering" for google) between nodes.

If you google "partial order dependency graph", you get a link to here, which should give you enough information to figure out a good solution.

In general, you want to sort the nodes in such a way that nodes come after their dependencies; AKA topological sort.

Answer 2

I'm a bit confused by your ordering constraints vs. the graphs that you picture: nothing matches up. That said, it sounds like you have soft ordering constraints (A should come before B, but doesn't have to) with costs for violating the constraint. An optimal algorithm for scheduling that is NP-hard, but I bet you could get a pretty good schedule using a DFS biased towards large-weight edges, then deleting all the back edges.

Answer 3

If you know in advance the dependencies of each node, you can easily build layers.

It's amusing, but I faced the very same problem when organizing... the compilation of the different modules of my application :)

The idea is simple:

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

Then you can pop the layers one at a time, and each time you'll be able to send the request to each of the nodes of this layer in parallel.

If you keep a set of the already selected nodes and the dependencies are also represented as a set the check is more efficient. Other implementations would use event propagations to avoid all those nested loops...

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