問題タブ [digraphs]

サイクルを含む場合と含まない場合があり、接続されている場合と接続されていない場合がある有向グラフを扱います。グラフ内の他のすべての頂点にアクセスできるように、頂点の最小セットを見つけたいと考えています。

たとえば、次のようになります: http://i.stack.imgur.com/wtRYB.png (だから画像を投稿できません:/)

解は (A, E) または (A, F) である可能性があります。

私の最初のアプローチは、親のないノード (indegree = 0) を探すことでしたが、これは前述のサイクルを考慮していません。

クイック検索の後、SO の非環状ダイグラフに関しては比較的ほとんど見つかりませんでした。それで、あなたが私に提案できる最も複雑でないアルゴリズムは何ですか?

私はGirvan - Newmanアルゴリズムを知っています - ここにアルゴリズムがあります:

1. ネットワーク内の既存のすべてのエッジの中間性が最初に計算されます。
2. 中間性が最も高いエッジが削除されます。
3. 削除によって影響を受けるすべてのエッジの中間性が再計算されます。
4. ステップ 2 と 3 は、エッジがなくなるまで繰り返されます。

しかし、このアルゴリズムを使用して、有向グラフ内の k 個のコンポーネントを見つけたいと考えています。ここで、k は指定された整数です。
これどうやってするの？出来ますか？
ありがとう。

NetworkX を手に取り、Shapefiles でそれを使用する方法を学ぼうとしています。

現在、2 つの GPS ポイント間の最短経路を見つけることができるように、NetworkX を使用してグラフで表現したい道路網を含む .shp があります。これを使用してみましたが、問題は、write_shp() 関数を実行すると、DiGraph では同じ 2 つのノード間で複数のエッジが許可されないため、エッジが失われることです。下図の矢印は、DiGraph を使用してエッジを失った例を示しています。

そのため、エッジを失わないように MultiDiGraph を作成する方法があるかどうか、またはその周りに使用できる方法があるかどうか疑問に思っていました。NetworkX の read_shp() を使用せずに、Shapefile から属性を抽出して MultiDiGraph を作成するコードを記述できるのではないかと考えていましたが、グラフを操作した経験がまったくないため、それが正確かどうかはわかりません。可能でしょう。

ヘルプやガイダンスをいただければ幸いです。また、不足しているドキュメントがありましたらお知らせください。前もって感謝します。

ポイントの座標（int、int）をパラメータとして受け取るようにJgraphtの関数を変更しようとしています。(x,y) で定義されたクラスと Point オブジェクトを作成し、それをdirectedGraph のパラメーターとして配置します。

私がやろうとしているのは、次のものを使用できるようにすることです:

Pointコードを実行すると、(int,int)で定義されているパラメーターが の場合でも、「メソッド addVertex は引数 (int,int) には適用できません」というエラーが表示されます。これを機能させるにはどうすればよいですか？

JavaベースのProcessingを使用しています

フラッド フィル アルゴリズムを使用して、マトリックスの 1 と 2 がループを形成しているかどうかを調べます。

例えば：

となります：

(2,7) である特定のポイントでアルゴリズムを初期化すると、アルゴリズムは開始点にリンクされている 1 ごとに 3 に変わります。また、(jgrapht を使用して) digraph を実装したいと思いました。各 1 は頂点であり、隣り合う 2 つの 1 の間に 1 つのエッジが作成されます。したがって、アルゴリズムが 1 を 3 に変えるたびに、両方の 3 が頂点になり、最後のスポットが塗りつぶされたエッジが作成されます。

注: 私は retivision を使用しているため、検出された各マーカーは 1 としてマトリックスに追加されます。現在、10 個のマーカーでテストできないため、マトリックスをプログラムに追加しました。

これを行うコードの一部は次のとおりです。 [編集]: エラーが見つからないため、コード全体を貼り付けました。

しかし、実行すると、「illegalArgumentException: no such vertex in graph [x=2 y=7]」というエラーが発生します。これが出発点です。そこで、次のようにして、この点を頂点として定義しようとしました。

その後：

しかし、それでもうまくいきません。常にこの行で同じエラーが発生します。 directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));しかし、Reactivision がマーカーを検出する場所に応じて、Flood Fill アルゴリズムの異なる場所で発生します (したがって、UP、DOWN、LEFT、または RIGHT セクションのいずれかになります)。アルゴリズムの）。

私は完全に立ち往生しています。print ステートメントを追加したので、draw メソッドが実行されるたびに、グラフの頂点が返され、[2,7] が存在します... わかりません。誰か助けてくれませんか?

digraph で重複を作成しないようにする方法を探しています (jgrapht ライブラリを使用しています)。

使用するように言われたいくつかのトピックを読みました:directedGraph.setCloneable(false); しかし、それは正しくないようです。ライブラリのドキュメントで見つけることができず、この行に存在しないというエラーが表示されます。

以下を使用してグラフを作成しました。

次に、フラッド フィル アルゴリズムに基づいて頂点を追加します (アルゴリズムがすべてのポイントを通過するときに頂点とエッジを追加します。以下はその一部です)。

しかし、頂点のリストを印刷すると、削除するか作成しないようにする必要がある重複があります。それを行う方法はありますか？

編集: Point クラスを作成しました:

次を使用して作成された有向グラフがあります。

頂点とエッジは、マトリックスに実装された Flood Fill アルゴリズムで作成されました。私が使用する行列には、0、1、および 2 しかありません。フラッド フィル アルゴリズムは、1 と 2 で形成されたループがあるかどうかを検出し、1 を通過するときにそれらを 3 に変換します。例：

となります：

アルゴリズムがマトリックスを通過する際に、頂点 (遭遇するそれぞれの 1) とエッジ (2 つの連続する点の間) を作成します。行列の点 (2,7) から始まるアルゴリズムは次のとおりです。

したがって、各 Point オブジェクト/頂点には、次のように使用できる識別子がありません。

そして、各頂点の外向きのエッジの数を出力したいと思います。jgrapht ライブラリでこの関数を見つけました。

そこで、リストを調べるのと同じように頂点セットを調べようとしました (私の Draw メソッドでは、Processing でループし続けます。つまり、プログラムの実行中に Draw メソッドが実行され続けます)。これが私の draw メソッドと、Flood Fill を開始する circuitState() メソッドです (通常、Reactivision を使用して要素をマトリックスに追加します。検出された各マーカーはマトリックスで 1 として表示されますが、それをテストするためにマトリックスを作成しました)。

しかし、このクラスで作成した Point オブジェクトが見つかりません。

これを行うためのより簡単な方法はありますか? そうでない場合、他のメソッドが Point オブジェクトを使用できるようにするために何が欠けていますか? (奇妙なのは、私が Point オブジェクトを他のメソッドとして使用していて、それが正常に動作するのに、Draw メソッドがそれにアクセスできないのはなぜですか?) 私は Java ベースの処理を使用しています。