Сериализация графика
Как будто вы пытаетесь получить доступ к объекту, который является null. Рассмотрим ниже пример:
TypeA objA;
. В это время вы только что объявили этот объект, но не инициализировали или не инициализировали. И всякий раз, когда вы пытаетесь получить доступ к каким-либо свойствам или методам в нем, он будет генерировать NullPointerException, что имеет смысл.
См. Также этот пример:
String a = null;
System.out.println(a.toString()); // NullPointerException will be thrown
4 ответа
Топологический Вид (Из Википедии):
В теории графов, топологическом виде или топологическом упорядочивании направленного графа без петель (DAG) линейное упорядочивание его узлов, в которые каждый узел прибывает перед всеми узлами, к которым это имеет исходящие края. Каждый DAG имеет один или несколько топологических видов.
Псевдо код:
L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
remove a node n from Q
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)
else
output message (proposed topologically sorted order: L)
Я ожидал бы инструменты, которым нужно, это просто обходит дерево способом в глубину и когда они поражают лист, просто обрабатывают его (например, компиляция) и удаляют его из графика (или отмечают его, как обработано, и узлы обработки со всеми листами, обработанными как листы).
, пока это - DAG, этот простой стековый обход должен быть тривиальным.
Если график содержит циклы, как может там существовать позволенный порядки выполнения для Ваших файлов? Мне кажется, что, если график содержит циклы, то у Вас нет решения, и об этом сообщает правильно вышеупомянутый алгоритм.
Я придумал довольно наивный рекурсивный алгоритм (псевдокод):
Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list
function resolve(a):
if (dest.contains(a)) return;
foreach (b in source[a]):
resolve(b);
dest.add(a);
foreach (a in source):
resolve(a);
самая большая проблема с этим состоит в том, что это не имеет никакой способности обнаружить циклические зависимости - это может войти в бесконечную рекурсию (т.е. переполнение стека;-p). Единственный путь вокруг того, что я вижу, состоял бы в том, чтобы зеркально отразить рекурсивный алгоритм в интерактивный с ручным стеком, и вручную проверить стек на повторные элементы.
у Кого-либо есть что-то лучше?