# Product of edge weights in path

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

-

(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 *)

-

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]));

-

Approach with sparse arrays and adjacency matrices:

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

w = WeightedAdjacencyMatrix@Graph[g, EdgeWeight -> ew] +

 SparseArray[<6>, {3, 3}]

MatrixForm[w]


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.

-
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