Реализация орграфа с меткой времени

У меня есть серия орграфов, содержащих одни и те же узлы, но разные ребра — динамический/временной граф — и я застрял в идеях о том, как лучше всего это реализовать (предпочтительно в Matlab или Python).

Я хотел бы построить структуру в стиле орграфа, в которой каждый узел соединяется с самим собой на каждом временном шаге (A0 -> A1 -> и т. д.), а также с любым другим. края на этом временном шаге. Например, в орграфе с узлами {A, B} в момент времени t_0 орграф отключен. В момент времени t_1 есть ребро от A до B. Я хотел бы создать что-то вроде: A0 -> {A1, B1}. В0 -> {В1}. Моя проблема в том, что я не могу заставить функцию digraph сохранить узел и временной шаг. Я не хочу использовать разные узлы для представления разных временных шагов, потому что это слишком усложняет сравнение. Я хочу указать на «тот же» узел, но сохранить дополнительную переменную времени, к которой я могу получить доступ, например, при обходе моего орграфа с использованием поиска в ширину.

Вот картина того, что я надеюсь реализовать!

Любые идеи?

Спасибо за вашу помощь!


python matlab data-structures digraphs graph-theory
person Community    schedule 04.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Как всегда, подходящая структура данных зависит от операций, которые вы хотите выполнить над структурой данных. Поэтому без лучшего понимания того, что вы планируете делать, нет четкого ответа.

Однако, возможно, вы могли бы хранить каждое состояние графа как матрицу смежности. Затем вы можете сложить 2D-матрицы смежности в 3D-массив. Это хорошая компактная структура, которая дала бы вам легкий доступ к каждому графику как фрагменту трехмерного массива и, возможно, позволила бы вам выполнять предполагаемые операции с временными шагами.

Используя networkx, вы можете конвертировать в матрицы смежности и из них, используя nx.from_numpy_matrix и nx.to_numpy_matrix:

import numpy as np
import networkx as nx

arrs = np.array([[(0,0), (0,0)], 
                [(1,1), (0,1)]])

for arr in arrs:
    G = nx.from_numpy_matrix(arr)
    print(G.edges())
    assert np.allclose(arr, nx.to_numpy_matrix(G))

на первой итерации печатает

[]

так как нет граней. И на второй итерации он печатает

[(0, 0), (0, 1), (1, 1)]

поскольку есть ребра от узла 0 до узла 0, от узла 0 до узла 1 и от узла 1 до узла 1:

person unutbu    schedule 04.02.2016