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.
nice good solution Looking forward to your your scala implementation
ReplyDeletethank you for your comment.
ReplyDeletei am expecting to have it in about one week
Nice ;)
ReplyDeleteThanks for the tutorial. Btw how about finding a dependency of a node? for example dependency of g are a,c,f,d. can you give me some references ? thanks
ReplyDeleteHi Nicolae,
ReplyDeleteI was planning to write something similar and stumbled upon your code in StackOverflow while trying to look for existing implementations. Would it be fine if I use your code in my work, with a few adjustments to suit my requirements, of course?
Thanks,
Sandeep
Hi Sandeep,
DeleteGlad to hear you can make a good use of this code. Please feel free to use it in your projects. The only thing I would ask you is to provide a link to this post.
Enjoy it!
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteThanks for the nice explanation with code
ReplyDeleteHowever, if we added more nodes (25+) it will give a stackoverflow error. are there any segment to tuneup.?
Exception in thread "main" java.lang.StackOverflowError
at java.base/java.lang.Object.equals(Object.java:151)
at java.base/java.util.ArrayList.indexOfRange(ArrayList.java:299)
at java.base/java.util.ArrayList.indexOf(ArrayList.java:286)
at java.base/java.util.ArrayList.contains(ArrayList.java:275)
at java.base/java.util.AbstractCollection.containsAll(AbstractCollection.java:309)
at org.madeforall.graph.Graph.areAlreadyEvaluated(Graph.java:88)
at org.madeforall.graph.Graph.generateDependencies(Graph.java:58)