directed-graph

29熱

3答えて

ここでは、Tarjanのサイクル検出を実装しています。アルゴリズムは、ここで発見された： http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm public class TarjanCycleDetect { private static List<List<Verte

1熱

1答えて

複数のルート頂点を持つグラフの最小スパニングツリー

これらのルート頂点のすべての間のルート頂点のセットを与えられた有向グラフで最小スパニングツリー（最適分岐）を計算するアルゴリズムがあるかどうかを知りたいと思います。グラフ内の1つのルート頂点と他のすべての頂点だけではありません。ルート頂点[1,4,6]及び次画像上のようなグラフGのセットが与えられると： ... algorighmは緑サブようなものを返すべき同じ絵の上に - グラフ。アルゴリズ

0熱

1答えて

完全に接続された有向グラフ内の可能なすべての非周期単純パスの数はいくらですか？

完全に接続された有向グラフGがNの頂点とMのエッジを持っているとします。グラフにはどのくらいの辺がありますか？それはM = N^2ですか？頂点を1つ取って隣人を「深さ優先検索」の方法で巡回してループを回避すると、いくつの非周期的な単純なパスが得られますか？私たちは4つの頂点のグラフに頂点1から始める場合例えば、ここでのパスは以下のとおりです。 - 1 - 1,2 - 1,3 - 1,4

2熱

1答えて

Erlangの有向グラフの中には何がありますか？

免責事項：著者はErlangの初心者です。私はErlangにある種の最短パスアルゴリズムを実装したいと思います。 Erlangでグラフデータ構造の標準実装があります：http://www.erlang.org/doc/man/digraph.html しかし、私はそれが使用する実際のデータ構造上の任意の情報を見つけていません。ほとんど私が知りたいのですが：頂点アクションのためにすべての「ネイ

2熱

3答えて

有向グラフでの効率的な検索

私は数百万の頂点とエッジを持つ有向グラフを持っています。頂点の集合が与えられ、それらが「START_POINTS」と呼ばれると仮定しよう。「END_POINTS」と呼ばれるもう1組の頂点も与えられる。問題は、どのSTART_POINTSからどのEND_POINTSに到達できるかを見つけることです。ここでは一例です： START_POINTS: S1 S2 S3 S4 S5 S6 S7 ...

0熱

1答えて

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

有向グラフが与えられ、各ベクトルが負ではないコストを持ち、各頂点が非負の利益を持つ場合、どのようにスパニングサブツリーを見つけるか最大の利益を持つグラフ？私は、予算が所与の予算に比べて小さいことを拘束したい。私は、多項式時間の複雑さと理論的近似係数で問題の近似アルゴリズムを探しています。

1熱

1答えて

有向グラフによる有向パスの類似性を比較するアルゴリズム

私はそこに2つの有向パスを持つ有向グラフを持っています。 2つのパス間の類似性を判断するアルゴリズムが必要です。 This postは、近似類似性を決定するためにLevenshtein distanceを使用して言及しています。私はまた、Hamming distanceが同様の指標を使用していることを認識しています。私の質問は：どのように2つのパスが互いに平行を実行ケースを処理します。つまり、

7熱

1答えて

このデータ構造には形式がありますか？

私は、関係する定理とアルゴリズムを追跡できるように、私が作業しているデータ構造の数学的形式を求めています。では、次があるとします。話題の有向非巡回グラフ。各トピックには、トピック、ドキュメントセット内のアイテム、および一連のグループ内のアイテム間に1つ以上の関係があります。グループは単純なセットでも、DAGとして終わることもあります。これらは、ドキュメントとトピックの関連付けの可視性を管理

2熱

5答えて

NetworkXの指示グラフの後継の検索

NetworkXの有向グラフのコードで作業していて、疑わしいプログラミング経験の結果である可能性が高いブロックにヒットしました。私がしようとしていることは、次のとおりです。私は有向グラフGを持ち、他のすべてのノードが流れる2つの「親ノード」が先頭にあります。このネットワークをグラフ化するとき、「親1」の子孫であるすべてのノードを1色、他のすべてのノードを別の色でグラフ化したいと思います。つまり、

1熱

2答えて

グラフ内のすべての「長い」単純な非循環パスを見つけるにはどうすればよいですか？

完全に接続された有向グラフGがあるとします。頂点は[a,b,c]です。各頂点の間には両方向にエッジがあります。出発点がaの場合、私はすべての方向でグラフをたどり、既にパスにある頂点に当たったときにのみそのパスを保存したいと思います。ので、機能full_paths(a,G)は返す必要があります： - [{a,b}, {b,c}, {c,d}] - [{a,b}, {b,d}, {d,c}]