我正在研究JavaScript依赖管理的一些代码,我想是有人已经解决了Java中的依赖图问题.
我的第一次尝试是在我的JSResource对象上实现可比较的,但是当有多个叶子节点没有依赖关系而因此没有合理的顺序时它会失败,除非受到它们的依赖性的影响.
所以我想我需要一个图表然后迭代图表.这不是一个不可能的问题,但我想我会在重新发明轮子之前发布这里.
干杯,皮特
我发布了一些可能回答你问题的内容.这是链接:http: //nicolaecaralicea.blogspot.com/2010/11/dependency-graphs-generic-approach-in.html
这是代码:
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);
}