1

頂点とエッジの既存のデータを、接続されていない 2 つ以上のグラフに分離したいと考えています。例として以下を挙げたいと思います。

2 つの六角形が重なっているが、異なる Z にあると想像してください。

六角形 1 には、次の頂点 A(0,0,1)、B(1,0,2)、C(2,1,2)、D(1,2,1)、E(0,2,1) があります。 、F(-1,2,1)。接続は次のとおりです: AB、BC、CD、DE、EF、FA。すべての頂点がこのレイヤーで接続されているため、グラフ 1 のこの部分。

Hexagon2 には、次の頂点 A1(0,0,6)、B1(1,0,7)、C1(2,1,7)、D1(1,2,8)、E1(0,2,7)、 F1(-1,2,6)。接続は次のとおりです: A1-B1、B1-C1、C1-D1、D1-E1、E1-F1、F1-A1。これはグラフ 2 の一部です

私のデータは、グラフを形成できる頂点のリストとエッジのリストの形式です。グラフ 2 を削除し、グラフ 1 の頂点と接続のみをアルゴリズムのポリゴン決定部分に与えたいと思います。私の実際のデータには、グラフ 1 として約 1000 個の接続されたポリゴンが含まれ、グラフ 2 として約 100 個の (面積がはるかに大きい) ポリゴンが含まれています。グラフ 2 を削除したいと思います。

4

1 に答える 1

2

あなたが説明している問題は、接続されたコンポーネントに関連しています。

Python Networkxモジュールには、この種のグラフの問題を処理する関数があります。すべてのコンポーネントを返すconnected_components関数を探しているので、適切なコンポーネントを選択できます (頂点の数によって可能)。

于 2012-10-25T10:57:19.150 に答える