Визуализация графов с минимальным числом пересечений ребер с использованием иерархического подхода

newEdge.target = to.toString();

newEdge.id = newIdE.toString();

graphWithFictitiousNodes.edges.push(newEdge);

fictEdges.push(newEdge);

from = newIdN;

to = newIdN + 1;

if (toAddNode) {

graphWithFictitiousNodes.nodes.push(newNode);

fictNodes.push(newNode);

newIdN++;

}

if (i == graph.nodes[adjIndNode].x - 2) {

to = adjIndNode;

toAddNode = false;

}

newIdE++;

}

}

}

}

else {

if (graph.nodes[adjIndNode].y == -1) {

graph.nodes[adjIndNode].y = YLevels[graph.nodes[adjIndNode].x];

YLevels[graph.nodes[adjIndNode].x]++;

}

}

dfsWithAddedFictNode(graph, adjIndNode, graphWithFictitiousNodes, YLevels);

});

}

function isEmpty(obj) {

for (let key in obj) {

returnfalse;// если тело цикла начнет выполняться - значит в объекте есть свойства

}

return true;

}

function removingLongEdges(graph) {

graph.edges.forEach(function (edge, i, arr) {

needRemoveIdEdges.forEach(function (removeEdge) {

if (edge.source == removeEdge.source && edge.target == removeEdge.target) {

var edgeForRemove = {};

edgeForRemove.source = graph.edges[i].source;

edgeForRemove.target = graph.edges[i].target;

edgeForRemove.id = graph.edges[i].id;

edgesForRemove.push(edgeForRemove);

graph.edges[i] = {};

}

})

});

/* removing empty edges */

var newEdges = [];

graph.edges.forEach(function (edge, i, arr) {

if (!isEmpty(edge))

newEdges.push(edge);

});

graph.edges = newEdges;

return graph;

}

/* set real rootNode from JSON */

function getRootNode(graph) {

for (let i=0; i<graph.nodes.length; i++) {

var rootNodeId = graph.nodes[i].id;

var isRootNode = true;

for (let j=0; j<graph.edges.length; j++) {

if (graph.edges[j].target == rootNodeId) {

isRootNode = false;

break;

}

}

if (isRootNode)

return graph.nodes[i];

}

}

function isIntersection(edge1, edge2, fullnodes) {

if ((fullnodes[parseInt(edge1.source)].y <= fullnodes[parseInt(edge2.source)].y && fullnodes[parseInt(edge1.target)].y <= fullnodes[parseInt(edge2.target)].y) ||

(fullnodes[parseInt(edge1.source)].y >= fullnodes[parseInt(edge2.source)].y && fullnodes[parseInt(edge1.target)].y >= fullnodes[parseInt(edge2.target)].y))

return false;

else

return true;

}

function setEdgesOnEveryLevels(edges, nodes) {

for (let i=0; i< lastLevel; i++) {

edgesOnEveryLevels.push([]);

}

for (let i=0; i< edges.length; i++) {

var t1 = edges[i].source;

var t2 = nodes[parseInt(t1)].x;

var t3 = edgesOnEveryLevels[t2];

if (t1 == undefined || t2 == undefined || t3 == undefined) {

console.log();

}

edgesOnEveryLevels[nodes[parseInt(edges[i].source)].x].push(edges[i]);

}

}

function getCountOfIntersectionsInGraph(edges, nodes) {

var countOfIS = 0;

for (let i=0; i<edgesOnEveryLevels.length; i++) {

intersectionsOnEveryLevels[i] = 0;

for (let j=0; j<edgesOnEveryLevels[i].length-1; j++) {

for (let z=j+1; z<edgesOnEveryLevels[i].length; z++) {

if (isIntersection(edgesOnEveryLevels[i][j], edgesOnEveryLevels[i][z], nodes)) {

countOfIS++;

intersectionsOnEveryLevels[i]++;

}

}

}

}

return countOfIS;

}

function updateCountOfIntersectionsOnLevel(idLevel, edges, nodes) {

//var countOfIS = 0;

intersectionsOnEveryLevels[idLevel] = 0;

for (let j=0; j<edgesOnEveryLevels[idLevel].length-1; j++) {

for (let z=j+1; z<edgesOnEveryLevels[idLevel].length; z++) {

if (isIntersection(edgesOnEveryLevels[idLevel][j], edgesOnEveryLevels[idLevel][z], nodes)) {

//countOfIS++;

intersectionsOnEveryLevels[idLevel]++;

}

}

}

//return countOfIS;

}

function updateCountOfIntersectionsInGraph(edges, nodes, from, to) {

for (let i=from; i<to; i++) {

intersectionsOnEveryLevels[i] = 0;

for (let j=0; j<edgesOnEveryLevels[i].length-1; j++) {

for (let z=j+1; z<edgesOnEveryLevels[i].length; z++) {

if (isIntersection(edgesOnEveryLevels[i][j], edgesOnEveryLevels[i][z], nodes)) {

intersectionsOnEveryLevels[i]++;

}

}

}

}

}

function minimizeIntersections(edges, nodes, leftToRight) {

let isExist = false;

if (leftToRight) {

for (let i = 0; i < edgesOnEveryLevels.length; i++) {

if (intersectionsOnEveryLevels[i] > 0) {

isExist = false;

//alert("Level " + i + ": " + intersectionsOnEveryLevels[i]);

for (let j = 0; j < edgesOnEveryLevels[i].length - 1; j++) {

for (let z = j + 1; z < edgesOnEveryLevels[i].length; z++) {

if (isIntersection(edgesOnEveryLevels[i][j], edgesOnEveryLevels[i][z], nodes)) {

//change on 2 level

let tmpYNode = nodes[parseInt(edgesOnEveryLevels[i][j].target)].y;

nodes[parseInt(edgesOnEveryLevels[i][j].target)].y = nodes[parseInt(edgesOnEveryLevels[i][z].target)].y;

nodes[parseInt(edgesOnEveryLevels[i][z].target)].y = tmpYNode;

isExist = true;

//updateCountOfIntersectionsOnLevel(i, edges, nodes);

updateCountOfIntersectionsInGraph(edges, nodes, i, edgesOnEveryLevels.length);

break;

}

}

if (isExist)

break;

}

}

}

}

else {

for (let i = edgesOnEveryLevels.length-1; i >=0; i--) {

if (intersectionsOnEveryLevels[i] > 0) {

isExist = false;

//alert("Level " + i + ": " + intersectionsOnEveryLevels[i]);

for (let j = 0; j < edgesOnEveryLevels[i].length - 1; j++) {

for (let z = j + 1; z < edgesOnEveryLevels[i].length; z++) {

if (isIntersection(edgesOnEveryLevels[i][j], edgesOnEveryLevels[i][z], nodes)) {

//change on 1 level

let tmpYNode = nodes[parseInt(edgesOnEveryLevels[i][j].source)].y;

nodes[parseInt(edgesOnEveryLevels[i][j].source)].y = nodes[parseInt(edgesOnEveryLevels[i][z].source)].y;

nodes[parseInt(edgesOnEveryLevels[i][z].source)].y = tmpYNode;

isExist = true;

//updateCountOfIntersectionsOnLevel(i, edges, nodes);

updateCountOfIntersectionsInGraph(edges, nodes, 0, i+1);

break;

}

}

if (isExist)

break;

}

}

}

}

}

function getEdgesWithMinI(graph) {

//edgesWithMinI = [];

for (let i=0; i<graph.edges.length; i++) {

let eachE = {};

eachE.source = graph.edges[i].source;

eachE.target = graph.edges[i].target;

eachE.id = graph.edges[i].id;

edgesWithMinI.push(eachE);

}

}

function deepCopy(array) {

let copyArray = [];

for (let i = 0, len = array.length; i < len; i++) {

let item = array[i];

let obj = {};

for (let k in item) {

obj[k] = item[k];

}

copyArray.push(obj);

}

return copyArray;

}

function main(graph, rootI) {

setXYRandom(graph);

setX(graph);

if (rootI == 0) {

let startOutputs = document.createElement("P");

startOutputs.id = "outputs";

document.getElementById("container").appendChild(startOutputs);

startOutputs.innerHTML += "CountOfRealNodes: " + graph.nodes.length + "; ";

startOutputs.innerHTML += "CountOfRealEdges: " + graph.edges.length + "; ";

}

let outputs = document.createElement("P");

outputs.id = "outputs";

document.getElementById("container").appendChild(outputs);

//outputs.innerHTML += "RootNode: " + rootNode.id + "; ";

//outputs.innerHTML += "CountOfOutgoingRibs: " + numOfOutgoingRibs[rootNode.id] + "; ";

outputs.innerHTML += rootNode.id + ", ";

let countRealNodes = graph.nodes.length;

let countRealEdges = graph.edges.length;

graph = addFictitiousNodes(graph);

graph = removingLongEdges(graph);//removing edges before fict nodes

//outputs.innerHTML += "CountFictNode: " + (graph.nodes.length-countRealNodes) + "; ";

//outputs.innerHTML += "CountFictEdges: " + (graph.edges.length-countRealEdges) + "; ";

outputs.innerHTML += (graph.nodes.length-countRealNodes) + ", ";

outputs.innerHTML += (graph.edges.length-countRealEdges) + ", ";

setEdgesOnEveryLevels(graph.edges, graph.nodes);

let minCountI,

prevCountI,

sameCountI = 0,

samePairCountI = 0,

sameTwoPairCountI = 0,

i = 0,

sequence = [],

nodesWithMinI = [];

var time = performance.now();

let countI = getCountOfIntersectionsInGraph(graph.edges, graph.nodes);

//outputs.innerHTML += "Count Of Intersections In Graph: " + countI + "! ";

prevCountI = countI;

minCountI = countI;

sequence.push(countI);

//i=300;

while (sameCountI < 5 && samePairCountI < 10 && sameTwoPairCountI < 15 && i < 300) {

if (i > 0) {

countI = getCountOfIntersectionsInGraph(graph.edges, graph.nodes);

sequence.push(countI);

if (prevCountI === countI)

sameCountI++;

else

sameCountI = 0;

prevCountI = countI;

//outputs.innerHTML += countI + "; ";

}

if (i > 3) {

if (countI == sequence[i-2] && sequence[i-1] == sequence[i-3])

samePairCountI++;

else

samePairCountI = 3;

}

if (i > 7) {

if (countI == sequence[i-4] && sequence[i-1] == sequence[i-5] && sequence[i-2] == sequence[i-6] && sequence[i-3] == sequence[i-7])

sameTwoPairCountI++;

else

sameTwoPairCountI = 7;

}

if (countI < minCountI) {

minCountI = countI;

nodesWithMinI = deepCopy(graph.nodes);

}

if (countI > 0) {

let leftToRight = i%2 > 0 ? false : true;

minimizeIntersections(graph.edges, graph.nodes, leftToRight);

}

else

break;

i++;

}

if (minCountI > 0) {

if (nodesWithMinI.length > 0)

graph.nodes = deepCopy(nodesWithMinI);

i--;

}

time = performance.now() - time;

//outputs.innerHTML += "Iterations: " + i + "; ";

//outputs.innerHTML += "Min Count: " + minCountI + "; ";

outputs.innerHTML += i + ", ";

outputs.innerHTML += numOfOutgoingRibs[rootNode.id] + ", ";

outputs.innerHTML += minCountI;

countIFromVertex[rootNode.id] = minCountI;

resultsTimeMinimize[rootI] += time;

resultsNumOfOut[rootI] += numOfOutgoingRibs[rootNode.id];

resultsMinCount[rootI] += minCountI;

clearVariables();

return graph;

}

/**

* This function loads a JSON file and creates a new sigma instance or

* updates the graph of a given instance. It is possible to give a callback

* that will be executed at the end of the process.

*

* @param {string} url The URL of the JSON file.

* @param {object|sigma} sig A sigma configuration object or a sigma

* instance.

* @param {?function} callback Eventually a callback to execute after

* having parsed the file. It will be called

* with the related sigma instance as

* parameter.

*/

sigma.parsers.json = function (url, sig, callback) {

var graph,

originGraph = {},

xhr = sigma.utils.xhr();

if (!xhr)

throw 'XMLHttpRequest not supported, cannot load the file.';

xhr.open('GET', url, true);

xhr.onreadystatechange = function () {

if (xhr.readyState === 4) {

graph = JSON.parse(xhr.responseText);

/*код для работы программы, считывая данные графа из файла json*/

/*rootNode = getRootNode(graph);

toSortNodes(graph);

originGraph.nodes = deepCopy(graph.nodes);

originGraph.edges = deepCopy(graph.edges);

setFullAdjacencyList(graph);

setNumbersOfOutgoingRibs();

clearVariables();

for (let rootI = 0; rootI < sortedNodeOnNumOfOutgoingRibs.length; rootI++) {

//for (let rootI=1; rootI < 2; rootI++) {

//rootNode = graph.nodes[4];

//rootI = 1;

graph.nodes = deepCopy(originGraph.nodes);

graph.edges = deepCopy(originGraph.edges);

rootNode = graph.nodes[sortedNodeOnNumOfOutgoingRibs[rootI]];

//rootNode = graph.nodes[sortedNodeOnNumOfOutgoingRibs[0]];

setNewAdjacencyList(graph);

graph = main(graph, rootI);

}*/

/*код для вычислительных экспериментов*/

for (let i=0; i<N; i++) {

resultsTimeMinimize[i] = 0;

resultsTimeAllMinimize = 0;

resultsNumOfOut[i] = 0;

resultsMinCount[i] = 0;

}

let countIterForAnalysis = 100;

for (let i=0; i<countIterForAnalysis; i++) {

let timeAll = performance.now();

graph = getRandomGraph();

rootNode = getRootNode(graph);

toSortNodes(graph);

originGraph.nodes = deepCopy(graph.nodes);

originGraph.edges = deepCopy(graph.edges);

setFullAdjacencyList(graph);

setNumbersOfOutgoingRibs();

//graph = main(graph);

clearVariables();

for (let rootI = 0; rootI < sortedNodeOnNumOfOutgoingRibs.length; rootI++) {

//for (let rootI=0; rootI < 1; rootI++) {

//rootNode = graph.nodes[4];

graph.nodes = deepCopy(originGraph.nodes);

graph.edges = deepCopy(originGraph.edges);

rootNode = graph.nodes[sortedNodeOnNumOfOutgoingRibs[rootI]];

setNewAdjacencyList(graph);

graph = main(graph, rootI);

}

timeAll = performance.now() - timeAll;

resultsTimeAllMinimize += timeAll;

fullAdjList = [];

numOfOutgoingRibs = [];

sortedNodeOnNumOfOutgoingRibs = [];

}

let timeAllMinimizeOutputs = document.createElement("P");

let timeMinimizeOutputs = document.createElement("P");

let numOutsOutputs = document.createElement("P");

let minCountOutputs = document.createElement("P");

timeAllMinimizeOutputs.id = "outputs";

timeMinimizeOutputs.id = "outputs";

numOutsOutputs.id = "outputs";

minCountOutputs.id = "outputs";

document.getElementById("container").appendChild(timeAllMinimizeOutputs);

document.getElementById("container").appendChild(timeMinimizeOutputs);

document.getElementById("container").appendChild(numOutsOutputs);

document.getElementById("container").appendChild(minCountOutputs);

timeAllMinimizeOutputs.innerHTML += "AverageExecutionTime, ";

timeMinimizeOutputs.innerHTML += "AverageTimeOfMinimization, ";

numOutsOutputs.innerHTML += "MeanNumOfOutgoingRibsFromEachNode, ";

minCountOutputs.innerHTML += "MeanMinCountOnEachNode, ";

for (let i=0; i<N; i++) {

resultsTimeMinimize[i] = resultsTimeMinimize[i]/countIterForAnalysis;

timeMinimizeOutputs.innerHTML += resultsTimeMinimize[i].toFixed(2) + ", ";

resultsNumOfOut[i] = resultsNumOfOut[i]/countIterForAnalysis;

numOutsOutputs.innerHTML += resultsNumOfOut[i] + ", ";

resultsMinCount[i] = resultsMinCount[i]/countIterForAnalysis;

minCountOutputs.innerHTML += resultsMinCount[i] + ", ";

}

resultsTimeAllMinimize = resultsTimeAllMinimize/countIterForAnalysis;

timeAllMinimizeOutputs.innerHTML += resultsTimeAllMinimize.toFixed(2) + ", ";

// Update the instance's graph:

if (sig instanceof sigma) {

sig.graph.clear();

sig.graph.read(graph);

// ...or instantiate sigma if needed:

} else if (typeof sig === 'object') {

sig.graph = graph;

sig = new sigma(sig);

// ...or it's finally the callback:

} else if (typeof sig === 'function') {

callback = sig;

sig = null;

}

// Call the callback if specified:

if (callback)

callback(sig || graph);

}

};

xhr.send();

};

}).call(this);

Ниже представлен пример входных данных для работы библиотеки, считывая данные в формате json.

{"edges":[

{"source":"1","target":"2","id":"0"},

{"source":"0","target":"6","id":"1"},

{"source":"4","target":"7","id":"2"},

{"source":"3","target":"6","id":"3"},

{"source":"2","target":"5","id":"4"},

{"source":"6","target":"7","id":"5"},

{"source":"7","target":"8","id":"6"},

{"source":"5","target":"7","id":"7"}],

"nodes":[

{"label":"0","x":3,"y":1,"id":"0","color":"#422892","size":8},

{"label":"1","x":2,"y":1,"id":"1","color":"#422892","size":8},

{"label":"4","x":4,"y":0,"id":"4","color":"#422892","size":8},

{"label":"6","x":6,"y":1,"id":"6","color":"#422892","size":8},

{"label":"8","x":5,"y":2,"id":"8","color":"#422892","size":8},

{"label":"2","x":7,"y":1,"id":"2","color":"#422892","size":8},

{"label":"5","x":1,"y":1,"id":"5","color":"#422892","size":8},

{"label":"3","x":6,"y":2,"id":"3","color":"#422892","size":8},

{"label":"7","x":1,"y":1,"id":"7","color":"#422892","size":8}]}

Размещено на Allbest.ru