GraphTheory[RandomGraphs] - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : RandomGraphs : GraphTheory/RandomGraphs/AssignEdgeWeights

GraphTheory[RandomGraphs]

 AssignEdgeWeights

 Calling Sequence AssignEdgeWeights(G,m..n) AssignEdgeWeights(G,a..b) AssignEdgeWeights(G,R)

Parameters

 G - graph m, n - integers satisfying n >= m a, b - floats satisfying b >= a R - user defined function for generating random edge weights

Description

 • If G is a weighted graph, AssignEdgeWeights(G,...) assigns new random edge weights to G, i.e., for each edge (i,j) in G the (i,j)'th entry in the weight matrix of G is updated inplace.
 • If G is an unweighted graph, a weighted graph is first created before assigning the edge weights.  The structure of G is not copied.
 • AssignEdgeWeights(G,m..n) assigns the edges of the weighted graph random integer weights uniformly distributed on [m,n].
 • AssignEdgeWeights(G,a..b) assigns the edges of the weighted graph random decimal weights uniformly distributed on [a,b).
 • AssignEdgeWeights(G,R) assigns the edges of the weighted graph G values defined by R().  The Maple procedure R must return numerical values, i.e., integers, rationals, or floating point constants.
 • The random number generator used to compute the edge weights can be seeded using the randomize function.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $T≔\mathrm{Graph}\left(\mathrm{weighted},\left\{\left[1,2\right],\left[2,3\right],\left[3,4\right],\left[4,1\right]\right\}\right)$
 ${T}{≔}{\mathrm{Graph 1: a directed weighted graph with 4 vertices and 4 arc\left(s\right)}}$ (1)
 > $\mathrm{WeightMatrix}\left(T\right)$
 $\left[\begin{array}{rrrr}{0}& {1}& {0}& {0}\\ {0}& {0}& {1}& {0}\\ {0}& {0}& {0}& {1}\\ {1}& {0}& {0}& {0}\end{array}\right]$ (2)
 > $\mathrm{AssignEdgeWeights}\left(T,1..9\right)$
 ${\mathrm{Graph 1: a directed weighted graph with 4 vertices and 4 arc\left(s\right)}}$ (3)
 > $\mathrm{WeightMatrix}\left(T\right)$
 $\left[\begin{array}{rrrr}{0}& {4}& {0}& {0}\\ {0}& {0}& {1}& {0}\\ {0}& {0}& {0}& {7}\\ {1}& {0}& {0}& {0}\end{array}\right]$ (4)
 > $T≔\mathrm{RandomTree}\left(4\right)$
 ${T}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 4 vertices and 3 edge\left(s\right)}}$ (5)
 > $T≔\mathrm{AssignEdgeWeights}\left(T,0.0..1.0\right)$
 ${T}{≔}{\mathrm{Graph 3: an undirected weighted graph with 4 vertices and 3 edge\left(s\right)}}$ (6)
 > $W≔\mathrm{WeightMatrix}\left(T\right)$
 ${W}{≔}\left[\begin{array}{cccc}{0.}& {0.}& {0.}& {0.957506835434298}\\ {0.}& {0.}& {0.546881519204984}& {0.278498218867048}\\ {0.}& {0.546881519204984}& {0.}& {0.}\\ {0.957506835434298}& {0.278498218867048}& {0.}& {0.}\end{array}\right]$ (7)
 > $\mathrm{op}\left(3,W\right)$
 ${\mathrm{datatype}}{=}{\mathrm{float}}{[}{8}{]}{,}{\mathrm{storage}}{=}{\mathrm{rectangular}}{,}{\mathrm{order}}{=}{\mathrm{Fortran_order}}{,}{\mathrm{shape}}{=}\left[{\mathrm{symmetric}}\right]$ (8)
 > $T≔\mathrm{RandomTree}\left(100\right)$
 ${T}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 100 vertices and 99 edge\left(s\right)}}$ (9)
 > $T≔\mathrm{AssignEdgeWeights}\left(T,1..99\right)$
 ${T}{≔}{\mathrm{Graph 5: an undirected weighted graph with 100 vertices and 99 edge\left(s\right)}}$ (10)
 > $\mathrm{op}\left(3,\mathrm{WeightMatrix}\left(T\right)\right)$
 ${\mathrm{datatype}}{=}{\mathrm{integer}}{,}{\mathrm{storage}}{=}{\mathrm{sparse}}{,}{\mathrm{order}}{=}{\mathrm{Fortran_order}}{,}{\mathrm{shape}}{=}\left[{\mathrm{symmetric}}\right]$ (11)

This example creates a network

 > $N≔\mathrm{Graph}\left(\left\{\left[1,2\right],\left[1,3\right],\left[1,4\right],\left[2,3\right],\left[4,3\right],\left[2,5\right],\left[3,5\right],\left[4,5\right]\right\}\right)$
 ${N}{≔}{\mathrm{Graph 6: a directed unweighted graph with 5 vertices and 8 arc\left(s\right)}}$ (12)
 > $U≔\mathrm{rand}\left(1..4\right):$
 > B := proc() if U()=1 then 1 else 2 fi end:

So Prob(B=1)=1/4, Prob(B=2)=3/4

 > $N≔\mathrm{AssignEdgeWeights}\left(N,B\right)$
 ${N}{≔}{\mathrm{Graph 7: a directed weighted graph with 5 vertices and 8 arc\left(s\right)}}$ (13)
 > $W≔\mathrm{WeightMatrix}\left(N\right)$
 ${W}{≔}\left[\begin{array}{rrrrr}{0}& {2}& {2}& {2}& {0}\\ {0}& {0}& {2}& {0}& {2}\\ {0}& {0}& {0}& {0}& {2}\\ {0}& {0}& {1}& {0}& {2}\\ {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (14)
 > $\mathrm{op}\left(3,W\right)$
 ${\mathrm{datatype}}{=}{\mathrm{anything}}{,}{\mathrm{storage}}{=}{\mathrm{rectangular}}{,}{\mathrm{order}}{=}{\mathrm{Fortran_order}}{,}{\mathrm{shape}}{=}\left[{}\right]$ (15)