Cheap and Secure Web Hosting Provider : See Now

[Solved]: Search in a partial ordering defined by tuples of numbers

, , No Comments
Problem Detail: 

This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a cost. Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.

An example of such a situation could be these 5 edges:

Example graph between nodes A and B

(I did not draw the time axis on scale)

There are five edges, I, II, III, IV and V. The costs are denoted at the edges, they are either 100, 10 or 1. Edge V is drawn red to easily discriminate it from the other edges, since it crosses through them. However, aside from that it is not different.

Given such edges, a few things are important:

  • An edge is only interesting if it departs after we arrive at A, for example in the image we can arrive at (a), then edge I is not an option anymore. The same goes for edges II and V if we arrive at (b), etc.
  • Given an arrival and its set of interesting edges, and edge ei is dominated if there exists an edge ej with ej< ei. This is the case iff aj ≤ ai ^ cj ≤ ci ^ (aj < ai v cj < ci). In layman terms, cost and arrival need to be at least as small, but one must be strictly smaller. This is a partial ordering, some edges are incomparable.
  • Given a arrival in A, I want to find all relevant, undominated (or Pareto) edges.

We can enumerate all the edges:

  • I: (0 , 1, 100)
  • II: (0.5, 2, 10)
  • III: (2 , 3, 100)
  • IV: (2.5, 4, 10)
  • V: (1.5, 5, 1)

Putting them in a partial ordering, using a directed acyclic graph (dag), we get this:

Directed acyclic graph of partial ordering

An arrow denotes the <-relation between edges. Note that an edge in this case is a node in the dag: confusing, I know. When I say edge, I mean a node in the dag above.

I added an edge (-∞, -∞), which is always irrelevant, but creates a nice 'root' of the dag. This way we sort of have a tree, where leaves sometimes merge without creating cycles. I also only denote the arrival at B and cost, needed to create the dag, but technically there is also a departure are A for each of the edges.

If we were to arrive at A at -1, we can simply return all the children of (-∞, -∞) as relevant and undominated, but for another arrival we may need to traverse the tree differently (in a more complicated fashion). I was thinking of this:

marker := map from edge to bool # marks whether edge has been traversed for all edges: marker(edge) := false # none have been traversed  traverse(root, arrival):     if(marker(root)) return []  #already been at this node     marker(root) := true;     if(departure(root) > arrival) return [root]; # return singleton list, all children will be dominated by this edge.      # this node is irrelevant, but possible some children are relevant.     l = [];     for each child of root:         append traverse(child, arrival) to l     return l 

Traverse returns a list of undominated, relevant edges. However, Is this an efficient way to tackle this problem? Is there a better solution to this problem? Is this problem known under a known name?

Asked By : Herbert

Answered By : Herbert

I solved my OP as my intuition was. First I created a graph as described by the second picture of the OP. Then I traverse it like this:

global: visited, front  function proceed(arrival)     visited := array of bool for each node initialized to false      for each x &isin; front         proceed(arrival, x)     return front  function proceed(arrival, node):     if(visited[node]): return     visited[node] := true     if(node.departure > arrival):        remove node from front        for each node x:            append x to the end of front  function calculate_outgoing:     outgoing := array of lists for each arrival at A, each list contains feasible and relevant A->B connections for that arrival.     front   := [(-&infin;, -&infin;)]     for each arrival at A in increasing order:         outgoing[arrival] := proceed(arrival)     return outgoing 

Initially only the root of the dag is in the is in the front. Then the front is moved towards the 'leaves' of the dag as the arrival times increase, that is, certain options 'fade away' and hence are replaced by other options.

Notice that I have a tree-view on the dag. The key difference is that a node can have more parents, hence I mark which nodes are already visited, preventing one from visiting them twice via different parents.

I find this solution more satisfying then @d-w's, since he did not address the problem of multiple costs, like stated in the OP: "Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.", nor did he comment on it. If you have only one cost, his solution is adequate.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28257

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback