Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindPathEdges

Source Notebook

Find edges in a graph that connect one vertex to another

Contributed by: Sjoerd Smit

ResourceFunction["FindPathEdges"][g,s,t]

finds a path between vertex s and vertex t in the graph g and returning the path as a list of edges.

ResourceFunction["FindPathEdges"][g,{v1,v2,…}]

converts a vertex path in graph g to an edge path.

ResourceFunction["FindPathEdges"][g,{path1,path2,…}]

converts a list of vertex paths.

Details

ResourceFunction["FindPathEdges"] takes the same arguments as FindPath, but it returns the result as a list of edges.
If there are multiple edge paths corresponding to a sequence of vertices returned by FindPath, all possibilities will be returned.
If s and t are the same, ResourceFunction["FindPathEdges"] will return all self-edges for that vertex. If s and t are different, only simple paths wil be returns (i.e., self-loops will be excluded).
When attempting to convert a list of vertices that do not form a path, ResourceFunction["FindPathEdges"] will return an empty list.

Examples

Basic Examples (2) 

Find a path between two individual vertices in a graph:

In[1]:=
g = \!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4}, {Null, SparseArray[ Automatic, {4, 4}, 0, {1, {{0, 3, 6, 9, 12}, {{2}, {3}, {4}, {1}, {3}, {4}, { 1}, {2}, {4}, {1}, {2}, {3}}}, Pattern}]}, {GraphLayout -> "StarEmbedding", VertexShapeFunction -> {{White, Disk[#, 0.1], Black, Text[#2, #]}& }}]]}, TagBox[{ {Hue[0.6, 0.7, 0.5], Opacity[0.7], LineBox[{{{0., 0.}, { 0.8660254037844389, -0.5000000000000012}}, {{0., 0.}, { 1.8369701987210297`*^-16, 1.}}, {{0., 0.}, {-0.8660254037844386, -0.49999999999999917`}}, {{ 0.8660254037844389, -0.5000000000000012}, { 1.8369701987210297`*^-16, 1.}}, {{ 0.8660254037844389, -0.5000000000000012}, {-0.8660254037844386, -0.49999999999999917`}}, {{ 1.8369701987210297`*^-16, 1.}, {-0.8660254037844386, -0.49999999999999917`}}}]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], { {GrayLevel[1], DiskBox[{0., 0.}, 0.1]}, {GrayLevel[0], InsetBox["1", {0., 0.}]}}, { {GrayLevel[1], DiskBox[{0.8660254037844389, -0.5000000000000012}, 0.1]}, {GrayLevel[0], InsetBox[ "2", {0.8660254037844389, -0.5000000000000012}]}}, { {GrayLevel[1], DiskBox[{1.8369701987210297`*^-16, 1.}, 0.1]}, {GrayLevel[0], InsetBox["3", {1.8369701987210297*^-16, 1.}]}}, { {GrayLevel[1], DiskBox[{-0.8660254037844386, -0.49999999999999917`}, 0.1]}, {GrayLevel[0], InsetBox[ "4", {-0.8660254037844386, -0.49999999999999917}]}}}}, MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FrameTicks->None, ImageSize->{100, Automatic}]\);
In[2]:=
ResourceFunction["FindPathEdges"][g, 3, 2]
Out[2]=

Highlight the path:

In[3]:=
HighlightGraph[g, First[%]]
Out[3]=

Convert a vertex path to an edge path:

In[4]:=
ResourceFunction["FindPathEdges"][g, {3, 1, 2}]
Out[4]=

Find all paths between two individual vertices in a graph:

In[5]:=
g = ExampleData[{"NetworkGraph", "Friendship"}]
Out[5]=
In[6]:=
ResourceFunction["FindPathEdges"][g, "Anna", "Larry", Infinity, All]
Out[6]=

Scope (7) 

If a graph has multiple edges per vertex-pair on a path, all possibilities are returned:

In[7]:=
g = Graph[{UndirectedEdge[1,2,a], UndirectedEdge[1,2,b], DirectedEdge[ 1,2,c], 3 \[UndirectedEdge] 2, 3 \[DirectedEdge] 4, 3 \[UndirectedEdge] 4, 3 -> 3, 3 \[UndirectedEdge] 3}, EdgeLabels -> Automatic, VertexLabels -> Automatic]
Out[7]=

FindPath returns a single path:

In[8]:=
FindPath[g, 1, 4]
Out[8]=

FindPathEdges returns all edge paths compatible with this:

In[9]:=
ResourceFunction["FindPathEdges"][g, 1, 4]
Out[9]=
In[10]:=
Column@ Map[HighlightGraph[g, #] &, %]
Out[10]=

Find the self-edges of a vertex:

In[11]:=
ResourceFunction["FindPathEdges"][g, 3, 3]
Out[11]=
In[12]:=
ResourceFunction["FindPathEdges"][g, 1, 1]
Out[12]=

Convert vertex paths to edge paths:

In[13]:=
ResourceFunction["FindPathEdges"][g, {1, 2, 3}]
Out[13]=
In[14]:=
ResourceFunction["FindPathEdges"][g, {{1, 2}, {2, 3}}]
Out[14]=

If no edge path exists, an empty list is returned:

In[15]:=
ResourceFunction["FindPathEdges"][g, {1, 3}]
Out[15]=

If the path contains a vertex that does not exist, an error is raised:

In[16]:=
ResourceFunction["FindPathEdges"][g, {1, 29}]
Out[16]=

Publisher

Sjoerd Smit

Requirements

Wolfram Language 14.0 (January 2024) or above

Version History

  • 1.0.0 – 25 June 2025

Related Resources

License Information