
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



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.



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 AC>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 :))



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 12:47 AM

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



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



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 3: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.



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 6: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.

