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);
}
有一篇关于Java图形处理库的讨论，或许会对您有所帮助。
很多时候，将任务表示为依赖图是不够的，您可能希望并行执行任务（表示为节点），满足依赖条件，并进行一些清理工作，例如检查循环等。为此，您可以借助这个框架的帮助，它是一个非常轻量级的框架，可靠地运行相关任务。以下是一个测试用例，以让您对其有一个简要的了解：
@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();
}
}
};
}
}
这里是控制台输出，让你了解底层发生了什么
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]