問題タブ [connected-components]

L * L行列で1、0、または-1の「島」を見つけるために、Pythonでプログラムを書いています。連結成分のこれらの「領域」を見つけ、それらのそれぞれにラベルを付け、行列 m[x][y] の特定の要素について、それが属する島のサイズを返すことができるようにする必要があります。

これにより、ランダム行列 m のラベル付きの島が得られるはずですが (例にすぎません)、特定のポイントが属する「領域」のサイズを取得する方法がわかりません。私たちを手伝ってくれますか？私はプログラミングの経験がほとんどないので、質問がばかげている場合はご容赦ください。

ありがとう

私はこれについて頭を悩ませ、他のトピックを検索しましたが、役立つものは何も見つかりませんでした. したがって、15 個のノードを持つランダムに生成されたグラフがあり、Python で NetworkX の関数 nx.connected_components を使用せずに接続コンポーネントを見つける必要があります。私の場合、それらを見つけるのは簡単です。私は以下を使用しました：

したがって、次のような出力が得られます1 [4,6,7]。私の質問は、各ノードとその隣接ノードをグループ化して、接続されているノードまたは接続されていないノードのグループのリストを取得する方法です。このようなもの: lis=[[1,4,6,7],[2,3],[5],[8,9,10,11],[0,12,13],[14]]. このコードは、任意のサイズのランダムに作成されたグラフに対して機能するはずです。

私が理解していることから、強く接続されたコンポーネントに対して既製の効率的なブラックボックスメソッドがある場合、トポロジカルソートを行う1つの方法は次のとおりです。

(仮定 - 自己ループなし)

1. 強連結成分を実行する
2. サイズ > 1 のコンポーネントが 1 つ以上ある場合、このグラフにはサイクルがあります。
3. それ以外の場合 (グラフには 1 つのサイズのコンポーネントしかありません)、これは DAG です。おめでとうございます!
4. それが DAG 実行のトポロジカル ソートである場合は、それができないと文句を言います。

効率に関係なく、上記はトポロジカルソートを行う「技術的に正しい」方法ですか?

物事を正しく理解していることを確認したいだけです。

CvConnectedCompからの出力であるを使用しようとしていますcvFloodFill。

comp.rectコンポーネントの描画にはcomp.contour使用できますNULLが、さらなる処理に使用したいです。マスクなしでも試してみましたが、それでも同じ結果です。

どんなアイデアでも大歓迎です。

https://www.lri.fr/~lacas/Publications/JRTIP10.pdfから Light Speed Labeling アルゴリズムを実装しようとしています。この論文に記載されているアルゴリズムのアプローチにできる限り厳密に従おうとしましたが (pgs 9-12)、同等化段階の後の出力は意味がありません。

問題が何であるか誰にも分かりますか？

私が解決しようとしていることを説明するタイトルを思い付くのに苦労しているので、より良いタイトルがあればコメントしてください!

ソリューションは、R、Python、または SQL である可能性があります(正確には Aster TeraData SQL ですが、SQL 言語のソリューションは学習目的に非常に役立ちます)。

問題: 順不同のアイテムのペアのリストが与えられた場合、少なくとも 1 つのリンクに関連するすべてのペアをリンクする出力を生成します。

R を使用した簡単な例を次に示します。

望ましい出力 (読みやすいデータ構造):

基本的に、入力はノードとエッジのグラフを表しています。目的の出力は、接続されているグラフ内のすべてのオブジェクトのリストです。

どんな助けや考えもいただければ幸いです！

デジタル形状は、バイナリ イメージ (ブロブ) 内の一連の接続されたピクセルです。

これは、ランレングス コーディングによってコンパクトに表すことができます。つまり、ピクセルを水平線分にグループ化し、始点の座標と長さを格納します。通常、RLC 表現はランをラスター順に格納します。つまり、行ごとに右に並べます。

滑らかな形状の場合、ストレージ要件は O(N²) から O(N) に低下します。

形状の輪郭は、(塗りつぶしアルゴリズムによって) 内部が塗りつぶされたときに形状を復元する、ピクセルの閉じたチェーンです。これは O(N) 表現でもあります。形状がビットマップとして利用できる場合、アウトラインは輪郭アルゴリズムによって取得できます。

中間ビットマップに描画せずに、RLC 表現を指定して形状の輪郭を直接計算するアルゴリズムを探しています。アルゴリズムは、実行回数に比例して時間内に実行されることが期待されます。

あなたは解決策に出くわしましたか？

グラフ G を作成し、2 つのノードを追加します。次に、このグラフの連結成分を見つけて変数 a に代入します。

次に、変数 a を出力します。

結果は次のようになります。

この後、同じプロンプトを使用して再度出力しましたが、何も得られませんでした:

私はこれについて非常に興味があります。接続されたコンポーネントを一度出力すると、それらが消えてしまったようです?! どうして？！