2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

This is the problem of enumerating all minimal elements of a partial order. Your edge dominance relation defines the partial order.


A warmup

In the simple case where you arrive at time $-1$, the partial order consists of all of the "edges", and you're just looking to enumerate all minimal elements in this partial order.

If you don't care about running time, this can be done by computing the dag that corresponds to this partial order and then pulling out all sources (all nodes in the dag with in-degree 0). Note that every partial order corresponds to a dag (the relation $x<y$ in the partial order corresponds to an edge from $x$ to $y$ in the dag), and so you can construct the dag using your partial order. The downside is that the running time to construct a dag in a naive fashion will be $O(n^2)$, if you test all pairs of edges for dominance.

In your case, there is a much more efficient algorithm. Each edge corresponds to a pair $(a,c)$, with the arrival time and the cost. Imagine plotting these on (the upper-right quadrant of) the 2-D plane. Now we want the subset of points that don't have any point below-and-to-the-left of them.

This subset can be computed in $O(n \lg n)$ time. First sort the points by arrival time, i.e., by $a$-value. Now iterate through the points, in increasing order of arrival time. As you iterate, keep track of the smallest cost (smallest $c$-value) you've seen so far. When you see a point that has a smaller cost than any previously seen, add it to the subset: it is a minimal point (it is not dominated by any other point).

In this way, you can find all of the minimal elements of your partial order in $O(n \lg n)$ time, where $n$ denotes the number of edges in your original problem.

The general case

We can adopt the above methods to the more general case where you arrive at time $t$. Now the partial order consists of all edges that apart after time $t$.

It's easy to construct this partial order with an initial filtering pass: simply throw away all of the edges that depart before time $t$. This can be done in a simple $O(n)$ time linear scan of all of the edges.

Next, you want to final all the minimal elements in this partial order. This can be done in $O(n \lg n)$ time, using the method described above. So, this solves your problem of finding all of the Pareto-minimal (undominated) edges, efficiently.

References

You might like to read the following articles about lattices and partial orders and their role in computer science:

$\endgroup$
  • $\begingroup$ Thank you! I also found this approach in a computation gemetry book. However, I guess this does not work for additional costs: (departure, arrival, c1, c2, ..., cn)? That is, one can not track the minimum of an n-dimensional vector. Nor can you use the algorithm iteratively. $\endgroup$ – Herbert Jul 8 '14 at 10:26
  • $\begingroup$ So my additional question would be, does the multiple costs situation enforce me to create and traverse the dag? Is that the best solution? $\endgroup$ – Herbert Jul 9 '14 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.