directed-acyclic-graphs 相关问题

有向非循环图出现在许多数据结构中，例如分布式版本控制系统中的变更集图。

指出dag的界限的索引我正在编写一个程序，以找到最长的DAG路径，并带有标准的输入。我终于让它进行了编译，它说它由于我的数组列表，BU ...

import java.io.*; import java.util.*; public class countLongPaths { static final int NINF = Integer.MIN_VALUE; public class AdjListNode { private int v; private int weight; AdjListNode(int inV, int inW) { v = inV; weight = inW; } int getV() { return v; } int getWeight() { return weight; } }//end of adj list class public class Graph { private int V; private LinkedList<AdjListNode>adj[]; //set up graph with given number of verticies Graph(int v) { V=v; adj = new LinkedList[V]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList<AdjListNode>(); } //function to add edges to graph void addEdge(int u, int v, int weight) { AdjListNode node = new AdjListNode(v,weight); adj[u].add(node);// Add v to u's list } //function to set order to go through vertices void setOrder(int v, Boolean visited[], Stack stack) { //Set node to visited when on it visited[v] = true; Integer i; //for all nodes connected to current repeat Iterator<AdjListNode> it = adj[v].iterator(); while (it.hasNext()) { AdjListNode node =it.next(); if (!visited[node.getV()]) setOrder(node.getV(), visited, stack); } //Once done with current add it to the stack stack.push(new Integer(v)); } //function to find longest paths from s int longestPath() { Stack stack = new Stack(); int LP[] = new int[V]; //set all vertices to unvisited Boolean visited[] = new Boolean[V]; for(int i = 1; i <= V; i++) visited[i] = false; //call set order function from each vertex for (int i = 1; i <= V; i++) { if(visited[i] == false) setOrder(i, visited, stack); } //initialize distaces to all verices as negative infinity //set distace to source to 0 LP[1] = 0; for(int i = 2; i <= V; i++) LP[i] = NINF; //go through vertices in order while(stack.empty() == false) { int u = (int)stack.pop(); //update LP for adj vertices Iterator<AdjListNode> it; if (LP[u] != NINF) { it = adj[u].iterator(); while (it.hasNext()) { AdjListNode i = it.next(); if(LP[i.getV()] < LP[u] + i.getWeight()) LP[i.getV()] = LP[u] + i.getWeight(); } } } return LP[V]; } }//end of graph class //Method to make a new graph public Graph newGraph(int number) { return new Graph(number); } public static void main(String[]args) { countLongPaths n = new countLongPaths(); int GN = 0; int count = 1; Scanner scan = new Scanner(System.in); GN = scan.nextInt(); while (count<= GN) { int N = 0;// nodes int M = 0;//edges N = scan.nextInt(); M = scan.nextInt(); //setup a new graph Graph g = n.newGraph(N); //set edges for new graph for(int i = 1; i <= M; i ++) { int I = scan.nextInt(); int J = scan.nextInt(); int W = scan.nextInt(); g.addEdge(I, J, W); } int dist = 0; dist = g.longestPath(); System.out.println("graph number: " + count); System.out.println("longest path: " + dist); System.out.println("number of longest paths: "); System.out.println(); count++; }//end of while }//end main }//end program

java directed-acyclic-graphs longest-path

回答 1 投票 0

我可以如何根据另一个任务进行任务，但也只能在某个时间运行？我有两个任务。 T05：30-我希望每天05:30运行。 T08：30-我希望每天08:30运行，但前提是今天T05：30成功。这可以在气流中实现吗？它

T05：30-我希望每天05:30运行。

python airflow task scheduled-tasks directed-acyclic-graphs

回答 0 投票 0

HourlyDAG ExternalTaskSensor检查外部DAG始终以“重新安排”模式

我有一个小时的dag（“ dag_b”）取决于外部dag的完整（“ dag_a”，也是一个小时的dag，比'execution_delta'中提到的“ dag_b”提前10分钟开始，因此想使用

dependencies external directed-acyclic-graphs

回答 1 投票 0

最小化有向无环图中颜色过渡的贪婪算法

我正在使用有向无环图（DAG），其中：一些节点已经分配了颜色（例如红色）。有些节点是无色的，可以选择指定颜色。输入和输出n...