4
$\begingroup$

Given a weighted, directed graph, I want to find the most influential paths (a combination of large weights). I reverse the usual shortest path problem because the context I am trying to model defines the shortest paths as paths with the largest influence weights. This means that the input into the usual shortest path algorithm should be the reciprocal of the weighted, directed graph. However, if I take the reciprocal of the weighted graph below, Infinity creates a problem, and I do not know how to handle this case.

I refer to the following weighted, directed graph for this problem.

WeightedAdjacencyGraph[{{\[Infinity], \[Infinity], 2, 
   1.4`}, {1.6`, \[Infinity], 
   1.9`, \[Infinity]}, {2, \[Infinity], \[Infinity], 
   0.62`}, {\[Infinity], \[Infinity], \[Infinity], \[Infinity]}}, 
 DirectedEdges -> True, VertexLabels -> "Name"]
HighlightGraph[%, PathGraph@FindShortestPath[%, 2, 4]]

What will be the longest path(s) between vertices 2 and 4 through an edge, say, from vertex 2 to 1?

$\endgroup$
11
  • 2
    $\begingroup$ Could you just replace $\infty$ with a large finite number instead? like wadj = (*weighted adj. mat.*)/.Infinity->10^6? $\endgroup$
    – ydd
    Aug 7, 2023 at 0:36
  • 2
    $\begingroup$ What is "the reciprocal of a graph"? Are you sure that the longest path problem is a good fit for your application? The classic definition of longest paths forbids repeated vertices. Otherwise, you could make the path arbitrarily long by going around the cycle you have in this graph. But forbidding repeated vertices causes this to be NP-hard. $\endgroup$
    – Szabolcs
    Aug 7, 2023 at 9:44
  • 1
    $\begingroup$ @ydd it does not return the longest path. The problem is that inverting the adjacency matrix inverts each edge weight individually, instead of inverting the full weight of the path. This can be a problem because $1/a_1+1/b_1$ < $1/a_1+1/b_2+1/c_2$ does not imply $a_1+b_1$ > $a_1+b_2+c_2$ (Ex: look at path length of {2,1,3,4} compared to this path {2,1,4} $\endgroup$
    – ydd
    Aug 7, 2023 at 14:54
  • 1
    $\begingroup$ @TugrulTemel the shortest path with the inverted weights is not in general the longest path with the original weights. Take this example: Suppose you have two paths between two vertices, one that goes through one other vertex and one that goes through two. Suppose the original edge weights of these two paths are {1/4,1/2} and {1/4,1/2,1/2} for total path weights 3/4 and 5/4 (so the second is longer). Taking the inverse weights of these paths we have {4,2} and {4,2,2}, so FindShortestPath will return the first path, even though it's shorter than the second in the original graph. $\endgroup$
    – ydd
    Aug 7, 2023 at 15:50
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – ydd
    Aug 7, 2023 at 15:56

2 Answers 2

2
$\begingroup$

The idea to take the inverse weight and search the shortest path is good. You simply need to retain the infinite weights:

dat1 = {{∞, ∞, 2, 1.4`}, {1.6`, ∞, 
    1.9`, ∞}, {2, ∞, ∞, 
    0.62`}, {∞, ∞, ∞, ∞}};
dat2 = Map[(If[# == ∞, ∞, 1/#]) &, dat1, {2}]

We now create the original graph for display and the graph with inverse weight for the shortest path:

gr1 = WeightedAdjacencyGraph[dat1, DirectedEdges -> True, 
  VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"];
gr2 = WeightedAdjacencyGraph[dat2, DirectedEdges -> True, 
  VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"];

Finally we display the longest path in the original graph:

HighlightGraph[gr1, PathGraph@FindShortestPath[gr2, 2, 4]]

enter image description here

$\endgroup$
2
  • $\begingroup$ Is there any way to count the number of paths that includes a given edge? I did the following and it works but I suspect an easier way exist. lstPaths = FindPath[gr2, 2,4, Infinity, All]; edges = DirectedEdge @@@ Partition[#, 2, 1] & /@ lstPaths; propSP = Count[Flatten@edges, "1" \[DirectedEdge] "3"]/Length[edges] // N $\endgroup$ Aug 7, 2023 at 18:49
  • 1
    $\begingroup$ In graphs with circular paths like your example, there are infinite many paths through some edge. $\endgroup$ Aug 7, 2023 at 19:05
4
$\begingroup$

I suppose one inefficient way could be to calculate all the possible paths from vertex 2 to 4, and then select the one with the highest path weight. This will get very slow for graphs with more edges.

originalAdj = 
 {{\[Infinity], \[Infinity], 2, 1.4`}, {1.6`, \[Infinity], 
    1.9`, \[Infinity]}, {2, \[Infinity], \[Infinity], 
    0.62`}, {\[Infinity], \[Infinity], \[Infinity], \[Infinity]}};
g = WeightedAdjacencyGraph[originalAdj, DirectedEdges -> True, 
  VertexLabels -> "Name"]

Then I calculate all possible paths from 2 to 4 using FindPath:

paths = FindPath[g, 2, 4, Infinity, All]
(*{{2, 3, 4}, {2, 1, 4}, {2, 3, 1, 4}, {2, 1, 3, 4}}*)

I am not sure if a built in function exists for calculating path length of a given path, so I just made this myself. It just adds up the edge weights along the path:

calcPathWeight[pathIn_] := 
 Sum[Part[originalAdj, i /. List -> Sequence], {i, 
   Partition[pathIn, 2, 1]}]

And then find the path with the largest total weight:

longestPath=Flatten@paths[[PositionLargest[calcPathWeight /@ paths]]]
(*{2, 3, 1, 4}*)

We can make the highlighted graph by converting the list of vertices visited to a list of rules:

longPathRuleList = 
 Table[longestPath[[i - 1]] -> longestPath[[i]], {i, 2, 
   Length@longestPath}];

HighlightGraph[g, PathGraph@longPathRuleList]

enter image description here

Edit: Apologies for having to edit so many times, but I did not see you also wanted the longest path that also goes through the vertex 2->1. We can do this by filtering out only the paths that have this vertex:

edges = Partition[#, 2, 1] & /@ paths;
truePos = Flatten[Position[MemberQ[#, {2, 1}] & /@ edges, True]];
pathsCandidates = paths[[truePos]]
(*{{2, 1, 4}, {2, 1, 3, 4}}*)

And then use the same method as above for finding the longest path in pathsCandidates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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