Tutorial

In this section we want to create an example project to explore some of the most important functions of Rocs. The goal is to create a graph and a script that illustrates a simple 2-approximate algorithm for the minimum vertex cover problem. The minimum vertex cover problem is the problem to find a subset of graph nodes C of minimal size such that each graph edge is connected to at least one node in C. This problem is known to be NP-hard and we want to illustrate how to find an approximation of factor 2 by computing a matching in the given graph.

Our goal is to visualize the relationship of the matching and the minimum vertex cover. For this, we want to specify two edge types, one to display matching edges and one type to display ordinary edges, as well as two node types that we use to distinguish nodes contained in C and those not contained in C.

Generating the Graph

For creating the graph, we use a default graph generator provided by Rocs. This can be found in the main menu at Graph DocumentToolsGenerate Graph. There, we select a Random Graph with 30 nodes, 90 edges, and with seed 1 (the seed is the starting seed for the random graph generator; using the same seed multiple times results in same and reproducible graphs).

Creating the Element Types

We use the Element Types and create a second node type as well as a second edge type. For both new types we open the properties dialog by using the respective Properties buttons and set the IDs to 2. Furthermore, we change the colors of elements of these two new types (to distinguish them from the default types). Finally, we set all edge types to be bidirectional, and the IDs of the default types to 1.

The Algorithm

At last we have to implement the approximation algorithm. For this we use the following implementation:

for (var i=0; i < Document.nodes.length; i++) {
    Document.nodes[i].type = 1;
}
for (var i=0; i < Document.edges.length; i++) {
    Document.edges[i].type = 1;
}

var E = Document.edges(); // set of unprocessed edges
var C = new Array();      // matching edges
while (E.length > 0) {
    var e = E[0];         // we take first edge e={u,v}
    var u = e.from();
    var v = e.to();
    e.type = 2;           // set edge to be a matching edge
    E.shift();            // remove e (i.e., E[0]) from edge list
    C.push(u);            // add u to C
    C.push(v);            // add v to C

    // mark u,v as nodes in C
    u.type = 2;
    v.type = 2;

    // remove from E all edges incident to u or v
    var adjacent = u.edges();
    for (var i=0; i < adjacent.length; i++) {
        var index = E.indexOf(adjacent[i]); // find the index
        if (index != -1) {
            E.splice(index, 1); // remove it if really found
        }
    }
    var adjacent = v.edges();
    for (var i=0; i < adjacent.length; i++) {
        var index = E.indexOf(adjacent[i]); // find the index
        if (index != -1) {
            E.splice(index, 1); // remove it if really found
        }
    }
}
Console.log("Vertex Cover contains " + C.length + " nodes.");

Execute the Algorithm

The algorithm can be executed by the Run button at the script control panel.