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] <github-actions[bot]@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/[email protected]/dist/react-with-addons.min.js"></script>
+ <script
src="//cdn.jsdelivr.net/npm/[email protected]/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/[email protected]/dist/react-with-addons.min.js"></script>
<script
src="//cdn.jsdelivr.net/npm/[email protected]/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/[email protected]/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() {
![https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG01.png?raw=true"](https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG01.png?raw=true"){kind=link}
![https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG02.png?raw=true"](https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG02.png?raw=true"){kind=link}
![https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG03.png?raw=true"](https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG03.png?raw=true"){kind=link}
![https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG04.png?raw=true"](https://github.com/QuakeWang/incubator-dolphinscheduler-website/blob/patch-1/img/DAG/DAG04.png?raw=true"){kind=link}