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.

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'],
},

Javascript:

edgeLabel: "w",

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