How should I represent a dependency graph in Java?

Question

I'm working on some code for JavaScript dependency management and I'm figuring someone has tackled the dependency graph problem in Java already.

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.

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

Answer 1

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

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);
}

Answer 2

There is a discussion about java graph handling libraries. Maybe it will help you.

Good Java graph algorithm library?

Answer 3

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]