我在我的应用程序中使用用于Python的NetworkX库来执行一些图形处理。 一个任务是调用NetworkX的all_simple_paths()函数来给我图中的所有非循环路径（最多一个路径的最大长度）。 这很好用。
使用图中所有简单路径的列表，任务现在是从该列表中找出n个路径的数量，其中这n个路径中的每个路径应尽可能与所有其他n个路径不同。 或者换句话说：来自生成的n个路径的任何两个路径应该具有尽可能少的公共节点。 或者换句话说：生成的n个路径中的每个路径应尽可能唯一。
你能想到任何（非强力）算法来实现这一目标吗？
I am using the NetworkX library for Python in my application that does some graph processing. One task is to call the all_simple_paths() function of NetworkX to give me all non-looping paths in the graph (up to a certain max. length of paths). This is working well.
Using this list of all simple paths in the graph the task is now to find a number of n paths out of this list, where each of these n paths should be as different from all other n paths as possible. Or in other words: any two paths from the resulting n paths should have as few common nodes as possible. Or in even other words: each path in the resulting n paths should be as unique as possible.
Can you guys think of any (non brute force) algorithm to achieve this?
最满意答案
这在很大程度上取决于您的特殊需求。 有几个选择。 两个内置，一个需要更多工作，但可能更快。
如果您真正想要的是找到两条非相交路径，那么您可以使用过滤图形 - 在找到一条路径后，引入一个删除了中间节点的子图，并找到该图形中的最短路径。
如果你不能保证路径不会相交，那么你又回到了蛮力。 由于路径不包括循环，并且它们是简单列表，因此查找相交节点的数量就像从两条路径生成集合并查找差异的长度一样简单，这非常快。 检查所有对，找到交叉点最小的对。
以上哪两个更快取决于您的特定图表 - 它是稀疏还是密集？ 有多少个节点？ 等等
由于all_simple_paths是一个生成器，因此您可以实际关注该算法。 也就是说，如果您绘制前两个路径的图形，并且它们完全不相交，那么您已经拥有了最小的情况，并且不再需要查看。 可能有很多路径，但是您可以使用上限的上限或允许的阈值（即不是绝对0，如果这些只有1个共同点，那就足够了，返回它） ），或其他一些组合使用我查看的路径数和当前最大值来约束计算时间。
如果计算时间对你的算法至关重要，也可以考虑切换到igraph ... networkx更容易处理，通常性能“足够好”，但对于像这样的大型强力算法，igraph可能至少是快一个数量级。
最后一种可能性是避免使用all_simple_paths ，而是使用bfs树。 我不确定all_simple_paths是否是BFS，它可能是，但是这可能会让你更好地选择使用第二种算法来查看的初始路径，但不确定。 如果你知道你的源节点有多个后继节点，那么你可以通过强制你的起始两条路径从两个不同的后继节点而不是从初始节点开始来获得不错的结果。 请注意，这也可以咬你 - 这个贪婪的算法也会让你误入歧途，除非你的图形已经很适合它（你可能已经知道，或者可能不是）。
It depends a lot on your particular needs. There are a few options. Two built-in, and one that requires a bit more work, but might be faster.
If what you really want is to find two non-intersecting paths, then you can use a filtered graph - after finding one path, induce a subgraph with the intermediate nodes removed, and find the shortest path in that graph.
If you can't guarantee that the paths won't be non-intersecting, then you are back to brute-force. Since paths don't include cycles, and they are simple lists, finding the number of intersecting nodes is as simple as generating sets from the two paths and finding the length of their difference, which is pretty fast. Check all pairs and find the one with the fewest intersection.
Which of the above two is faster depends on your particular graph - is it sparse or dense? How many nodes are there? etc.
Since all_simple_paths is a generator, you can actually focus that algorithm somewhat. i.e. if you graph the first two paths, and they are completely non-intersecting, then you already have your minimal case and don't need to look at any more. There may be a lot of paths, but you can bound with an upper limit of how many to look at, or a threshold that is allowable (i.e. instead of absolutely 0, if these only have 1 in common, it's good enough, return it), or some other combination that uses both how many paths I've looked at and the current maximum to bound the calculation time.
If calculation time is really critical to your algorithm, also consider switching to igraph... networkx is MUCH easier to deal with, and usually performance is 'good enough', but for large brute force algorithms like this, igraph will probably be at least an order of magnitude faster.
One last possibility is to avoid using all_simple_paths at all, and use the bfs tree instead. I am not sure if all_simple_paths is BFS, it probably is, but that might give you a better selection of initial paths to look at with the second algorithm, not sure. E.G. if you know that your source node has multiple successors, you may get decent results by just forcing your starting two paths to start with two different successors instead of just from the initial node. Note that this can also bite you too - this greedy algorithm can lead you astray as well, unless your graph is already a good fit for it (which you may already know, or may not).
更多推荐
发布评论