# Introduction

This tutorial is for familiarizing you with the `Graph` widget (docs). We’ll be implementing Prim’s MST algorithm. As with the Array Tutorial, basic knowledge of other widgets is assumed.

# Getting Started

We created the start for Prim’s Algorithm. It uses a `Queue` widget (docs) which is a very simple wrapper for the `Array` widget. All that is missing from Prim's is a `Graph`!

prims1.html

 for each u ∈ G.V u.key = ∞ u.pred = nil r.key = 0 Q = G.V while Q ≠ ∅ u = ExtractMin(Q) for each v ∈ G.Adj[u] if v ∈ Q and w(u,v) < v.key u.pred = v v.key = w(u,v)

# The Graph Widget

The `Graph` widget takes the same required arguments as most other widgets - `varName` and `container`.

Prim’s has an argument `r`, that needs to be provided somehow. We can use `Graph`’s `inputVars` argument for that. It takes an object mapping a variable name to a “graph id”.

Speaking of graph ids - we can use a `Graph` data structure (docs) to define a default graph for the widget. The `Graph` data structure has many methods essential for writing graph algorithms. In Prim’s we use `eachNeighbor` and `vertices`. It is highly recommended that you check out the API.

Lets put it in to Prim’s and see how it looks.

Javascript:

``````new Vamonos.Widget.Graph({
container: "graph",
varName: "G",
inputVars: { r: "v3" },
defaultGraph: new Vamonos.DataStructure.Graph({
vertices: [
{id: "v0", x: 17,  y: 10},
{id: "v1", x: 98,  y: 10},
{id: "v2", x: 176, y: 13},
{id: "v3", x: 15,  y: 78},
{id: "v4", x: 100, y: 80},
{id: "v5", x: 182, y: 80},
{id: "v6", x: 15,  y: 138},
{id: "v7", x: 100, y: 140},
{id: "v8", x: 182, y: 140},
],
edges: [
{source: "v0",target: "v4", w:1},
{source: "v1",target: "v2", w:2},
{source: "v1",target: "v4", w:5},
{source: "v3",target: "v4", w:3},
{source: "v3",target: "v6", w:1},
{source: "v4",target: "v8", w:10},
{source: "v5",target: "v8", w:2},
{source: "v6",target: "v7", w:3},
{source: "v7",target: "v8", w:2},
]
}),
})
``````

prims2.html

for each u ∈ G.V u.key = ∞ u.pred = nil r.key = 0 Q = G.V while Q ≠ ∅ u = ExtractMin(Q) for each v ∈ G.Adj[u] if v ∈ Q and w(u,v) < v.key u.pred = v v.key = w(u,v)

# Fancy Graph Stuff

What’s missing you say? Edge weights. Labeling of `u`, `v`, and `r` variables. Labeling of `key` values for each vertex. Seeing some representation of the MST when it’s all done!

Fortunately the Vamonos team has created solutions for all of these problems.

• `vertexLabels` - lets you declare labels around vertices. It will either display a variable name when the corresponding variable equals that vertex, or some arbitrary attribute of the vertex, accessed with a function. It is perhaps best explained by example:

Javascript:

``````vertexLabels: {
inner: {
edit: function(vtx){ return vtx.name },
display: function(vtx){ return vtx.key },
},
sw: {
edit: function(vtx){ return "" },
display: function(vtx){ return vtx.name },
},
ne: ['u','v'],
nw: ['r'],
},
``````
• `edgeLabel` - lets you tell `Vamonos` to display an arbitrary edge attribute. It has a few options, but the simplest is to just give it the name of the attribute you want to see.

Javascript:

``````edgeLabel: "w",
``````
• `edgeCssAttributes` - is a little trickier. You can apply a class to an edge when two vertex variables are connected by an edge. The edge must be encoded as a string with the variable names and an arrow between them. You can also perform custom calulations based on an edge input to a function that you provide. When you return true, the class will be applied to the edge-path.

Javascript:

``````edgeCssAttributes: {
green: function(edge){
return (edge.target.pred === edge.source.name)
|| (edge.source.pred === edge.target.name)
},
red: "u<->v",
},
``````

Finally, we can customize how the labels (and vertices) look with CSS.

CSS:

``````<style type="text/css">
.vertex {
width: 40;
height: 30;
}

.vertex-contents {
font-size: .8em;
}

.vertex-ne-label, .vertex-nw-label {
font-weight: bold;
}

.vertex-sw-label {
font-style: italic;
}

path.red {
stroke: #FF7D7D;
}

path.green {
stroke: #92E894;
}
</style>
``````

Now we have a fully functional Prim’s MST algorithm visualization!

prims3.html

for each u ∈ G.V u.key = ∞ u.pred = nil r.key = 0 Q = G.V while Q ≠ ∅ u = ExtractMin(Q) for each v ∈ G.Adj[u] if v ∈ Q and w(u,v) < v.key u.pred = v v.key = w(u,v)
Next page: Other widgets