Function Repository Resource:

GraphPathAggregate

Source Notebook

Evaluate a function along a path in a graph

Contributed by: Sjoerd Smit

ResourceFunction["GraphPathAggregate"][g,f,path]

evaluates f[w₁,w₂,…] for a sequence of edge weights along a path in graph g.

ResourceFunction["GraphPathAggregate"][g,f]

represents an operator form of ResourceFunction["GraphPathAggregate"] that can be applied to paths.

Details and Options

Paths can be specified as either a List of edges or vertices. If a list of vertices is used, all paths compatible with that sequence of vertices will be computed.

A List of multiple edge paths is also supported as path specification.

ResourceFunction["GraphPathAggregate"] takes the following options:

"EdgeProperty"

EdgeWeight

edge property to use for computation

"VertexProperty"

None

vertex property to use for computation

ResourceFunction["GraphPathAggregate"] will extract vertex and edge properties along the specified path and feed them sequentially into f. If "EdgeProperty" or "VertexProperty" is set to None, no values for that type of graph element will be extracted. If a property is not defined for an edge or vertex, Missing[…] will be returned.

Examples

Basic Examples (4)

Sum the EdgeWeight along a path in a Graph:

In[1]:=

$gr = Graph[{UndirectedEdge[a,b,x], UndirectedEdge[a,b,y], c \[UndirectedEdge] b}, EdgeWeight -> {UndirectedEdge[a,b,x] -> 1, UndirectedEdge[a,b,y] -> 2, c \[UndirectedEdge] b -> 3}, VertexLabels -> Automatic, EdgeLabels -> "EdgeWeight"]$

Out[1]=

Use a path specified by edges:

In[2]:=

$ResourceFunction[ "GraphPathAggregate"][gr, Plus, {UndirectedEdge[a,b,x], c \[UndirectedEdge] b}]$

Out[2]=

Compute multiple paths:

In[3]:=

$ResourceFunction[ "GraphPathAggregate"][gr, Plus, {{UndirectedEdge[a,b,x], c \[UndirectedEdge] b}, {UndirectedEdge[a,b,y], c \[UndirectedEdge] b}}]$

Out[3]=

When a path is specified by vertices, all applicable paths will be evaluated:

In[4]:=

Out[4]=

Scope (2)

Use the operator form to map over multiple paths:

In[5]:=

$gr = \!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{$CellContext`a, $CellContext`b, $CellContext`c}, {Null, {{1, 2}, {1, 2}, {3, 2}}, {$CellContext`x, $CellContext`y, Null}}, {EdgeLabels -> {"EdgeWeight"}, VertexLabels -> {Automatic}, EdgeWeight -> {1, 2, 3}}]]}, TagBox[GraphicsGroupBox[{ {Hue[0.6, 0.7, 0.7], Opacity[0.7], CapForm["Round"], { {Arrowheads[0.], ArrowBox[ BezierCurveBox[{{0., 3.6739403974420594`*^-16}, { 0.4999999999999994, 0.16444074718311658`}, {1., 2.4492935982947064`*^-16}}], 0.02261146496815286]}, InsetBox["1", {0.5, 0.0700000000000004}, ImageScaled[{0.5, 0.5}], BaseStyle->"Graphics"]}, { {Arrowheads[0.], ArrowBox[ BezierCurveBox[{{0., 3.6739403974420594`*^-16}, { 0.4999999999999998, -0.1644407471831159}, {1., 2.4492935982947064`*^-16}}], 0.02261146496815286]}, InsetBox["2", {0.5, -0.06999999999999973}, ImageScaled[{0.5, 0.5}], BaseStyle->"Graphics"]}, { {Arrowheads[0.], ArrowBox[{{1., 2.4492935982947064`*^-16}, {2., 0.}}, 0.02261146496815286]}, InsetBox["3", {1.5, 1.2246467991473532*^-16}, ImageScaled[{0.5, 0.5}], BaseStyle->"Graphics"]}}, {Hue[0.6, 0.5, 1.], EdgeForm[{GrayLevel[0], Opacity[ 0.7]}], { DiskBox[{0., 3.6739403974420594`*^-16}, 0.02261146496815286], InsetBox["a", Offset[{2, 2}, {0.02261146496815286, 0.02261146496815323}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}, { DiskBox[{1., 2.4492935982947064`*^-16}, 0.02261146496815286], InsetBox["b", Offset[{2, 2}, {1.0226114649681528, 0.022611464968153108}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}, {DiskBox[{2., 0.}, 0.02261146496815286], InsetBox["c", Offset[{2, 2}, {2.022611464968153, 0.02261146496815286}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None, ImageSize->{345.7265624999999, Automatic}]\); ResourceFunction["GraphPathAggregate"][gr, Plus] /@ { {a, b}, {a, b, c} }$

Out[6]=

Any operator can be used:

In[7]:=

Out[7]=

In[8]:=

$ResourceFunction[ "GraphPathAggregate"][gr, f, {UndirectedEdge[a,b,y], c \[UndirectedEdge] b}]$

Out[8]=

Options (5)

EdgeProperty (2)

Any edge property can be used for computation:

In[9]:=

$gr = Graph[{ Annotation[UndirectedEdge[a,b,x], "MyProperty" -> \[Alpha]], Annotation[UndirectedEdge[a,b,y], "MyProperty" -> \[Beta]], Annotation[c \[UndirectedEdge] b, "MyProperty" -> \[Gamma]] }, VertexLabels -> Automatic]$

Out[9]=

In[10]:=

Out[10]=

If a property is not defined on an edge, Missing[…] will be returned:

In[11]:=

$ResourceFunction["GraphPathAggregate"][ Graph[{Annotation[a \[UndirectedEdge] b, "MyProperty" -> \[Alpha]], c \[UndirectedEdge] b}], f, {a, b, c}, "EdgeProperty" -> "MyProperty" ]$

Out[11]=

VertexProperty (3)

Specify a vertex property to extract values from along the path:

In[12]:=

$gr = Graph[ {Annotation[a, "Name" -> "John"], Annotation[b, "Name" -> "Marie"], Annotation[c, "Name" -> "Hugh"]}, { Annotation[UndirectedEdge[a,b,x], EdgeWeight -> 1], Annotation[UndirectedEdge[a,b,y], EdgeWeight -> 2], Annotation[c \[UndirectedEdge] b, EdgeWeight -> 3] }, VertexLabels -> Automatic ]$

Out[12]=

Do a computation on both vertices and edges along a path:

In[13]:=

Out[13]=

Compute only with vertex properties:

In[14]:=

Out[14]=

Possible Issues (2)

If edge weights are not explicitly provided then they are treated as missing:

In[15]:=

$ResourceFunction[<|"SymbolName" -> "FunctionRepository`$b875dc0537a04e14bf615376943238ca`GraphPathAggregate", "UUID" -> "0aae9c2e-3de1-4d10-9b1d-5bdaa2f133a6", "ResourceType" -> "Function", "Name" -> InterpretationBox[ TagBox[ FrameBox[ PaneBox[ GridBox[{{ StyleBox[ StyleBox[ AdjustmentBox[ "\"[\[FilledSmallSquare]]\"", BoxBaselineShift -> -0.25, BoxMargins -> {{0, 0}, {-1, -1}}], "ResourceFunctionIcon", FontColor -> RGBColor[ 0.8745098039215686, 0.2784313725490196, 0.03137254901960784]], ShowStringCharacters -> False, FontFamily -> "Source Sans Pro Black", FontSize -> 0.65 Inherited, FontWeight -> "Heavy", PrivateFontOptions -> {"OperatorSubstitution" -> False}], StyleBox[ RowBox[{ StyleBox[ "\"GraphPathAggregate\"", "ResourceFunctionLabel", FontFamily -> "Source Sans Pro"], " "}], ShowAutoStyles -> False, ShowStringCharacters -> False, FontSize -> 0.9 Inherited, FontColor -> GrayLevel[0.1]]}}, GridBoxSpacings -> {"Columns" -> {{0.25}}}], Alignment -> Left, BaseStyle -> {LineSpacing -> {0, 0}, LineBreakWithin -> False}, BaselinePosition -> Baseline, FrameMargins -> {{3, 0}, {0, 0}}], Background -> RGBColor[0.968627, 0.976471, 0.984314], BaselinePosition -> Baseline, DefaultBaseStyle -> {}, FrameMargins -> {{0, 0}, {1, 1}}, FrameStyle -> RGBColor[0.831373, 0.847059, 0.85098], RoundingRadius -> 4], {"FunctionResourceBox", RGBColor[0.8745098039215686, 0.2784313725490196, 0.03137254901960784], "GraphPathAggregate"}, TagBoxNote -> "FunctionResourceBox"], ResourceFunction["GraphPathAggregate"], BoxID -> "GraphPathAggregate", Selectable -> False], "ShortName" -> InterpretationBox[ TagBox[ FrameBox[ PaneBox[ GridBox[{{ StyleBox[ StyleBox[ AdjustmentBox[ "\"[\[FilledSmallSquare]]\"", BoxBaselineShift -> -0.25, BoxMargins -> {{0, 0}, {-1, -1}}], "ResourceFunctionIcon", FontColor -> RGBColor[ 0.8745098039215686, 0.2784313725490196, 0.03137254901960784]], ShowStringCharacters -> False, FontFamily -> "Source Sans Pro Black", FontSize -> 0.65 Inherited, FontWeight -> "Heavy", PrivateFontOptions -> {"OperatorSubstitution" -> False}], StyleBox[ RowBox[{ StyleBox[ "\"GraphPathAggregate\"", "ResourceFunctionLabel", FontFamily -> "Source Sans Pro"], " "}], ShowAutoStyles -> False, ShowStringCharacters -> False, FontSize -> 0.9 Inherited, FontColor -> GrayLevel[0.1]]}}, GridBoxSpacings -> {"Columns" -> {{0.25}}}], Alignment -> Left, BaseStyle -> {LineSpacing -> {0, 0}, LineBreakWithin -> False}, BaselinePosition -> Baseline, FrameMargins -> {{3, 0}, {0, 0}}], Background -> RGBColor[0.968627, 0.976471, 0.984314], BaselinePosition -> Baseline, DefaultBaseStyle -> {}, FrameMargins -> {{0, 0}, {1, 1}}, FrameStyle -> RGBColor[0.831373, 0.847059, 0.85098], RoundingRadius -> 4], {"FunctionResourceBox", RGBColor[0.8745098039215686, 0.2784313725490196, 0.03137254901960784], "GraphPathAggregate"}, TagBoxNote -> "FunctionResourceBox"], ResourceFunction["GraphPathAggregate"], BoxID -> "GraphPathAggregate", Selectable -> False], "Description" -> "Evaluate a function along a path in a graph", "FunctionLocation" -> CloudObject[ "https://www.wolframcloud.com/obj/resourcesystem/marketplacestorage/submissions/4d052d0bc026e682/a3b/a3b67481-14ea-4835-8d41-dc1d6e9c84d9/159c4f70b635db4f/data"]|>][ CompleteGraph[4], Plus, {1, 2, 3}]$

Out[15]=

Giving one edge weight explicitly sets all others to the default of 1:

In[16]:=

Out[16]=

Applications (3)

Define a graph with transition probabilities of an experiment that first flips a biased coin and then rolls a die; if the coin lands on an edge, don't roll the die:

In[17]:=

$gr = Graph[ { Annotation["Start" \[DirectedEdge] "Heads", EdgeWeight -> 47/100], Annotation["Start" \[DirectedEdge] "Tails", EdgeWeight -> 52/100], Annotation["Start" \[DirectedEdge] "Edge", EdgeWeight -> 1/100], Splice@Map[Splice@{ Annotation[# \[DirectedEdge] "6", EdgeWeight -> 1/6], Annotation[# \[DirectedEdge] "<6", EdgeWeight -> 5/6] } &, {"Heads", "Tails"} ] }, VertexLabels -> Automatic, EdgeLabels -> "EdgeWeight", GraphLayout -> {"LayeredDigraphEmbedding", "Orientation" -> Left} ]$