Как я могу рассчитать обхват графа, используя Graph-Tool?

Question

Graph-tool предлагает множество инструментов для оценки графа: https://graph-tool.skewed.de/static/doc/topology.html. Тем не менее, я не могу найти какой-либо метод для расчета обхвата, то есть самый короткий цикл на графике.

Знаете ли вы, существует ли подходящий метод или я могу использовать существующие, чтобы получить эффективный расчет?

Answer 1

Я думаю, что это можно легко рассчитать, используя all_paths функция.

g = gt.collection.data["karate"]
min_cycle_lengths = []
for v in g.vertices():
    cycles_v = list(gt.all_paths(g, source = v, target = v))
    min_cycle_lengths.append(min([len(x)-1 for x in cycles_v if len(x) > 3]))

girth = min(min_cycle_lengths)