TutorialIn 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.
For creating the graph, we use a default graph generator provided by Rocs. This can be found in the main menu at → → . 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).
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 
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.
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.");
