weight that are function of time

Topics: algorithm, graph
Jul 29, 2009 at 11:34 PM

Is it possible to apply function over time as weight for an edge, In oder word if i have this graph

A->B, B->D,A->C,C->D,D->E and wanna go from A to E

then i have 2 solutions: A->B->D->E and A->C->D->E,

can D->E weight be different depending on the path that was taked?

If yes how look the function that we can add into the graph for the weight

Dictionary<Edge<TVertex>, ???> where ??? is a function of time?

thz in advance

Jul 30, 2009 at 1:29 PM

What are you trying to accomplish? Are you trying to determine which path you took from A to E? I'm not an expert but I don't believe the weight of the edge between D -> E should change.

Jul 30, 2009 at 2:36 PM

The goal is to use weight that can be different for the same edge depending on the path that you take. As a example consider a shortest path algorith that represent a human running trough a road. It is pretty easy to set a weight for each edge base on the distance. Let say A->B= 2 ,B->D=3, A->C=1,C->D=6,D->E=8. That is working fine and is pretty easy to represent with Quickgraph. But let consider that we want to also take care about the wind or the time that the runner have to wait if a train go trought the path. Then depending on the way that you select the same edge can have a different weight since the wind can change direction. Let say in this example that if you use the path A->B->D->E the edge D->E = 7.5 and if you take the path A-C->D->E the edge D->E = 8.5. So instead of having a static value for the edge weight, is it possible to use a function, and if yes, how this function look like?

I aggre that in this example the shortest path will always be the same, but ive selected a really simple example just to show the concept since i am using huge graph. In that case it can makes huge difference,

Thz in advance (since english is not my main language it can be possible that some sentense look special :))

Jul 30, 2009 at 3:29 PM

Just to add a little precision, when i am talking about weight that are function of time, it could also be weight that are function of the sommation of the weight to reach that edge, This is mostly equivalent.

have a nice day

Coordinator
Jul 31, 2009 at 1:47 AM

It seems that you could acheive this by having multiple edges between D and E with different weights.

Jul 31, 2009 at 2:46 PM

In the specific case of an algorith like the shortest path, if i use multiple edges between 2 vertex, it will always select the same one, ie the shortest one. So I am presently looking of the effort that it could take to implement this features because after looking to the constructor that accept the weight ive conclude that it is not possible for now to use function instead of static weight. If it is not too complicated ill send you proposed code in the case you want to add it to the next version of quickgraph. I plan to try to do it in function of the sommation of the weight since it seems lot easier to code than in function of time. by example in providing weight function = currentWeightToReachThisEdge+ 4. In that specific case it is equivalent to set a static value of 4, but it open the possibility of using complex formulas by example weight function = currentWeightToReachThisEdge*1.1+2, etc... If anyone got any better idea of how to implement it or want to have more information about what i am trying to do plz add your idea in this blog.

have a nice day

Jul 31, 2009 at 3:08 PM

there is a distance relaxer that seem to do someting similar, if anyone that have already use it can provide extra information about what it is doing, it will be appreciated.

thz in advance

Coordinator
Jul 31, 2009 at 4:22 PM

The edge weights is already a delegate (a Func<Edge, double>), so you can use your own logic to give a cost to edges. If your weight depends on the path taken, you will break invariants of the shortest path algorithms and they will provide incorrect results.

Jul 31, 2009 at 10:28 PM

I don't understand how the delegate (Func<Edge,double> ) can be use as weight that change over time, so ive implemented it using a Func<Edge,IWeight> where IWeight is just a interface with a double as value and a method computeWeight(double cumulativeWeight). Ive add the related constructor. And modify the Relax from ShortestPathAlgorithmBase to support both double and IWeight. It seems to work well, so id like to know which invariants could be break to validate that i've not forget someting?

Relax{

...

<font size="2">

we =

</font>

this.Weights2(e).ComputeWeight(du);

...

}

note: i could have added a TWeight to the constructor instead but i was just doing a fast test to check if it was supported so i wouldnt want to have to add it to each shortest path algorith.

have a nice day

Coordinator
Aug 10, 2009 at 7:25 AM

The algorithm keeps a dictionary of the aggregated weights computed so far - it caches those values since it assumes they are not changing (relaxer.Combine(du, we)). As soon as you start changing weights values, the values in the distances dictionary are not valid - which means the prioritization of the BFS gets bogus.