Выделите фактический путь в дереве в соответствии с данными в Cytoscape

Я пытаюсь выделить все узлы и пути при щелчке от узла до корня.

В этой ссылке я нашел частичный пример - Как выделить путь между двумя узлами в CYTOSCAPE JS.

Код в приведенной выше ссылке использует алгоритм Дейкстры для поиска кратчайшего пути. Но мне нужен фактический путь, указанный в данных.

Например, рассмотрим следующие данные:

nodes: [
    { data: { id: 'a' } },
    { data: { id: 'b' } },
    { data: { id: 'c' } },
    { data: { id: 'd' } },
    { data: { id: 'e' } },
    { data: { id: 'f' } },
    { data: { id: 'g' } }
  ], 

edges: [
    { data: { id: 'ab', weight: 1, source: 'a', target: 'b' } },
    { data: { id: 'ac', weight: 2, source: 'a', target: 'c' } },
    { data: { id: 'bd', weight: 3, source: 'b', target: 'd' } },
    { data: { id: 'be', weight: 4, source: 'b', target: 'e' } },
    { data: { id: 'cg1', weight: 5, source: 'c', target: 'g' } },
    { data: { id: 'gc1', weight: 6, source: 'g', target: 'c' } },
    { data: { id: 'cg2', weight: 7, source: 'c', target: 'g' } },
    { data: { id: 'gf', weight: 8, source: 'g', target: 'f' } }
  ]

Используя код в ссылке, выделение дерева работает следующим образом, если источник - a, а цель - f.

Выделение дерева с помощью алгоритма Дейкстры

Если кто-нибудь может помочь мне отследить и выделить путь, указанный в данных, это было бы очень полезно.


javascript cytoscape cytoscape.js
person Chirag A.M.    schedule 12.01.2017    source источник
comment
Путь, который дает Дейкстра - это путь, взятый от a до f. Уточните пожалуйста свой вопрос. Непонятно, чего ты хочешь. У вас есть пример данных, поэтому укажите, что вы ожидаете в качестве вывода для этого набора данных.   -  person maxkfranz    schedule 14.01.2017

Ответы (1)


arrow_upward
0
arrow_downward

Мне удалось распечатать кратчайший путь с помощью метода A *. Изменив его для алгоритма Дейкстры, я бы, вероятно, реализовал, например, ffg:

var dijkstra = cy.elements().dijkstra('#e', function(){
  return this.data('weight');
});

var pathToJ = dijkstra.pathTo( cy.$('#j') ); 

                for (i = 0,j=0; i < pathToJ.nodes().size(),j<pathToJ.edges().size(); i++,j++) {
                    console.log('Nodes Size - '+ pathToJ.nodes().size());
                    console.log('Edges Size - '+ pathToJ.edges().size());
                    console.log('Node - \t' + pathToJ.nodes()[i].data('id'));
                    console.log('edge - \t' + pathToJ.edges()[j].data('id'));
                }

pathTo(node) возвращает коллекцию, содержащую кратчайший путь от исходного узла к узлу.

Если весовая функция не определена, для каждого ребра используется постоянный вес, равный 1.

person MetaKnight    schedule 24.01.2017