Как я могу рассчитать обхват графа, используя 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)