Сжатие зацикленных участков в графе

shrimp-graph.js

var vertexes = [[1], [2], [3]];

var routes = [
    [[1], [2]],
    [[2], [1]],
    [[2], [3]],
    [[3], [2]],
];

/**
 * Равенство двух массивов
 * [1,2,3] === [1,2,3]
 * [1,2] !== [1,2,3]
 * console.log(equal([1, 2], [1, 2]))
 */
function equal(a, b)
{
    if (a.length !== b.length) {
        return false;
    }
    
    for (var i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) {
            return false;
        }
    }
    
    return true;
}

/**
 * Проверяет есть для заданного маршрута обратный
 * findOppositeFor([[1], [2]], routes)
 */
function findOppositeFor(path, routes)
{
    for (var i = 0; i < routes.length; i++) {
        var route = routes[i];
        
        if (equal(route[0], path[1]) && equal(route[1], path[0])) {
            return i;
        }
    }
    
    return false;
}

/**
 * Проверяет остались ли циклы в графе
 * hasCyclePath(routes)
 */
function hasCyclePath(routes)
{
    var j;

    for (var i = 0; i < routes.length; i++) {
        j = findOppositeFor(routes[i], routes);

        if (j !== false) {
            return [i, j];
        }
    }
    
    return false;
}

/**
 * Сцепляет две вершины
 * concatPath([[1], [2]])
 */
function concatPath(path)
{
    var a = path[0];
    return a.concat(path[1]);
}

function deleteVertex(vertex, vertexes)
{
    for (var i = 0; i < vertexes.length; i++) {
        if (equal(vertex, vertexes[i])) {
            delete vertexes[i];
        }
    }
}

/**
 * Удаляет элемент из массива
 */
function deleteRoute(i, routes)
{
    delete routes[i];
}

/**
 * Сцепляет циклический путь в одну вершину
 * concatCyclePath(0, 1, routes)
 */
function concatCyclePath(i, j, routes, vertexes)
{
    var concatedPath = concatPath(routes[i]);
    var concatedPathFor1 = routes[i][0];
    var concatedPathFor2 = routes[i][1];

    deleteRoute(i, routes);
    deleteRoute(j, routes);
    
    routes = routes.filter(function(route){return route;});
    
    deleteVertex(concatedPathFor1, vertexes);
    
    vertexes = vertexes.filter(function(vertex){return vertex;});
    
    replaceVertex(concatedPathFor1, concatedPath, routes);
    replaceVertex(concatedPathFor2, concatedPath, routes);
    
    replaceInVertexes(concatedPathFor2, concatedPath, vertexes);
    
    return {
        vertexes: vertexes,
        routes: routes
    }
}

function replaceInVertexes(needle, replacement, vertexes)
{
    for (var i = 0; i < vertexes.length; i++) {
        if (equal(needle, vertexes[i])) {
            vertexes[i] = replacement;
        }
    }
}

/**
 * Заменяет компоненты на заданный другой компонент
 */
function replaceVertex(needle, replacement, routes)
{
    for (var i = 0; i < routes.length; i++) {
        var route = routes[i];
        
        if (equal(needle, route[0])) {
            route[0] = replacement;
        }
        
        if (equal(needle, route[1])) {
            route[1] = replacement;
        }
    }
}

var path;

while ((path = hasCyclePath(routes)) !== false) {
    var obj = concatCyclePath(path[0], path[1], routes, vertexes);
    routes = obj.routes;
    vertexes = obj.vertexes;
}

console.log(routes, vertexes);