GraphTheory/PathWeight - Maple Help

GraphTheory

 PathWeight
 compute path weight

 Calling Sequence PathWeight(G, w)

Parameters

 G - graph w - list or Trail object corresponding to a walk in the graph

Description

 • The PathWeight(G) command returns the path weight of the walk w in the graph G.
 • When G is weighted, this is the sum of the edge weights for all edges appearing in the walk w.
 • When G is unweighted, this is simply the number of edges of the walk.
 • Note that self-loops appearing in w are not included in the edge count for the purposes of computing graph density.

Examples

Compute the path weight of a walk through an unweighted graph.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$
 ${\mathrm{K4}}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{PathWeight}\left(\mathrm{K4},\left[1,2,3,4\right]\right)$
 ${4}$ (2)

Compute the path weight of a walk through a weighted directed graph including a self-loop.

 > $\mathrm{GS}≔\mathrm{Graph}\left(3,\mathrm{Matrix}\left(3,\left[\left[0,2,3\right],\left[2,0,4\right],\left[5,3,3\right]\right]\right)\right)$
 ${\mathrm{GS}}{≔}{\mathrm{Graph 2: a directed weighted graph with 3 vertices, 6 arc\left(s\right), and 1 self-loop\left(s\right)}}$ (3)
 > $\mathrm{PathWeight}\left(\mathrm{GS},\mathrm{Trail}\left(1,2,3,3,1\right)\right)$
 ${14}$ (4)
 > $\mathrm{BavarianCities}≔\mathrm{Import}\left("example/bayern10.csv",\mathrm{base}=\mathrm{datadir},\mathrm{output}=\mathrm{Matrix}\right)$
 ${\mathrm{BavarianCities}}{≔}\left[\begin{array}{ccc}{"München"}& {48.137222}& {11.575556}\\ {"Nürnberg"}& {49.455556}& {11.078611}\\ {"Augsburg"}& {48.371667}& {10.898333}\\ {"Regensburg"}& {49.017222}& {12.096944}\\ {"Ingolstadt"}& {48.76415}& {11.42434}\\ {"Würzburg"}& {49.79441}& {9.92937}\\ {"Fürth"}& {49.4774}& {10.98844}\\ {"Erlangen"}& {49.596361}& {11.004311}\\ {"Bamberg"}& {49.891667}& {10.891667}\\ {"Bayreuth"}& {49.9475}& {11.5775}\end{array}\right]$ (5)
 > $\mathrm{G1}≔\mathrm{GraphTheory}:-\mathrm{CompleteGraph}\left(\mathrm{convert}\left({\mathrm{BavarianCities}}_{\left(\right)..\left(\right),1},\mathrm{list}\right),\mathrm{vertexpositions}={\mathrm{BavarianCities}}_{\left(\right)..\left(\right),2..3}\right)$
 ${\mathrm{G1}}{≔}{\mathrm{Graph 3: an undirected graph with 10 vertices and 45 edge\left(s\right)}}$ (6)
 > $\mathrm{G2}≔\mathrm{MakeWeighted}\left(\mathrm{G1},\mathrm{vertexpositions},\mathrm{metric}=\mathrm{Euclidean}\right)$
 ${\mathrm{G2}}{≔}{\mathrm{Graph 4: an undirected weighted graph with 10 vertices and 45 edge\left(s\right)}}$ (7)
 > $\mathrm{PathWeight}\left(\mathrm{G2},\left["M303274nchen","Regensburg","Bayreuth","Bamberg","Erlangen","W303274rzburg","F303274rth","N303274rnberg","Ingolstadt","Augsburg","M303274nchen"\right]\right)$
 ${7.52978991560743}$ (8)

Compatibility

 • The GraphTheory[PathWeight] command was introduced in Maple 2023.