//Detection Algorithms for Clique, Fan and D-Connector
/**
* Detects cliques of a graph.
* @param {Network} network - Network object containg a graph in which to detect cliques.
* @param {number} min - Minimum number of nodes that have to be inside a clique.
* @param {number} max - Maximum number of nodes that have to be inside a clique.
*/
function detectCliques(network, min, max) {
var result = [];
var cliques = jsnx.findCliques(network.nxGraph);
var i = cliques.next();
while (!i.done) {
if (i.value.length >= min && i.value.length <= max) {
result.push(i.value);
}
i = cliques.next();
}
return filterCliques(result);
}
/**
* Filters the cliques such that there are no overlapping cliques and such that the biggest cliques are kept.
* @param {Array} cliques - Array of arrays containing the ids of the nodes of the corresponding clique.
* @returns {Array} Array containing the filtered cliques.
*/
function filterCliques (cliques) {
var result = [];
var tmpNodes = [];
var addClique = true;
//sort by size (descending) to keep the bigger motifs
cliques.sort(function(a, b){return b.length - a.length});
cliques.forEach(function (clique) {
clique.forEach(function (value) {
if (tmpNodes.indexOf(value) >= 0) {
addClique = false;
}
});
if (addClique) {
clique.forEach(function (value) {
if (!(tmpNodes.indexOf(value) >= 0)) {
tmpNodes.push(value)
}
});
result.push(clique);
}
addClique = true;
});
return result;
}
/**
* Detects Fans.
* @param {Network} network - Network object containg a graph in which to detect cliques.
* @returns {Array} Array of fans, where each fan is an array starting with the central node, followed by the adjacent leaves.
*/
function detectFans(network) {
var fans = [];
var nodeiter = network.nxGraph.nodesIter();
var n = nodeiter.next();
do {
var nodename = n.value;
var neighbors = network.nxGraph.neighbors(nodename);
if (neighbors.length >= 2) {
var leaves = [];
for (var i = 0; i < neighbors.length; i++) {
var nbr = neighbors[i];
if (network.nxGraph.neighbors(nbr).length === 1) {
leaves.push(nbr);
}
}
if (leaves.length >= 2) {
var fan = [nodename];
fan = fan.concat(leaves);
fans.push(fan);
}
}
n = nodeiter.next();
} while(!n.done);
return fans;
}
/**
* Help-Function for detectConnectors. Adds the connector c to the output array out and updates the used-map.
*/
function addConnector(out, used, c) {
out.push(c);
for (var i = 0; i < c.spanners.length; i++) {
used.set(c.spanners[i], c);
}
for (var i = 0; i < c.anchors.length; i++) {
used.set(c.anchors[i], c);
}
}
/**
* Detects D-Connectors.
* @param {Network} network - Network object containg a graph in which to detect cliques.
* @param {number} min - Minimum number of anchors
* @param {number} max - Maximum number of anchors
* @returns {Array} Array of D-Connectors, where each connector is an object with attributes "anchors" and "spanners" (arrays containing the corresponding node names).
*/
function detectConnectors(network, min, max) {
var nxGraph = network.nxGraph;
var found = new Map();
var nodeiter = nxGraph.nodesIter();
var n = nodeiter.next();
while (!n.done) {
var nodename = n.value;
var neighbors = nxGraph.neighbors(nodename);
if (neighbors.length >= min && neighbors.length <= max) {
var potentialSpan = true;
for (var i = 0; potentialSpan && i < neighbors.length; i++) {
var nbr = neighbors[i];
if (nxGraph.neighbors(nbr).length < 2) {
potentialSpan = false;
}
}
if (potentialSpan) {
//ADD SPAN
var anchors = neighbors.slice().sort();
var key = anchors.join();
if (!found.has(key)) {
found.set(key, {
anchors: anchors,
spanners: [nodename]
});
} else {
found.get(key).spanners.push(nodename);
}
}
}
n = nodeiter.next();
}
var out = [];
var used = new Map();
found.forEach(function(c){
if (c.spanners.length >= 2) {
for (var j = 0; j < c.spanners.length; j++) {
var s = c.spanners[j];
if (used.has(s)) {
//Other connector with this node already exists
var oldc = used.get(s);
var newcTotal = c.anchors.length + c.spanners.length;
var oldcTotal = oldc.anchors.length + oldc.spanners.length;
if (newcTotal > oldcTotal || (newcTotal === oldcTotal && c.spanners.length > oldc.spanners.length)) {
out.splice(out.indexOf(oldc),1);
//Delete all nodes from oldc from used
for (var k = 0; k < oldc.spanners.length; k++) {
used.delete(oldc.spanners[k]);
}
for (var k = 0; k < oldc.anchors.length; k++) {
used.delete(oldc.anchors[k]);
}
addConnector(out, used, c);
}
return;
}
}
addConnector(out, used, c);
}
});
return filterConnectors(out);
}
/**
* Filters the cconnectors such that there are no overlapping connectors and such that the biggest connectors are kept.
* @param {Array} connectors - Array of arrays containing the ids of the nodes of the corresponding connector.
* @returns {Array} Array containing the filtered connectors.
*/
function filterConnectors (connectors) {
var result = [];
var tmpNodes = [];
var addConnector = true;
var motifs = [];
connectors.forEach(function (value) {
var arr = value.spanners;
motifs.push(arr);
});
//sort by size (descending) to keep the bigger motifs
motifs.sort(function(a, b){return b.length-a.length});
motifs.forEach(function (connector) {
motifs.forEach(function (value) {
if (tmpNodes.indexOf(value) >= 0) {
addConnector = false;
}
});
if (addConnector) {
connector.forEach(function (value) {
if (!(tmpNodes.indexOf(value) >= 0)) {
tmpNodes.push(value)
}
});
result.push(connector);
}
addConnector = true;
});
return result;
}