精华内容
下载资源
问答
  • 有向无环图

    千次阅读 2016-09-03 23:05:48
    有向无环图

    /*

    Problem B: 有向无环图
    Time Limit: 5 Sec Memory Limit: 128 MB
    Submit: 20 Solved: 11
    [Submit][Status][Web Board]
    Description

    Bobo 有一个 n 个点,m 条边的有向无环图(即对于任意点 v,不存在从点 v 开始、点 v 结束的路径)。

    为了方便,点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量(规定 count(x,x)=0),Bobo 想知道

    对所有i,j,求f(e(i,j))*(ai,bj)

    除以 (109+7) 的余数。其中f(e(i,j))表示i—>所有边的数目.

    其中,ai,bj 是给定的数列。

    Input

    输入包含不超过 15 组数据。

    每组数据的第一行包含两个整数 n,m (1≤n,m≤105).

    接下来 n 行的第 i 行包含两个整数 ai,bi (0≤ai,bi≤109).

    最后 m 行的第 i 行包含两个整数 ui,vi,代表一条从点 ui 到 vi 的边 (1≤ui,vi≤n)。

    Output

    对于每组数据,输出一个整数表示要求的值。

    Sample Input
    3 3
    1 1
    1 1
    1 1
    1 2
    1 3
    2 3
    2 2
    1 0
    0 2
    1 2
    1 2
    2 1
    500000000 0
    0 500000000
    1 2

    Sample Output
    4
    4
    250000014
    */

    /*
    题意:给一个有向无环图,顶点编号1~n,m条边(注意,多重图),同时,给ai,bi,1<=i<=n; 求:对所有1<=i,j<=n, count(i,j)*a[i]*b[j] 的和对1e9+7取模.
    思路:在回来的车上教练讨论过,听了一点,不太清楚,后来自己去思考.感觉很妙!然后等重现实现Orz…
    主要是妙在求解顺序上,是个拓扑排序.dfs一般超时,bfs分层O(n)吧; 每次先计算入度为零的顶点v与其邻点u的值,然后
    把这个顶点v的a累加到下个顶点u上(v->u),这样当计算到u到它的邻点w的时候,a[u]事实上是已经包括a[v]了,所以算u->w
    的时候顺便把v->w也算了; 不得不说,真的很妙的解法啊!!!
    */

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    typedef long long LL ;
    const LL mod=1e9+7;
    const int maxn=1e5+100;
    int n,m;
    int a[maxn],b[maxn];
    vector<int> G[maxn];
    int vis[maxn];//入度
    void init()
    {
        for (int i=1;i<=n;i++){
            vis[i]=0;
            G[i].clear();
        }
    }
    int main()
    {
        //freopen("D:in.txt","r",stdin);
        while (scanf("%d%d",&n,&m)==2)
        {
            init();
            for (int i=1;i<=n;i++){
                scanf("%d%d",&a[i],&b[i]);
            }
            for (int i=1;i<=m;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                G[a].push_back(b);
                vis[b]++;
            }
            queue<LL> que;
            for (int i=1;i<=n;i++){
                if (!vis[i]) {que.push(i);}//所有入度为零的入队列
            }
            LL res=0;
            while (!que.empty())
            {
                int v=que.front();que.pop();
                for (int i=0;i<(int)G[v].size();i++){
                    int &u=G[v][i];
                    res=(res+(a[v]%mod) * (b[u]%mod)%mod)%mod;
                    a[u]=(a[u]+a[v])%mod;//把部分现在的结果加到下个顶点来算
                    vis[u]--;
                    if (!vis[u]){//入度为零又可以入队了
                        que.push(u);
                    }
                }
            }
            cout<<res%mod<<endl;
        }
        return 0;
    }
    展开全文
  • 有向无环图任务的执行有依赖关系,如下图所示:可以使用DAG(有向无环图)来维护这种依赖关系;定义task@Data@NoArgsConstructorpublic class NodeTask {private String id;private Set dependences = Sets....

    有向无环图

    任务的执行有依赖关系,如下图所示:

    a5b246436c807bd92d803f62ac88a78b.png

    可以使用DAG(有向无环图)来维护这种依赖关系;

    定义task

    @Data

    @NoArgsConstructor

    public class NodeTask {

    private String id;

    private Set dependences = Sets.newConcurrentHashSet(); //依赖的taskID

    public NodeTask(String id) {

    this.id = id;

    }

    public NodeTask addDependence(String nodeTaskId) {

    this.dependences.add(nodeTaskId);

    return this;

    }

    }

    Graph

    package com.ssslinppp.graph.directd;

    import com.google.common.collect.Lists;

    import com.google.common.collect.Maps;

    import com.google.common.collect.Queues;

    import com.google.common.graph.GraphBuilder;

    import com.google.common.graph.MutableGraph;

    import java.util.List;

    import java.util.Map;

    import java.util.Queue;

    public class TaskGraph {

    private MutableGraph taskGraph = GraphBuilder.directed().allowsSelfLoops(false).build();

    /**

    * 转换节点任务为Graph

    *

    * @param nodeTasks

    */

    public void parseNodeTasksToGraph(Map nodeTasks) {

    for (NodeTask nodeTask : nodeTasks.values()) {

    if (!taskGraph.nodes().contains(nodeTask)) {

    taskGraph.addNode(nodeTask);

    }

    for (String dependence : nodeTask.getDependences()) {

    taskGraph.putEdge(nodeTask, nodeTasks.get(dependence));

    }

    }

    }

    /**

    * 判断是否为DAG(Directed Acyclic Graph)有向无环图

    *

    * 算法思路:

    *

    *

    1. 根据"拓扑排序"算法判断:拓扑排序之后,若还剩有点,则表示有环

    *

    2. 拓扑排序算法:找到图中所有入度为0的点,放入序列,删除这些点和以这些点为出度的边,再找所有入度为0的点,依次循环

    *

    *

    * @return

    */

    public boolean isDAGraph() {

    Map nodeInDegreeMap = Maps.newHashMap();

    Queue queue = Queues.newArrayDeque();

    List topologicalSortList = Lists.newArrayList(); //拓扑排序列表维护

    // 获取所有入度为0的节点

    for (NodeTask nodeTask : taskGraph.nodes()) {

    int indegree = taskGraph.inDegree(nodeTask);

    nodeInDegreeMap.put(nodeTask.getId(), indegree);

    if (indegree == 0) {

    queue.add(nodeTask);

    topologicalSortList.add(nodeTask.getId());

    }

    }

    while (!queue.isEmpty()) {

    NodeTask preNode = queue.poll(); //获取并删除

    for (NodeTask successorNode : taskGraph.successors(preNode)) {

    int indegree = nodeInDegreeMap.get(successorNode.getId());

    if (--indegree == 0) {//-1:等效删除父节点以及相应的边

    queue.offer(successorNode); //insert

    topologicalSortList.add(successorNode.getId());

    }

    nodeInDegreeMap.put(successorNode.getId(), indegree);

    }

    }

    System.out.println("拓扑排序(topologicalSortList):" + topologicalSortList);

    if (topologicalSortList.size() != taskGraph.nodes().size()) {

    return false;

    }

    return true;

    }

    /**

    * 打印Graph中task的依赖关系

    */

    public void print() {

    System.out.println("=============NodeTask count: " + taskGraph.nodes().size());

    for (NodeTask nodeTask : taskGraph.nodes()) {

    System.out.println("-------- NodeTask: " + nodeTask.getId() + "--------");

    System.out.print("Dependent on: ");

    taskGraph.successors(nodeTask).forEach((v) -> System.out.print(v.getId() + ", "));

    System.out.println();

    System.out.print("all predecessors: ");

    taskGraph.predecessors(nodeTask).forEach((v) -> System.out.print(v.getId() + ", "));

    System.out.println();

    System.out.println();

    }

    }

    }

    Test

    package com.ssslinppp.graph.directd;

    import com.google.common.collect.Maps;

    import org.junit.Test;

    import java.util.Map;

    public class TaskGraphTest {

    /**

    * 测试依赖关系

    */

    @Test

    public void testDependence() {

    Map nodeTaskMap = Maps.newConcurrentMap();

    NodeTask nodeTaskA = new NodeTask("nodeTaskA");

    NodeTask nodeTaskB = new NodeTask("nodeTaskB");

    NodeTask nodeTaskC = new NodeTask("nodeTaskC").addDependence("nodeTaskA");

    NodeTask nodeTaskD = new NodeTask("nodeTaskD").addDependence("nodeTaskB");

    NodeTask nodeTaskE = new NodeTask("nodeTaskE").addDependence("nodeTaskC").addDependence("nodeTaskD");

    NodeTask nodeTaskF = new NodeTask("nodeTaskF").addDependence("nodeTaskE");

    NodeTask nodeTaskG = new NodeTask("nodeTaskG").addDependence("nodeTaskE");

    nodeTaskMap.put(nodeTaskA.getId(), nodeTaskA);

    nodeTaskMap.put(nodeTaskB.getId(), nodeTaskB);

    nodeTaskMap.put(nodeTaskC.getId(), nodeTaskC);

    nodeTaskMap.put(nodeTaskD.getId(), nodeTaskD);

    nodeTaskMap.put(nodeTaskE.getId(), nodeTaskE);

    nodeTaskMap.put(nodeTaskF.getId(), nodeTaskF);

    nodeTaskMap.put(nodeTaskG.getId(), nodeTaskG);

    TaskGraph taskGraph = new TaskGraph();

    taskGraph.parseNodeTasksToGraph(nodeTaskMap);

    System.out.println("======== DAG(有向无环图)判断 ===========");

    if (taskGraph.isDAGraph()) {

    System.out.println("is DAG");

    } else {

    System.out.println("Not DAG");

    }

    System.out.println("=============== print ===========");

    taskGraph.print();

    }

    /**

    * 判断是否为有向无环图

    */

    @Test

    public void testDAG() {

    // E依赖D, D依赖B, B依赖E ==>(B,E,G)为一个环

    Map nodeTaskMap = Maps.newConcurrentMap();

    NodeTask nodeTaskA = new NodeTask("nodeTaskA");

    NodeTask nodeTaskB = new NodeTask("nodeTaskB");

    // nodeTaskB.addDependence("nodeTaskE"); // 在这里控制是否有环,进行测试

    NodeTask nodeTaskC = new NodeTask("nodeTaskC").addDependence("nodeTaskA");

    NodeTask nodeTaskD = new NodeTask("nodeTaskD").addDependence("nodeTaskB");

    NodeTask nodeTaskE = new NodeTask("nodeTaskE").addDependence("nodeTaskC").addDependence("nodeTaskD");

    NodeTask nodeTaskF = new NodeTask("nodeTaskF").addDependence("nodeTaskE");

    NodeTask nodeTaskG = new NodeTask("nodeTaskG").addDependence("nodeTaskE");

    nodeTaskMap.put(nodeTaskA.getId(), nodeTaskA);

    nodeTaskMap.put(nodeTaskB.getId(), nodeTaskB);

    nodeTaskMap.put(nodeTaskC.getId(), nodeTaskC);

    nodeTaskMap.put(nodeTaskD.getId(), nodeTaskD);

    nodeTaskMap.put(nodeTaskE.getId(), nodeTaskE);

    nodeTaskMap.put(nodeTaskF.getId(), nodeTaskF);

    nodeTaskMap.put(nodeTaskG.getId(), nodeTaskG);

    TaskGraph taskGraph = new TaskGraph();

    taskGraph.parseNodeTasksToGraph(nodeTaskMap);

    System.out.println("======== DAG(有向无环图)判断 ===========");

    if (taskGraph.isDAGraph()) {

    System.out.println("It is DAG");

    } else {

    System.out.println("Not DAG");

    }

    }

    }

    pom

    org.springframework.boot

    spring-boot-starter

    com.google.guava

    guava

    23.0

    org.projectlombok

    lombok

    true

    org.springframework.boot

    spring-boot-starter-test

    test

    源码

    展开全文
  • 点击上方蓝字关注DolphinScheduler(海豚调度) |作者:鲍亮|编辑:卢凯瑞1 名词解释DAG,全称:Directed Acyclic Graph,中文:有向无环图入度:有向图中某点作为图中边的终点的次数之和出度:对于有向图来说,顶点的...

    b865b589e086a30dd0f8cf0dbb479eaa.gif

    点击上方蓝字关注DolphinScheduler(海豚调度)

    b865b589e086a30dd0f8cf0dbb479eaa.gif

    |作者:鲍亮

    |编辑:卢凯瑞

    1 名词解释

    DAG,全称:Directed Acyclic Graph,中文:有向无环图

    入度:有向图中某点作为图中边的终点的次数之和

    出度:对于有向图来说,顶点的出边条数即为该顶点的出度

    2 调度系统中的有向无环图

    数据调度系统中,多个任务之间的依赖关系,用图可以表示,如下图所示,每个顶点表示一个任务,箭头方向表示任务的执行顺序。任何顶点都无法经过边回到该顶点,则该图就是无环图,即为有向无环图(DAG图)。

    b443b5a95f6c269b286cd2775d888e4a.png

    图一

    那么在有向图中,如果有环的存在,如图示:

    68e1d311288483fabc7e5afeb7d4b683.png

    图二

    在有环的情况下,任务3的执行需要任务5完成,而5的执行又需要3,4依次执行完成,这样就会造成死循环,此调度任务永远无法成功执行。所以在调度系统中,对于无环的检测就非常重要。

    3 无环检测

    在调度系统中,检查图是否有环,分两种场景:1. 编辑图的过程中每一步操作都需要对其做无环检测;2. 对已经存在的图进行拓扑排序,检测是否有环。

    3.1 编辑时检测

    对于新创建的图来说,每增加一条边,都需要检测,这条边是否导致环的存在 思路:如图1到图2, 如果要加一条5到3的边,就从3开始遍历后续顶点,如果能回到顶点5的话就证明新加的边导致环的产生;如果不能回到5,证明新添加的边不会导致有环。检测代码如下:

    /**

    * 判断增加边(fromVertex --> toVertex)是否合法,需要判断是否符合无环的约束

    *

    * @param fromVertex     起点

    * @param toVertex       终点

    * @param createVertex 是否创建结点

    * @return

    */

    private boolean isLegalAddEdge(Vertex fromVertex, Vertex toVertex, boolean isCreate){

    if (fromVertex.equals(toVertex)) {

    logger.error("edge fromVertex({}) can't equals toVertex({})",fromVertex,toVertex);

    return false;

    }

    if (!isCreate) {

    if (!hasVertex(fromVertex) || !hasVertex(toVertex)){

    logger.error("edge fromVertex({}) or toVertex({}) is not in vertices map",fromVertex,toVertex);

    return false;

    }

    }

    Queue queue = new LinkedList<>();

    queue.add(toVertex);

    int verticesCount = getVerticesCount();

    //如果没有找到fromVertex, 表示无环;

    while (!queue.isEmpty() && verticesCount > 0) {

    verticesCount -= 1;

    Vertex key = queue.poll();

    // 遍历后续顶点

    for (Vertex subsequentVertex : getSubsequentNodes(key)) {

    if (subsequentVertex.equals(fromVertex)) {

    return false;

    }

    queue.add(subsequentVertex);

    }

    }

    return true;

    }

    3.2 拓扑排序检测

    有向图的拓扑排序,思路如下:

    遍历图中所有的顶点,将入度为0的顶点入队列(如果多个顶点入度为0,取顶点顺序可能不一样,所以此处排序结果可能是多个)。

    从队列中poll出一个顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后等于0,则将该邻接点入队列。

    一直执行第2步,直到队列为空。

    如果无法遍历完所有的结点,则意味着当前的图不是无环图。不存在拓扑排序。

    例如图1 入度出度:

    顶点

    入度

    出度

    顶点1

    0

    2

    顶点2

    1

    1

    顶点3

    1

    1

    顶点4

    2

    1

    顶点5

    1

    0

    拓扑排序流程如下:

    7f3795e399931f583c0b65c6ecec4700.png

    图三

    java实现如下:

    /**

    * 判断是否有环及拓扑排序结果

    *

    * 有向无环图(DAG)才有拓扑(topological)排序

    * 广度优先遍历的主要做法:

    *    1、遍历图中所有的顶点,将入度为0的顶点入队列。

    *    2、从队列中poll出一个顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后等于0,则将该邻接点入队列。

    *    3、一直执行第2步,直到队列为空。

    * 如果无法遍历完所有的结点,则意味着当前的图不是有向无环图。不存在拓扑排序。

    *

    *

    * @return key返回的是状态, 如果成功(无环)为true, 失败则有环, value为拓扑排序结果(可能是其中一种)

    */

    private Map.Entry> topologicalSortImpl() {

    //入度为0的结点队列

    Queue zeroIndegreeVertexQueue = new LinkedList<>();

    //保存结果

    List topoResultList = new ArrayList<>();

    //保存入度不为0的结点

    Map notZeroIndegreeVertexMap = new HashMap<>();

    //扫描所有的顶点,将入度为0的顶点入队列

    for (Map.Entry vertices : verticesMap.entrySet()) {

    Vertex vertex = vertices.getKey();

    int inDegree = getIndegree(vertex);

    if (inDegree == 0) {

    zeroIndegreeVertexQueue.add(vertex);

    topoResultList.add(vertex);

    } else {

    notZeroIndegreeVertexMap.put(vertex, inDegree);

    }

    }

    //扫描完后,没有入度为0的结点,说明有环,直接返回

    if(zeroIndegreeVertexQueue.isEmpty()){

    return new AbstractMap.SimpleEntry(false, topoResultList);

    }

    //采用topology算法, 删除入度为0的结点和它的关联边

    while (!zeroIndegreeVertexQueue.isEmpty()) {

    Vertex v = zeroIndegreeVertexQueue.poll();

    //得到相邻结点

    Set subsequentNodes = getSubsequentNodes(v);

    for (Vertex subsequentVertex : subsequentNodes) {

    Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);

    if(--degree == 0){

    topoResultList.add(subsequentVertex);

    zeroIndegreeVertexQueue.add(subsequentVertex);

    notZeroIndegreeVertexMap.remove(subsequentVertex);

    }else{

    notZeroIndegreeVertexMap.put(subsequentVertex, degree);

    }

    }

    }

    //notZeroIndegreeVertexMap如果为空, 表示没有环

    AbstractMap.SimpleEntry resultMap = new AbstractMap.SimpleEntry(notZeroIndegreeVertexMap.size() == 0 , topoResultList);

    return resultMap;

    }

    }

    输出每个顶点的同时还要删除以它为起点的边。如果图有V个顶点,E条边,则一般该算法的时间复杂度为O(V+E)。这里实现的算法最终key返回的是状态, 如果成功(无环)为true, 失败则有环, 无环时value为拓扑排序结果(可能是其中一种)。

    展开全文
  • 目录:1、有向无环图2、代码结构3、代码学习步鄹及方法4、重点代码讲解5、代码展现6、运行结果———————————————————————————————————1、有向无环图在图论中,如果一个有向图无法...

    目录:

    1、有向无环图

    2、代码结构

    3、代码学习步鄹及方法

    4、重点代码讲解

    5、代码展现

    6、运行结果

    ———————————————————————————————————

    1、有向无环图

    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。

    因为有向图中一个点经过两种路线到达另一个点未必形成环,因此有向无环图未必能转化成树,但任何有向树均为有向无环图。

    性质:有向无环图的生成树个数等于入度非零的节点的入度积。

    dcfdd881587de28752176b49a25903af.png

    2、代码结构

    f3a96194e240bd40f6bbe989a2cc10c7.png

    3、代码学习步鄹及方法

    1、本文中涉及到了Spark的Dag和设计模式中的命令

    2、Dag学习步鄹:task –> Node –> DAG –> DAGExecutor

    3、设计模式命令 http://www.voidcn.com/article/p-fxkbitkn-ov.html

    4、图解Dag类的学习步鄹

    b5830c9c2df2f89450189d0812b345c5.png

    4、重点代码讲解

    下面这段代码是核心也是最难的,如何找到父节点

    //判断Node的task节点的父节点运行状态(flase ,true)

    private def getPending: Option[T] = {

    _pending.find { name =>

    val parents = _nodes(name)

    !parents.exists(name => !_success.contains(name))

    }

    }

    1、nodes没有父节点时,!parents.exists() 为true

    2、parents.exists() 为flase时,!parents.exists() 为true

    f17705f897f33f345f419a58a13e5f7a.png

    5、代码展现

    DAG.scala

    package com.yh.dag

    import java.time.{Duration, LocalDate}

    import com.yh.nodeexecutor._

    import org.slf4j.LoggerFactory

    import scala.collection.immutable.{ListMap, ListSet}

    /** * Created by yuhui on 2016/8/25. * task --> Node --> DAG --> DAGExecutor */

    case class Node[T](task: T, parent: T*) {

    override def toString: String = {

    s"$task(${parent.mkString(",")})"

    }

    }

    case class DAG[T](nodes: Node[T]*)

    case class DAGExecutor[T](dag: DAG[T]) {

    private val LOG = LoggerFactory.getLogger(this.getClass)

    private val _nodes: Map[T, Seq[T]] = dag.nodes.map(node => (node.task, node.parent.filter(_ != null))).toMap

    private var _pending: Set[T] = ListSet()

    private var _fails = ListMap[T, String]()

    private var _success = Seq[T]()

    //判断Node的task节点的父节点运行状态(flase ,true)

    private def getPending: Option[T] = {

    _pending.find { name =>

    val parents = _nodes(name)

    !parents.exists(name => !_success.contains(name))

    }

    }

    private def fail(name: T, message: String): Unit = {

    _pending -= name

    _fails += name -> message

    for (child _nodes(child).contains(name))) {

    fail(child, s"依赖的任务无法执行: $name")

    }

    }

    private def success(name: T): Unit = {

    _pending -= name

    _success = _success :+ name

    }

    def execute(func: T => Unit): Unit = {

    _pending = _nodes.keySet

    _fails = ListMap()

    _success = Seq()

    var running = true

    while (running) {

    val taskOpt = getPending

    if (taskOpt.nonEmpty) {

    val task = taskOpt.get

    val startMills = System.currentTimeMillis()

    LOG.info("start task {}", task)

    try {

    println("=============")

    func(task) //执行executor方法

    println("+++++++++++++")

    val time = Duration.ofMillis(System.currentTimeMillis() - startMills)

    LOG.info(s"end task $task time=$time")

    success(task)

    } catch {

    case e: Throwable => fail(task, e.getMessage)

    LOG.error(e.getMessage, e)

    LOG.info(s"fail task $task")

    }

    } else {

    running = false

    }

    }

    for (name

    LOG.info(s"success task: $name")

    }

    for (name

    LOG.info(s"fail task: ${name._1} - ${name._2}")

    }

    }

    }

    object DAG {

    val allSDKDAG = new DAG[Task](

    Node(UserDetailsExecutor, WebSdkparseExecutor),

    Node(UserTagExecutor, WebSdkparseExecutor,WebSdkparseExecutor),

    Node(WebSdkparseExecutor),

    Node(UserOverviewExecutor, WebSdkparseExecutor)

    )

    def main(args: Array[String]): Unit = {

    DAGExecutor(allSDKDAG).execute { task =>task.executor("appkey": String, LocalDate.now(), LocalDate.now())}

    }

    }

    Task.scala

    package com.yh.dag

    import java.time.LocalDate

    import org.apache.spark.sql.SQLContext

    import org.slf4j.LoggerFactory

    /** * Created by yuhui on 2016/12/27. */

    abstract class Task {

    protected val LOG = LoggerFactory.getLogger(this.getClass)

    def executor(appkey: String, startDay: LocalDate, endDay: LocalDate): Unit

    def run(appkey: String, startDay: LocalDate, endDay: LocalDate): Unit = {

    executor(appkey, startDay, endDay)

    }

    }

    abstract class Executor extends Task with SQLContextAware {

    override def run(appkey: String, startDay: LocalDate, endDay: LocalDate)={}

    }

    trait SQLContextAware {

    implicit var ctx: SQLContext = _

    }

    UserDetailsExecutor.scala

    package com.yh.nodeexecutor

    import java.time.LocalDate

    import com.yh.dag.Executor

    object UserDetailsExecutor extends Executor{

    override def executor(appkey: String, startDay: LocalDate, endDay: LocalDate): Unit = {

    println("++++我的UserDetailsProcessor的执行过程++++")

    }

    }

    UserOverviewExecutor.scala

    package com.yh.nodeexecutor

    import java.time.LocalDate

    import com.yh.dag.Executor

    /** * Created by yuhui on 2016/12/27. */

    object UserOverviewExecutor extends Executor{

    override def executor(appkey: String, startDay: LocalDate, endDay: LocalDate): Unit = {

    println("++++我的UserOverviewProcessor的执行过程++++")

    }

    }

    UserTagExecutor.scala

    package com.yh.nodeexecutor

    import java.time.LocalDate

    import com.yh.dag.Executor

    /** * Created by yuhui on 2016/12/27. */

    object UserTagExecutor extends Executor{

    override def executor(appkey: String, startDay: LocalDate, endDay: LocalDate): Unit = {

    println("++++我的UserTagProcessor的执行过程++++")

    }

    }

    WebSdkparseExecutor.scala

    package com.yh.nodeexecutor

    import java.time.LocalDate

    import com.yh.dag.Executor

    /** * Created by yuhui on 2016/12/27. */

    object WebSdkparseExecutor extends Executor{

    override def executor(appkey: String, startDay: LocalDate, endDay: LocalDate): Unit = {

    println("++++我的WebSdkparseProcessor的执行过程++++")

    }

    }

    6、运行结果

    =============

    ++++我的WebSdkparseProcessor的执行过程++++

    +++++++++++++

    =============

    ++++我的UserDetailsProcessor的执行过程++++ +++++++++++++

    =============

    ++++我的UserTagProcessor的执行过程++++

    +++++++++++++

    =============

    ++++我的UserOverviewProcessor的执行过程++++ +++++++++++++

    Process finished with exit code 0

    展开全文
  • 在验证有向无环图相关的各种算法时需要一些测试数据,手动构造的话太麻烦了,于是便想着能不能自动生成一些测试数据来。这个问题的难点在于如何保证生成的图没有环,查了一下相关资料,这个可以借助拓扑排序的原理来...
  • 图图是很常见的一种结构...有向无环图有向无环图,即 Directed Acyclic Graph,属于有向图,图结构中不存在环,可用来表示事件之间依赖关系。Trie树Trie 是一种搜索树,它的 key 都为字符串,通过 key 可以找到 valu...
  • 关键字:DAG,有向无环图,算法,背包,深度优先搜索,栈,BlockChain,区块链图图是数据结构中最为复杂的一种,我在上大学的时候,图的这一章会被老师划到考试范围之外,作为我们的课后兴趣部分。但实际上,图在...
  • 有向无环图及其应用一定义 一个无环的有向图称为有向无环图简写为DAGdirected acycline graph 与有向二叉树相比有向无环图是更一般的特殊有向图实例有向树有向无环图有向图 教材179页给出了有向无环图的一个简单应用...
  • 有向无环图描述表达式

    千次阅读 2020-07-18 20:22:36
    什么是有向无环图2. 有向无环图描述表达式3. 有向无环图描述表达式的生成步骤 1. 什么是有向无环图 2. 有向无环图描述表达式 3. 有向无环图描述表达式的生成步骤 这样,比较混乱,如果式子一长,不容易看出来。 ...
  • 原标题:拓扑排序-有向无环图中的最长路径给定一个加权d irected (DAG)和一个源点s在它,找到从s中最长的距离在给定图中的所有其他顶点。一般图的最长路径问题并不像最短路径问题那么容易,因为最长路径问题没有最优...
  • 有向图的环和有向无环图

    千次阅读 2018-07-25 07:10:00
    本篇主要分享关于有向图的环和有向无环图(DAG,估计做大数据的同学到处都可以看到),所以相关概念我就不做详细介绍了。 用有向图中各个节点代表着一个又一个的任务,...
  • 有向无环图 任务的执行有依赖关系,如下图所示: 可以使用DAG(有向无环图)来维护这种依赖关系; 定义task @Data @NoArgsConstructor public class NodeTask { private String id; private Set&lt;String&...
  • 判断给定的图是不是是有向无环图,方法是应用拓扑排序,代码如下
  • 71图的定义和术语 72图的存储结构 73图的遍历 74图的连通性问题 7.5有向无环图及其应用 7.6最短路径 7.5有向无环图及其应用 75.1有向无环图 有向无环图( directed acycline graph:无环的有向图,简称DAG 图DAG图是一...
  • 有向无环图VS树

    万次阅读 2017-09-20 22:52:52
    有向无环图VS树前言: Big-man在看着终极算法的时候,突然一个和要好的朋友抛出了一数据结构有关的问题: 有向无环图 VS 树。Big-man想着他们之间有什么差别了,虽然这样想着。但是Big-man还是想着需要去分析一下的。...
  • 有向无环图 没有环,有方向的图(directed acycline graph),简称 DAG 图 有向树、有向无环图和有向图的对比图例 有向无环图是描述含有公共子式的表达式的有效工具 例如表达式:( ( a + b ) * ( b * ( c + d )...
  • 怎样造一个有向无环图

    千次阅读 2017-10-22 20:54:18
    有向无环图
  • 本篇文章给大家带来的内容是关于Python实现有向无环图的拓扑排序代码示例,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。Python有向无环图的拓扑排序拓扑排序的官方定义为:由某个集合上的一个...
  • 环和有向无环图

    2018-10-31 17:22:49
    文章目录定义有向环检测基于DFS的顶点排序拓扑排序 在和有向图相关的实际应用中,有向环特别的重要。 优先级限制下的调度问题:给定一组需要...优先级限制下的调度问题等价于计算有向无环图中所有顶点的拓扑排序。 ...
  • 图-有向无环图

    2015-03-21 09:53:25
    有向无环图 如图所示为一个非有向无环图,因为A点出发向B经C可回到A,形成一个环。将从C到A的边方向改为从A到C,则变成有向无环图。 在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这...
  • 文章目录拓扑排序有向无环图拓扑排序排序方法 有向无环图 如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个图为有向无环图(Directed Acyclic Graph, DAG)。 拓扑排序 拓扑排序是将有向无环图 G ...
  • 有向无环图DAG

    2016-02-19 09:55:03
    有向无环图DAG是图论中的概念。 算法中有时称有向无环图为DAG ( Directed Acyclic Graph)。所谓有向无环图是指:任意一条边有方向,且不存在环路的图。 spark里面有这个东西,做个笔记。
  • 有向无环图的支配树

    2019-11-16 17:12:16
    支配树:树上的任何一个点的所有祖先都是在有向无环图中这个点到树根的所有路径的必经点。 有向无环图支配树求法: 由于在有向无环图中可能有很多联通块,所有需要先记录入度,然后从每个入度为0的点开始跑bfs,每个...
  • 1:什么是DAGDAG,中文名"有向无环图"。"有向"指的是有方向,准确的说应该是同一个方向,"无环"则指够不成闭环。在DAG中,没有区块的概念,他的组成单元是一笔笔的交易,每个单元记录的是单个用户的交易,这样就省去...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,814
精华内容 3,925
关键字:

有向无环图