GraphDistance
GraphDistance[g,i,j]
gives the distance from vertex i to vertex j in the graph g.
Details and Options
- GraphDistance functionality is now available in the built-in Wolfram Language function GraphDistance.
- To use GraphDistance, you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].
- GraphDistance returns the graph distance from one vertex to another. Infinity is returned if no path exists from i to j. By default every edge is assumed to have an edge weight of 1.
- The following option can be used:
-
Weighted False specifies whether edge weight is to be used in calculating distance
Examples
open all close allBasic Examples (2)
Needs["GraphUtilities`"]This defines a simple directed graph:
g = {1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4, 4 -> 5, 5 -> 6, 6 -> 4};GraphPlot[g, VertexLabeling -> True, DirectedEdges -> True]This calculates the distance from vertex 1 to vertex 5:
GraphDistance[g, 1, 5]This function has been superseded by GraphDistance in the Wolfram System:
g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4, 4 -> 5, 5 -> 6, 6 -> 4}]GraphDistance[g, 1, 5]Scope (1)
Needs["GraphUtilities`"]This defines a simple directed graph:
g = {1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4, 4 -> 5, 5 -> 6, 6 -> 4};GraphPlot[g, VertexLabeling -> True, DirectedEdges -> True]This calculates the distance from vertex 1 to vertex 5:
GraphDistance[g, 1, 5]There is no path from vertex 4 to vertex 1:
GraphDistance[g, 4, 1]This defines a simple directed graph with edge weights:
g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}];GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]This shows that the distance from vertex 1 to 3 is 2 if unit edge weights are assumed:
GraphDistance[g, 1, 3]But the distance becomes 0 if edge weights are taken into account:
GraphDistance[g, 1, 3, Weighted -> True]Applications (1)
Needs["GraphUtilities`"]This generates a random directed graph with n nodes and degree d:
randomGraph[n_, d_] := SparseArray[Floor[RandomReal[{0, 1} + (d/n), {n, n}]]]Average distance between vertices 1 and 100, of 200 random directed graphs of 100 vertices and degree 2:
Mean[DeleteCases[Table[
GraphDistance[randomGraph[100, 2], 1, 100],
{200}], ∞]]//NThe average distance decreases with an increase in the degree:
ListLinePlot[Table[{degree, Mean[DeleteCases[Table[
GraphDistance[randomGraph[100, degree], 1, 100],
{200}], ∞]]}, {degree, 2, 10}], AxesOrigin -> {0, 0}, AxesLabel -> {"degree", "mean distance"}]Possible Issues (1)
This defines a small directed graph:
Needs["GraphUtilities`"]g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}];GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]This shows that the distance between vertices 1 and 3 is 2, assuming a unit edge weight:
GraphDistance[g, 1, 3]This shows that when edge weights are taken into account, the distance between vertices 1 and 3 is 0:
GraphDistance[g, 1, 3, Weighted -> True]This shows the shortest path when edge weights are taken into account:
GraphPath[g, 1, 3]This shows the shortest path when edge weights are ignored:
GraphPath[g, 1, 3, Weighted -> False]Text
Wolfram Research (2007), GraphDistance, Wolfram Language function, https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistance.html.
CMS
Wolfram Language. 2007. "GraphDistance." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistance.html.
APA
Wolfram Language. (2007). GraphDistance. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistance.html