Как извлечь индексы альтернативных узлов в графе
У меня есть следующий график, созданный с помощью команд в MATLAB,
tail = [1 2 3 4 5 6 6 7 8 9 10 12 13 14 15];
head = [2 3 4 5 6 7 12 8 9 10 11 13 14 15 16];
NodeLabel = string(1:16)';
EdgeLabel = strcat(string(tail),string(head));
Graph = graph(tail,head)
Graph.Nodes.Name = cellstr(NodeLabel);
Я хочу извлечь индексы альтернативных узлов. Для графа без ветвей я могу получить позиции альтернативных узлов из Graph.Nodes.Name, используя размер шага два. Поскольку у приведенного выше графика есть две ветви, я не знаю, как это сделать.
Желаемый результат:
Альтернативные узлы = [1 3 5 7 9 11 12 14 16]
Я хотел бы попросить совета, как получить индексы альтернативных узлов из разветвленного графа.
Ответы 1
Для данного графика это возможно с помощью функции кратчайшего пути. Сначала вы можете идентифицировать головные и хвостовые узлы графа:
hNodes = setdiff(tail, head);
tNodes = setdiff(head, tail);
Для простоты здесь я предполагаю, что ваши два пути лежат от узла 1 к узлам 11 и 16. Вы можете расширить это по мере необходимости, изменив следующий блок кода, чтобы перебрать hNodes или tNodes.
Вы можете использовать кратчайший путь, чтобы получить список узлов вдоль каждого из путей ветвления. Вызов setdiff используется для поиска узлов, принадлежащих только второй ветви. Затем вы можете получить желаемые результаты, взяв каждый другой узел на пути 1, а затем добавив каждый другой узел из второй ветви
path1 = shortestpath(Graph, 1, 11);
path2 = shortestpath(Graph, 1, 16);
branch2 = setdiff(path2, path1);
AlternateNodes = [path1(1:2:end) branch2(1:2:end)]
AlternateNodes =
1 3 5 7 9 11 12 14 16