Macro Library graphtheory

A library of graph theory and scheduling functions. Version 1.1, April 3, 2012

Most graphing functions in this library use an options array. Here are the
common options - specific functions will mention other options.
options['width'] = width of output, in pixels. Defaults to 300.
options['height'] = height of output, in pixels. Defaults to 300.
options['digraph'] = true/false. If true, g[i][j] > 0 means i leads to j
options['useweights'] = true/false. If true, g[i][j] used as weight
options['labels'] = "letters" or array of labels. If "letters", letters
A-Z used for labels. If array, label[i] used for vertex g[i]
options['weightoffset'] = position (0-1) along edge where weights should go
options['connected'] = true/false. When randomizing graphs, whether you
want to force the result to be connected. If false for a tree, this
forces a disconnected graph
options['randweights'] = max or array(min,max). Randomizes weights of edges
options['randedges'] = probability (0-1). Randomly keeps edges of original
graph with given probability.
options['tree'] = true. Creates a minimum cost spanning tree from the original graph
options['labelposition'] = "above","below","right","left","aboveright",etc.
position of vertex labels.

graphcircleladder

/graphcircleladder(n,m,[options])
draws a circular ladder graph
n vertices around a circle
m concentric circles
connected around circle and between circles
returns array(pic,g)

graphnestedpolygons

graphnestedpolygons(n,m,[options])
draws a graph of offset nested polygons
n vertices around a polygon
m concentric polygons
vertices of inner polygon touches midpoint of outer polygon
returns array(pic,g)

graphcircle

graphcircle(n,[options])
draws a complete graph with a circular layout
with n vertices
returns array(pic,g)

graphcircledstar

graphcircledstar(n,[options])
draws n vertices in a circle, plus 1 vertex in the middle
vertices are connected along the circle, plus all
connected to the center vertex
returns array(pic,g)

graphbipartite

graphbipartite(n,[options])
draws a complete bipartite graph (every vertex on left is
connected to every vertex on the right)
with n vertices in the first column, m in the second
returns array(pic,g)

graphgrid

graphgrid(n, m, [options])
draws a n by m grid of vertices.
returns array(pic,g)

graphrandom

graphrandom(n,[options])
draws a randomly spring laid out graph with n vertices.

graphemptygraph

graphemptygraph(n)
creates an empty graph matrix, nxn

graphdijkstra

graphdijkstra(g,[dest])
computes dijkstras algorithm on the graph g
g is a 2-dimensional matrix
g[i][j] > 0 if vertexes i and j are connected
if dest vertex not set then
the last vertex will be used as the destination vertex
returns array(dist,next) where
dist[i] is the shortest dist to end, and
next[i] is the vertex next closest to the end

graphkruskal

graphkruskal(g)
return a minimum cost spanning tree graph from graph g

graphrepeatednearestneighbor

graphrepeatednearestneighbor(g, [multi])
returns an array (graph,mincostarr), where graph is the
hamiltonian circuit graph using repeated nearest neighbor, and mincostarr
is an array of starting vertex indices that gave that graph.
If multi is set to true, an array of graphs is returned rather than just one

graphnearestneighbor

graphnearestneighbor(g,start)
returns a hamiltonian circuit graph using nearest neighbor
starting at vertex start

graphsortededges

graphsortededges(g)
returns a hamiltonian circuit graph using sorted edges

graphsequenceeuleredgedups

function graphsequenceeuleredgedups(g,op,seq)
determines if given sequence of labels determines
an edge-covering circuit on graph g. options op is needed
for labels
returns -1 if not all edges covered or seq uses nonexisting edges
returns 0 if all edges covered with no dup
returns # of dups if covers all edges with duplications

graphsequenceishamiltonian

function graphsequencishamiltonian(g,op,seq)
determines if given sequence of labels determines
a hamiltonian circuit on graph g. options op is needed
for labels

graphgetpathlength

graphgetpathlength(g,op,seq)
Given sequence seq of graph labels, determine the
length of the path on graph g
options needed for vertex labels

graphshortestpath

graphshortestpath(g,op,start,end,[type])
find shortest path on graph g from vertex start to end
returns array(shortest path,length of path)
for path,
type=0 returns labeledpath, like ABCD
type=1 returns array of vertex indices

graphcircuittostringans

graphcircuittostringans(gs,[lbl, start])
converts graph or array of graphs containing circuits to
a string of labels that can be used as an $answer.
lbl is an array of labels (defaults to A,B,C,etc.)
start is the index of the vertex to start the string circuits with

graphcircuittoarray

graphcircuittoarray(g,[start])
converts graph containing a circuit to an array
of vertices in circuit order

graphgetedges

graphgetedges(g,op)
gets list of edges in and not in graph
need op['labels'] set
return (goodedges,badedges)

graphgetedgesarray

graphgetedgesarray(g)
gets array of edges in a graph
returns array of edges; each edge is array(startvert,endvert)

graphgettotalcost

graphgettotalcost(g)
gets total cost of all edges in a graph

graphadjacencytoprereqs

graphadjacencytoprereqs(g,[options])
create incidence lists from adjacency matrix g
g[i][j] > 0 if edge from i to j
outputs list where list[i] is array of vertices
that lead to i. Only intended for digraphs.

graphprereqtable

graphprereqtable(g,w,[op])
creates an HTML table showing the tasks in g, the task times in w, and
the tasks that must be completed first.
use $op['labels'] to provide array of labels, or ='letters' to use letters

graphadjacencytoincidence

graphadjacencytoincidence(g,[options])
create incidence lists from adjacency matrix g
g[i][j] > 0 if edge from i to j
outputs list where list[i] is array of vertices
that i leads to

graphincidencetoadjacency

graphincidencetoadjacency(list,[options])
create adjacency matrix g from incidence list
list is where list[i] is array of vertices
that i leads to
outputs matrix g[i][j]=1 if edge from i to j

graphgetvalence

graphgetvalence(g,vert,[dir])
gets valence(degree) of vertex vert
if digraph, can use dir:
0: indegree, 1: outdegree, 2: both (default)

graphmakesymmetric

graphmakesymmetric(g)
ensures that all edges are bidirectional.

graphisconnected

graphisconnected
checks if graph is connected

graphmaketable

graphmaketable(g,[op])
makes a weights table based on a given graph

graphspringlayout

graphspringlayout(g,[options])
draws a graph based on a graph incidence matrix
using a randomized spring layout engine. Doesn't work great.
g is a 2-dimensional upper triangular matrix
g[i][j] > 0 if vertices i and j are connected
not a digraph

graphcirclelayout

graphcirclelayout(graph,[options])
draws a graph based on a graph incidence matrix
using a circular layout
g is a 2-dimensional upper triangular matrix
g[i][j] > 0 if vertexes i and j are connected

graphcircledstarlayout

graphcircledstarlayout(graph,[options])
draws a graph based on a graph incidence matrix
using a circular layout with the first vertex in the center of the circle
g is a 2-dimensional upper triangular matrix
g[i][j] > 0 if vertexes i and j are connected

graphgridlayout

graphgridlayout(graph,[options])
draws a graph based on a graph incidence matrix
using a rectangular grid layout. Could hide
some edges that connect colinear vertices
use options['wiggle'] = true to perterb off exact grid
g is a 2-dimensional matrix
g[i][j] > 0 if vertexes i and j are connected

graphpathlayout

graphpathlayout(graph,[options])
draws a graph based on a graph incidence matrix
using a backflow to place the vertices in approximate
order of incidence. Could hide
some edges that connect colinear vertices
use options['wiggle'] = true to perterb off exact grid
g is a 2-dimensional matrix
g[i][j] > 0 if vertexes i and j are connected

graphprocessoptions

internal function, not to be used directly

graphdrawit

internal function, not usually used directly
can get called with graph matrix g, g[i][j] if vertex i has edge to j
pos is array where pos[i] = array(x,y) positions for vertices

graphcomparecircuits

graphcomparecircuits(A,B)
returns true or false
compares two circuits to see if they are the same, regardless of starting
vertex. So "ABCDA" would be considered equivalent to "DCBAD"
can be used with the conditional answer type to score circuits.

graphrandomgridschedule

graphrandomgridschedule(n, m, p,[options])
draws a n by m grid of vertices. Each pair of neighboring
and diagonal vertices has a p probabilility (0 to 1) of being connected
an end vertex is added
options['weights'] as an array of n*m elements will be used as weights.
options['weights'] as a single number will randomize weights from 1 to that
value
if options['labels'] are used, "start" and "end" will be added automatically

graphdecreasingtimelist

graphdecreasingtimelist(g,w)
uses the scheduling priority list generated by the decreasing time list
algorithm
g is the graph
w is the array of task times

graphcriticaltimelist

graphcriticaltimelist(g,w)
uses the scheduling priority list generated by the critical path algorithm
g is the graph
w is the array of task times

graphbackflow

graphbackflow(g,[w])
computes longest-path algorithm on the graph g
g is a 2-dimensional matrix
g[i][j] > 1 if vertexes i leads to j
This might give bad/weird results if graph has a circuit
the last vertex will be used as the destination vertex
w are weights for the vertices, if a scheduling digraph and
tasks rather than edges have weights
returns array(dist,next) where
dist[i] is the longest dist to end, and
next[i] is the vertex next closest to the end

graphlistprocessing

graphlistprocessing(g,t,L,p,[options])
calculates the list processing algorithm on p processors with priority list L
t is an array of task times
L is an array of indices into g showing the priority list
g is a 2-dimensional matrix
g[i][j] > 0 if vertexes i leads to j, where cost of task i is c
This might give bad/weird results if graph has a circuit
the last vertex will be used as the destination vertex; it should be the
last task on the priority list and have task time 0.
output is out[processor] = array of array(task, timestarted, tasklength)

graphscheduletaskinfo

graphscheduletaskinfo(schedule,n)
where schedule is the result of graphlistprocessing
and n is the task number (0 indexed)
returns array(processor assigned (0 indexed), task start, task time)

graphschedulecompletion

graphschedulecompletion(schedule)
where schedule is the result of graphlistprocessing
returns completion time of the schedule

graphscheduleidle

graphscheduleidle(schedule,p)
where schedule is the result of graphlistprocessing
and p is the processor number (0-indexed)

graphscheduleproctasks

graphscheduleproctasks(schedule,p,[oneindex])
return an array of the tasks the processor worked on, in order
set oneindex=true to add one to the last index to get task numbers

graphdrawschedule

graphdrawschedule(sc,[width,height,names])
draws the schedule generated by graphlistprocessing
defaults to width=600,height=70*# of processors
can provide array of task names, or it will default to task numbers (starting at 1)

graphschedulelayout

graphschedulelayout(g,w,pos,[op])
draws a schedule digraph
g is the graph, w is an array of task times
pos is array where L[task number] = array(column,row (counting up from bottom))
use $options['labels'] to specify labels, or T1 - TN will be used

graphschedulemultchoice

graphschedulemultchoice(g,t,L,p)
attempts to return 4 schedules which are different. The first is the
correct schedule based on the provided priority list L