Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I need to calculate the product of graph edge weights on the path taking into account edge direction. I.e. for graph

g={1->2,2->3,1->3};
ew={2,3,4};
Graph[g,EdgeWeight->ew]

for path 2->1->3 we should get 4/2=2 for path 1->2->3 we should get 2*3=6

share|improve this question

3 Answers 3

up vote 3 down vote accepted

(Started writing before I realized there is no built-in PathLength function, oh well)

Since $\prod_{i=1}^n w_i = \exp(\sum_{i=1}^n \log w_i )$ You can use the log of the weights and then take the exponential of the corresponding path length to get the desired product.

To take reverse direction into account reverse each directed edge and invert its weight.

pathLength[graph_Graph, path_] :=
  With[{
   w = Thread[List @@@ EdgeList[graph] -> PropertyValue[graph, EdgeWeight]]},
  Total[Partition[path, 2, 1] /. w]]

lg = Join[#, Reverse[#, 2]] &@{1 -> 2, 2 -> 3, 1 -> 3};
lew = Log@Join[#, 1/#] &@{2, 3, 4};
lgraph = Graph[lg, EdgeWeight -> lew];

pathLength[lgraph, {2, 1, 3}] // Exp
(* 2 *)
pathLength[lgraph, {1, 2, 3}] // Exp
(* 6 *)
share|improve this answer

Assuming that a well defined path is entered as list of consecutive vertices, for directed graph:

pathwdg[g_, u_] := 
  Times @@ (PropertyValue[{g, #}, EdgeWeight] & /@ (Rule @@@ 
       Partition[u, 2, 1]));

then

g = {1 -> 2, 2 -> 3, 1 -> 3};
ew = {2, 3, 4};
grp = Graph[g, EdgeWeight -> ew]

applying:

pathwdg[grp, {1, 2, 3}]

gives 6.

For undirected graph:

pathwug[g_, u_] := 
  Times @@ (PropertyValue[{g, #}, EdgeWeight] & /@ (UndirectedEdge @@@
        Partition[u, 2, 1]));
share|improve this answer

Approach with sparse arrays and adjacency matrices:

 g = {1 -> 2, 2 -> 3, 1 -> 3};
 ew = {2, 3, 4};    

 w = WeightedAdjacencyMatrix@Graph[g, EdgeWeight -> ew] + 
   WeightedAdjacencyMatrix@ReverseGraph@Graph[g, EdgeWeight -> 1/ew]
 SparseArray[<6>, {3, 3}]
MatrixForm[w]

enter image description here

length[path_] := Times @@ Extract[w, Partition[path, 2, 1]]

length[{1, 2, 3}]

6

length[{2, 1, 3}]

2

I think this method must be efficient for very big graphs. If you want to work with packed arrays add N[...] to eg.

share|improve this answer
    
I think so too, especially in repeated usage on same graph. I have found PropertyValue and EdgeList to often slow things down to a crawl. –  ssch Oct 15 '13 at 14:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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