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 finding a matching in the given graph (in the following we use the common terms for graph algorithms: graph is the data structure, nodes are the data elements, edges are the pointers).
Our goal is to visualize the correspondence of the matching and the minimum vertex cover. For this, we want to specify two pointer types, one to display matching edges and one type to display ordinary edges, as well as two data types that we use to distinguish nodes contained in C and those not contained in C.
For the data structure backend "Graph", Rocs ships a helper tool that can generate graphs. We go to → → .
There we generate 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).
Finally, we modify the graph name at the data structure panel and call the graph testgraph.
We use the at the data structure panel to open the properties dialog for data and pointer types of the current graph document.
For the data types we add a new type called "C", which automatically gets ID 1.
For this type we select the server picture as icon.
Furthermore, we switch to the pointer type page and add a new pointer type called "matching".
This gets automatically ID 1 and we set the color to blue.
At last we have to implement the approximation algorithm. For this we use the following implementation:
var E = testgraph.list_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.start();
var v = e.end();
e.set_type(1); // 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.set_type(1);
v.set_type(1);
// remove from E all edges incident to u or v
var adjacent = u.adj_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.adj_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
}
}
}
output("Vertex Cover contains " + C.length + " nodes.");