問題タブ [directed-graph]

Java Jung2 グラフ ライブラリが、開始ベクトルを指定して Digraph (有向グラフ) をトラバースする組み込み機能を提供するかどうかを知っている人はいますか? BFSDistanceLabeler距離のマップを返すクラスがあることがわかりましたが、それは可能ですが、値を並べ替え (最大距離が最初)、並べ替えられたセットを反復処理する必要があります。

Maven を使用して Javascript の依存関係管理機能を作成しているので、Jung2 を使用して依存関係グラフを維持することを考えていました。

ソースsから宛先fまでの有向非巡回グラフで最長のパスを見つける必要があります。正の重みサイクルが存在しない場合でも、正の重みサイクルが存在しないと仮定します。0または負の重みのサイクルは存在します。この場合、誰かが最長のパスを見つけるためのアルゴリズムを提案できますか？可能であれば出典を引用してください。

ありがとう

I'm considering graph data structure implementations and am looking at the "incidence list" representation. There is a brief description of it here:

Incidence list

So each vertex in the graph stores a list of those edges upon which it is incident.

Given that my graph is a directed graph, I'm not very clear from this description on a couple of points:

1. Does the graph itself also store a list of all edges?
2. Do vertices only store outgoing edges, or incoming and outgoing?
3. If both, are they in separate lists?

I'm quite familiar with the other graph representations (adjacency list, adjacency matrix, edge list, incidence matrix), so this isn't a question about graph implementations in general, just this particular one.

Any pointers would be much appreciated.

Visual Studio 2010 には、有向グラフ ドキュメント (拡張子が dgml のファイル) と呼ばれるこの機能があります。UML と同様に、オブジェクト間の関係を示すために使用できます。VS2010 ベータ版で遊ぶことができました。私が現在持っているバージョン (VS2010 pro) にはこの機能がなく、Ultimate または Architect バージョンにアクセスできません。

推奨できる同様の XML ベースの有向グラフ技術はありますか?

プロジェクトでグラフ表現を行うために を使用しようとしnetworkxていますが、単純にする必要があるいくつかのことを行う方法がわかりません。このグラフにはルート要素が 1 つしかないように、多数のノードとエッジを持つ有向グラフを作成しました。ここで、私がやりたいことは、ルートから始めて、各要素の子を繰り返し処理し、それらからいくつかの情報を抽出することです。この DiGraph のルート要素を取得するにはどうすればよいですか?

したがって、次のようになります。

ドキュメントには、DiGraph のルートを取得する簡単な方法を示唆するものは何もありませんでした。これを手動で推測する必要がありますか? :Oiter(myDiGraph)ルートから反復することを期待して取得しようとしましたが、順序はランダムなようです... :\

助けていただければ幸いです、ありがとう！

更新:以下のアドバイスに従い、アプリに Memcached 層を実装することにしました。今、私は別の考えを持っています。Memcached をチェックし、Memcached の有効期限が切れたときに更新するポーリング (5 分または 10 分ごとなど) で AJAX 要求を実行することは可能ですか? この方法では、バックグラウンドでサイレントに実行されるため、エンド ユーザーが遅延を経験することはありません。

Directed Edge の REST API を使用して、Web アプリでレコメンデーションを行っています。私が直面している問題は、サイト全体の複数の場所でかなりの数の推奨事項をクエリすることです。待ち時間が非常に長く、クエリごとにページが 2 ～ 5 秒程度読み込まれます。ひどいですね。

Directed Edge の PHP バインディングは使用していません。代わりに、自分で作成した PHP バインディングをいくつか使用しています。バインディングは GitHub で確認できます。cURL を使用して API に接続しています。

受信したデータをキャッシュするにはどうすればよいですか? 実装がかなり簡単で、かなり柔軟である限り、メソッドの数に制限はありません。

レコメンデーションを取得するためのクライアント コードの例を次に示します。

有向グラフのメソッドDFSメソッドを書き込もうとしています。現在、セグメンテーション違反が発生していますが、それがどこにあるのかよくわかりません。有向グラフについて私が理解していることから、私の論理は正しいと信じています...しかし、新鮮な目が非常に役立つでしょう。

これが私の関数です：

クラス定義：

ありがとう！

私はアルゼンチン出身ですが、データ構造のクラスを受講したことのある人なら誰でも、グラフが何であるかを知っていると思います。そうすれば、どのような実装が「一般的」または「標準的」であるかを知っているかもしれません。これは、リストまたは配列を介して実装できます。ウィキペディアでさえこれを言っています。マーク・アレン・ワイス、ブルーノ・プライス、ルイス・ジョヤネス・アギラールも同様です。

事はです。これが良い方法ではないと誰も考えたことがありませんか？最も推奨される方法は、リストを使用することです。しかし、頂点の間にエッジが1つしかないことを考えると、リストがこれを行うための優れたインターフェイスであるとは思いません。つまり、VertexV1がVertexV2に接続されている場合、エッジは1つだけです。

リストではなくセットになると思いませんか？

いくつかの意見を知りたいだけですが、どう思いますか？

ありがとう！！

編集： また、グラフに繰り返し要素を含めることができないと思われる場合は、挿入時の頂点のルックアップを最小限に抑えるためにHashSetが適しています。

次のルールに一致する単語の可能な限り長いシーケンスを見つけたいと思います。

• 各単語は最大1回使用できます
• すべての単語は文字列です
• 2つの文字列saであり、の最後の2文字がの最初の2文字と一致するsb場合は連結できます。sasb

連結の場合は、それらの文字を重ねて実行します。例えば：

• sa="トリノ"
• sb = "novara"
• sa concat sb = "torinovara"

たとえば、次の入力ファイル「input.txt」があります。

novara

トリノ

ベルチェリ

ラヴェンナ

ナポリ

リバノ

メッセニア

ノビリグレ

ローマ

また、上記のルールに従った上記のファイルの出力は次のようになります。

トリノ

novara

ラヴェンナ

ナポリ

リボルノ

ノビリグレ

可能な最長の連結は次のとおりです。

誰かがこれで私を助けてくれますか？これに最適なデータ構造は何でしょうか？

組み合わせデジタル回路を分析したい。ASCIIファイルには、次の形式に従って回路の説明が含まれています。

ここで、： <name>は、論理ゲートの名前を持つ20文字以下の文字列です。 <logic gate>論理ゲートのタイプを識別する20文字以下の文字列です。INPUT、、、、、にすることOUTPUTができます。 は、INPUTの場合は0、NOTまたはOUTPUTの場合は1、ANDの場合は2、ORの場合は2に等しい整数です。 OUTPUTの場合は0に等しい整数、それ以外の場合は0よりも大きい整数です。 、>は、それぞれ20文字以下の文字列であり、論理ゲートの入出力ネットの名前を識別します。 論理ゲートがその機能を計算するのにかかる時間を識別する整数です。ANDORNOT<inputs><outputs><input 1><last input>, <output<delay>

プログラムは、回路の説明を含むファイルを読み取った後、回路のクリティカルパスを計算する必要があります。これは、タイプINPUTのゲートとタイプOUTPUTのゲートを接続するパスとして定義できます。パス内は、回路内のすべての可能なパスの中で最も高くなっています。

例

どうすればこれを実行できますか？