You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@dolphinscheduler.apache.org by gi...@apache.org on 2021/05/12 12:47:27 UTC
[dolphinscheduler-website] branch asf-site updated: Automated
deployment: e4a4e180996dca6c4884f5c883cdc6119cf22a4b
This is an automated email from the ASF dual-hosted git repository.
github-bot pushed a commit to branch asf-site
in repository https://gitbox.apache.org/repos/asf/dolphinscheduler-website.git
The following commit(s) were added to refs/heads/asf-site by this push:
new b5a8128 Automated deployment: e4a4e180996dca6c4884f5c883cdc6119cf22a4b
b5a8128 is described below
commit b5a81284f7ef4368bbf3e21a72bfc3c607cc6a61
Author: github-actions[bot] <gi...@users.noreply.github.com>
AuthorDate: Wed May 12 12:47:20 2021 +0000
Automated deployment: e4a4e180996dca6c4884f5c883cdc6119cf22a4b
---
build/{blog.00152d1.js => blog.c9ac780.js} | 2 +-
en-us/blog/DAG.html | 157 +++++++++++++++++++++++++++++
en-us/blog/DAG.json | 6 ++
en-us/blog/index.html | 4 +-
img/DAG/DAG01.png | Bin 0 -> 20119 bytes
img/DAG/DAG02.png | Bin 0 -> 22772 bytes
img/DAG/DAG03.png | Bin 0 -> 22570 bytes
img/DAG/DAG04.png | Bin 0 -> 17224 bytes
zh-cn/blog/index.html | 2 +-
9 files changed, 167 insertions(+), 4 deletions(-)
diff --git a/build/blog.00152d1.js b/build/blog.c9ac780.js
similarity index 63%
rename from build/blog.00152d1.js
rename to build/blog.c9ac780.js
index e048960..0c80420 100644
--- a/build/blog.00152d1.js
+++ b/build/blog.c9ac780.js
@@ -1 +1 @@
-webpackJsonp([1],{1:function(e,t){e.exports=React},2:function(e,t){e.exports=ReactDOM},401:function(e,t,n){e.exports=n(402)},402:function(e,t,n){"use strict";function r(e){return e&&e.__esModule?e:{default:e}}function a(e,t){if(!(e instanceof t))throw new TypeError("Cannot call a class as a function")}function o(e,t){if(!e)throw new ReferenceError("this hasn't been initialised - super() hasn't been called");return!t||"object"!=typeof t&&"function"!=typeof t?e:t}function l(e,t){if("functi [...]
\ No newline at end of file
+webpackJsonp([1],{1:function(e,t){e.exports=React},2:function(e,t){e.exports=ReactDOM},401:function(e,t,n){e.exports=n(402)},402:function(e,t,n){"use strict";function r(e){return e&&e.__esModule?e:{default:e}}function a(e,t){if(!(e instanceof t))throw new TypeError("Cannot call a class as a function")}function o(e,t){if(!e)throw new ReferenceError("this hasn't been initialised - super() hasn't been called");return!t||"object"!=typeof t&&"function"!=typeof t?e:t}function l(e,t){if("functi [...]
\ No newline at end of file
diff --git a/en-us/blog/DAG.html b/en-us/blog/DAG.html
new file mode 100644
index 0000000..2694097
--- /dev/null
+++ b/en-us/blog/DAG.html
@@ -0,0 +1,157 @@
+<!DOCTYPE html>
+<html lang="en">
+<head>
+ <meta charset="UTF-8">
+ <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
+ <meta name="keywords" content="DAG">
+ <meta name="description" content="DAG">
+ <title>DAG</title>
+ <link rel="shortcut icon" href="/img/favicon.ico">
+ <link rel="stylesheet" href="/build/vendor.82f7db8.css">
+ <link rel="stylesheet" href="/build/blog.md.fd8b187.css">
+</head>
+<body>
+ <div id="root"><div class="blog-detail-page" data-reactroot=""><header class="header-container header-container-dark"><div class="meetup-container meetup-container-dark"><a href="https://www.meetup.com/dolphinscheduler/events/277413098/"><p>2021-05-15 14:00（PDT） Apache DolphinScheduler & Apache ShardingSphere Global Online co-Meetup is coming!</p></a></div><div class="header-body"><a href="/en-us/index.html"><img class="logo" src="/img/hlogo_white.svg"/></a><div class="search searc [...]
+<h3>Reviewing the basics：</h3>
+<h4>Graph traversal：</h4>
+<p>A graph traversal is a visit to all the vertices in a graph once and only once, starting from a vertex in the graph and following some search method along the edges of the graph.</p>
+<p>Note : the tree is a special kind of graph, so tree traversal can actually be seen as a special kind of graph traversal.</p>
+<h4>There are two main algorithms for graph traversal</h4>
+<h5>Breadth First Search (BFS)</h5>
+<p>The basic idea: first visit the starting vertex v, then from v, visit each of v's unvisited adjacent vertices w1, w2 , ... ,wi, then visit all the unvisited adjacent vertices of w1, w2, ... , wi in turn; from these visited vertices, visit all their unvisited adjacent vertices until all vertices in the graph have been visited. and from these visited vertices, visit all their unvisited adjacent vertices, until all vertices in the graph have been visited. If there are still vertices in t [...]
+<h5>Depth First Search (DFS)</h5>
+<p>The basic idea: first visit a starting vertex v in the graph, then from v, visit any vertex w~1~ that is adjacent to v and has not been visited, then visit any vertex w~2~ that is adjacent to w~1~ and has not been visited ...... Repeat the above process. When it is no longer possible to go down the graph, go back to the most recently visited vertex, and if it has adjacent vertices that have not been visited, continue the search process from that point until all vertices in the graph h [...]
+<h4>Example</h4>
+<p>In the diagram below, if the breadth first search (BFS) is used, the traversal is as follows: <code>1 2 5 3 4 6 7</code>. If the depth first search (DFS) is used, the traversal is as follows <code>1 2 3 4 5 6 7</code>.</p>
+<p><img src="https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG01.png?raw=true" alt="DAG01"></p>
+<h3>Topological Sorting</h3>
+<p>The definition of topological ordering on Wikipedia is :</p>
+<p>For any Directed Acyclic Graph (DAG), the topological sorting is a linear sorting of all its nodes (there may be multiple such node sorts in the same directed graph). This sorting satisfies the condition that for any two nodes U and V in the graph, if there is a directed edge pointing from U to V, then U must appear ahead of V in the topological sorting.</p>
+<p><strong>In layman's terms: Topological sorting is a linear sequence of all vertices of a directed acyclic graph (DAG), which must satisfy two conditions :</strong></p>
+<ul>
+<li>Each vertex appears and only appears once.</li>
+<li>If there is a path from vertex A to vertex B, then vertex A appears before vertex B in the sequence.</li>
+</ul>
+<p><strong>How to find out its topological sort? Here is a more commonly used method :</strong></p>
+<p>Before introducing this method, it is necessary to add the concepts of indegree and outdegree of a directed graph node.</p>
+<p>Assuming that there is no directed edge whose starting point and ending point are the same node in a directed graph, then:</p>
+<p>In-degree: Assume that there is a node V in the graph, and the in-degree is the number of edges that start from other nodes and end at V. That is, the number of all directed edges pointing to V.</p>
+<p>Out-degree: Assuming that there is a node V in the directed graph, the out-degree is the number of edges that currently have a starting point of V and point to other nodes. That is, the number of edges issued by V.</p>
+<ol>
+<li>Select a vertex with an in-degree of 0 from the DAG graph and output it.</li>
+<li>Delete the vertex and all directed edges starting with it from the graph.</li>
+<li>Repeat 1 and 2 until the current DAG graph is empty or there are no vertices of degree 0 in the current graph. The latter case indicates that a ring must exist in the directed graph.</li>
+</ol>
+<p><strong>For example, the following DAG graph :</strong></p>
+<p><img src="https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG02.png?raw=true" alt="DAG02"></p>
+<p>In degree of node 1: 0, out degree: 2</p>
+<p>In degree of node 2: 1, out degree: 2</p>
+<p>In degree of node 3: 2, out degree: 1</p>
+<p>In degree of node 4: 2, out degree: 2</p>
+<p>In degree of node 5: 2, out degree: 0</p>
+<p><strong>Its topological sorting process is:</strong></p>
+<p><img src="https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG03.png?raw=true" alt="DAG03"></p>
+<p>Therefore, the result of topological sorting is: {1,2,4,3,5}.</p>
+<p>If there is no node 2 —> the arrow of node 4, then it is as follows:</p>
+<p><img src="https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG04.png?raw=true" alt="DAG04"></p>
+<p>We can get its topological sort as: {1,2,4,3,5} or {1,4,2,3,5}, that is, for the same DAG graph, there may be multiple topological sort results .</p>
+<p>Topological sorting is mainly used to solve the dependency problem in directed graphs.</p>
+<p>**When talking about the implementation, it is necessary to insert the following : **</p>
+<p>From this we can further derive an improved depth first search or breadth first search algorithm to accomplish topological sorting. Taking the breadth first search as an example, the only difference between this improved algorithm and the ordinary breadth first search is that we should save the degree of entry corresponding to each node and select the node with a degree of entry of 0 at each level of the traversal to start the traversal (whereas the ordinary breadth first search has n [...]
+<ol>
+<li>Initialize a Map or similar data structure to save the in-degree of each node.</li>
+<li>For the child nodes of each node in the graph, add 1 to the in-degree of its child nodes.</li>
+<li>Select any node with an in-degree of 0 to start traversal, and add this node to the output.</li>
+<li>For each node traversed, update the in-degree of its child node: subtract 1 from the in-degree of the child node.</li>
+<li>Repeat step 3 until all nodes have been traversed.</li>
+<li>If it is impossible to traverse all the nodes, it means that the current graph is not a directed acyclic graph. There is no topological sort.</li>
+</ol>
+<p><strong>The core Java code for breadth first search topological sorting is as follows :</strong></p>
+<pre><code class="language-java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">TopologicalSort</span> </span>{
+ <span class="hljs-comment">/**
+ * Determine whether there is a ring and the result of topological sorting
+ *
+ * Only directed acyclic graph (DAG) has topological sorting
+ * The main methods of breadth first search:
+ * 1、Iterate over all the vertices in the graph, and put the vertices whose in-degree is 0 into the queue.
+ * 2、A vertex is polled from the queue, and the in-degree of the adjacent point of the vertex is updated (minus 1). If the in-degree of the adjacent point is reduced by 1 and then equals to 0, the adjacent point is entered into the queue.
+ * 3、Keep executing step 2 until the queue is empty.
+ * If it is impossible to traverse all the vertics, it means that the current graph is not a directed acyclic graph. There is no topological sort.
+ *
+ *
+ * <span class="hljs-doctag">@return</span> key returns the state, true if successful (no-loop), value if failed (loop), value is the result of topological sorting (could be one of these)
+ */</span>
+ <span class="hljs-keyword">private</span> Map.Entry<Boolean, List<Vertex>> topologicalSort() {
+ <span class="hljs-comment">// Node queue with an in-degree of 0</span>
+ Queue<Vertex> zeroIndegreeVertexQueue = <span class="hljs-keyword">new</span> LinkedList<>();
+ <span class="hljs-comment">// Save the results</span>
+ List<Vertex> topoResultList = <span class="hljs-keyword">new</span> ArrayList<>();
+ <span class="hljs-comment">// Save the nodes whose in-degree is not 0</span>
+ Map<Vertex, Integer> notZeroIndegreeVertexMap = <span class="hljs-keyword">new</span> HashMap<>();
+
+ <span class="hljs-comment">// Scan all nodes and queue vertices with in-degree 0</span>
+ <span class="hljs-keyword">for</span> (Map.Entry<Vertex, VertexInfo> vertices : verticesMap.entrySet()) {
+ Vertex vertex = vertices.getKey();
+ <span class="hljs-keyword">int</span> inDegree = getIndegree(vertex);
+
+ <span class="hljs-keyword">if</span> (inDegree == <span class="hljs-number">0</span>) {
+ zeroIndegreeVertexQueue.add(vertex);
+ topoResultList.add(vertex);
+ } <span class="hljs-keyword">else</span> {
+ notZeroIndegreeVertexMap.put(vertex, inDegree);
+ }
+ }
+
+ <span class="hljs-comment">// After scanning, there is no node with an in-degree of 0, indicating that there is a loop, and return directly</span>
+ <span class="hljs-keyword">if</span>(zeroIndegreeVertexQueue.isEmpty()){
+ <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> AbstractMap.SimpleEntry(<span class="hljs-keyword">false</span>, topoResultList);
+ }
+
+ <span class="hljs-comment">// Using the topology algorithm, delete the node with an in-degree of 0 and its associated edges</span>
+ <span class="hljs-keyword">while</span> (!zeroIndegreeVertexQueue.isEmpty()) {
+ Vertex v = zeroIndegreeVertexQueue.poll();
+ <span class="hljs-comment">// Get the adjacent nodes</span>
+ Set<Vertex> subsequentNodes = getSubsequentNodes(v);
+
+ <span class="hljs-keyword">for</span> (Vertex subsequentVertex : subsequentNodes) {
+
+ Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);
+
+ <span class="hljs-keyword">if</span>(--degree == <span class="hljs-number">0</span>){
+ topoResultList.add(subsequentVertex);
+ zeroIndegreeVertexQueue.add(subsequentVertex);
+ notZeroIndegreeVertexMap.remove(subsequentVertex);
+ }<span class="hljs-keyword">else</span>{
+ notZeroIndegreeVertexMap.put(subsequentVertex, degree);
+ }
+
+ }
+ }
+
+ <span class="hljs-comment">//notZeroIndegreeVertexMap If it is empty, it means there is no ring</span>
+ AbstractMap.SimpleEntry resultMap = <span class="hljs-keyword">new</span> AbstractMap.SimpleEntry(notZeroIndegreeVertexMap.size() == <span class="hljs-number">0</span> , topoResultList);
+ <span class="hljs-keyword">return</span> resultMap;
+
+ }
+}
+</code></pre>
+<p><em>Notice: the output result is one of the topological sorting sequences of the graph.</em></p>
+<p>Every time a vertex is taken from a set with an in-degree of 0, there is no special rule for taking out. The order of taking the vertices will result in a different topological sorting sequence (if the graph has multiple sorting sequences).</p>
+<p>Since each vertex is outputted with the edges starting from it removed. If the graph has V vertices and E edges, the time complexity of the algorithm is typically O(V+E). The final key of the algorithm as implemented here returns the state, true if it succeeds (no rings), with rings if it fails, and value if there are no rings as the result of topological sorting (which may be one of these). Note that the output is one of the topologically sorted sequences of the graph.</p>
+</section><footer class="footer-container"><div class="footer-body"><div><h3>About us</h3><h4>Do you need feedback? Please contact us through the following ways.</h4></div><div class="contact-container"><ul><li><img class="img-base" src="/img/emailgray.png"/><img class="img-change" src="/img/emailblue.png"/><a href="/en-us/community/development/subscribe.html"><p>Email List</p></a></li><li><img class="img-base" src="/img/twittergray.png"/><img class="img-change" src="/img/twitterblue.png [...]
+ <script src="//cdn.jsdelivr.net/npm/react@15.6.2/dist/react-with-addons.min.js"></script>
+ <script src="//cdn.jsdelivr.net/npm/react-dom@15.6.2/dist/react-dom.min.js"></script>
+ <script>window.rootPath = '';</script>
+ <script src="/build/vendor.abc30e3.js"></script>
+ <script src="/build/blog.md.57874be.js"></script>
+ <script>
+ var _hmt = _hmt || [];
+ (function() {
+ var hm = document.createElement("script");
+ hm.src = "https://hm.baidu.com/hm.js?4e7b4b400dd31fa015018a435c64d06f";
+ var s = document.getElementsByTagName("script")[0];
+ s.parentNode.insertBefore(hm, s);
+ })();
+ </script>
+</body>
+</html>
\ No newline at end of file
diff --git a/en-us/blog/DAG.json b/en-us/blog/DAG.json
new file mode 100644
index 0000000..24d8153
--- /dev/null
+++ b/en-us/blog/DAG.json
@@ -0,0 +1,6 @@
+{
+ "filename": "DAG.md",
+ "__html": "<h2>Big Data Workflow Task Scheduling - Directed Acyclic Graph (DAG) for Topological Sorting</h2>\n<h3>Reviewing the basics：</h3>\n<h4>Graph traversal：</h4>\n<p>A graph traversal is a visit to all the vertices in a graph once and only once, starting from a vertex in the graph and following some search method along the edges of the graph.</p>\n<p>Note : the tree is a special kind of graph, so tree traversal can actually be seen as a special kind of graph traversal.</p>\n<h4>T [...]
+ "link": "/dist/en-us/blog/DAG.html",
+ "meta": {}
+}
\ No newline at end of file
diff --git a/en-us/blog/index.html b/en-us/blog/index.html
index c5adfd9..3ea8ba0 100644
--- a/en-us/blog/index.html
+++ b/en-us/blog/index.html
@@ -11,12 +11,12 @@
<link rel="stylesheet" href="/build/blog.acc2955.css">
</head>
<body>
- <div id="root"><div class="blog-list-page" data-reactroot=""><header class="header-container header-container-dark"><div class="meetup-container meetup-container-dark"><a href="https://www.meetup.com/dolphinscheduler/events/277413098/"><p>2021-05-15 14:00（PDT） Apache DolphinScheduler & Apache ShardingSphere Global Online co-Meetup is coming!</p></a></div><div class="header-body"><a href="/en-us/index.html"><img class="logo" src="/img/hlogo_white.svg"/></a><div class="search search- [...]
+ <div id="root"><div class="blog-list-page" data-reactroot=""><header class="header-container header-container-dark"><div class="meetup-container meetup-container-dark"><a href="https://www.meetup.com/dolphinscheduler/events/277413098/"><p>2021-05-15 14:00（PDT） Apache DolphinScheduler & Apache ShardingSphere Global Online co-Meetup is coming!</p></a></div><div class="header-body"><a href="/en-us/index.html"><img class="logo" src="/img/hlogo_white.svg"/></a><div class="search search- [...]
<script src="//cdn.jsdelivr.net/npm/react@15.6.2/dist/react-with-addons.min.js"></script>
<script src="//cdn.jsdelivr.net/npm/react-dom@15.6.2/dist/react-dom.min.js"></script>
<script>window.rootPath = '';</script>
<script src="/build/vendor.abc30e3.js"></script>
- <script src="/build/blog.00152d1.js"></script>
+ <script src="/build/blog.c9ac780.js"></script>
<script>
var _hmt = _hmt || [];
(function() {
diff --git a/img/DAG/DAG01.png b/img/DAG/DAG01.png
new file mode 100644
index 0000000..0facc98
Binary files /dev/null and b/img/DAG/DAG01.png differ
diff --git a/img/DAG/DAG02.png b/img/DAG/DAG02.png
new file mode 100644
index 0000000..fe95588
Binary files /dev/null and b/img/DAG/DAG02.png differ
diff --git a/img/DAG/DAG03.png b/img/DAG/DAG03.png
new file mode 100644
index 0000000..628ad1b
Binary files /dev/null and b/img/DAG/DAG03.png differ
diff --git a/img/DAG/DAG04.png b/img/DAG/DAG04.png
new file mode 100644
index 0000000..27334ce
Binary files /dev/null and b/img/DAG/DAG04.png differ
diff --git a/zh-cn/blog/index.html b/zh-cn/blog/index.html
index a047902..d5c3810 100644
--- a/zh-cn/blog/index.html
+++ b/zh-cn/blog/index.html
@@ -16,7 +16,7 @@
<script src="//cdn.jsdelivr.net/npm/react-dom@15.6.2/dist/react-dom.min.js"></script>
<script>window.rootPath = '';</script>
<script src="/build/vendor.abc30e3.js"></script>
- <script src="/build/blog.00152d1.js"></script>
+ <script src="/build/blog.c9ac780.js"></script>
<script>
var _hmt = _hmt || [];
(function() {