问题标签 [topology]

我需要绘制一些简单的网络拓扑图，感谢一些好的工具的建议。

编辑：爱免费软件:-)

莫比乌斯带是具有一侧的表面。

如何在 XAML/WPF 中定义这样一个对象？
如何使用 C# 在 3D 中操作、放大和缩小和旋转这样的对象？

我继承了一个分布在仓库/前台办公室的网络，该网络由大约 50 台台式电脑、各种服务器、网络打印机和路由器/交换机组成。

“智能”路由器位于服务器机房中。随着公司的发展，我们增加了额外的空间，并且不是很优雅地通过天花板等运行各种长度的 CAT5。我一直在天花板上找到各种集线器和开关——它们都没有以任何方式标记或记录.

当然，das blinken-lights 告诉我有人连接到这些设备，我只是无法找出是谁。

我可以运行传统的网络地图工具（有很多这样的东西），它向我展示了网络中基于 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-foo。

我必须以最佳方式解决以下问题。

输入数据为：

• 平面中的 N 个点，以 (x, y) 对整数坐标的形式给出
• M 点在同一平面上，以 (x, y) 对表示圆心的整数坐标给出。所有这些圆圈的边缘都有 (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)

现在，如果我们将 (1) 中的 Rc 代入 (2)，然后在我们进行一些简单计算后将不等式平方，我们得到：

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

对于从输入数据中选择的任何 (x, y)，对于给定的圆 C(Xc, Yc)，(3.1) 和 (3.2) 必须为真。

为简单起见，让我们做一些符号：

• 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) 写为：

• 对于 y > 0 的所有点，Yc < MIN(E(Xc)) (5.1)
• 对于 y < 0 的所有点，Yc > MAX(E(Xc)) (5.2)

我们可以看到 E(Xc) 是关于 Xc 的线性函数，具有 2 个参数 - A(x, y) 和 B(x, y)。这意味着基本上 E(Xc) 在欧几里得空间中表示具有 2 个参数的线族。

现在来了我不明白的部分。他们说，由于上一段中所述的属性，我们可以使用包络算法在 O(1) 分摊时间而不是 O(N) 时间内计算 MIN() 和 MAX()。我不知道信封算法如何工作。

关于如何实现信封算法的任何提示？

提前致谢！

编辑：

问题不在于数学意义上的信封是什么——我已经知道了。问题是如何在比 O(n) 更好的时间内确定包络，显然它可以在摊销 O(1) 中完成。

我有计算包络所需的一系列函数，并且我有一个包含所有可能参数的数组。如何以最佳方式解决最大化问题？

再次感谢！

我有一个三角形网格类，其中包含一个节点列表（在我的例子中是 2d，但这不重要）和一个面列表。每个面都是一个三角形，它只包含节点数组的索引。网格来自 Delaunay 算法，因此非常干净。

对于网格中的每个节点，我需要找到哪些节点通过一条边连接到它。构建和搜索此拓扑数据库的快速方法是什么？

非常感谢，大卫·鲁滕

我有一个 Web 应用程序，它允许用户创建实体，并定义实体之间的关系和关联。我想使用 silverlight 直观地显示实体的拓扑图。希望它能够有一些智能来计算每个实体的初始位置，然后可能允许用户移动他们认为合适的实体。类似于数据库图表在 sql 2000 企业资源管理器中的工作方式。这是在silverlight中完成的吗，也许我可以重复使用，或者用作样本让我继续前进。甚至我可以移植的东西可能会有所帮助。

我们正在尝试开发网络中可用设备的拓扑图。

我有系统的详细信息，例如 IP、设备名称。

我需要做的就是在图表上填充它们并以图形方式显示，问题是我们需要在 JSP 中完成。

有没有另一种方式，比如使用 Flex 显示，我会传递 IP/设备名称并创建环境。顺便说一句，它没有固定多少系统，所以它必须是动态的。

有人可以帮忙吗？

服务，

您是否知道任何框架、APIS、语言或其他非常适合绘制允许用户与地图上的对象交互的拓扑图的资源？我不受语言选择的限制，该程序可以是基于网络的，也可以是独立的。我想我会在自己滚动之前检查一下。

我的目标不是绘制地图，而是更像这张图：http ://www.fineconnection.com/files/images/GraphicalNM.PNG ，或者如果你熟悉 Edward Tufte 的书，他描述的数据可视化机制例如地铁或地铁的地图。

此外，如果您有任何渲染这些类型的用户界面或使用底层数据结构的经验，我会很高兴听到您对这个主题的任何想法、建议、任何“陷阱”。

非常感谢您的时间，

-bn

我需要使用近乎均匀的三角形平铺来填充任意多边形。我该怎么做？您可以提供对现有算法的参考，甚至可以提供您自己的想法或提示。

推测如下：

• 多边形可能是凸的（但如果您想出适用于凹形的算法，则可以加分）
• 多边形具有任意数量的边（3 个或更多）
• 镶嵌的数量（最好是算法添加的顶点数）应该参数化
• 多边形的边可以被算法分割
• 三角形的大小和形状应该几乎一致（即角趋向于 60 度）
• 顶点处的边数最好少而不是多。这可能会从前一点开始（即算法应该产生一个“干净的网格”）。

这不是一个容易解决的问题，我希望“启发式”解决方案可能是最有效的......（对吗？）