Инструмент gvpr , входящий в состав graphviz tools , позволяет применять правила к графу и выводить измененный граф.
Из описания:
Копирует входные графы в свой вывод, возможно преобразовывая их структуру и атрибуты, создавая новые графы, ...
Похоже, вы хотите удалить все узлы, имеющие степень0 и имеющие только связанные узлы (преемники) со степенью 0.
Вот моя версия gvpr сценария nostraynodes.gv:
BEGIN {node_t n; int candidates[]; int keepers[];}
E{
if (tail.indegree == 0 && head.outdegree == 0)
{
candidates[tail] = 1;
candidates[head] = 1;
}
else if (tail.indegree == 0)
{
keepers[tail] = 1;
}
else if (head.outdegree == 0)
{
keepers[head] = 1;
}
}
END_G {
for (candidates[n]){
if (n in keepers == 0)
{
delete(NULL, n);
}
}
}
Вот что делает сценарий:
Цикл по всем ребрам один время и заполнение двух списков:
- кандидатов - список узловкоторые, возможно, придется удалить, и
- хранители - список узлов, которые могут закончиться кандидатами , но не должны быть удалены.
Так что же добавляется в какой список?
- Любые два узла, соединенные друг с другом, гдехвостовой узел не имеет никаких входящих ребер, а головной узел не имеет никаких исходящих ребер, образует цепочку только из 2 узлов и поэтому кандидатов подлежит удалению;то есть, если одни и те же узлы не являются частью другой цепочки длиннее двух узлов:
- Хвостовой узел без каких-либо входящих ребер, но связанный с головным узлом, который сам имеет исходящие ребра, является хранителем;и
- Головной узел без каких-либо исходящих ребер, но связанный с хвостовым узлом, который сам имеет входящие ребра, также является хранителем .
- Удалить все кандидатов не в хранителях
Это решение является не общим и работает только для проблемы, указанной в вопросе, чтодержит только цепочки длиной не менее 3 узлов.Он также не удалит короткие циклы (два узла соединены друг с другом).
Вы можете вызвать это, используя следующую строку:
gvpr -c -f .\nostraynodes.gv .\graph.dot
Вывод с использованием вашего примера диаграммы:
digraph g {
1 -> 2;
2 -> 3;
3 -> 4;
}
Обратите внимание, что это мой первый скрипт gvpr - возможно, есть лучшие способы написать это, и я не уверен, как он обрабатывает 35000 узлов, хотя я уверен, что этого не должно бытьбольшое дело.
См. также Graphviz / Dot - как пометить все листья в дереве отличительным цветом? для более простого примера преобразования графа.