مرحبا بالجميع! في الأسبوع القادم ، ستبدأ الدروس في المجموعة الجديدة من دورة "خوارزميات للمطورين" . في هذا الصدد ، نشارككم ترجمة مادة صغيرة جدًا ولكنها مثيرة للاهتمام إلى حد ما.
أردت أن أبدأ هذه السلسلة من المقالات بهيكل بيانات نعلمه جميعًا كمطورين ، لكن من الممكن أننا لا نعرف حتى كيف يعمل.
"الرسم البياني الحاد الاتجاه؟ لم يسمع بهذا من قبل. لا تعتقد أنك تعرف كل شيء عني! "، يمكنك القول ، لكن هذا الرسم البياني هو الذي يجعل التحكم في الإصدار ممكنًا. نعم ، جيت هو الرسم البياني acyclic. في هذه المقالة ، سوف أطلعكم على معرفة الرسوم البيانية الحلقية الموجهة (DAGs) ، ثم أريكم كيفية كتابة رسالتك.
ما هو DAG؟
إذن ماذا يعني ذلك؟ DAG عبارة عن رسم بياني أحادي الاتجاه حيث لا يمكن اعتبار أي عنصر تابعًا. الكثير منا على دراية بالقوائم والأشجار والرسوم البيانية المرتبطة. DAG يشبه إلى حد كبير الأول والثاني في تنفيذ الثالث.
يبدو وكأنه شجرة ، ولكن ليس تمامافي أقل أشكاله ، تحتوي DAG على 4 مكونات:
- العقد. انهم تخزين البيانات.
- الحواف الاتجاهية : الأسهم التي تشير في اتجاه واحد (ما يجعل بنية البيانات هذه على عكس الاتجاهات الأخرى).
- عقدة سلف "عظيمة" بدون آباء . (حقيقة ممتعة: يتم توجيه معظم أشجار الأسلاف في الواقع الرسوم البيانية الحلقية ، وليس الأشجار ، لأنه في بعض الأحيان "يتزوج أبناء العمومة من بعضهم البعض")
- الأوراق. أو العقد بدون العقد التابعة.
دعنا نكتب الرسم البياني الحاد الموجهالآن دعنا نكتب الكود. أولاً ، قم بإنشاء مُنشئ ذو خاصيتين واسمه DAG.
function DAG() { this.nodes = []; this.vertices = {}; }
إنشاء طريقة لإضافة العقد. انظر ماذا فعلت هنا؟
DAG.prototype.add = function(node) { if (!node) { return; } if (this.vertices[node]) { return this.vertices[node]; } const vertex = { node: node, incoming: {}, incomingNodes: [], hasOutgoing: false, value: null }; this.vertices[node] = vertex; this.nodes.push(node); return vertex; };
كيف يعمل؟ كائن
vertex هو حيث يحدث كل السحر. نضيف عقدة ، كائن ذو عقد واردة ، ومصفوفة بكل أسمائهم ، متغير من النوع Boolean يشير إلى ما إذا كانت العقدة تشير إلى شيء أم لا ، وقيمته. سوف ننتقل إلى هذا لاحقًا.
الآن دعونا نضيف بعض الحواف وربط العقد معا. قبل أن نتمكن من القيام بذلك ، يجب أن ننشئ وظيفة مساعدة تتحقق مما إذا قمنا بزيارة هذه العقدة أم لا. دعنا ندعو لها
visit .
function visit(vertex, fn, visited, path) { const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) { visited = {}; } if (!path) { path = []; } if (visited.hasOwnProperty(name)) { return; } path.push(name); visited[name] = true; for (i = 0; i < len; i++) { visit(vertices[names[i]], fn, visited, path); } fn(vertex, path); path.pop(); }
يحدث ما يلي:
DAG.prototype.addEdge = function(fromName, toName) { if (!fromName || !toName || fromName === toName) { return; } const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) { return; } function checkCycle(vertex, path) { if (vertex.name === toName) { throw new Error(“Theres a cycle foo!!!!!“)); } } visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); };
حان الوقت للاشادة
بينما كنت أدرس مواد لكتابة هذا المقال ، قرأت بعض الرسائل الرائعة من أناس أذكياء بشكل مثير للدهشة ، ونتيجة لذلك ، تم تلقي معظم المعلومات منهم. حصلت على بعض المعلومات النظرية من
هذا المنشور الجيد التنظيم على DAG والتحكم في الإصدار. الكود المقدم هنا مستوحى من مصادر
emberjs ومؤلفيها. لقد تعلمت الكثير من المقالات والمنشورات الأخرى حول DAG في مدونات العديد من الأشخاص الرائعين.
شكرا للقراءة!