I recently came across the dependency graph topic that was not too familiar to me and tried to put together something simple and working. A sheer background of graphs I already had but never really tried to seriously play with them.
Refusing to read all the involved math in dealing with such matter, my first two tries of having something working were doomed to fail.
I still kept refusing to get more educated in the matter and tried one more time still repeating to myself - "The approach should be just common sense - we bump into graphs everywhere from transit buses to web, so why math for it- we should not be that dumb"
Here you can find some code that works fine for me, so feel free to use it. In my next posts I might add something to it, or implement it in Scala. Let me know if this works for you or if you need some extra features. I am open for any suggestions.
I also added the graph which nodes where generated by the following statements:
(Note that the order the following statements are executed does not matter. The result should be the same)
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");
As you can see the result should be this:[a, h, b, c, f, e, d, g]
To test the code use this:
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);
}
Dependency Graphs - A Generic Approach In Java by
nicolae caralicea is licensed under a
Creative Commons Attribution-NoDerivs 3.0 Unported License.
