当前位置： 文江博客话题详情

我应该如何在 Java 中表示依赖图？

发布于 2024-10-31 11:13:09 字数 228 浏览 0 评论 0原文

我正在编写一些 JavaScript 依赖管理代码，并且我认为有人已经解决了 Java 中的依赖图问题。

我的第一次尝试是在 JSResource 对象上实现比较，但是当存在多个没有依赖性的叶节点时，它会失败，因此没有合理的顺序，除非受到其依赖项的影响。

所以我想我需要一个图表，然后需要一种迭代该图表的方法。这不是一个不可能的问题，但我想在重新发明轮子之前我应该​​在这里发帖。

干杯， 皮特

原文

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

颜 2024-11-07 11:13:09

我发布了一些内容可能可以回答您的问题。这是链接：
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);
}

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);
}
回复 原文
橙幽之幻 2024-11-07 11:13:09

很多时候，将任务表示为依赖图是不够的，您可能希望并行执行满足依赖条件的任务（表示为节点），再加上做一些内务工作，例如检查周期等。为此，您可以借助这个框架，这是一个非常轻量级的框架，可以在可靠的方式。这是一个测试用例，可以让您有一个简单的了解：

@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]

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]
回复 原文
~没有更多了~

关于作者

拧巴小姐

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

烙印

文章 0 评论 0

singlesman

文章 0 评论 0

给自己一个微笑

文章 0 评论 0

独孤求败

文章 0 评论 0

晨钟暮鼓

文章 0 评论 0

我是自愿种绣球花的

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文