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)