問題タブ [directed-graph]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
1 に答える
1505 参照

javascript - Javascript Infovis Toolit でノードの形状を変更する/有向グラフを強制する

Javascript Infovis ツールキット (JIT) を使用しており、ノードの形状を画像に変更したい..どうすればよいですか? デフォルトの形状は円で、さらに長方形、正方形、楕円形などに変更できますが、私の場合は、ローカル ディスク ドライブにあるイメージに変更する必要があります。

彼らは「タイプ」フィールドでそうすることが可能だと言っていますが、追加する必要がある、または影響を確認するために必要なすべてのメソッドは何ですか...?? 以下のリンクを参照してください。

http://thejit.org/static/v20/Docs/files/Options/Options-Node-js.html

そして、どのように正確にそれを行うことができますか?

助けてください...

0 投票する
0 に答える
168 参照

algorithm - Digraph 最小サブグラフ アルゴリズム

どのアルゴリズムが有向サブグラフ (同じ頂点と最小量のエッジで構成される) を見つけることができ、すべてのパスが残りますか?

G(V,E) --> E で V=V & E' である最小の G'(V,E') を見つけ、すべてのパスが残ります。

ありがとう。

0 投票する
1 に答える
1381 参照

multithreading - 有向グラフでのデータ処理のスレッドモデル

有向グラフを介してさまざまな種類のデータを処理する単純なデータ分析ツールを設計します。有向グラフは、ユーザーがある程度カスタマイズできます。各ノードは、通過するデータに対するロギング、分析、および数学演算で構成されます。グラフは、各ノードで追加の処理を行うことを除いて、多くの点でニューラルネットワークに似ています。一部のノードは通過するデータ要素に対して単純な操作を行いますが、他のノードは複雑なアルゴリズムを備えています。

グラフから結果を最速かつ最も効率的な方法で取得できるように、この有向グラフで処理をマルチスレッド化するにはどうすればよいですか?ここではメモリは問題ではなく、このタスクの初期化にかかる時間も問題ではありません。

作業をマルチスレッド化するためのいくつかの異なる方法を考えました。

  • 各スレッドインスタンスは、このグラフの開始ノードに入る各データ要素を「追跡」します。スレッドは、各ノードを通過するときにこのデータ要素にとどまり、ツリーの最後まで各ノードの処理メソッドを呼び出します。これには、基本的に、システムに入るデータ要素ごとに1つのスレッドが必要になります。もちろん、データ要素がシステム全体に渡されると、スレッドはリサイクルされます。ここでの問題は、ノードに2つの出力エッジが存在する場合です。つまり、スレッドは両方に従う必要があります(これは、スレッドプールから新しいスレッドをプルすることを意味しますか?)。

  • ノードごとにスレッドを作成し、各グラフの端にデータバッファーを作成します。ノード上のワーカースレッドは、1つのスレッドがデータを処理するのに時間がかかる場合に、データを保持するために継続的にチェックします。このアプローチの問題は、バッファの処理を開始するのに十分なデータを持つためのバッファの固有の「ポーリング」です。おそらく、グラフ構成のデータフローを単純化するために支払うわずかな代償です。

誰かがより良い方法を考えることができますか、またはあなたはどれをお勧めしますか?システム全体の待ち時間を最小限に抑え、受信データのストリームを常に処理する機能を探しています。

ありがとう!ブレット

0 投票する
2 に答える
3876 参照

graphviz - graphvizの重複するエッジ

2つのエッジが重なっていますが、理由がわかりません。

ここに画像の説明を入力してください

両方のエッジn1 -> n2n2 -> n1別々に表示する方法はありますか?クラスターを削除することはオプションではありませんが、役立つでしょう...

0 投票する
4 に答える
1173 参照

algorithm - 指定されたノードからすべての入力エッジに到達できないノードを見つける有向グラフ

最近のインタビューで、以下の質問をされました。

ノードとエッジのセットが与えられ、開始ノードが最終終了ノードを指します。下の図では、1 で開始し、15 で終了します。彼らの質問には、ノード 2 (または任意のノード) が開始点として与えられ、入力エッジがすべてノード 2 から到達可能ではないパス内の次のノードをどのように見つけることができますか (つまり、どうすれば 14 に到達できますか)。

どうすればこれを行うことができますか、疑似コードは問題ないはずです。

ここに画像の説明を入力

0 投票する
1 に答える
231 参照

algorithm - 有向グラフの制約付き最大スパニング サブツリーの近似アルゴリズム

各ベクトルに負でないコストがあり、各頂点に負でない利益がある有向グラフが与えられた場合、利益が最大になるグラフのスパニング サブツリーをどのように見つけますか? コストを特定の予算に抑える必要があります。多項式時間の複雑さと理論上の近似係数の問題の近似アルゴリズムを探しています。

0 投票する
1 に答える
341 参照

data-structures - このデータ構造には形式がありますか?

関連する定理とアルゴリズムを追跡できるように、使用しているデータ構造の数学的形式を探しています。

次のものがあるとします。

  • トピックの有向非巡回グラフ。
  • 各トピックでは、トピック、一連のドキュメント内のアイテム、および一連のグループ内のアイテムの間に 1 つ以上の関係があります。
  • グループは単純なセットの場合もあれば、最終的に DAG になる場合もあります。ドキュメントとトピックの関連付けの可視性を管理するために使用されます。

関連性はあるが一般的すぎるハイパーグラフに出くわしたのはつい最近のことです。このデータ構造には形式がありますか? そうでない場合、数学用語でより簡潔に説明できますか?

0 投票する
1 に答える
377 参照

algorithm - D*Liteでのパス方向の定義

私は現在、SvenKoenigのD*Liteアルゴリズムの実装に取り​​組んでいます。 http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf。基本的に、実装を開始する前に、すべての詳細を理解しようとしています。アルゴリズムは有向グラフで機能するようです。これがPredSucc関数を定義する方法です。

グラフの方向を定義するにはどうすればよいですか。また、どのパラメーターがグラフの方向を決定しますか。gコスト(アルゴリズムが更新gする値と一緒にコストがあるrhsため)や距離のヒューリスティック推定などのパラメータの値を使用する必要がありますか?

0 投票する
2 に答える
1452 参照

algorithm - sharir kosaraju アルゴリズムと頂点

有向グラフで sharir kosaraju アルゴリズムを実行するとします。このグラフにはアーク (u,v) があります。このアルゴリズムには、2 つの DFS パスがあります。ここで、頂点 u を最初の深さツリー T に挿入するとします。v はどこに現れるでしょうか? 以前または後で作成された別のツリーにありますか? 前もって感謝します !

私はテストのために学んでいます...これは一種の宿題だと思いますが、私は本当に手がかりがありません!

0 投票する
1 に答える
1120 参照

python - 有向グラフ ノード: 後続ノードと先行ノードを追跡する

Node特に後継者と先行者のセットを持つ有向グラフのノードを表すクラスを実装しようとしています。セットのように動作したいNode.predecessorsNode.predecessors思います。特に、それらの要素を反復処理し、要素を追加および削除し、包含をチェックし、反復可能オブジェクトからそれらを設定したいと考えています。ただし、node_1.sucessors.add(node_2)それが True である必要がありますnode_1 in node_2.pedecessors

この魔法を実装する の新しいサブクラスを書くことは可能だと思われますsetが、私が見る限り、そのようなクラスの実装は非常に面倒ですNode。後継者であり、追加などのためにいくつかの特別なメソッドが必要になるため、それnode_1.sucessors.add(node_2)は呼び出さnode_2.predecessors.add(node_1)れず、無限ループにつながります。

その場で 2 つのアトリビュートの 1 つを生成する(node for node in all_nodes if self in node.sucessors)ことは可能ですが、グラフに属するすべてのノードを追跡する必要がありweakref.WeakSetます__init__。すべてのノードの大きなセットは、複数のばらばらなグラフがある場合に計算量が大きくなり、先行ノードのセットを変更する方法がわかりません。

誰かがこれに対する良い解決策を持っていますか?