3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

(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 *)
$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – ssch Oct 15 '13 at 14:36
5
$\begingroup$

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]));
$\endgroup$

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.