最小カット グラフ クラスタリングを実装しています。いくつかの s頂点とt頂点の各クラスタリング ステップで構築する st 最小カットに従って、グラフをSとTの 2 つの部分に分割できる必要があります。基本的に、グラフG、ノードs、およびノードtを取り、ノードSとTの2つの互いに素なセットを返す関数が必要です。
私の知る限り、st 最小カットを見つける最も簡単な方法は、最小カット ~ 最大フローの双対性を利用し、最大フローの計算にPush-relabel アルゴリズムを使用することです。しかし、push-relabel アルゴリズムは、 SセットとTセットが何であるかについての情報を提供しません。
では、 SおよびTの最小カット サブセットを取得する正しい方法は何でしょうか? Push-relabel アルゴリズムを使用する方法はありますか? これは C++ または Python で実装されていますか?