グラフ中の長さ３と長さ４の閉路を検出したい

Question

グラフ中に含まれる長さが３と４の閉路を求めるアルゴリズムを考えています。
なにか良いアイデアはないでしょうか？
（グラフの情報は外部からストリームして、C言語で開発しています。）

ただし、以下のような場合は長さ３の閉路が２つで４の閉路があるとはカウントしません。

Comments

[wwbQzhMkhhgEmhU]

ルールが明確じゃないですよ。
ストリームとやらの法則だって重要です。
また、まずは自分で組んでから聞きましょう。

[tiitoi]

効率的に求めるアルゴリズムはなく、深さ優先探索で地道に探すしかないと思います。
以下のページが参考になるのではないでしょうか。
https://www.geeksforgeeks.org/cycles-of-length-n-in-an-undirected-and-connected-graph/

Answer 1

アイデアということなので。

長さが３の閉路は、スタートのノードと結ばれる２つのノードを必ず含みます。（質問の図でいうと、スタートをiとすると、[v1,v2],[v1,j],[v2,j]のいずれかが候補になる）また、この候補の組み合わせのノード間には必ずエッジがあります。（長さ３のうち、２つのノードで長さ２が消費されるため）
よって、上記の条件を実装すれば長さ３の閉路の検出ができることになります。もう少し具体的にいうと

１．ノード間のエッジの有無を0と1で表現した行列（Xとする）を準備する。（縦軸をi,v1,v2,j、横軸をi,v1,v2,jとして交差する部分にエッジがあれば1、なければ0を設定）
２．Xの行数分、以下の処理を実施
１）特定の行を取り出して1が設定されているインデックスを検出（x[0,:]であれば、[0,1,1,1]
なので、[1,2,3]となる。
２）上記の[1,2,3]から2つを取り出した組み合わせを生成（[1,2],[1,3],[2,3]となる）
３）Xから上記の組み合わせの要素を取り出して１であれば長さ3の閉路と判定
３．重複ケースをチェックして除外

というコードでうまくいくはずです。

長さ4の閉路もおおよそは上記のルールの応用でうまくいくはずです。スタートのノードと結ばれるノード2つが候補というところまでは同じです。長さ4の場合は、この候補各々と結ばれるノードを検出してこのノードの集合の積を取った結果、残ったノードがあれば長さ4のノードということになります。
上記もエッジの有無を表す行列を使えば、それほど難しくないはずです。

最後の「以下のような場合は長さ３の閉路が２つで４の閉路があるとはカウントしません。」については以前に回答した記憶があるので確認願います。

細かなケースは検証していないので、実装して問題の有無を確認願います。