問題タブ [graph-traversal]

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 に答える
596 参照

scala - GraphX は内部でどのようにグラフをトラバースしますか?

GraphX による Graph の内部トラバーサルを知りたいです。頂点とエッジに基づくトラバーサルですか、それとも RDDS のシーケンシャル トラバーサルですか? たとえば、グラフの頂点が与えられた場合、その近傍のみを取得したいのですが、すべての頂点の近傍ではありませんか? この場合、GraphX がグラフをトラバースする方法。

ありがとうございます。

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

sql - クエリのために複数のテーブルをトラバースするためのアルゴリズム

複数のテーブルを介してクエリのデータをフェッチするための最適なパスを見つけるのに役立つアルゴリズムを作成しようとしています。テーブルには、それらを相互に関連付ける重複する変数があります。たとえば、次のようなクエリがあるとします。

'T3:F6 > 0 となるように T1:F1 を選択'

テーブルは次のように設定されています。

表 1 (T1): F1、F2

表 2 (T2): F2、F3、F4

表 3 (T3): F4、F5、F6

ここで、F1 から F6 のエントリに割り当てられた値があります。したがって、表 1 には F1 があり、F2 はその兄弟です。F2 も表 2 にあり、F4 もその兄弟です。F4 も表 3 にあり、F6 はその兄弟です。

テーブルをトラバースする正しい方法は次のとおりです: T1:F1 -> T1:F2 -> T2:F2 -> T2:F4 -> T3:F4 -> T3:F6

これを行うためのアルゴリズムはありますか?各テーブルの兄弟を単純に検索するのは難しすぎるようです。ある種のツリー検索アルゴリズムのようですが、ツリーの設定方法がわかりません。

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

tree - ツリー エッジとフォワード エッジの違い

この質問に出くわしたとき、私は本を読んでいました: DFS が実行されているときに、グラフ内の特定の頂点の検出時間と終了時間から、前方エッジとツリー エッジの違いをどのように見分けることができますか?

私がこれまでに試みたことは次のとおりです。 Fwd との主な違い。Tree Edges は、A と B の間にツリー エッジが存在する場合、A は経路長 1 の B の直接の隣人ですが、Fwd の場合です。エッジの場合、パスの長さは 1 程度よりも大きくする必要があります。そのため、配列に格納できる検出時刻と終了時刻を分析すると、それらの終了時刻と開始時刻が 1 異なるかどうかを確認できます。そうである場合、それはツリー エッジであり、そうでない場合は前方エッジです。

しかし、私はアルゴリズムを開発することができず、このアプローチがバグのあるものであることも疑っています. 私を助けてください。ありがとうございました。

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

java - Titan グラフの使用例における GremlinPipeLine Java API チェーン トラバーサル

特定の頂点から始まる頂点のチェーンをトラバースする必要があるユースケースがあります。前の頂点に接続されている頂点が 1 つだけある (列車のような) 線形チェーンです。移動中に、チェーンの最後に到達するまで、いくつかの基準に基づいて特定の頂点を放出する必要があります。

2 番目のユース ケースは上記のユース ケースの拡張ですが、1 つの頂点から始まる 1 つのチェーンの代わりに、1 つの頂点から始まる複数のチェーンがあります。各チェーンをトラバースし、頂点の特定のプロパティ値を確認する必要があります。そのプロパティの一致が見つかったら、その頂点を放出し、2 番目のチェーンから開始する必要があります。

Gremlin Java API を使用してそれを達成する必要があります。これは単純なもののように見えますが、私はgremlinに不慣れで、gremlin Java APIでもインターネットからの助けはあまりありません.

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

java - 点と線分に沿って可能なすべてのパスを決定する

そこでObjects、Java プログラムで 2 つのPointオブジェクト (x 用と y 用の 2 つの double クラス変数を含む 2 次元空間内)LineSegmentと、2 つのエンドポイントをクラス変数として持つクラスを作成しました。

また、Path後でポイントの配列をクラス変数として使用してクラスを作成し、ポイントの順序がパスを決定し、最初のポイントが開始ポイントであり、後続の各ポイントが順番に訪問され、ポイント間を直線で移動すると仮定します方向。

ポイントのセットが与えられた場合、指定された開始点と終了点、およびこれらのパスのいずれも何らかの理由でどのポイントにも再訪できないというルールを使用して、考えられるすべてのパスを決定するにはどうすればよいでしょうか?

ありがとう!

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

arangodb - 特定のノードを介した ArangoDB GRAPH TRAVERSAL

米国の都市を例にとると、NYC、シカゴ、シアトルを通るすべての都市と道路を横断したいとします。

これは、TRAVERSAL AQL 関数 (filterVertices を使用) で実行できます。ただし、この関数は ID のみを取得し、GRAPH_TRAVERSAL のように頂点の例は取得しません。

GRAPH_TRAVERSAL にはフィルター オプションがないため、グラフ操作を使用して結果をフィルター処理する方法はありますか?

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

arangodb - AQL トラバーサルから頂点とエッジの単一ドキュメントを返す

Arango でトラバーサルを行うと、次のような json 構造の配列が得られます。

AQL を使用して、トラバーサルで見つかったすべてのエッジ/頂点を上記のような単一の構造に取得する方法はありますか?

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

graph - コードは、グラフ内の 2 つの基本的な回路を決定できますか

私は基本回路、基本カットセット関連の定理を研究していましたが、頭の中で質問に出くわしました。

0 投票する
3 に答える
2883 参照

algorithm - 組み合わせ回路の電圧を計算するには、どのアルゴリズムを使用しますか?

非常に大規模な回路の電圧変化をプログラムで計算しようとしています。

*この質問は電子機器に向けられているように見えるかもしれませんが、一連のデータにアルゴリズムを適用することに関するものです。

簡単にするため
に、電圧がすでに計算された完全な回路を次に示します。

ここに画像の説明を入力

私はもともとバッテリー電圧と抵抗のみを与えられています:

ここに画像の説明を入力

私が抱えている問題は、並列回路と直列回路の間で電圧の計算が異なることです。
SOで尋ねられたやや似た質問。

いくつかの数式:

When resistors are in parallel:
Rtotal = 1/(1/R1 + 1/R2 + 1/R3 ... + 1/Rn)

When resistors are in series:
Rtotal = R1 + R2 + R3 ... + Rn

オームの法則:

V = IR
I = V/R
R = V/I

V is voltage (volts)
I is current (amps)
R is resistance(ohms)

私がインターネットで見つけたすべてのチュートリアルは、並列回路を概念的にグループ化して総抵抗を取得し、その抵抗を使用して直列抵抗を計算する人々で構成されています。

ここに画像の説明を入力

これは小さな例では問題ありませんが、大規模な回路のアルゴリズムを導き出すのは困難です。

私の質問:
すべての完全なパスのマトリックスが与えられた場合、
すべての電圧降下を計算する方法はありますか?

私は現在、システムをグラフデータ構造として持っています。
すべてのノードは ID 番号で表されます (また、ID 番号で検索できます)。

上記の例では、トラバーサルを実行すると、次のようなパスのリストが返されます。

各番号は、実際のノードとそれに対応するデータを導出するために使用できます。このデータセットに対してどのような変換/アルゴリズムを実行する必要がありますか?


回路の一部が複合化される可能性が非常に高く、それらの複合化セクションは、他の複合化セクションと並列または直列になる可能性があります。

私の問題はこれに似ていると思います:
http://en.wikipedia.org/wiki/Series-parallel_partial_order