banana, banana2

• Description: Generate a "banana" graph, which is two vertices with n edges between them.  The second version, banana2, introduces extra vertices so that there are no double edges.  The resulting graphs are normalized, i.e. they have total length 1.
• Usage: banana(n), banana2(n)
• Examples:

>	G:=banana2(3): draw(Linear([3,4,5]),G);

star

• Description: Generate a "star" graph: a center vertex connected to n other vertices.  The resulting graph is normalized, i.e. it has total length 1.
• Usage: star(n)
• Note: Star is the bi-partite complete graph K_1,n so it can alternately be constructed with the built-in function complete(1,n) .
• Examples:

>	G:=star(3): draw3d(G);

bouquet / flower , bouquet2 / flower2

• Description: Generate a "bouquet" graph: a center vertex with n loops.  The first version creates n+1 vertices, so there are no self-loops.  The second version creates 2n+1 vertices so there are no double edges.  flower is just a synonym four bouquet.  The resulting graphs are normalized, i.e. they have total length 1.
• Usage: bouquet(n), flower(n), bouquet2(n), flower2(n),
• Examples:

>	G:=bouquet2(2): draw3d(G);

hypercube

• Description: Generate a hypercube.  A vertex (a_1, a_2, ..., a_n) where a=0 or a=1 is connected to another vertex (b_1, b_2, ..., b_n) if all except one a_i = b_i.
• Usage: hypercube(n)
• Examples:

>	G:=hypercube(2): draw(Linear([0,1]),G);

>	G:=hypercube(3): draw3d(G);

supercirc

• Description: Creates a graph with n^2 vertices such that every vertex is connected to its neighbor and the vertex +/- n mod n^2.  This graph is useful because it has a small tau value.
• Usage: supercirc(n)
• Examples:

>	G:=supercirc(5): draw(G);

>	draw3d(G);

>	evalf(tau(G));

normalize

• Description: Normalize the graph G so that the sum of the weights equals 1.  Modifies the graph in place.
• Usage: normalize(G)
• Examples:

>	G:=complete(4): eweight(G)[e1]:=3:      # change one of the default weights print(`Originally:` ,eweight(G)); normalize(G): print(`Normalized:`,eweight(G));

subdividegraph, subdivideedge

• Description: subdivideedge divides an edge of a graph into n edges.  The total length of the new edges equals the length of the old edge.  subdividegraph subdivides each edge ofa graph into n edges.
• Usage: subdividegraph(G,n), subdivideedge(e,G,n)
• Examples:

>	G:=star(3): draw(G); subdivideedge(e1,G,3): draw3d(G); G:=star(3):subdividegraph(G,3): draw(Linear([v2,v3,2],[1,v4,v5,3],[v6,v7,4]),G);

identifyedge

• Description: Identifies an edge of a graph to a single point, modifying the graph in place.
• Usage: identifyedge(e,G)
• Note: It so happens that "identifyedge" does the same thing as the built-in function "contract".
• Examples:

>	G:=cycle(4): draw(G); identifyedge(e1,G):   draw(G); G:=cycle(4): contract(e1,G):   # the same thing, but built-in draw(G);

assigndirections

• Description: Arbitrarily turns a graph into a directed graph.
• Usage: assigndirections(G)
• Note: This function is no longer used anywhere in laplacian.mpl, but it might still be handy.
• Examples:

>	G:=complete(3): ends(G); assigndirections(G): ends(G);

laplacian

• Description: Generate the discrete laplacian matrix for a graph G.  This is a symmetric matrix of dimension (# of vertices).  The off-diagonal entry a_{i,j} represents the negative sum of the reciprocals of the weights (admittances) of the edges connecting vertex i and vertex j.  The diagonal entries make the sum of any row or column 0.  laplacian does not accept graphs with self-loops.
• Usage: laplacian(G)  or laplacian(G,flt)
  The first syntax produces a matrix whose shape is symmetric and whose datatype is realcons.  The second syntax produces a matrix whose data type is float[8] and without special shape constraints.  The latter is ideal for approximate calculations; the former for exact calculations.  You can let "flt" be anything; the procedure just checks for the number of arguments.
• Implementation notes: the matrix is generated by looping over every vertex and filling in the appropriate column of the matrix.  The matrix is declared symmetric, so we really only fill out half the matrix and the rest is done automatically.  Note that the graph object has unordered vertices.  Whenever we need to order the vertices (as we do to produce a matrix), we order them buy using the list sort([op(vertices(G)]) .  
• Warning: laplacian was perhaps a bad name for this function since the `linalg' package already has a function named laplacian.  If you use linalg, be sure to load laplacian.mpl afterwards, so this laplacian procedure is used and not linalg's.
• Examples:

>	G:=cycle(3): eweight(G)[e1]:=2: # change a default weight laplacian(G); laplacian(G,foobar);

>	laplacian(graph({1},{{1,1}}));  # a self-looping graph

Error, (in laplacian) Laplacian dont make no sense with self-loops

effresistance, resistancevec

• Description: Calculate the effective resistance between two vertices on a graph.  effresistancevec calculates the resistance between a given vertex and all the other vertices and puts that in a vector.  Infinity is returned if two vertices are on different components of a graph.
• Usage: effresistance(G,v1,v2) or effresistance(G,v1,v2,Qgiven)
      resistancevec(G,v) or resistance(G,v,Qgiven)
  The user may, if he so chooses, provide the laplacian ready-made, which is what Qgiven is.
• Implementation: The resistance is calculated by running a unit current and measuring the potential difference.  If Q is the laplacian, v is a vector representing the potentials at each vertex, and i is the vector representing net current flow at every vertex, we have Qv = -i.  So, we can let i be the 0 vector except for a 1 in the place corresponding to v1 and a -1 in the place corresponding to v2.  The solution to the linear system can then be expressed in terms of one indeterminate, and this allows us to solve the effective resistance problem.  The way we actually do this is we take the minor around (v1,v1) of the matrix Q and solve the system that way.  It is clear that this yields the same solution.  [This discussion assumes that G is a connected graph, which also implies that Q has rank n-1.]
• Examples:

>	G:=petersen(): effresistance(G,1,2), effresistance(G,1,2,laplacian(G));

>	G:=graph({1,2,3,4},{{1,2},{2,3}}): resistancevec(G,1);

canonical

• Description: Calculates the discrete canonical measure.  We define this as (1/2)Qv + delta_i, where Q is the laplacian matrix, v is the effective resistance vector based around the vertex i and delta_i is the zero vector except for a 1 in the i'th position.
• Usage: canonical(G) or canonical(G,v1)
  It can be shown that the discrete canonical measure is independent of the vertex we choose, but if you wish to specify a vertex, you may.
• Note: canonical is most often used as an argument to the "eigs" procedure, described below.
• Examples:

>	G:=cycle(3): canonical(G),canonical(G,2),canonical(G,3);

canonicalcts

• Description: Calculates the continuous canonical measure.  It has been shown that this is 1/(R_i+L_i) dx for the edges and 1-valence(v)/2 for the vertices.
• Usage: canonicalcts(G)
• Examples:

>	G:=cycle(3): canonicalcts(G); G:=star(3): canonicalcts(G);

dxmeasure, IDeltaX

• Description: dxmeasure calculates the discrete dx measure.  To every vertex it assigns one half the sum of the weights of the edges coming out of that vertex.  IDeltaX puts the result in a diagonal matrix.
• Usage: dxmeasure(G), IDeltaX(G)
• Note: canonical is most often used as an argument to the "eigs" procedure, described below.
• Examples:

>	G:=cycle(3): dxmeasure(G), IDeltaX(G); G:=star(3):           # produces a normalized star dxmeasure(G);

eigs

• Description: eigs:=proc(Gorig, measure, n, nonormalize)
  local i, Q, G, nverts, mu, muv, mum, A, C, P, Delta, dim, dum;
  description `Computes the eigenvalues of the discrete Laplacian given a graph and a measure.`;
• Usage: eigs(G,measure,numdivs) , eigs(G,measure,numdivs,nonormalize)
  measure is typically either 'dxmeasure' or 'canonical'.  numdivs is the number of subdivisions--each edge is subdivided into numdivs edges.  Provide nonormalize if you don't want the graph G to be normalized first.
• Implementation: For the math, see the file canonical.pdf.  The eigs code is tricky only because of the way the LinearAlgebra package works.  The following help topics might be helpful: LA_numerics, LA_Programming, LA_Overview.
  Computing the eigenvalues is reasonably quick if Maple is able to call the numerical libraries.  This means you need to make all the matrices have datatype float[8].  The variable infolevel[LinearAlgebra]   can be adjusted (to be greater or equal to 1) to display more information about the inner workings of the LinearAlgebra function.  You want output about the NAG routines; that means it's going fast.
• Examples:

>	G:=star(3): eigs(G,dxmeasure,16)[1..8];  # only print out the first 8

>	eigs(G,canonical,16)[1..8];  # only print out the first 8

>	infolevel[LinearAlgebra]:=2:  eigs(G,dxmeasure,4);  infolevel[LinearAlgebra]:=0:

Transpose:   "calling external function"

HermitianTranspose:   hw_MatTransRR

MatrixMatrixMultiply:   "calling external function"

MatrixMatrixMultiply:   "NAG"   hw_f06yaf

MatrixScalarMultiply:   "calling external function"

MatrixScalarMultiply:   "NAG"   hw_f06edf

MatrixScalarMultiply:   "calling external function"

MatrixScalarMultiply:   "NAG"   hw_f06edf

MatrixAdd:   "calling external function"

MatrixAdd:   "NAG"   hw_f06ecf

MatrixMatrixMultiply:   "calling external function"

MatrixMatrixMultiply:   "NAG"   hw_f06yaf

MatrixMatrixMultiply:   "calling external function"

MatrixMatrixMultiply:   "NAG"   hw_f06yaf

MatrixMatrixMultiply:   "copying first Matrix to enable external call"

MatrixMatrixMultiply:   "calling external function"

MatrixMatrixMultiply:   "NAG"   hw_f06yaf

MatrixMatrixMultiply:   "calling external function"

MatrixMatrixMultiply:   "NAG"   hw_f06yaf

MatrixInverse:   "calling external function"

MatrixInverse:   "NAG"   hw_f07adf

MatrixInverse:   "NAG"   hw_f07ajf

MatrixMatrixMultiply:   "calling external function"

MatrixMatrixMultiply:   "NAG"   hw_f06yaf

Eigenvalues:   "calling external function"

Eigenvalues:   "CLAPACK"   hw_dgeevx_

tau

• Description: Computes the Tau constant of a graph.
• Usage: tau(G) or tau(G,nonormalize)
  Supply a second argument if you don't want tau to normalize the graph to have total length 1 first.
• Implementation: tau chooses a base point and iterates over all the edges calculating effective resistances to sum up tau.  See the PDF for a discussion of the mathematics involved.  Esentially, we've pre-determined the integral of d/dx j_x(z,z)^2 and are using that.
• Note: tau is kinda slow.  It does not take account into any symmetries that a graph might have.  Furthermore, it solves everything exactly, and I imagine that the effective resistance calculations are slowing it down significantly.
• Examples:

>	G:=cycle(12): tau(G),tau(G,nonormalize);

taushorten

• Description: Investigates the behavior of tau as an edge is shortened.
• Usage: taushorten(G,e,n) or   taushorten(G,e,n,donormalize)
  n is the number of steps to take.  The last step is identifying the edge completely and measuring tau then.  Specify a fourth argument if you want the graphs to be normalized at each step.
• Examples:

>	G:=complete(4): m:=taushorten(G,e1,30); plot([seq([i,m[i]],i=1..30)]);

>	G:=complete(4): m:=taushorten(G,e1,30,donormalize); plot([seq([i,m[i]],i=1..30)]);

vname

• Description: Creates a unique v+integer name (e.g. "v3") for a vertex that could be put on the graph (ie doesn't already exist).
• Usage: vname(G)
• Note: This function is 100% based on the networks/ename function already in existence.  It is used when subdividying edges to add vertices which must have unique names.  Though vertex names are typically just integers, it doesn't matter, so this function makes them "vN" where N is an integer.
• Examples:

>	G:=complete(4): vertices(G); addvertex(vname(G),G); vertices(G); addvertex(vname(G),G); vertices(G);

makeeigspread, graphspread

• Description: The first makes a big spreadsheet of known eigenvalues for graphs.  The second does eigenvalues of increasing subdivisions for a given graph.
• Note: In some sense, both of these functions are meant to be modified to suit your needs.   After you've run the procedures, issue an "Evaluate Spreadsheet" command.
• Usage: makeeigspread() or graphspread(G,ssid1,ssid2)
  ssid1/ssid2 are spreadsheet ids generated by CreateSpreadsheet().
• Examples:
  makeeigspread is just called with no arguments.  It takes a long time, and copying and pasting seems to crash Maple, so we'll do without an example.

>	with(Spread): G:=cycle(3): ssid1:=CreateSpreadsheet(): ssid2:=CreateSpreadsheet(): graphspread(G,ssid1,ssid2);