Как извлечь индексы альтернативных узлов в графе

Question

У меня есть следующий график, созданный с помощью команд в 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, используя размер шага два.Поскольку приведенный выше график имеет две ветви, я не уверен, как это сделать.

Требуемый вывод:

AlternateNodes = [1 3 5 7 9 11 12 14 16]

Я хотел бы спросить, как получить индексы альтернативных узлов из разветвленного графа.

Answer 1

Для данного графика это возможно с помощью функции кратчайшего пути.Сначала вы можете идентифицировать главные и конечные узлы графа следующим образом:

hNodes = setdiff(tail, head);
tNodes = setdiff(head, tail);

Для простоты здесь я предполагаю, что ваши два пути идут от узла 1 к узлам 11 и 16. Вы можете расширитьэто по мере необходимости путем изменения следующего блока кода для цикла по hNodes или tNodes.

Вы можете использовать кратчайший путь, чтобы получить список узлов вдоль каждого из путей ветвления.Вызов setdiff используется для поиска узлов, которые принадлежат только второй ветви.Затем вы можете получить желаемые результаты, взяв каждый второй узел в path1, а затем добавив каждый второй узел из второй ветви

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