問題タブ [topology]

いくつかの簡単なネットワークトポロジチャートを描く必要があります。いくつかの優れたツールの提案を歓迎します。

編集：フリーウェアが大好き:-)

メビウスの帯は片面を持つ面です。

XAML/WPF でそのようなオブジェクトをどのように定義しますか?
C# を使用して、このようなオブジェクトを 3D で操作したり、拡大縮小したり、回転したりするにはどうすればよいでしょうか?

約50台のデスクトップPC、さまざまなサーバー、ネットワークプリンター、ルーター/スイッチで構成される倉庫/フロントオフィスに広がるネットワークを継承しました。

「インテリジェント」ルーターはサーバールームにあります。会社が成長するにつれて、私たちは追加のスペースを追加し、天井などにさまざまな長さのCAT5をエレガントに走らせることはできませんでした。天井にさまざまなハブやスイッチを見つけました。 。

もちろん、das点滅-ライトは誰かがこれらのデバイスに接続していることを教えてくれます。私には誰を見つける方法がありません。

従来のネットワークマップツール（これらのものはたくさんあります）を実行でき、ネットワーク内のIPベースのものが表示されます。それはいいことですが、私がすでに持っている情報です。私が知る必要があるのは、ネットワークトポロジ、つまりスイッチ（ブリッジ）がどのように相互接続されているかなどです。また、市販のlinksysアンマネージドタイプであるため、SNMPに応答しないため、使用できません。 ..。。

SNMPに応答しないネットワーク内のハブやスイッチなどを分析および検出するために使用できる、最も優れた/最も安価なツールは何ですか？

知っているツールがない場合、これを見つけるためにどのような一般化されたアルゴリズムを提案しますか？私の推測では、デバイス（スイッチ、デスクトップなど）のMAC転送テーブルを調べて、そのようにチェーンを構築できますが、管理されていないスイッチからそれを取得できるかどうかはわかりません（ましてやハブ）。

（この特許にはいくつかの優れたアイデアがありますが、それを使用して構築されたソフトウェアは見つかりません：http: //www.freepatentsonline.com/6628623.html）

ありがとう！！

データ：依存関係リスト。非周期的であることがすでに確認されています。したがって、ここでは、「a」は「b」、「c」（cはdに依存）などに依存します。

たとえば、「a」で始まるチェーンを見つけるためのトップダウンの再帰的なソリューションが必要です：a、c、d、e、g、f、b

したがって、現在（非ジェネレータソリューション）：

明らかに、これはかなり弱いです:)私はそこで利回りを得る方法について頭を悩ませてきました、そして私はすべてのpy-fooy'allがこれにもたらすことができることを感謝します。

次の問題を最適な方法で解決する必要があります。

入力データは次のとおりです。

• 整数座標の (x, y) ペアとして与えられる平面上の N 点
• 円の中心を表す整数座標の (x, y) ペアとして与えられる同じ平面上の M 点。このすべての円の端には (0, 0) があります。

選択した円または選択した円の端に最初の N 点からの点がない「良い」円よりもプロパティを持ついくつかの円を分離する方法を見つける必要があります。

点と円の数は 100,000 のオーダーです。すべての点ですべての円をチェックする明白な解決策は、複雑さ O(N * M) を持ち、100,000 の円と 100,000 の点で、64 ビット SSE3 単精度コードを使用する Core 2 Duo で約 15 秒かかります。私が競合する参照実装は、同じデータで約 0.1 秒しかかかりません。リファレンス実装が O(Nlog N + Mlog M) であることは知っています。

次の方法でアルゴリズムを最適化することを考えました。ポイント データの 2 つのコピーを作成し、それぞれ x 座標、y 座標に関してコピーを並べ替えます。次に、[(xc - r, yc - r); で定義される正方形内にある点のみを使用します。(xc + r, yc + r)]、ここで (xc, yc) は半径 r の「現在の」円の中心です。ソートされたデータを扱うようになったので、バイナリ検索を使用してその間隔内のポイントを見つけることができます。このアプローチの複雑さは O(Nlog N + Mlog^2 N) である必要があり、実際には参照よりも高速ですが、それでもかなり低速です。

リファレンス実装がどのように機能するかはある程度知っていますが、理解できない手順がいくつかあります。私がこれまでに知っていることを説明しようとします：

座標 (Xc, Yc) の円の半径は次のとおりです。

• Rc = sqrt(Xc * Xc + Yc * Yc) (1)

これは、(0, 0) が円の端にあるためです。

点 P(x, y) が円の外側にあるためには、次の不等式が真でなければなりません。

• sqrt((Xc - x)^2 + (Yc - y)^2) > Rc (2)

ここで、Rc を (1) から (2) に代入すると、いくつかの簡単な計算を行った後に不等式を 2 乗すると、次のようになります。

• Yc < 1/2y * (x^2 + y^2) - Xc * x/y (3.1) for y > 0
• Yc > 1/2y * (x^2 + y^2) - Xc * x/y (3.2) for y < 0

(3.1) と (3.2) は、入力データから選択された任意の (x, y) の任意の円 C(Xc, Yc) に対して真でなければなりません。

簡単にするために、いくつかの表記を作成しましょう。

• A(x, y) = 1/2y * (x^2 + y^2) (4.1)
• B(x, y) = -x/y (4.2)
• E(Xc) = 1/2y * (x^2 + y^2) - Xc * x/y = A(x, y) + Xc * B(x, y) (4.3)

与えられた円 C(Xc, Yc) に対して、(3) を次のように書けることがわかります。

• Yc < MIN(E(Xc)) (5.1) y > 0 のすべてのポイント
• Yc > MAX(E(Xc)) (5.2) y < 0 のすべてのポイント

E(Xc) は、A(x, y) と B(x, y) の 2 つのパラメーターを持つ Xc に関する線形関数であることがわかります。つまり、基本的に E(Xc) は、ユークリッド空間で 2 つのパラメーターを持つ直線のファミリーを表します。

ここで、私が理解できない部分が来ます。彼らは、上記の段落で述べた特性により、エンベロープアルゴリズムを使用して O(N) 時間ではなく O(1) 償却時間で MIN() と MAX() を計算できると言っています。Envelope アルゴリズムがどのように機能するかはわかりません。

Envelope アルゴリズムの実装方法に関するヒントはありますか?

前もって感謝します！

編集：

問題は、数学的な意味でのエンベロープが何であるかではありません - 私はすでにそれを知っています. 問題は、O(n) よりも適切な時間でエンベロープを決定する方法です。明らかに、償却された O(1) で実行できます。

エンベロープを計算するために必要な一連の関数があり、可能なすべてのパラメーターの配列があります。最大化問題を最適な方法で解くにはどうすればよいですか?

再度、感謝します！

ノードのリスト（私の場合は2dですが、それは問題ではありません）と面のリストを含む三角メッシュクラスがあります。各面は三角形で、ノード配列へのインデックスのみが含まれています。メッシュは Delaunay アルゴリズムから生成されるため、非常にクリーンです。

メッシュ内のすべてのノードについて、単一のエッジで接続されているノードを見つける必要があります。このトポロジ データベースを構築して検索するための高速な方法は何ですか?

大変お世話になりました、デビッド・ルッテン

ユーザーがエンティティを作成し、エンティティ間の関係と関連付けを定義できる Web アプリケーションがあります。Silverlight を使用して、エンティティのトポロジ図を視覚的に表示したいと考えています。うまくいけば、各エンティティの初期位置を把握し、ユーザーが適切と思われる方法でエンティティを移動できるようになる可能性があります。データベース ダイアグラムが SQL 2000 エンタープライズ エクスプローラーでどのように機能するかに似ています。これは Silverlight で行われたのでしょうか。再利用したり、サンプルとして使用したりして、作業を進めることができます。または、移植できるものでさえ役立つかもしれません。

ネットワークで使用可能なデバイスのトポロジ マップを作成しようとしています。

IP、デバイス名など、システムの詳細があります。

私がする必要があるのは、それらをグラフに取り込んでグラフィカルに表示することだけです。問題は、JSP でそれを行う必要があることです。

Flex を使用して表示するなど、IP/デバイス名を渡して環境を作成する別の方法はありますか。ところで、システムの数が固定されていないため、動的にする必要があります。

誰か助けてくれませんか？

サーバス、

ユーザーがマップ上のオブジェクトを操作できるようにするトポロジ マップの描画に適したフレームワーク、APIS、言語、またはその他のリソースを知っていますか? 言語の選択に制約されることはなく、プログラムは Web ベースでもスタンドアロンでもかまいません。自分で巻く前に確認しようと思いました。

私の目標は、地図を描くことではなく、次の図のようなものです。地下鉄や地下鉄の地図など。

また、これらのタイプのユーザー インターフェイスをレンダリングしたり、基礎となるデータ構造を使用したりした経験がある場合は、この件についての考え、アドバイス、「落とし穴」を聞いていただければ幸いです。

お時間をいただき、誠にありがとうございました。

-億

三角形のほぼ均一なタイリングを使用して、任意のポリゴンを塗りつぶす必要があります。どうすればいいですか？既存のアルゴリズムへの参照を提供することも、単に独自のアイデアやヒントを提供することもできます。

次のことが推測されます。

• 多角形は凸面である可能性があります (ただし、凹面形状で機能するアルゴリズムを思いついた場合はボーナス ポイント)
• 多角形に任意の数のエッジ (3 つ以上) がある
• テッセレーションの量 (できれば、アルゴリズムによって追加される頂点の数) をパラメーター化する必要があります。
• ポリゴンのエッジはアルゴリズムによって分割される場合があります
• 三角形はサイズと形状がほぼ均一である必要があります (つまり、角は 60 度に近づく傾向があります)。
• 頂点のエッジの数は、多くするよりも少なくする必要があります。これは、前のポイントから続く可能性があります (つまり、アルゴリズムは「クリーン メッシュ」を生成する必要があります)。

これは簡単に解決できる問題ではなく、「ヒューリスティック」な解決策が最も効率的であると期待しています... (そうですか?)