Count all cycles in simple undirected graph

バージョン 1.2.0.0 (5.43 KB) 作成者: Jeff Howbert
Counts all cycles in a simple undirected graph up to specified size limit, using backtracking.

ダウンロード 1.5K 件

更新 2011/8/29

ライセンスの表示

Counts all cycles in input graph up to (optional) specified size limit, using a backtracking algorithm. Designed for undirected graphs with no self-loops or multiple edges. Returns count of each size cycle from 3 up to size limit, and elapsed time.

Algorithm is guaranteed to find each cycle exactly once. It is essentially equivalent to Johnson (SIAM J. Comput. (1975), 4, 77), but for undirected graphs, and without the look-ahead feature. The lack of look-ahead is expected to have negligible performance impact on dense random graphs.

Reads input graph using separate m-file readGraph(), which supports reading a graph from a file or workspace array in four different formats. A test file for each format is included.

In practice this algorithm is much faster than the ILCA cycle counting algorithm posted by Joe Kirk (run_loops.m).

引用

Jeff Howbert (2022). Count all cycles in simple undirected graph (https://www.mathworks.com/matlabcentral/fileexchange/29438-count-all-cycles-in-simple-undirected-graph), MATLAB Central File Exchange. 取得済み .

MATLAB リリースの互換性
作成: R2011a
すべてのリリースと互換性あり
プラットフォームの互換性
Windows macOS Linux
謝辞

ヒントを与えたファイル: PM Architectures Project

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!