Dapatkah seseorang menjelaskan secara sederhana kepada saya apa itu grafik asiklik terarah?

Dapatkah seseorang menjelaskan secara sederhana kepada saya apa itu grafik asiklik terarah? Saya telah melihat di Wikipedia tetapi itu tidak benar-benar membuat saya melihat penggunaannya dalam pemrograman.

titik dengan garis menunjuk ke titik lain

graph = struktur yang terdiri dari node-node, yang saling berhubungan dengan ujung-ujungnya

diarahkan = hubungan antar node (edge) memiliki arah: A -> B tidak sama dengan B -> A

acyclic = "non-circular" = berpindah dari node ke node dengan mengikuti tepinya, Anda tidak akan pernah menemukan node yang sama untuk kedua kalinya.

Contoh yang baik dari grafik asiklik terarah adalah pohon. Perhatikan, bagaimanapun, bahwa tidak semua grafik asiklik diarahkan adalah pohon.

Saya melihat banyak jawaban yang menunjukkan arti DAG (Grafik Asiklik Terarah) tetapi tidak ada jawaban pada aplikasinya. Ini yang sangat sederhana -

Grafik prasyarat - Selama kursus teknik setiap siswa menghadapi tugas memilih mata pelajaran yang mengikuti persyaratan seperti prasyarat. Sekarang jelas bahwa Anda tidak dapat mengambil kelas pada Artificial Intelligence [B] tanpa kursus prasyarat tentang Algoritma [A]. Oleh karena itu B bergantung pada A atau dalam istilah yang lebih baik A memiliki tepi yang diarahkan ke B. Jadi untuk mencapai Node B Anda harus mengunjungi Node A. Nanti akan segera jelas bahwa setelah menambahkan semua subjek dengan prasyaratnya ke dalam grafik , itu akan berubah menjadi Grafik Asiklik Terarah.

Jika ada siklus maka Anda tidak akan pernah menyelesaikan kursus: p

Sistem perangkat lunak di universitas yang memungkinkan siswa untuk mendaftar mata kuliah dapat memodelkan mata pelajaran sebagai node untuk memastikan bahwa siswa telah mengambil mata kuliah prasyarat sebelum mendaftar untuk mata kuliah saat ini.

Profesor saya memberikan analogi ini dan ini paling membantu saya memahami DAG daripada menggunakan beberapa konsep yang rumit!

Contoh waktu nyata lainnya -> Contoh Waktu Nyata tentang bagaimana DAG dapat digunakan dalam sistem versi

Contoh penggunaan grafik asiklik terarah dalam pemrograman mencakup lebih atau kurang apa pun yang mewakili konektivitas dan kausalitas.

Misalnya, Anda memiliki pipeline komputasi yang dapat dikonfigurasi saat runtime. Sebagai salah satu contohnya, anggaplah perhitungan A, B, C, D, E, F, dan G bergantung satu sama lain: A bergantung pada C, C bergantung pada E dan F, B bergantung pada D dan E, dan D bergantung pada F. Ini dapat direpresentasikan sebagai DAG. Setelah Anda memiliki DAG di memori, Anda dapat menulis algoritme ke:

• pastikan penghitungan dievaluasi dalam urutan yang benar ( topologi )
• Jika komputasi dapat dilakukan secara paralel tetapi setiap komputasi memiliki waktu eksekusi maksimum, Anda dapat menghitung waktu eksekusi maksimum dari seluruh rangkaian

di antara banyak hal lainnya.

Di luar bidang pemrograman aplikasi, semua alat pembuatan otomatis yang layak (merek, semut, scon, dll.) Akan menggunakan DAG untuk memastikan urutan pembuatan komponen program yang tepat.

Beberapa jawaban telah memberikan contoh penggunaan grafik (misalnya pemodelan jaringan) dan Anda telah bertanya "apa hubungannya ini dengan pemrograman?".

Jawaban untuk sub-pertanyaan itu adalah bahwa itu tidak ada hubungannya dengan pemrograman. Ini ada hubungannya dengan pemecahan masalah.

Sama seperti daftar tertaut adalah struktur data yang digunakan untuk kelas masalah tertentu, grafik berguna untuk merepresentasikan hubungan tertentu. Daftar tertaut, pohon, grafik, dan struktur abstrak lainnya hanya memiliki koneksi ke pemrograman sehingga Anda dapat menerapkannya dalam kode. Mereka ada di tingkat abstraksi yang lebih tinggi. Ini bukan tentang pemrograman, ini tentang penerapan struktur data dalam solusi masalah.

Grafik Asiklik Terarah (DAG) memiliki properti berikut yang membedakannya dari grafik lain:

1. Tepi mereka menunjukkan arah.
2. Mereka tidak memiliki siklus.

Nah, saya dapat memikirkan satu kegunaan sekarang - DAG (dikenal sebagai Wait-For-Graphs - detail teknis lebih lanjut ) berguna dalam mendeteksi kebuntuan karena mereka menggambarkan ketergantungan di antara serangkaian proses dan sumber daya (keduanya adalah node di DAG) . Kebuntuan akan terjadi ketika sebuah siklus terdeteksi.

Saya berasumsi bahwa Anda sudah mengetahui terminologi grafik dasar; jika tidak, Anda harus mulai dari artikel tentang teori grafik .

Terarah mengacu pada fakta bahwa tepi (koneksi) memiliki arah. Dalam diagram, arah ini ditunjukkan oleh panah. Kebalikannya adalah grafik tidak berarah, yang ujungnya tidak menentukan arah.

Acyclic artinya, jika Anda memulai dari sembarang node X dan berjalan melalui semua sisi yang memungkinkan, Anda tidak dapat kembali ke X tanpa kembali ke sisi yang sudah digunakan.

Beberapa aplikasi:

• Spreadsheet; ini dijelaskan di artikel DAG .
• Kontrol revisi : jika Anda melihat diagram di halaman itu, Anda akan melihat bahwa evolusi kode yang dikontrol revisi diarahkan ("turun", dalam diagram ini) dan asiklik (tidak pernah kembali "ke atas") .
• Silsilah keluarga: itu diarahkan (Anda adalah anak orang tua Anda, bukan sebaliknya) dan asiklik (nenek moyang Anda tidak akan pernah bisa menjadi keturunan Anda).

DAG adalah grafik di mana segala sesuatu mengalir ke arah yang sama dan tidak ada node yang dapat mereferensikan kembali ke dirinya sendiri.

Pikirkan tentang pohon leluhur; mereka sebenarnya adalah DAG.

Semua DAG memiliki

• Nodes (tempat menyimpan data)
• Tepi Berarah (titik itu ke arah yang sama)
• Node leluhur (simpul tanpa orang tua)
• Daun (node ​​yang tidak memiliki anak)

DAG berbeda dari pohon. Dalam struktur seperti pohon, harus ada jalur unik antara setiap dua node. Di DAG, sebuah node dapat memiliki dua node induk.

Berikut artikel bagus tentang DAG . Saya harap itu membantu.

Grafik, dari segala jenis, digunakan dalam pemrograman untuk memodelkan berbagai hubungan dunia nyata yang berbeda. Misalnya, jaringan sosial sering kali diwakili oleh grafik (dalam hal ini siklik). Demikian juga, topologi jaringan, silsilah keluarga, rute penerbangan, ...

Dari perspektif kode sumber atau bahkan kode tiga alamat (TAC), Anda dapat memvisualisasikan masalah dengan sangat mudah di halaman ini ...

http://cgm.cs.mcgill.ca/~hagha/topic30/topic30.html#Exptree

Jika Anda pergi ke bagian pohon ekspresi, dan kemudian sedikit turun halaman itu menunjukkan "pengurutan topologi" dari pohon tersebut, dan algoritma untuk bagaimana mengevaluasi ekspresi.

Jadi dalam hal ini Anda dapat menggunakan DAG untuk mengevaluasi ekspresi, yang berguna karena evaluasi biasanya diinterpretasikan dan menggunakan DAG evaluator akan membuat penyusup sederhana lebih cepat pada prinsipnya karena tidak mendorong dan muncul ke tumpukan dan juga karena menghilangkan sub-ekspresi umum.

Algoritme dasar untuk menghitung DAG di Mesir kuno (yaitu bahasa Inggris) adalah ini:

1) Buat objek DAG Anda seperti itu

Anda memerlukan daftar langsung dan daftar ini menampung semua node DAG langsung dan sub-ekspresi DAG. Sub ekspresi DAG adalah Node DAG, atau Anda juga bisa menyebutnya node internal. Yang saya maksud dengan Node DAG langsung adalah jika Anda menetapkan ke variabel X maka variabel itu menjadi langsung. Sub-ekspresi umum yang kemudian menggunakan X menggunakan contoh itu. Jika X ditetapkan ke lagi maka NODE DAG BARU dibuat dan ditambahkan ke daftar langsung dan X lama dihapus sehingga sub-ekspresi berikutnya yang menggunakan X akan merujuk ke contoh baru dan dengan demikian tidak akan bertentangan dengan sub-ekspresi yang cukup gunakan nama variabel yang sama.

Setelah Anda menetapkan ke variabel X, secara kebetulan semua node sub-ekspresi DAG yang berada pada titik penugasan menjadi tidak aktif, karena tugas baru membatalkan arti sub-ekspresi menggunakan nilai lama.

class Dag {
  TList LiveList;
  DagNode Root;
}

// In your DagNode you need a way to refer to the original things that
// the DAG is computed from. In this case I just assume an integer index
// into the list of variables and also an integer index for the opertor for
// Nodes that refer to operators. Obviously you can create sub-classes for
// different kinds of Dag Nodes.
class DagNode {
  int Variable;
  int Operator;// You can also use a class
  DagNode Left;
  DagNode Right;
  DagNodeList Parents;
}

Jadi yang Anda lakukan adalah berjalan melalui pohon Anda dalam kode Anda sendiri, seperti pohon ekspresi dalam kode sumber misalnya. Panggil node yang ada XNodes misalnya.

Jadi untuk setiap XNode Anda perlu memutuskan cara menambahkannya ke DAG, dan ada kemungkinan sudah ada di DAG.

Ini adalah kode pseudo yang sangat sederhana. Tidak dimaksudkan untuk kompilasi.

DagNode XNode::GetDagNode(Dag dag) {
  if (XNode.IsAssignment) {
    // The assignment is a special case. A common sub expression is not
    // formed by the assignment since it creates a new value.

    // Evaluate the right hand side like normal
    XNode.RightXNode.GetDagNode();  


    // And now take the variable being assigned to out of the current live list
    dag.RemoveDagNodeForVariable(XNode.VariableBeingAssigned);

    // Also remove all DAG sub expressions using the variable - since the new value
    // makes them redundant
    dag.RemoveDagExpressionsUsingVariable(XNode.VariableBeingAssigned);

    // Then make a new variable in the live list in the dag, so that references to
    // the variable later on will see the new dag node instead.
    dag.AddDagNodeForVariable(XNode.VariableBeingAssigned);

  }
  else if (XNode.IsVariable) {
    // A variable node has no child nodes, so you can just proces it directly
    DagNode n = dag.GetDagNodeForVariable(XNode.Variable));
    if (n) XNode.DagNode = n;
    else {
      XNode.DagNode = dag.CreateDagNodeForVariable(XNode.Variable);
    }
    return XNode.DagNode;
  }
  else if (XNode.IsOperator) {
    DagNode leftDagNode = XNode.LeftXNode.GetDagNode(dag);
    DagNode rightDagNode = XNode.RightXNode.GetDagNode(dag);


    // Here you can observe how supplying the operator id and both operands that it
    // looks in the Dags live list to check if this expression is already there. If
    // it is then it returns it and that is how a common sub-expression is formed.
    // This is called an internal node.
    XNode.DagNode = 
      dag.GetOrCreateDagNodeForOperator(XNode.Operator,leftDagNode,RightDagNode) );

    return XNode.DagNode;
  }
}

Jadi itulah salah satu cara untuk melihatnya. Penjelajahan dasar dari pohon dan hanya menambahkan dan merujuk ke simpul Dag saat berjalan. Akar dag adalah apa pun DagNode yang dikembalikan akar pohon misalnya.

Tentunya prosedur contoh dapat dipecah menjadi bagian-bagian yang lebih kecil atau dibuat sebagai sub-kelas dengan fungsi virtual.

Sedangkan untuk menyortir Dag, Anda melewati setiap DagNode dari kiri ke kanan. Dengan kata lain ikuti tepi kiri DagNodes, lalu tepi sisi kanan. Nomor-nomor tersebut ditetapkan secara terbalik. Dengan kata lain ketika Anda mencapai DagNode tanpa anak, tetapkan Node tersebut nomor pengurutan saat ini dan tambahkan nomor pengurutan, sehingga rekursi melepaskan nomor yang ditetapkan dalam urutan yang meningkat.

Contoh ini hanya menangani pohon dengan node yang memiliki nol atau dua turunan. Jelas beberapa pohon memiliki node dengan lebih dari dua anak sehingga logikanya masih sama. Alih-alih menghitung kiri dan kanan, hitung dari kiri ke kanan dll ...

// Most basic DAG topological ordering example.
void DagNode::OrderDAG(int* counter) {
  if (this->AlreadyCounted) return;

  // Count from left to right
  for x = 0 to this->Children.Count-1
    this->Children[x].OrderDag(counter)

  // And finally number the DAG Node here after all
  // the children have been numbered
  this->DAGOrder = *counter;

  // Increment the counter so the caller gets a higher number
  *counter = *counter + 1;

  // Mark as processed so will count again
  this->AlreadyCounted = TRUE;
}

Jika Anda tahu pohon apa itu dalam pemrograman, maka DAG dalam pemrograman serupa tetapi memungkinkan sebuah node memiliki lebih dari satu induk. Ini bisa berguna ketika Anda ingin membiarkan sebuah node dikelompokkan di bawah lebih dari satu orang tua, namun tidak memiliki masalah kekacauan grafik umum dengan siklus yang diikat. Anda masih dapat menavigasi DAG dengan mudah, tetapi ada beberapa cara untuk kembali ke akar (karena mungkin ada lebih dari satu induk). Sebuah DAG tunggal secara umum bisa memiliki banyak akar tetapi dalam praktiknya mungkin lebih baik hanya menempel dengan satu akar, seperti pohon. Jika Anda memahami pewarisan tunggal vs. ganda di OOP, Anda tahu pohon vs. DAG. Saya sudah menjawab ini di sini .

Namanya memberi tahu Anda sebagian besar dari apa yang perlu Anda ketahui tentang definisinya: Ini adalah grafik di mana setiap sisi hanya mengalir dalam satu arah dan begitu Anda merangkak menuruni tepi, jalur Anda tidak akan pernah mengembalikan Anda ke simpul yang baru saja Anda tinggalkan.

Saya tidak dapat berbicara dengan semua kegunaan (Wikipedia membantu di sana), tetapi bagi saya DAG sangat berguna saat menentukan ketergantungan antar sumber daya. Mesin gim saya misalnya mewakili semua sumber daya yang dimuat (bahan, tekstur, shader, teks biasa, json yang diuraikan, dll.) Sebagai DAG tunggal. Contoh:

Materi adalah program N GL, yang masing-masing membutuhkan dua shader, dan setiap shader membutuhkan sumber shader teks biasa. Dengan merepresentasikan sumber daya ini sebagai DAG, saya dapat dengan mudah meminta grafik untuk sumber daya yang ada untuk menghindari beban duplikat. Katakanlah Anda ingin beberapa bahan menggunakan shader vertex dengan kode sumber yang sama. Akan sia-sia jika memuat ulang sumber dan mengompilasi ulang shader untuk setiap penggunaan saat Anda bisa membuat edge baru ke resource yang ada. Dengan cara ini Anda juga dapat menggunakan grafik untuk menentukan apakah ada sesuatu yang bergantung pada sumber daya, dan jika tidak, hapus dan kosongkan memorinya, sebenarnya ini terjadi secara otomatis.

Dengan ekstensi, DAG berguna untuk mengekspresikan pipeline pemrosesan data. Sifat asiklik berarti Anda dapat dengan aman menulis kode pemrosesan kontekstual yang dapat mengikuti petunjuk ke tepi dari simpul tanpa pernah bertemu kembali dengan simpul yang sama. Bahasa pemrograman visual seperti VVVV , Max MSP atau antarmuka berbasis node Autodesk Maya semuanya bergantung pada DAG.

Grafik asiklik terarah berguna ketika Anda ingin merepresentasikan ... grafik asiklik terarah! Contoh kanonik adalah silsilah keluarga atau silsilah.