我应该如何在 Java 中表示依赖图？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5604475/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-10-30 11:52:16 来源:igfitidea点击:
How should I represent a dependency graph in Java?
提问by Peter Wilkinson
I'm working on some code for JavaScript dependency management and I'm figuring someone has tackled the dependency graph problem in Java already.
我正在编写一些用于 JavaScript 依赖管理的代码，并且我认为有人已经解决了 Java 中的依赖图问题。
My first attempt was to just implement comparable on my JSResource object, but it falls over when there are multiple leaf nodes with no dependency and hence no sensible order unless influenced by their dependents.
我的第一次尝试是在我的 JSResource 对象上实现可比性，但是当有多个没有依赖关系的叶节点时它会失败，因此除非受它们的依赖关系影响，否则没有合理的顺序。
So I figure I need a graph and then a way to iterate through the graph. Not an impossible problem but I thought I'd post here before reinventing the wheel.
所以我想我需要一个图形，然后是一种遍历图形的方法。这不是一个不可能的问题，但我想在重新发明轮子之前我会在这里发帖。
Cheers, Pete
干杯，皮特
采纳答案by aav
There is a discussion about java graph handling libraries. Maybe it will help you.
有一个关于 java 图形处理库的讨论。也许它会帮助你。
回答by ncaralicea
I posted something that might answer to your question. Here is the link: http://nicolaecaralicea.blogspot.com/2010/11/dependency-graphs-generic-approach-in.html
我发布了一些可能会回答您的问题的内容。这是链接：http: //nicolaecaralicea.blogspot.com/2010/11/dependency-graphs-generic-approach-in.html
Here is the code:
这是代码：
package org.madeforall.graph.test;
import java.util.ArrayList;
import java.util.List;
import org.madeforall.graph.Graph;
import org.madeforall.graph.NodeValueListener;
public class TestDependecyGraph {
public static void main(String[] args) {
testWithGenericInt();
testWithGenericString();
}
public static void testWithGenericInt() {
final List<Integer> nodeValueList = new ArrayList<Integer>();
Graph<Integer> graph = new Graph<Integer>(new NodeValueListener<Integer>() {
public void evaluating(Integer nodeValue) {
nodeValueList.add(nodeValue);
}
});
graph.addDependency(1, 2);
graph.addDependency(1, 3);
graph.addDependency(3, 4);
graph.addDependency(3, 5);
graph.addDependency(5, 8);
graph.addDependency(2, 7);
graph.addDependency(2, 9);
graph.addDependency(2, 8);
graph.addDependency(9, 10);
graph.generateDependencies();
System.out.println(nodeValueList);
}
public static void testWithGenericString() {
final List<String> nodeValueList = new ArrayList<String>();
Graph<String> graph = new Graph<String>(new NodeValueListener<String>() {
public void evaluating(String nodeValue) {
nodeValueList.add(nodeValue);
}
});
graph.addDependency("a", "b");
graph.addDependency("a", "c");
graph.addDependency("a", "f");
graph.addDependency("c", "d");
graph.addDependency("d", "g");
graph.addDependency("f", "d");
graph.addDependency("h", "e");
graph.generateDependencies();
System.out.println(nodeValueList);
}
}
The first and the second argument of the addDependency method of the Graph class are some two arbitrarily chosen nodes of the oriented graph. Watch out for circular dependencies, because I did not take care of them yet.
Here are the classes.
package org.madeforall.graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Set;
/**
*
* Represents a graph of nodes. Every node is of GraphNode type and it has set a
* value of the generic type <T>. It basically derives an evaluation order out
* of its nodes. A node gets the chance to be evaluated when all the incoming
* nodes were previously evaluated. The evaluating method of the
* NodeValueListener is used to notify the outside of the fact that a node just
* got the chance to be evaluated. A value of the node that is of the generic
* type <T> is passed as argument to the evaluating method.
*
*
* @author nicolae caralicea
*
* @param <T>
*/
final public class Graph<T> {
/**
* These are basically the nodes of the graph
*/
private HashMap<T, GraphNode<T>> nodes = new HashMap<T, GraphNode<T>>();
/**
* The callback interface used to notify of the fact that a node just got
* the evaluation
*/
private NodeValueListener<T> listener;
/**
* It holds a list of the already evaluated nodes
*/
private List<GraphNode<T>> evaluatedNodes = new ArrayList<GraphNode<T>>();
/**
* The main constructor that has one parameter representing the callback
* mechanism used by this class to notify when a node gets the evaluation.
*
* @param listener
* The callback interface implemented by the user classes
*/
public Graph(NodeValueListener<T> listener) {
this.listener = listener;
}
/**
* Allows adding of new dependicies to the graph. "evalFirstValue" needs to
* be evaluated before "evalAfterValue"
*
* @param evalFirstValue
* The parameter that needs to be evaluated first
* @param evalAfterValue
* The parameter that needs to be evaluated after
*/
public void addDependency(T evalFirstValue, T evalAfterValue) {
GraphNode<T> firstNode = null;
GraphNode<T> afterNode = null;
if (nodes.containsKey(evalFirstValue)) {
firstNode = nodes.get(evalFirstValue);
} else {
firstNode = createNode(evalFirstValue);
nodes.put(evalFirstValue, firstNode);
}
if (nodes.containsKey(evalAfterValue)) {
afterNode = nodes.get(evalAfterValue);
} else {
afterNode = createNode(evalAfterValue);
nodes.put(evalAfterValue, afterNode);
}
firstNode.addGoingOutNode(afterNode);
afterNode.addComingInNode(firstNode);
}
/**
* Creates a graph node of the <T> generic type
*
* @param value
* The value that is hosted by the node
* @return a generic GraphNode object
*/
private GraphNode<T> createNode(T value) {
GraphNode<T> node = new GraphNode<T>();
node.value = value;
return node;
}
/**
*
* Takes all the nodes and calculates the dependency order for them.
*
*/
public void generateDependencies() {
List<GraphNode<T>> orphanNodes = getOrphanNodes();
List<GraphNode<T>> nextNodesToDisplay = new ArrayList<GraphNode<T>>();
for (GraphNode<T> node : orphanNodes) {
listener.evaluating(node.value);
evaluatedNodes.add(node);
nextNodesToDisplay.addAll(node.getGoingOutNodes());
}
generateDependencies(nextNodesToDisplay);
}
/**
* Generates the dependency order of the nodes passed in as parameter
*
* @param nodes
* The nodes for which the dependency order order is executed
*/
private void generateDependencies(List<GraphNode<T>> nodes) {
List<GraphNode<T>> nextNodesToDisplay = null;
for (GraphNode<T> node : nodes) {
if (!isAlreadyEvaluated(node)) {
List<GraphNode<T>> comingInNodes = node.getComingInNodes();
if (areAlreadyEvaluated(comingInNodes)) {
listener.evaluating(node.value);
evaluatedNodes.add(node);
List<GraphNode<T>> goingOutNodes = node.getGoingOutNodes();
if (goingOutNodes != null) {
if (nextNodesToDisplay == null)
nextNodesToDisplay = new ArrayList<GraphNode<T>>();
// add these too, so they get a chance to be displayed
// as well
nextNodesToDisplay.addAll(goingOutNodes);
}
} else {
if (nextNodesToDisplay == null)
nextNodesToDisplay = new ArrayList<GraphNode<T>>();
// the checked node should be carried
nextNodesToDisplay.add(node);
}
}
}
if (nextNodesToDisplay != null) {
generateDependencies(nextNodesToDisplay);
}
// here the recursive call ends
}
/**
* Checks to see if the passed in node was aready evaluated A node defined
* as already evaluated means that its incoming nodes were already evaluated
* as well
*
* @param node
* The Node to be checked
* @return The return value represents the node evaluation status
*/
private boolean isAlreadyEvaluated(GraphNode<T> node) {
return evaluatedNodes.contains(node);
}
/**
* Check to see if all the passed nodes were already evaluated. This could
* be thought as an and logic between every node evaluation status
*
* @param nodes
* The nodes to be checked
* @return The return value represents the evaluation status for all the
* nodes
*/
private boolean areAlreadyEvaluated(List<GraphNode<T>> nodes) {
return evaluatedNodes.containsAll(nodes);
}
/**
*
* These nodes represent the starting nodes. They are firstly evaluated.
* They have no incoming nodes. The order they are evaluated does not
* matter.
*
* @return It returns a list of graph nodes
*/
private List<GraphNode<T>> getOrphanNodes() {
List<GraphNode<T>> orphanNodes = null;
Set<T> keys = nodes.keySet();
for (T key : keys) {
GraphNode<T> node = nodes.get(key);
if (node.getComingInNodes() == null) {
if (orphanNodes == null)
orphanNodes = new ArrayList<GraphNode<T>>();
orphanNodes.add(node);
}
}
return orphanNodes;
}
}
package org.madeforall.graph;
import java.util.ArrayList;
import java.util.List;
/**
*
* It represents the node of the graph. It holds a user value that is passed
* back to the user when a node gets the chance to be evaluated.
*
* @author nicolae caralicea
*
* @param <T>
*/
final class GraphNode<T> {
public T value;
private List<GraphNode<T>> comingInNodes;
private List<GraphNode<T>> goingOutNodes;
/**
* Adds an incoming node to the current node
*
* @param node
* The incoming node
*/
public void addComingInNode(GraphNode<T> node) {
if (comingInNodes == null)
comingInNodes = new ArrayList<GraphNode<T>>();
comingInNodes.add(node);
}
/**
* Adds an outgoing node from the current node
*
* @param node
* The outgoing node
*/
public void addGoingOutNode(GraphNode<T> node) {
if (goingOutNodes == null)
goingOutNodes = new ArrayList<GraphNode<T>>();
goingOutNodes.add(node);
}
/**
* Provides all the coming in nodes
*
* @return The coming in nodes
*/
public List<GraphNode<T>> getComingInNodes() {
return comingInNodes;
}
/**
* Provides all the going out nodes
*
* @return The going out nodes
*/
public List<GraphNode<T>> getGoingOutNodes() {
return goingOutNodes;
}
}
package org.madeforall.graph;
/**
* The main mechanism used for notifying the outside of the fact that a node
* just got its evaluation
*
* @author nicolae caralicea
*
* @param <T>
*/
public interface NodeValueListener<T> {
/**
*
* The callback method used to notify the fact that a node that has assigned
* the nodeValue value just got its evaluation
*
* @param nodeValue
* The user set value of the node that just got the evaluation
*/
void evaluating(T nodeValue);
}
回答by craftsmannadeem
Many a times representing tasks as dependency graph is not sufficient, you would want to execute the tasks (represented as nodes) in parallel meeting the dependency conditions, plus do some house keeping works such as check for cycle etc.. For that purpose you can take help of this framework, which is a very light weight framework to run dependent tasks in a reliable way. Here is a test case to give you a brief idea:
很多时候将任务表示为依赖图是不够的，您可能希望并行执行满足依赖条件的任务（表示为节点），并做一些内务工作，例如检查循环等。为此，您可以借助这个框架，这是一个非常轻量级的框架，可以以可靠的方式运行相关任务。这是一个测试用例，可以让您简要了解：
@Test
public void testDependentTaskExecution() {
DefaultDependentTasksExecutor<Integer> executor = newTaskExecutor();
executor.addDependency(1, 2);
executor.addDependency(1, 3);
executor.addDependency(3, 4);
executor.addDependency(3, 5);
executor.addDependency(3, 6);
//executor.addDependency(10, 2); // cycle
executor.addDependency(2, 7);
executor.addDependency(2, 9);
executor.addDependency(2, 8);
executor.addDependency(9, 10);
executor.addDependency(12, 13);
executor.addDependency(13, 4);
executor.addDependency(13, 14);
executor.addIndependent(11);
executor.execute();
}
private DefaultDependentTasksExecutor<Integer> newTaskExecutor() {
return new DefaultDependentTasksExecutor<Integer>(newExecutor(), new SleepyTaskProvider<Integer>());
}
private ExecutorService newExecutor() {
return Executors.newCachedThreadPool();
}
private static class SleepyTaskProvider<T> implements TaskProvider<T> {
public Task provid(T id) {
return new Task() {
public void execute() {
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
}
}
Here is the console output to give you an idea of what is going under the hood
这是控制台输出，让您了解引擎盖下的情况
19:57:43.705 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 1 node
19:57:43.710 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 11 node
19:57:43.710 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 12 node
19:57:44.212 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 1 done
19:57:44.213 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 2 node
19:57:44.214 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 3 node
19:57:44.215 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 11 done
19:57:44.216 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 12 done
19:57:44.217 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 13 node
19:57:44.717 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 2 done
19:57:44.718 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 7 node
19:57:44.719 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 9 node
19:57:44.720 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 8 node
19:57:44.721 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 3 done
19:57:44.722 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 83 - node 4 depends on [3, 13]
19:57:44.724 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 5 node
19:57:44.726 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 6 node
19:57:44.728 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 13 done
19:57:44.729 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 4 node
19:57:44.730 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 14 node
19:57:45.219 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 7 done
19:57:45.221 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 9 done
19:57:45.223 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doExecute 80 - Going to schedule 10 node
19:57:45.225 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 8 done
19:57:45.227 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 5 done
19:57:45.228 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 6 done
19:57:45.234 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 4 done
19:57:45.235 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 14 done
19:57:45.725 [main] DEBUG c.n.e.DefaultDependentTasksExecutor.doWaitForExecution 105 - Processing of node 10 done
19:57:45.726 [main] INFO c.n.e.DefaultDependentTasksExecutor.execute 69 - Total Time taken to process 14 jobs each taking 500 ms is 2022 ms instead of 7000 ms
19:57:45.728 [main] INFO c.n.e.DefaultDependentTasksExecutor.execute 70 - [1, 11, 12, 2, 3, 13, 7, 9, 8, 5, 6, 4, 14, 10]
