问题描述
给定一个有向的连接图，找到从源到目的地的所有路径。
寻找代码审查，优化和最佳做法。还需要帮助找出复杂性，我最好的尝试是 O(E！)，其中 E 是边数。
class GraphFindAllPaths<T> implements Iterable<T> {
/* A map from nodes in the graph to sets of outgoing edges. Each
* set of edges is represented by a map from edges to doubles.
*/
private final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();
/**
* Adds a new node to the graph. If the node already exists then its a
* no-op.
*
* @param node Adds to a graph. If node is null then this is a no-op.
* @return true if node is added, false otherwise.
*/
public boolean addNode(T node) {
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;
graph.put(node, new HashMap<T, Double>());
return true;
}
/**
* Given the source and destination node it would add an arc from source
* to destination node. If an arc already exists then the value would be
* updated the new value.
*
* @param source the source node.
* @param destination the destination node.
* @param length if length if
* @throws NullPointerException if source or destination is null.
* @throws NoSuchElementException if either source of destination does not exists.
*/
public void addEdge (T source, T destination, double length) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
/* A node would always be added so no point returning true or false */
graph.get(source).put(destination, length);
}
/**
* Removes an edge from the graph.
*
* @param source If the source node.
* @param destination If the destination node.
* @throws NullPointerException if either source or destination specified is null
* @throws NoSuchElementException if graph does not contain either source or destination
*/
public void removeEdge (T source, T destination) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
graph.get(source).remove(destination);
}
/**
* Given a node, returns the edges going outward that node,
* as an immutable map.
*
* @param node The node whose edges should be queried.
* @return An immutable view of the edges leaving that node.
* @throws NullPointerException If input node is null.
* @throws NoSuchElementException If node is not in graph.
*/
public Map<T, Double> edgesFrom(T node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
Map<T, Double> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("Source node does not exist.");
}
return Collections.unmodifiableMap(edges);
}
/**
* Returns the iterator that travels the nodes of a graph.
*
* @return an iterator that travels the nodes of a graph.
*/
@Override public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}
/**
* Given a connected directed graph, find all paths between any two input points.
*/
public class FindAllPaths<T> {
private final GraphFindAllPaths<T> graph;
/**
* Takes in a graph. This graph should not be changed by the client
*/
public FindAllPaths(GraphFindAllPaths<T> graph) {
if (graph == null) {
throw new NullPointerException("The input graph cannot be null.");
}
this.graph = graph;
}
private void validate (T source, T destination) {
if (source == null) {
throw new NullPointerException("The source: " + source + " cannot be null.");
}
if (destination == null) {
throw new NullPointerException("The destination: " + destination + " cannot be null.");
}
if (source.equals(destination)) {
throw new IllegalArgumentException("The source and destination: " + source + " cannot be the same.");
}
}
/**
* Returns the list of paths, where path itself is a list of nodes.
*
* @param source the source node
* @param destination the destination node
* @return List of all paths
*/
public List<List<T>> getAllPaths(T source, T destination) {
validate(source, destination);
List<List<T>> paths = new ArrayList<List<T>>();
recursive(source, destination, paths, new LinkedHashSet<T>());
return paths;
}
// so far this dude ignore's cycles.
private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path) {
path.add(current);
if (current == destination) {
paths.add(new ArrayList<T>(path));
path.remove(current);
return;
}
final Set<T> edges = graph.edgesFrom(current).keySet();
for (T t : edges) {
if (!path.contains(t)) {
recursive (t, destination, paths, path);
}
}
path.remove(current);
}
public static void main(String[] args) {
GraphFindAllPaths<String> graphFindAllPaths = new GraphFindAllPaths<String>();
graphFindAllPaths.addNode("A");
graphFindAllPaths.addNode("B");
graphFindAllPaths.addNode("C");
graphFindAllPaths.addNode("D");
graphFindAllPaths.addEdge("A", "B", 10);
graphFindAllPaths.addEdge("A", "C", 10);
graphFindAllPaths.addEdge("B", "D", 10);
graphFindAllPaths.addEdge("C", "D", 10);
graphFindAllPaths.addEdge("B", "C", 10);
graphFindAllPaths.addEdge("C", "B", 10);
FindAllPaths<String> findAllPaths = new FindAllPaths<String>(graphFindAllPaths);
List<List<String>> paths = new ArrayList<List<String>>();
// ABD
List<String> path1 = new ArrayList<String>();
path1.add("A"); path1.add("B"); path1.add("D");
// ABCD
List<String> path2 = new ArrayList<String>();
path2.add("A"); path2.add("B"); path2.add("C"); path2.add("D");
//ACD
List<String> path3 = new ArrayList<String>();
path3.add("A"); path3.add("C"); path3.add("D");
//ABCD
List<String> path4 = new ArrayList<String>();
path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");
paths.add(path1);
paths.add(path2);
paths.add(path3);
paths.add(path4);
findAllPaths.getAllPaths("A", "D");
assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
}
}
最佳解决方法
这是美丽，易于阅读，和 well-documented 代码。阅读这段代码是一种快乐，Java 方面几乎没有什么改进。
在这段代码中显示的最大的弱点不在于你对 Java 的技能 (远远超过我的)，而是你对英语的认识。
-
在
addEdgeJavaDoc 中，您可以谈论弧线而不是边。 -
可以改进该方法的错误消息中的语法：「源和目的地，都应该是 non-null」 。可以是 「源和目的地应该是 non-null」 或 「源和目的地都应该是 non-null」 。
-
该方法也运行非常混乱的 JavaDoc「@param length if length if」 – 我不知道这是什么意思。
但是我们来谈谈技术方面。
-
recursive方法有一个很好的错误：您正在通过==比较T实例：if (current == destination) {但是，这是默认比较指针。它只在这里工作，因为常量字符串
"A"，"B"等由 Java 实现合并。除非你的实际需要比较，否则请比较current.equals(destination)。 -
recursive将忽略循环的注释是错误的 – 它将仅构造最多访问每个节点的路径。这是处理循环的唯一正确方法，否则在循环图中将有无数个路径。 -
来自
validate的错误消息没有任何意义。if (source == null) { throw new NullPointerException("The source: " + source + " cannot be null.");所以我们得到 「源：null 不能为 null」 作为错误消息。这是没有帮助的，我建议改为：
if (source == null) { throw new NullPointerException("The "source" parameter cannot be null."); -
在您的测试代码中，您会经历过多的麻烦，产生预期的
paths。我非常喜欢Arrays.asList(…)：List<List<String>> paths = Arrays.asList( Arrays.asList("A", "B", "D"), Arrays.asList("A", "B", "C", "D"), Arrays.asList("A", "C", "D"), Arrays.asList("A", "C", "B", "D") );这段代码很简洁，self-documenting 。您将路径放入注释除了指定它们作为代码，当评论说
ABCD高于ACBD路径时出错了;-)此外，您测试返回路径的顺序是否相同。应该将路径的顺序视为不相关的 (您实际上对路径集合感兴趣)，并且未指定，因为
HashMap的用法不保证键的保存顺序。的确，你正在迭代keySet()，这将决定路径的顺序！更好的平等考验可能是：assertEquals(new HashSet<List<String>>(paths), new HashSet<List<String>>(result));
次佳解决方法
只是一些小事情：
-
评论在这里不正确，应该是
ACBD：//ABCD
List<String> path4 = new ArrayList<String>();
path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");
您可以使用 Guava 的
newArrayList(或编写类似的方法) 来从测试代码中删除一些重复：List<String> path4 = newArrayList("A", "C", "B", "D"); -
这里第一个电话是不必要的：
findAllPaths.getAllPaths("A", "D");assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
-
为了这：
if (graph.containsKey(node)) return false;
根据 Code Conventions for the Java Programming Language，
if 语句总是使用大括号 {} 。
省略它们是 error-prone 。我发现 one-liner 难以阅读，因为如果您逐行扫描代码，很容易错过，在行尾有一个
return语句。 -
我会重命名
-
validate至validateNotSame， -
paths至expectedPaths，
为了更好的清晰度。
-
-
GraphFindAllPaths可以简单地是Graph。 -
从清洁代码，第 25 页：类和对象应该有名词或名词短语名称，如
Customer，WikiPage，Account和AddressParser。 […] 类名不应该是动词。考虑AllPathFinder代替FindAllPaths。 -
您可能希望在此创建防御性副本：
public FindAllPaths(GraphFindAllPaths<T> graph) {
if (graph == null) {
throw new NullPointerException("The input graph cannot be null.");
}
this.graph = graph;
}
它将禁止恶意客户端修改类的内部数据，并可能节省您几个小时的调试。 (有效 Java，第 2 版，第 39 项：需要时制作防御副本)
-
Iterable功能和removeEdge方法不使用也不进行测试。您可能可以删除它们。 -
测试方法通常在
Test文件 (例如 FindAllPathsTest) 中，并由 JUnit 运行。它们通常位于一个独立的源文件夹中，无法使用生产代码打包junit.jar(和其他测试依赖项) 。 Maven’s directory structure 是一个 well-known 项目结构，考虑使用它 (以及 Maven，Gradle 或任何其他构建工具) 。
第三种解决方法
这真的是一个有趣的问题。首先我想提到，IMHO 没有多项式解决这个任务，因为它不是一个优化问题。所需的结果不是最大/最小的东西，而是枚举所有可能的路径。我认为所有可能的路径可能导致 n！完整图中的不同路径，其中 n 是节点数。所以找到一个解决方案取决于输入的大小。如果一个大的图形是在输入，那么使用这个算法将需要很多的时间和 memory ，可能不会完成。我不知道这个解决方案的确切用法，但我想这是一种 Map/导航应用程序。如果你不介意我会标出一些有用的点，并分享我的注意事项：
-
我看不到你在哪里使用双重值，这是为每一个边所持有的。我想它将用于计算路径的成本并返回按此标准排序的路径。如果这样，请考虑一个接一个地发现一小段路径，每次使用一些流行的算法进行 shortest path problem
-
如果输入上有一个稀疏图，那么使用每个节点的 Map 将导致很多重的对象，只保留几个值。这将不必要地增加内存消耗。我不知道用例，将使用什么类型的节点 (T)，但是我建议使用从 int 到 T 的单个映射，并使用整数作为节点号。然后可以使用 double [] [] 矩阵来保存边值，并使用整数作为矩阵中的索引。一个例子：
-
0 – > “A”
-
1 – > “B”
-
2 – > “C”
-
然后边”A” –4.2 – > “C” 将如下所示：matrix [0] [2] = 4.2 。再次，这将导致矩阵的许多未使用的单元格。即使一个更好的解决方案是拥有一个单一的数组/列表来保存每个节点的数组/邻居列表。其实你正在迭代邻居，所以你不需要一个 HashMap，只需持有一个 key-value 对的列表就足够了。我的意思是：List<List<Double>> nodes 表示图，而 node.get(i) 是另一个列表， nodeNumber，edgeCost) 。使用前面的例子：
List<Double> aNeighbours = nodes.get(0);
aNeighbours.set(2, 4.2);
如果你使用 ArrayList 考虑提供小的初始容量，因为默认是 16 我想。
我希望你找到一个解决这个问题的工作方法:) 。
参考文献
注：本文内容整合自 Google/Baidu/Bing 辅助翻译的英文资料结果。如果您对结果不满意，可以加入我们改善翻译效果：薇晓朵技术论坛。