CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Directed acyclic graph - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"5320c6f1-58ae-44bd-91da-1c98cbfa10a2","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Directed_acyclic_graph","wgTitle":"Directed acyclic graph","wgCurRevisionId":1261432631,"wgRevisionId":1261432631,"wgArticleId":204002,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: overridden setting","Articles with short description","Short description matches Wikidata","Good articles","Commons category link is on Wikidata","Directed graphs","Directed acyclic graphs"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Directed_acyclic_graph","wgRelevantArticleId":204002,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[], "wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":50000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1195339","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false, "wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging", "ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.18"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/1200px-Tred-G.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1648"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/800px-Tred-G.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="1098"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/640px-Tred-G.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="879"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Directed acyclic graph - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Directed_acyclic_graph"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Directed_acyclic_graph&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Directed_acyclic_graph rootpage-Directed_acyclic_graph skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Directed+acyclic+graph" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Directed+acyclic+graph" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Directed+acyclic+graph" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Directed+acyclic+graph" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definitions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definitions</span> </div> </a> <ul id="toc-Definitions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Mathematical_properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Mathematical_properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Mathematical properties</span> </div> </a> <button aria-controls="toc-Mathematical_properties-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Mathematical properties subsection</span> </button> <ul id="toc-Mathematical_properties-sublist" class="vector-toc-list"> <li id="toc-Reachability_relation,_transitive_closure,_and_transitive_reduction" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Reachability_relation,_transitive_closure,_and_transitive_reduction"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Reachability relation, transitive closure, and transitive reduction</span> </div> </a> <ul id="toc-Reachability_relation,_transitive_closure,_and_transitive_reduction-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Topological_ordering" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Topological_ordering"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Topological ordering</span> </div> </a> <ul id="toc-Topological_ordering-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Combinatorial_enumeration" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Combinatorial_enumeration"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Combinatorial enumeration</span> </div> </a> <ul id="toc-Combinatorial_enumeration-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Related_families_of_graphs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Related_families_of_graphs"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Related families of graphs</span> </div> </a> <ul id="toc-Related_families_of_graphs-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Computational_problems" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Computational_problems"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Computational problems</span> </div> </a> <button aria-controls="toc-Computational_problems-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Computational problems subsection</span> </button> <ul id="toc-Computational_problems-sublist" class="vector-toc-list"> <li id="toc-Topological_sorting_and_recognition" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Topological_sorting_and_recognition"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Topological sorting and recognition</span> </div> </a> <ul id="toc-Topological_sorting_and_recognition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Construction_from_cyclic_graphs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Construction_from_cyclic_graphs"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Construction from cyclic graphs</span> </div> </a> <ul id="toc-Construction_from_cyclic_graphs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Transitive_closure_and_transitive_reduction" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Transitive_closure_and_transitive_reduction"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Transitive closure and transitive reduction</span> </div> </a> <ul id="toc-Transitive_closure_and_transitive_reduction-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Closure_problem" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Closure_problem"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.4</span> <span>Closure problem</span> </div> </a> <ul id="toc-Closure_problem-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Path_algorithms" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Path_algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.5</span> <span>Path algorithms</span> </div> </a> <ul id="toc-Path_algorithms-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Applications</span> </div> </a> <button aria-controls="toc-Applications-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Applications subsection</span> </button> <ul id="toc-Applications-sublist" class="vector-toc-list"> <li id="toc-Scheduling" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Scheduling"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Scheduling</span> </div> </a> <ul id="toc-Scheduling-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Data_processing_networks" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Data_processing_networks"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Data processing networks</span> </div> </a> <ul id="toc-Data_processing_networks-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Causal_structures" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Causal_structures"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Causal structures</span> </div> </a> <ul id="toc-Causal_structures-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Genealogy_and_version_history" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Genealogy_and_version_history"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Genealogy and version history</span> </div> </a> <ul id="toc-Genealogy_and_version_history-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Citation_graphs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Citation_graphs"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.5</span> <span>Citation graphs</span> </div> </a> <ul id="toc-Citation_graphs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Data_compression" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Data_compression"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.6</span> <span>Data compression</span> </div> </a> <ul id="toc-Data_compression-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Directed acyclic graph</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 22 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-22" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">22 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%A8%D9%8A%D8%A7%D9%86_%D9%85%D9%88%D8%AC%D9%87_%D8%AE%D8%A7%D9%84_%D9%85%D9%86_%D8%A7%D9%84%D8%AD%D9%84%D9%82%D8%A7%D8%AA" title="بيان موجه خال من الحلقات – Arabic" lang="ar" hreflang="ar" data-title="بيان موجه خال من الحلقات" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Graf_ac%C3%ADclic_dirigit" title="Graf acíclic dirigit – Catalan" lang="ca" hreflang="ca" data-title="Graf acíclic dirigit" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Rettet_acyklisk_graf" title="Rettet acyklisk graf – Danish" lang="da" hreflang="da" data-title="Rettet acyklisk graf" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Graph_(Graphentheorie)#Teilgraphen.2C_Wege_und_Zyklen" title="Graph (Graphentheorie) – German" lang="de" hreflang="de" data-title="Graph (Graphentheorie)" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%9A%CE%B1%CF%84%CE%B5%CF%85%CE%B8%CF%85%CE%BD%CF%8C%CE%BC%CE%B5%CE%BD%CE%BF%CF%82_%CE%AC%CE%BA%CF%85%CE%BA%CE%BB%CE%BF%CF%82_%CE%B3%CF%81%CE%AC%CF%86%CE%BF%CF%82" title="Κατευθυνόμενος άκυκλος γράφος – Greek" lang="el" hreflang="el" data-title="Κατευθυνόμενος άκυκλος γράφος" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Grafo_ac%C3%ADclico_dirigido" title="Grafo acíclico dirigido – Spanish" lang="es" hreflang="es" data-title="Grafo acíclico dirigido" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%81_%D8%AC%D9%87%D8%AA%E2%80%8C%D8%AF%D8%A7%D8%B1_%D8%BA%DB%8C%D8%B1%D9%85%D8%AF%D9%88%D8%B1" title="گراف جهت‌دار غیرمدور – Persian" lang="fa" hreflang="fa" data-title="گراف جهت‌دار غیرمدور" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Graphe_orient%C3%A9_acyclique" title="Graphe orienté acyclique – French" lang="fr" hreflang="fr" data-title="Graphe orienté acyclique" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%96%A5_%EB%B9%84%EC%88%9C%ED%99%98_%EA%B7%B8%EB%9E%98%ED%94%84" title="유향 비순환 그래프 – Korean" lang="ko" hreflang="ko" data-title="유향 비순환 그래프" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Digrafo_aciclico" title="Digrafo aciclico – Italian" lang="it" hreflang="it" data-title="Digrafo aciclico" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%92%D7%A8%D7%A3_%D7%9E%D7%9B%D7%95%D7%95%D7%9F_%D7%97%D7%A1%D7%A8_%D7%9E%D7%A2%D7%92%D7%9C%D7%99%D7%9D" title="גרף מכוון חסר מעגלים – Hebrew" lang="he" hreflang="he" data-title="גרף מכוון חסר מעגלים" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Virz%C4%ABts_aciklisks_grafs" title="Virzīts aciklisks grafs – Latvian" lang="lv" hreflang="lv" data-title="Virzīts aciklisks grafs" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Ir%C3%A1ny%C3%ADtott_k%C3%B6rmentes_gr%C3%A1f" title="Irányított körmentes gráf – Hungarian" lang="hu" hreflang="hu" data-title="Irányított körmentes gráf" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E9%9D%9E%E5%B7%A1%E5%9B%9E%E3%82%B0%E3%83%A9%E3%83%95" title="有向非巡回グラフ – Japanese" lang="ja" hreflang="ja" data-title="有向非巡回グラフ" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Rettet_asyklisk_graf" title="Rettet asyklisk graf – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Rettet asyklisk graf" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Skierowany_graf_acykliczny" title="Skierowany graf acykliczny – Polish" lang="pl" hreflang="pl" data-title="Skierowany graf acykliczny" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Grafos_ac%C3%ADclicos_dirigidos" title="Grafos acíclicos dirigidos – Portuguese" lang="pt" hreflang="pt" data-title="Grafos acíclicos dirigidos" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9E%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84" title="Ориентированный ациклический граф – Russian" lang="ru" hreflang="ru" data-title="Ориентированный ациклический граф" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%94%D0%B8%D1%80%D0%B5%D0%BA%D1%82%D0%B0%D0%BD_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%BD%D0%B8_%D0%B3%D1%80%D0%B0%D1%84" title="Директан ациклични граф – Serbian" lang="sr" hreflang="sr" data-title="Директан ациклични граф" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Suunnattu_syklit%C3%B6n_verkko" title="Suunnattu syklitön verkko – Finnish" lang="fi" hreflang="fi" data-title="Suunnattu syklitön verkko" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A1%D0%BF%D1%80%D1%8F%D0%BC%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B9_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D1%96%D1%87%D0%BD%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84" title="Спрямований ациклічний граф – Ukrainian" lang="uk" hreflang="uk" data-title="Спрямований ациклічний граф" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE" title="有向无环图 – Chinese" lang="zh" hreflang="zh" data-title="有向无环图" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1195339#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Directed_acyclic_graph" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Directed_acyclic_graph" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Directed_acyclic_graph"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Directed_acyclic_graph"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Directed_acyclic_graph" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Directed_acyclic_graph" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&oldid=1261432631" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Directed_acyclic_graph&id=1261432631&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDirected_acyclic_graph"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDirected_acyclic_graph"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Directed_acyclic_graph&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Directed_acyclic_graph&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Directed_acyclic_graphs" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1195339" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> <div id="mw-indicator-good-star" class="mw-indicator"><div class="mw-parser-output"><span typeof="mw:File"><a href="/wiki/Wikipedia:Good_articles*" title="This is a good article. Click here for more information."><img alt="This is a good article. Click here for more information." src="//upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/19px-Symbol_support_vote.svg.png" decoding="async" width="19" height="20" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/29px-Symbol_support_vote.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/39px-Symbol_support_vote.svg.png 2x" data-file-width="180" data-file-height="185" /></a></span></div></div> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Directed graph with no directed cycles</div> <p class="mw-empty-elt"> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Tred-G.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/220px-Tred-G.svg.png" decoding="async" width="220" height="302" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/330px-Tred-G.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/440px-Tred-G.svg.png 2x" data-file-width="252" data-file-height="346" /></a><figcaption>Example of a directed acyclic graph</figcaption></figure> <p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, particularly <a href="/wiki/Graph_theory" title="Graph theory">graph theory</a>, and <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>directed acyclic graph</b> (<b>DAG</b>) is a <a href="/wiki/Directed_graph" title="Directed graph">directed graph</a> with no <a href="/wiki/Cycle_graph#Directed_cycle_graph" title="Cycle graph">directed cycles</a>. That is, it consists of <a href="/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> and <a href="/wiki/Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a> (also called <i>arcs</i>), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be <a href="/wiki/Topological_ordering" class="mw-redirect" title="Topological ordering">topologically ordered</a>, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling). </p><p>Directed acyclic graphs are also called <b>acyclic directed graphs</b><sup id="cite_ref-thul_1-0" class="reference"><a href="#cite_note-thul-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> or <b>acyclic digraphs</b>.<sup id="cite_ref-bang_2-0" class="reference"><a href="#cite_note-bang-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=1" title="Edit section: Definitions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> is formed by <a href="/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> and by <a href="/wiki/Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a> connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a <a href="/wiki/Directed_graph" title="Directed graph">directed graph</a>, each edge has an orientation, from one vertex to another vertex. A <a href="/wiki/Path_(graph_theory)" title="Path (graph theory)">path</a> in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles.<sup id="cite_ref-thul_1-1" class="reference"><a href="#cite_note-thul-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-bang_2-1" class="reference"><a href="#cite_note-bang-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>A vertex <span class="texhtml mvar" style="font-style:italic;">v</span> of a directed graph is said to be <a href="/wiki/Reachability" title="Reachability">reachable</a> from another vertex <span class="texhtml mvar" style="font-style:italic;">u</span> when there exists a path that starts at <span class="texhtml mvar" style="font-style:italic;">u</span> and ends at <span class="texhtml mvar" style="font-style:italic;">v</span>. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Mathematical_properties">Mathematical properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=2" title="Edit section: Mathematical properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Reachability_relation,_transitive_closure,_and_transitive_reduction"><span id="Reachability_relation.2C_transitive_closure.2C_and_transitive_reduction"></span>Reachability relation, transitive closure, and transitive reduction</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=3" title="Edit section: Reachability relation, transitive closure, and transitive reduction"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1273380762/mw-parser-output/.tmulti">.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:307px;max-width:307px"><div class="trow"><div class="tsingle" style="width:177px;max-width:177px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Tred-G.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/175px-Tred-G.svg.png" decoding="async" width="175" height="240" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/263px-Tred-G.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/350px-Tred-G.svg.png 2x" data-file-width="252" data-file-height="346" /></a></span></div><div class="thumbcaption">A DAG</div></div><div class="tsingle" style="width:126px;max-width:126px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Tred-Gprime.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Tred-Gprime.svg/124px-Tred-Gprime.svg.png" decoding="async" width="124" height="240" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Tred-Gprime.svg/186px-Tred-Gprime.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Tred-Gprime.svg/248px-Tred-Gprime.svg.png 2x" data-file-width="168" data-file-height="325" /></a></span></div><div class="thumbcaption">Its transitive reduction</div></div></div></div></div> <p>The <a href="/wiki/Reachability" title="Reachability">reachability relation</a> of a DAG can be formalized as a <a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">partial order</a> <span class="texhtml">≤</span> on the vertices of the DAG. In this partial order, two vertices <span class="texhtml mvar" style="font-style:italic;">u</span> and <span class="texhtml mvar" style="font-style:italic;">v</span> are ordered as <span class="texhtml"><i>u</i> ≤ <i>v</i></span> exactly when there exists a directed path from <span class="texhtml mvar" style="font-style:italic;">u</span> to <span class="texhtml mvar" style="font-style:italic;">v</span> in the DAG; that is, when <span class="texhtml mvar" style="font-style:italic;">u</span> can reach <span class="texhtml mvar" style="font-style:italic;">v</span> (or <span class="texhtml mvar" style="font-style:italic;">v</span> is reachable from <span class="texhtml mvar" style="font-style:italic;">u</span>).<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> However, different DAGs may give rise to the same reachability relation and the same partial order.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> For example, a DAG with two edges <span class="texhtml"><i>u</i> → <i>v</i></span> and <span class="texhtml"><i>v</i> → <i>w</i></span> has the same reachability relation as the DAG with three edges <span class="texhtml"><i>u</i> → <i>v</i></span>, <span class="texhtml"><i>v</i> → <i>w</i></span>, and <span class="texhtml"><i>u</i> → <i>w</i></span>. Both of these DAGs produce the same partial order, in which the vertices are ordered as <span class="texhtml"><i>u</i> ≤ <i>v</i> ≤ <i>w</i></span>. </p><p>The <a href="/wiki/Transitive_closure" title="Transitive closure">transitive closure</a> of a DAG is the graph with the most edges that has the same reachability relation as the DAG. It has an edge <span class="texhtml"><i>u</i> → <i>v</i></span> for every pair of vertices (<span class="texhtml mvar" style="font-style:italic;">u</span>, <span class="texhtml mvar" style="font-style:italic;">v</span>) in the reachability relation <span class="texhtml">≤</span> of the DAG, and may therefore be thought of as a direct translation of the reachability relation <span class="texhtml">≤</span> into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set <span class="texhtml">(<i>S</i>, ≤)</span>, the graph that has a vertex for every element of <span class="texhtml mvar" style="font-style:italic;">S</span> and an edge for every pair of elements in <span class="texhtml">≤</span> is automatically a transitively closed DAG, and has <span class="texhtml">(<i>S</i>, ≤)</span> as its reachability relation. In this way, every finite partially ordered set can be represented as a DAG. </p> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Hasse_diagram_of_powerset_of_3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/300px-Hasse_diagram_of_powerset_of_3.svg.png" decoding="async" width="300" height="227" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/450px-Hasse_diagram_of_powerset_of_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/600px-Hasse_diagram_of_powerset_of_3.svg.png 2x" data-file-width="429" data-file-height="325" /></a><figcaption>A <a href="/wiki/Hasse_diagram" title="Hasse diagram">Hasse diagram</a> representing the partial order of set inclusion (⊆) among the subsets of a three-element set</figcaption></figure> <p>The <a href="/wiki/Transitive_reduction" title="Transitive reduction">transitive reduction</a> of a DAG is the graph with the fewest edges that has the same reachability relation as the DAG. It has an edge <span class="texhtml"><i>u</i> → <i>v</i></span> for every pair of vertices (<span class="texhtml mvar" style="font-style:italic;">u</span>, <span class="texhtml mvar" style="font-style:italic;">v</span>) in the <a href="/wiki/Covering_relation" title="Covering relation">covering relation</a> of the reachability relation <span class="texhtml">≤</span> of the DAG. It is a subgraph of the DAG, formed by discarding the edges <span class="texhtml"><i>u</i> → <i>v</i></span> for which the DAG also contains a longer directed path from <span class="texhtml mvar" style="font-style:italic;">u</span> to <span class="texhtml mvar" style="font-style:italic;">v</span>. Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler <a href="/wiki/Graph_drawing" title="Graph drawing">graph drawings</a>. A <a href="/wiki/Hasse_diagram" title="Hasse diagram">Hasse diagram</a> of a partial order is a drawing of the transitive reduction in which the orientation of every edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Topological_ordering">Topological ordering</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=4" title="Edit section: Topological ordering"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1273380762/mw-parser-output/.tmulti" /><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:408px;max-width:408px"><div class="trow"><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Topological_Ordering.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c6/Topological_Ordering.svg/200px-Topological_Ordering.svg.png" decoding="async" width="200" height="200" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c6/Topological_Ordering.svg/300px-Topological_Ordering.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c6/Topological_Ordering.svg/400px-Topological_Ordering.svg.png 2x" data-file-width="324" data-file-height="324" /></a></span></div><div class="thumbcaption">A <a href="/wiki/Topological_sorting" title="Topological sorting">topological ordering</a> of a directed acyclic graph: every <a href="/wiki/Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edge</a> goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.</div></div><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Transitive_Closure.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Transitive_Closure.svg/200px-Transitive_Closure.svg.png" decoding="async" width="200" height="200" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Transitive_Closure.svg/300px-Transitive_Closure.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Transitive_Closure.svg/400px-Transitive_Closure.svg.png 2x" data-file-width="324" data-file-height="324" /></a></span></div><div class="thumbcaption">Adding the red edges to the blue directed acyclic graph produces another DAG, the <a href="/wiki/Transitive_closure" title="Transitive closure">transitive closure</a> of the blue graph. For each red or blue edge <span class="texhtml"><i>u</i> → <i>v</i></span>, <span class="texhtml mvar" style="font-style:italic;">v</span> is <a href="/wiki/Reachability" title="Reachability">reachable</a> from <span class="texhtml mvar" style="font-style:italic;">u</span>: there exists a blue path starting at <span class="texhtml mvar" style="font-style:italic;">u</span> and ending at <span class="texhtml mvar" style="font-style:italic;">v</span>.</div></div></div></div></div> <p>A <a href="/wiki/Topological_ordering" class="mw-redirect" title="Topological ordering">topological ordering</a> of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings.<sup id="cite_ref-bang_2-2" class="reference"><a href="#cite_note-bang-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p><p>The family of topological orderings of a DAG is the same as the family of <a href="/wiki/Linear_extension" title="Linear extension">linear extensions</a> of the reachability relation for the DAG,<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> so any two graphs representing the same partial order have the same set of topological orders. </p> <div class="mw-heading mw-heading3"><h3 id="Combinatorial_enumeration">Combinatorial enumeration</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=5" title="Edit section: Combinatorial enumeration"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <a href="/wiki/Graph_enumeration" title="Graph enumeration">graph enumeration</a> problem of counting directed acyclic graphs was studied by <a href="#CITEREFRobinson1973">Robinson (1973)</a>.<sup id="cite_ref-enum_11-0" class="reference"><a href="#cite_note-enum-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> The number of DAGs on <span class="texhtml mvar" style="font-style:italic;">n</span> labeled vertices, for <span class="texhtml"><i>n</i> = 0, 1, 2, 3, …</span> (without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is </p> <dl><dd>1, 1, 3, 25, 543, 29281, 3781503, … (sequence <span class="nowrap external"><a href="//oeis.org/A003024" class="extiw" title="oeis:A003024">A003024</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</dd></dl> <p>These numbers may be computed by the <a href="/wiki/Recurrence_relation" title="Recurrence relation">recurrence relation</a> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </msup> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7d6b288e5e3203dfb301a6063177c59a82f5908a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:33.569ex; height:6.843ex;" alt="{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.}" /></span><sup id="cite_ref-enum_11-1" class="reference"><a href="#cite_note-enum-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></dd></dl> <p><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Eric W. Weisstein</a> conjectured,<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> and <a href="#CITEREFMcKayRoyleWanlessOggier2004">McKay et al. (2004)</a> proved, that the same numbers count the <a href="/wiki/Logical_matrix" title="Logical matrix">(0,1) matrices</a> for which all <a href="/wiki/Eigenvalue" class="mw-redirect" title="Eigenvalue">eigenvalues</a> are positive <a href="/wiki/Real_number" title="Real number">real numbers</a>. The proof is <a href="/wiki/Bijective_proof" title="Bijective proof">bijective</a>: a matrix <span class="texhtml mvar" style="font-style:italic;">A</span> is an <a href="/wiki/Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> of a DAG if and only if <span class="texhtml"><i>A</i> + <i>I</i></span> is a (0,1) matrix with all eigenvalues positive, where <span class="texhtml mvar" style="font-style:italic;">I</span> denotes the <a href="/wiki/Identity_matrix" title="Identity matrix">identity matrix</a>. Because a DAG cannot have <a href="/wiki/Loop_(graph_theory)" title="Loop (graph theory)">self-loops</a>, its adjacency matrix must have a zero diagonal, so adding <span class="texhtml mvar" style="font-style:italic;">I</span> preserves the property that all matrix coefficients are 0 or 1.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Related_families_of_graphs">Related families of graphs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=6" title="Edit section: Related families of graphs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1273380762/mw-parser-output/.tmulti" /><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:408px;max-width:408px"><div class="trow"><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Butterfly_multitree.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/Butterfly_multitree.svg/200px-Butterfly_multitree.svg.png" decoding="async" width="200" height="169" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/Butterfly_multitree.svg/300px-Butterfly_multitree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/57/Butterfly_multitree.svg/400px-Butterfly_multitree.svg.png 2x" data-file-width="288" data-file-height="243" /></a></span></div><div class="thumbcaption">A <a href="/wiki/Multitree" title="Multitree">multitree</a>, a DAG in which the subgraph reachable from any vertex induces an undirected tree (e.g. in red)</div></div><div class="tsingle" style="width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Polytree.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/6/61/Polytree.svg/200px-Polytree.svg.png" decoding="async" width="200" height="148" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/61/Polytree.svg/300px-Polytree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/61/Polytree.svg/400px-Polytree.svg.png 2x" data-file-width="512" data-file-height="378" /></a></span></div><div class="thumbcaption">A <a href="/wiki/Polytree" title="Polytree">polytree</a>, a DAG formed by orienting the edges of an undirected tree</div></div></div></div></div> <p>A <i><a href="/wiki/Multitree" title="Multitree">multitree</a></i> (also called a <i>strongly unambiguous graph</i> or a <i>mangrove</i>) is a DAG in which there is at most one directed path between any two vertices. Equivalently, it is a DAG in which the subgraph reachable from any vertex induces an <a href="/wiki/Tree_(graph_theory)" title="Tree (graph theory)">undirected tree</a>.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </p><p>A <i><a href="/wiki/Polytree" title="Polytree">polytree</a></i> (also called a <i>directed tree</i>) is a multitree formed by orienting the edges of an undirected tree.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p><p>An <i><a href="/wiki/Arborescence_(graph_theory)" title="Arborescence (graph theory)">arborescence</a></i> is a polytree formed by <a href="/wiki/Orientation_(graph_theory)" title="Orientation (graph theory)">orienting</a> the edges of an undirected tree away from a particular vertex, called the <i>root</i> of the arborescence. </p> <div class="mw-heading mw-heading2"><h2 id="Computational_problems">Computational problems</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=7" title="Edit section: Computational problems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Topological_sorting_and_recognition">Topological sorting and recognition</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=8" title="Edit section: Topological sorting and recognition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Topological_sorting" title="Topological sorting">Topological sorting</a></div> <p><a href="/wiki/Topological_sorting" title="Topological sorting">Topological sorting</a> is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a>.<sup id="cite_ref-clrs_16-0" class="reference"><a href="#cite_note-clrs-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way.<sup id="cite_ref-j50_17-0" class="reference"><a href="#cite_note-j50-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> Alternatively, a topological ordering may be constructed by reversing a <a href="/wiki/Postorder" class="mw-redirect" title="Postorder">postorder</a> numbering of a <a href="/wiki/Depth-first_search" title="Depth-first search">depth-first search</a> graph traversal.<sup id="cite_ref-clrs_16-1" class="reference"><a href="#cite_note-clrs-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p><p>It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is valid<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.<sup id="cite_ref-j50_17-1" class="reference"><a href="#cite_note-j50-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Construction_from_cyclic_graphs">Construction from cyclic graphs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=9" title="Edit section: Construction from cyclic graphs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Any undirected graph may be made into a DAG by choosing a <a href="/wiki/Total_order" title="Total order">total order</a> for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting <a href="/wiki/Orientation_(graph_theory)" title="Orientation (graph theory)">orientation</a> of the edges is called an <a href="/wiki/Acyclic_orientation" title="Acyclic orientation">acyclic orientation</a>. Different total orders may lead to the same acyclic orientation, so an <span class="texhtml mvar" style="font-style:italic;">n</span>-vertex graph can have fewer than <span class="texhtml"><i>n</i>!</span> acyclic orientations. The number of acyclic orientations is equal to <span class="texhtml">|<i>χ</i>(−1)|</span>, where <span class="texhtml mvar" style="font-style:italic;">χ</span> is the <a href="/wiki/Chromatic_polynomial" title="Chromatic polynomial">chromatic polynomial</a> of the given graph.<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Graph_Condensation.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/20/Graph_Condensation.svg/330px-Graph_Condensation.svg.png" decoding="async" width="330" height="207" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/20/Graph_Condensation.svg/495px-Graph_Condensation.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/20/Graph_Condensation.svg/660px-Graph_Condensation.svg.png 2x" data-file-width="774" data-file-height="486" /></a><figcaption>The yellow directed acyclic graph is the <a href="/wiki/Condensation_(graph_theory)" class="mw-redirect" title="Condensation (graph theory)">condensation</a> of the blue directed graph. It is formed by <a href="/wiki/Edge_contraction" title="Edge contraction">contracting</a> each <a href="/wiki/Strongly_connected_component" title="Strongly connected component">strongly connected component</a> of the blue graph into a single yellow vertex.</figcaption></figure> <p>Any directed graph may be made into a DAG by removing a <a href="/wiki/Feedback_vertex_set" title="Feedback vertex set">feedback vertex set</a> or a <a href="/wiki/Feedback_arc_set" title="Feedback arc set">feedback arc set</a>, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is <a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> to find.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> An arbitrary directed graph may also be transformed into a DAG, called its <a href="/wiki/Condensation_(graph_theory)" class="mw-redirect" title="Condensation (graph theory)">condensation</a>, by <a href="/wiki/Edge_contraction" title="Edge contraction">contracting</a> each of its <a href="/wiki/Strongly_connected_component" title="Strongly connected component">strongly connected components</a> into a single supervertex.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are <a href="/wiki/Empty_set" title="Empty set">empty</a>, and its condensation is the graph itself. </p> <div class="mw-heading mw-heading3"><h3 id="Transitive_closure_and_transitive_reduction">Transitive closure and transitive reduction</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=10" title="Edit section: Transitive closure and transitive reduction"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The transitive closure of a given DAG, with <span class="texhtml mvar" style="font-style:italic;">n</span> vertices and <span class="texhtml mvar" style="font-style:italic;">m</span> edges, may be constructed in time <span class="texhtml"><i>O</i>(<i>mn</i>)</span> by using either <a href="/wiki/Breadth-first_search" title="Breadth-first search">breadth-first search</a> or <a href="/wiki/Depth-first_search" title="Depth-first search">depth-first search</a> to test reachability from each vertex.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> Alternatively, it can be solved in time <span class="texhtml"><i>O</i>(<i>n</i><sup><i>ω</i></sup>)</span> where <span class="texhtml"><i>ω</i> < 2.373</span> is the <a href="/wiki/Computational_complexity_of_matrix_multiplication#Matrix_multiplication_exponent" title="Computational complexity of matrix multiplication">exponent for matrix multiplication algorithms</a>; this is a theoretical improvement over the <span class="texhtml"><i>O</i>(<i>mn</i>)</span> bound for <a href="/wiki/Dense_graph" title="Dense graph">dense graphs</a>.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> </p><p>In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Closure_problem">Closure problem</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=11" title="Edit section: Closure problem"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Closure_problem" title="Closure problem">Closure problem</a></div> <p>The <a href="/wiki/Closure_problem" title="Closure problem">closure problem</a> takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices <i>C</i>, such that no edges leave <i>C</i>. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the <a href="/wiki/Maximum_flow_problem" title="Maximum flow problem">maximum flow problem</a>.<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Path_algorithms">Path algorithms</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=12" title="Edit section: Path algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find <a href="/wiki/Shortest_path" class="mw-redirect" title="Shortest path">shortest paths</a> and <a href="/wiki/Longest_path_problem" title="Longest path problem">longest paths</a> from a given starting vertex in DAGs in linear time by <a href="/wiki/Topological_sorting#Application_to_shortest_path_finding" title="Topological sorting">processing the vertices in a topological order</a>, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as <a href="/wiki/Dijkstra%27s_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a> or the <a href="/wiki/Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford algorithm</a>,<sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup> and longest paths in arbitrary graphs are <a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> to find.<sup id="cite_ref-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=13" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Scheduling">Scheduling</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=14" title="Edit section: Scheduling"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Directed acyclic graph representations of partial orderings have many applications in <a href="/wiki/Schedule" title="Schedule">scheduling</a> for systems of tasks with ordering constraints.<sup id="cite_ref-29" class="reference"><a href="#cite_note-29"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup> An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a <a href="/wiki/Spreadsheet" title="Spreadsheet">spreadsheet</a> after one of the cells has been changed, or the <a href="/wiki/Object_file" title="Object file">object files</a> of a piece of computer software after its <a href="/wiki/Source_code" title="Source code">source code</a> has been changed. In this context, a <a href="/wiki/Dependency_graph" title="Dependency graph">dependency graph</a> is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a <a href="/wiki/Circular_dependency" title="Circular dependency">circular dependency</a>, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. Dependency graphs without circular dependencies form DAGs.<sup id="cite_ref-30" class="reference"><a href="#cite_note-30"><span class="cite-bracket">[</span>30<span class="cite-bracket">]</span></a></sup> </p><p>For instance, when one cell of a <a href="/wiki/Spreadsheet" title="Spreadsheet">spreadsheet</a> changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.<sup id="cite_ref-hgt1181_31-0" class="reference"><a href="#cite_note-hgt1181-31"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup> Similar problems of task ordering arise in <a href="/wiki/Makefile" class="mw-redirect" title="Makefile">makefiles</a> for program compilation<sup id="cite_ref-hgt1181_31-1" class="reference"><a href="#cite_note-hgt1181-31"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup> and <a href="/wiki/Instruction_scheduling" title="Instruction scheduling">instruction scheduling</a> for low-level computer program optimization.<sup id="cite_ref-32" class="reference"><a href="#cite_note-32"><span class="cite-bracket">[</span>32<span class="cite-bracket">]</span></a></sup> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Pert_chart_colored.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/37/Pert_chart_colored.svg/220px-Pert_chart_colored.svg.png" decoding="async" width="220" height="134" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/37/Pert_chart_colored.svg/330px-Pert_chart_colored.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/37/Pert_chart_colored.svg/440px-Pert_chart_colored.svg.png 2x" data-file-width="308" data-file-height="188" /></a><figcaption>PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.</figcaption></figure> <p>A somewhat different DAG-based formulation of scheduling constraints is used by the <a href="/wiki/Program_evaluation_and_review_technique" title="Program evaluation and review technique">program evaluation and review technique</a> (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent <a href="/wiki/Milestone_(project_management)" title="Milestone (project management)">milestones</a> of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The <a href="/wiki/Longest_path_problem" title="Longest path problem">longest path</a> in this DAG represents the <a href="/wiki/Critical_path_method" title="Critical path method">critical path</a> of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<sup id="cite_ref-33" class="reference"><a href="#cite_note-33"><span class="cite-bracket">[</span>33<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Data_processing_networks">Data processing networks</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=15" title="Edit section: Data processing networks"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges. </p><p>For instance, in electronic circuit design, static <a href="/wiki/Combinational_logic" title="Combinational logic">combinational logic</a> blocks can be represented as an acyclic system of <a href="/wiki/Logic_gate" title="Logic gate">logic gates</a> that computes a function of an input, where the input and output of the function are represented as individual <a href="/wiki/Bit" title="Bit">bits</a>. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties.<sup id="cite_ref-34" class="reference"><a href="#cite_note-34"><span class="cite-bracket">[</span>34<span class="cite-bracket">]</span></a></sup> Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed. </p><p><a href="/wiki/Dataflow_programming" title="Dataflow programming">Dataflow programming</a> languages describe systems of operations on <a href="/wiki/Data_stream" title="Data stream">data streams</a>, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a <a href="/wiki/Parallel_algorithm" title="Parallel algorithm">parallel algorithm</a> in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.<sup id="cite_ref-35" class="reference"><a href="#cite_note-35"><span class="cite-bracket">[</span>35<span class="cite-bracket">]</span></a></sup> </p><p>In <a href="/wiki/Compiler" title="Compiler">compilers</a>, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform <a href="/wiki/Common_subexpression_elimination" title="Common subexpression elimination">common subexpression elimination</a> efficiently.<sup id="cite_ref-36" class="reference"><a href="#cite_note-36"><span class="cite-bracket">[</span>36<span class="cite-bracket">]</span></a></sup> At a higher level of code organization, the <a href="/wiki/Acyclic_dependencies_principle" title="Acyclic dependencies principle">acyclic dependencies principle</a> states that the dependencies between modules or components of a large software system should form a directed acyclic graph.<sup id="cite_ref-37" class="reference"><a href="#cite_note-37"><span class="cite-bracket">[</span>37<span class="cite-bracket">]</span></a></sup> </p><p><a href="/wiki/Feedforward_neural_network" title="Feedforward neural network">Feedforward neural networks</a> are another example. </p> <div class="mw-heading mw-heading3"><h3 id="Causal_structures">Causal structures</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=16" title="Edit section: Causal structures"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Bayesian_network" title="Bayesian network">Bayesian network</a></div> <p>Graphs in which vertices represent events occurring at a definite time, and where the edges always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any <a href="/wiki/Path_(graph_theory)" title="Path (graph theory)">path</a> in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no <a href="/wiki/Causal_loop" class="mw-redirect" title="Causal loop">causal loops</a>. An example of this type of directed acyclic graph are those encountered in the <a href="/wiki/Causal_sets" title="Causal sets">causal set approach to quantum gravity</a> though in this case the graphs considered are <a href="#Transitive_closure_and_transitive_reduction">transitively complete</a>. In the version history example below, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. In the citation graph examples below, the documents are published at one time and can only refer to older documents. </p><p>Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent <a href="/wiki/Causality" title="Causality">causal relations</a> between the events, we will have a directed acyclic graph.<sup id="cite_ref-38" class="reference"><a href="#cite_note-38"><span class="cite-bracket">[</span>38<span class="cite-bracket">]</span></a></sup> For instance, a <a href="/wiki/Bayesian_network" title="Bayesian network">Bayesian network</a> represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG.<sup id="cite_ref-39" class="reference"><a href="#cite_note-39"><span class="cite-bracket">[</span>39<span class="cite-bracket">]</span></a></sup> In this context, the <a href="/wiki/Moral_graph" title="Moral graph">moral graph</a> of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called <i>marrying</i>), and then replacing all directed edges by undirected edges.<sup id="cite_ref-40" class="reference"><a href="#cite_note-40"><span class="cite-bracket">[</span>40<span class="cite-bracket">]</span></a></sup> Another type of graph with a similar causal structure is an <a href="/wiki/Influence_diagram" title="Influence diagram">influence diagram</a>, the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another.<sup id="cite_ref-41" class="reference"><a href="#cite_note-41"><span class="cite-bracket">[</span>41<span class="cite-bracket">]</span></a></sup> In <a href="/wiki/Epidemiology" title="Epidemiology">epidemiology</a>, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.<sup id="cite_ref-42" class="reference"><a href="#cite_note-42"><span class="cite-bracket">[</span>42<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-pearl:95_43-0" class="reference"><a href="#cite_note-pearl:95-43"><span class="cite-bracket">[</span>43<span class="cite-bracket">]</span></a></sup> </p><p>The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a <a href="#Topological_ordering">topological ordering</a>, i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order. </p> <div class="mw-heading mw-heading3"><h3 id="Genealogy_and_version_history">Genealogy and version history</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=17" title="Edit section: Genealogy and version history"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:EgyptianPtolemies2.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/52/EgyptianPtolemies2.jpg/330px-EgyptianPtolemies2.jpg" decoding="async" width="330" height="271" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/52/EgyptianPtolemies2.jpg/495px-EgyptianPtolemies2.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/5/52/EgyptianPtolemies2.jpg 2x" data-file-width="589" data-file-height="484" /></a><figcaption>Family tree of the <a href="/wiki/Ptolemaic_dynasty" title="Ptolemaic dynasty">Ptolemaic dynasty</a>, with many marriages between <a href="/wiki/Consanguinity" title="Consanguinity">close relatives</a> causing <a href="/wiki/Pedigree_collapse" title="Pedigree collapse">pedigree collapse</a>.</figcaption></figure> <p><a href="/wiki/Family_tree" title="Family tree">Family trees</a> may be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship.<sup id="cite_ref-44" class="reference"><a href="#cite_note-44"><span class="cite-bracket">[</span>44<span class="cite-bracket">]</span></a></sup> Despite the name, these graphs are not necessarily trees because of the possibility of marriages between relatives (so a child has a common ancestor on both the mother's and father's side) causing <a href="/wiki/Pedigree_collapse" title="Pedigree collapse">pedigree collapse</a>.<sup id="cite_ref-45" class="reference"><a href="#cite_note-45"><span class="cite-bracket">[</span>45<span class="cite-bracket">]</span></a></sup> The graphs of <a href="/wiki/Matrilineal" class="mw-redirect" title="Matrilineal">matrilineal</a> descent (mother-daughter relationships) and <a href="/wiki/Patrilineal" class="mw-redirect" title="Patrilineal">patrilineal</a> descent (father-son relationships) are trees within this graph. Because no one can become their own ancestor, family trees are acyclic.<sup id="cite_ref-46" class="reference"><a href="#cite_note-46"><span class="cite-bracket">[</span>46<span class="cite-bracket">]</span></a></sup> </p><p>The version history of a <a href="/wiki/Distributed_revision_control" class="mw-redirect" title="Distributed revision control">distributed revision control</a> system, such as <a href="/wiki/Git" title="Git">Git</a>, generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other. These are not trees in general due to merges.<sup id="cite_ref-47" class="reference"><a href="#cite_note-47"><span class="cite-bracket">[</span>47<span class="cite-bracket">]</span></a></sup> </p><p>In many <a href="/wiki/Randomization" title="Randomization">randomized</a> <a href="/wiki/Algorithm" title="Algorithm">algorithms</a> in <a href="/wiki/Computational_geometry" title="Computational geometry">computational geometry</a>, the algorithm maintains a <i>history DAG</i> representing the version history of a geometric structure over the course of a sequence of changes to the structure. For instance in a <a href="/wiki/Randomized_algorithm#Randomized_incremental_constructions_in_geometry" title="Randomized algorithm">randomized incremental</a> algorithm for <a href="/wiki/Delaunay_triangulation" title="Delaunay triangulation">Delaunay triangulation</a>, the triangulation changes by replacing one triangle by three smaller triangles when each point is added, and by "flip" operations that replace pairs of triangles by a different pair of triangles. The history DAG for this algorithm has a vertex for each triangle constructed as part of the algorithm, and edges from each triangle to the two or three other triangles that replace it. This structure allows <a href="/wiki/Point_location" title="Point location">point location</a> queries to be answered efficiently: to find the location of a query point <span class="texhtml mvar" style="font-style:italic;">q</span> in the Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains <span class="texhtml mvar" style="font-style:italic;">q</span>. The final triangle reached in this path must be the Delaunay triangle that contains <span class="texhtml mvar" style="font-style:italic;">q</span>.<sup id="cite_ref-48" class="reference"><a href="#cite_note-48"><span class="cite-bracket">[</span>48<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Citation_graphs">Citation graphs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=18" title="Edit section: Citation graphs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In a <a href="/wiki/Citation_graph" title="Citation graph">citation graph</a> the vertices are documents with a single publication date. The edges represent the citations from the bibliography of one document to other necessarily earlier documents. The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of Scientific Papers"<sup id="cite_ref-49" class="reference"><a href="#cite_note-49"><span class="cite-bracket">[</span>49<span class="cite-bracket">]</span></a></sup> by <a href="/wiki/Derek_J._de_Solla_Price" title="Derek J. de Solla Price">Derek J. de Solla Price</a> who went on to produce the first model of a citation network, the <a href="/wiki/Price%27s_model" title="Price's model">Price model</a>.<sup id="cite_ref-50" class="reference"><a href="#cite_note-50"><span class="cite-bracket">[</span>50<span class="cite-bracket">]</span></a></sup> In this case the <a href="/wiki/Citation_impact" title="Citation impact">citation count</a> of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in <a href="/wiki/Citation_analysis" title="Citation analysis">citation analysis</a>. <a href="/wiki/Judgment_(law)" title="Judgment (law)">Court judgements</a> provide another example as judges support their conclusions in one case by recalling other earlier decisions made in previous cases. A final example is provided by patents which must refer to earlier <a href="/wiki/Prior_art" title="Prior art">prior art</a>, earlier patents which are relevant to the current patent claim. By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using <a href="/wiki/Network_Science" class="mw-redirect" title="Network Science">network analysis</a>. For instance <a href="#Transitive_closure_and_transitive_reduction">transitive reduction</a> gives new insights into the citation distributions found in different applications highlighting clear differences in the mechanisms creating citations networks in different contexts.<sup id="cite_ref-51" class="reference"><a href="#cite_note-51"><span class="cite-bracket">[</span>51<span class="cite-bracket">]</span></a></sup> Another technique is <a href="/wiki/Main_path_analysis" title="Main path analysis">main path analysis</a>, which traces the citation links and suggests the most significant citation chains in a given <a href="/wiki/Citation_graph" title="Citation graph">citation graph</a>. </p><p>The <a href="/wiki/Price%27s_model" title="Price's model">Price model</a> is too simple to be a realistic model of a <a href="/wiki/Citation_graph" title="Citation graph">citation network</a> but it is simple enough to allow for analytic solutions for some of its properties. Many of these can be found by using results derived from the undirected version of the <a href="/wiki/Price%27s_model" title="Price's model">Price model</a>, the <a href="/wiki/Barab%C3%A1si%E2%80%93Albert_model" title="Barabási–Albert model">Barabási–Albert model</a>. However, since <a href="/wiki/Price%27s_model" title="Price's model">Price's model</a> gives a directed acyclic graph, it is a useful model when looking for analytic calculations of properties unique to directed acyclic graphs. For instance, the length of the longest path, from the n-th node added to the network to the first node in the network, scales as<sup id="cite_ref-ECV_52-0" class="reference"><a href="#cite_note-ECV-52"><span class="cite-bracket">[</span>52<span class="cite-bracket">]</span></a></sup> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ln(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ln</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \ln(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b40d8af55c5679aa769abbd67a7b98612c2aeaf5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.143ex; height:2.843ex;" alt="{\displaystyle \ln(n)}" /></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Data_compression">Data compression</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=19" title="Edit section: Data compression"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Directed acyclic graphs may also be used as a <a href="/wiki/Data_compression" title="Data compression">compact representation</a> of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the <a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">directed acyclic word graph</a> is a <a href="/wiki/Data_structure" title="Data structure">data structure</a> in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of <a href="/wiki/String_(computer_science)" title="String (computer science)">strings</a>, such as English words.<sup id="cite_ref-53" class="reference"><a href="#cite_note-53"><span class="cite-bracket">[</span>53<span class="cite-bracket">]</span></a></sup> Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a <a href="/wiki/Trie" title="Trie">trie</a>. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.<sup id="cite_ref-54" class="reference"><a href="#cite_note-54"><span class="cite-bracket">[</span>54<span class="cite-bracket">]</span></a></sup> </p><p>The same idea of using a DAG to represent a family of paths occurs in the <a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">binary decision diagram</a>,<sup id="cite_ref-55" class="reference"><a href="#cite_note-55"><span class="cite-bracket">[</span>55<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-56" class="reference"><a href="#cite_note-56"><span class="cite-bracket">[</span>56<span class="cite-bracket">]</span></a></sup> a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any <a href="/wiki/Truth_assignment" class="mw-redirect" title="Truth assignment">truth assignment</a> to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of tries, binary decision diagrams can be viewed as compressed forms of <a href="/wiki/Decision_tree" title="Decision tree">decision trees</a> that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.<sup id="cite_ref-57" class="reference"><a href="#cite_note-57"><span class="cite-bracket">[</span>57<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=20" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-thul-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-thul_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-thul_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFThulasiramanSwamy1992" class="citation cs2">Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", <i>Graphs: Theory and Algorithms</i>, John Wiley and Son, p. 118, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-471-51356-8" title="Special:BookSources/978-0-471-51356-8"><bdi>978-0-471-51356-8</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=5.7+Acyclic+Directed+Graphs&rft.btitle=Graphs%3A+Theory+and+Algorithms&rft.pages=118&rft.pub=John+Wiley+and+Son&rft.date=1992&rft.isbn=978-0-471-51356-8&rft.aulast=Thulasiraman&rft.aufirst=K.&rft.au=Swamy%2C+M.+N.+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-bang-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-bang_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-bang_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-bang_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBang-Jensen2008" class="citation cs2">Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", <i>Digraphs: Theory, Algorithms and Applications</i>, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, pp. <span class="nowrap">32–</span>34, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-84800-997-4" title="Special:BookSources/978-1-84800-997-4"><bdi>978-1-84800-997-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=2.1+Acyclic+Digraphs&rft.btitle=Digraphs%3A+Theory%2C+Algorithms+and+Applications&rft.series=Springer+Monographs+in+Mathematics&rft.pages=%3Cspan+class%3D%22nowrap%22%3E32-%3C%2Fspan%3E34&rft.edition=2nd&rft.pub=Springer-Verlag&rft.date=2008&rft.isbn=978-1-84800-997-4&rft.aulast=Bang-Jensen&rft.aufirst=J%C3%B8rgen&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFChristofides1975" class="citation cs2"><a href="/wiki/Nicos_Christofides" title="Nicos Christofides">Christofides, Nicos</a> (1975), <i>Graph theory: an algorithmic approach</i>, Academic Press, pp. <span class="nowrap">170–</span>174</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Graph+theory%3A+an+algorithmic+approach&rft.pages=%3Cspan+class%3D%22nowrap%22%3E170-%3C%2Fspan%3E174&rft.pub=Academic+Press&rft.date=1975&rft.aulast=Christofides&rft.aufirst=Nicos&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFMitrani1982" class="citation cs2">Mitrani, I. (1982), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27"><i>Simulation Techniques for Discrete Event Systems</i></a>, Cambridge Computer Science Texts, vol. 14, Cambridge University Press, p. 27, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521282826" title="Special:BookSources/9780521282826"><bdi>9780521282826</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Simulation+Techniques+for+Discrete+Event+Systems&rft.series=Cambridge+Computer+Science+Texts&rft.pages=27&rft.pub=Cambridge+University+Press&rft.date=1982&rft.isbn=9780521282826&rft.aulast=Mitrani&rft.aufirst=I.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DCF04AAAAIAAJ%26pg%3DPA27&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFKozen1992" class="citation cs2"><a href="/wiki/Dexter_Kozen" title="Dexter Kozen">Kozen, Dexter</a> (1992), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA9"><i>The Design and Analysis of Algorithms</i></a>, Monographs in Computer Science, Springer, p. 9, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-97687-7" title="Special:BookSources/978-0-387-97687-7"><bdi>978-0-387-97687-7</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Design+and+Analysis+of+Algorithms&rft.series=Monographs+in+Computer+Science&rft.pages=9&rft.pub=Springer&rft.date=1992&rft.isbn=978-0-387-97687-7&rft.aulast=Kozen&rft.aufirst=Dexter&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DL_AMnf9UF9QC%26pg%3DPA9&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBanerjee1993" class="citation cs2">Banerjee, Utpal (1993), "Exercise 2(c)", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19"><i>Loop Transformations for Restructuring Compilers: The Foundations</i></a>, Springer, p. 19, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1993ltfr.book.....B">1993ltfr.book.....B</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7923-9318-4" title="Special:BookSources/978-0-7923-9318-4"><bdi>978-0-7923-9318-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Exercise+2%28c%29&rft.btitle=Loop+Transformations+for+Restructuring+Compilers%3A+The+Foundations&rft.pages=19&rft.pub=Springer&rft.date=1993&rft_id=info%3Abibcode%2F1993ltfr.book.....B&rft.isbn=978-0-7923-9318-4&rft.aulast=Banerjee&rft.aufirst=Utpal&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DCog7zSSlqFwC%26pg%3DPA19&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBang-JensenGutin2008" class="citation cs2">Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=4UY-ucucWucC&pg=PA36"><i>Digraphs: Theory, Algorithms and Applications</i></a>, Springer Monographs in Mathematics, Springer, pp. <span class="nowrap">36–</span>39, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-84800-998-1" title="Special:BookSources/978-1-84800-998-1"><bdi>978-1-84800-998-1</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=2.3+Transitive+Digraphs%2C+Transitive+Closures+and+Reductions&rft.btitle=Digraphs%3A+Theory%2C+Algorithms+and+Applications&rft.series=Springer+Monographs+in+Mathematics&rft.pages=%3Cspan+class%3D%22nowrap%22%3E36-%3C%2Fspan%3E39&rft.pub=Springer&rft.date=2008&rft.isbn=978-1-84800-998-1&rft.aulast=Bang-Jensen&rft.aufirst=J%C3%B8rgen&rft.au=Gutin%2C+Gregory+Z.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D4UY-ucucWucC%26pg%3DPA36&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFJungnickel2012" class="citation cs2">Jungnickel, Dieter (2012), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92"><i>Graphs, Networks and Algorithms</i></a>, Algorithms and Computation in Mathematics, vol. 5, Springer, pp. <span class="nowrap">92–</span>93, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-642-32278-5" title="Special:BookSources/978-3-642-32278-5"><bdi>978-3-642-32278-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Graphs%2C+Networks+and+Algorithms&rft.series=Algorithms+and+Computation+in+Mathematics&rft.pages=%3Cspan+class%3D%22nowrap%22%3E92-%3C%2Fspan%3E93&rft.pub=Springer&rft.date=2012&rft.isbn=978-3-642-32278-5&rft.aulast=Jungnickel&rft.aufirst=Dieter&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DPrXxFHmchwcC%26pg%3DPA92&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSedgewickWayne2011" class="citation cs2"><a href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Wayne, Kevin (2011), "4,2,25 Unique topological ordering", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598"><i>Algorithms</i></a> (4th ed.), Addison-Wesley, pp. <span class="nowrap">598–</span>599, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-13-276256-4" title="Special:BookSources/978-0-13-276256-4"><bdi>978-0-13-276256-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=4%2C2%2C25+Unique+topological+ordering&rft.btitle=Algorithms&rft.pages=%3Cspan+class%3D%22nowrap%22%3E598-%3C%2Fspan%3E599&rft.edition=4th&rft.pub=Addison-Wesley&rft.date=2011&rft.isbn=978-0-13-276256-4&rft.aulast=Sedgewick&rft.aufirst=Robert&rft.au=Wayne%2C+Kevin&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DidUdqdDXqnAC%26pg%3DPA598&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBenderWilliamson2005" class="citation cs2">Bender, Edward A.; Williamson, S. Gill (2005), "Example 26 (Linear extensions – topological sorts)", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=iuEoAwAAQBAJ&pg=PA142"><i>A Short Course in Discrete Mathematics</i></a>, Dover Books on Computer Science, Courier Dover Publications, p. 142, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-486-43946-4" title="Special:BookSources/978-0-486-43946-4"><bdi>978-0-486-43946-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Example+26+%28Linear+extensions+%E2%80%93+topological+sorts%29&rft.btitle=A+Short+Course+in+Discrete+Mathematics&rft.series=Dover+Books+on+Computer+Science&rft.pages=142&rft.pub=Courier+Dover+Publications&rft.date=2005&rft.isbn=978-0-486-43946-4&rft.aulast=Bender&rft.aufirst=Edward+A.&rft.au=Williamson%2C+S.+Gill&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DiuEoAwAAQBAJ%26pg%3DPA142&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-enum-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-enum_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-enum_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFRobinson1973" class="citation cs2">Robinson, R. W. (1973), "Counting labeled acyclic digraphs", in <a href="/wiki/Frank_Harary" title="Frank Harary">Harary, F.</a> (ed.), <i>New Directions in the Theory of Graphs</i>, Academic Press, pp. <span class="nowrap">239–</span>273</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Counting+labeled+acyclic+digraphs&rft.btitle=New+Directions+in+the+Theory+of+Graphs&rft.pages=%3Cspan+class%3D%22nowrap%22%3E239-%3C%2Fspan%3E273&rft.pub=Academic+Press&rft.date=1973&rft.aulast=Robinson&rft.aufirst=R.+W.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>. See also <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHararyPalmer1973" class="citation cs2"><a href="/wiki/Frank_Harary" title="Frank Harary">Harary, Frank</a>; Palmer, Edgar M. (1973), <i>Graphical Enumeration</i>, <a href="/wiki/Academic_Press" title="Academic Press">Academic Press</a>, p. 19, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-12-324245-7" title="Special:BookSources/978-0-12-324245-7"><bdi>978-0-12-324245-7</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Graphical+Enumeration&rft.pages=19&rft.pub=Academic+Press&rft.date=1973&rft.isbn=978-0-12-324245-7&rft.aulast=Harary&rft.aufirst=Frank&rft.au=Palmer%2C+Edgar+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><span class="citation mathworld" id="Reference-Mathworld-Weisstein's_Conjecture"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFWeisstein" class="citation web cs2"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a>, <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/WeissteinsConjecture.html">"Weisstein's Conjecture"</a>, <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Weisstein%27s+Conjecture&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FWeissteinsConjecture.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_web" title="Template:Cite web">cite web</a>}}</code>: CS1 maint: overridden setting (<a href="/wiki/Category:CS1_maint:_overridden_setting" title="Category:CS1 maint: overridden setting">link</a>)</span></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFMcKayRoyleWanlessOggier2004" class="citation cs2"><a href="/wiki/Brendan_McKay_(mathematician)" title="Brendan McKay (mathematician)">McKay, B. D.</a>; <a href="/wiki/Gordon_Royle" title="Gordon Royle">Royle, G. F.</a>; Wanless, I. M.; <a href="/wiki/Fr%C3%A9d%C3%A9rique_Oggier" title="Frédérique Oggier">Oggier, F. E.</a>; <a href="/wiki/Neil_Sloane" title="Neil Sloane">Sloane, N. J. A.</a>; <a href="/wiki/Herbert_Wilf" title="Herbert Wilf">Wilf, H.</a> (2004), <a rel="nofollow" class="external text" href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html">"Acyclic digraphs and eigenvalues of (0,1)-matrices"</a>, <i><a href="/wiki/Journal_of_Integer_Sequences" title="Journal of Integer Sequences">Journal of Integer Sequences</a></i>, <b>7</b>: 33, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0310423">math/0310423</a></span>, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2004JIntS...7...33M">2004JIntS...7...33M</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Integer+Sequences&rft.atitle=Acyclic+digraphs+and+eigenvalues+of+%280%2C1%29-matrices&rft.volume=7&rft.pages=33&rft.date=2004&rft_id=info%3Aarxiv%2Fmath%2F0310423&rft_id=info%3Abibcode%2F2004JIntS...7...33M&rft.aulast=McKay&rft.aufirst=B.+D.&rft.au=Royle%2C+G.+F.&rft.au=Wanless%2C+I.+M.&rft.au=Oggier%2C+F.+E.&rft.au=Sloane%2C+N.+J.+A.&rft.au=Wilf%2C+H.&rft_id=http%3A%2F%2Fwww.cs.uwaterloo.ca%2Fjournals%2FJIS%2FVOL7%2FSloane%2Fsloane15.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>, Article 04.3.3.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFFurnasZacks1994" class="citation cs2"><a href="/wiki/George_Furnas" title="George Furnas">Furnas, George W.</a>; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", <i>Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)</i>, pp. <span class="nowrap">330–</span>336, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F191666.191778">10.1145/191666.191778</a></span>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0897916509" title="Special:BookSources/978-0897916509"><bdi>978-0897916509</bdi></a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18710118">18710118</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Multitrees%3A+enriching+and+reusing+hierarchical+structure&rft.btitle=Proc.+SIGCHI+conference+on+Human+Factors+in+Computing+Systems+%28CHI+%2794%29&rft.pages=%3Cspan+class%3D%22nowrap%22%3E330-%3C%2Fspan%3E336&rft.date=1994&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A18710118%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F191666.191778&rft.isbn=978-0897916509&rft.aulast=Furnas&rft.aufirst=George+W.&rft.au=Zacks%2C+Jeff&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFRebanePearl1987" class="citation cs2">Rebane, George; <a href="/wiki/Judea_Pearl" title="Judea Pearl">Pearl, Judea</a> (1987), "The recovery of causal poly-trees from statistical data", <a rel="nofollow" class="external text" href="http://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf"><i>Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987</i></a> <span class="cs1-format">(PDF)</span>, pp. <span class="nowrap">222–</span>228</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+recovery+of+causal+poly-trees+from+statistical+data&rft.btitle=Proc.+3rd+Annual+Conference+on+Uncertainty+in+Artificial+Intelligence+%28UAI+1987%29%2C+Seattle%2C+WA%2C+USA%2C+July+1987&rft.pages=%3Cspan+class%3D%22nowrap%22%3E222-%3C%2Fspan%3E228&rft.date=1987&rft.aulast=Rebane&rft.aufirst=George&rft.au=Pearl%2C+Judea&rft_id=http%3A%2F%2Fftp.cs.ucla.edu%2Ftech-report%2F198_-reports%2F870031.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-clrs-16"><span class="mw-cite-backlink">^ <a href="#cite_ref-clrs_16-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-clrs_16-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs2"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="/wiki/Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2001) [1990], <a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a> (2nd ed.), MIT Press and McGraw-Hill, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-262-03293-7" title="Special:BookSources/0-262-03293-7"><bdi>0-262-03293-7</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Algorithms&rft.edition=2nd&rft.pub=MIT+Press+and+McGraw-Hill&rft.date=2001&rft.isbn=0-262-03293-7&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_book" title="Template:Cite book">cite book</a>}}</code>: CS1 maint: overridden setting (<a href="/wiki/Category:CS1_maint:_overridden_setting" title="Category:CS1 maint: overridden setting">link</a>)</span> Section 22.4, Topological sort, pp. 549–552.</span> </li> <li id="cite_note-j50-17"><span class="mw-cite-backlink">^ <a href="#cite_ref-j50_17-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-j50_17-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFJungnickel2012">Jungnickel (2012)</a>, pp. 50–51.</span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text">For <a href="/wiki/Depth-first_search" title="Depth-first search">depth-first search</a> based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSkiena2009" class="citation cs2">Skiena, Steven S. (2009), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179"><i>The Algorithm Design Manual</i></a>, Springer, pp. <span class="nowrap">179–</span>181, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-84800-070-4" title="Special:BookSources/978-1-84800-070-4"><bdi>978-1-84800-070-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Algorithm+Design+Manual&rft.pages=%3Cspan+class%3D%22nowrap%22%3E179-%3C%2Fspan%3E181&rft.pub=Springer&rft.date=2009&rft.isbn=978-1-84800-070-4&rft.aulast=Skiena&rft.aufirst=Steven+S.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D7XUSn0IKQEgC%26pg%3DPA179&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFStanley1973" class="citation cs2"><a href="/wiki/Richard_P._Stanley" title="Richard P. Stanley">Stanley, Richard P.</a> (1973), <a rel="nofollow" class="external text" href="http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf">"Acyclic orientations of graphs"</a> <span class="cs1-format">(PDF)</span>, <i>Discrete Mathematics</i>, <b>5</b> (2): <span class="nowrap">171–</span>178, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2873%2990108-8">10.1016/0012-365X(73)90108-8</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Mathematics&rft.atitle=Acyclic+orientations+of+graphs&rft.volume=5&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E171-%3C%2Fspan%3E178&rft.date=1973&rft_id=info%3Adoi%2F10.1016%2F0012-365X%2873%2990108-8&rft.aulast=Stanley&rft.aufirst=Richard+P.&rft_id=http%3A%2F%2Fmath.mit.edu%2F~rstan%2Fpubs%2Fpubfiles%2F18.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFGareyJohnson1979" class="citation book cs2"><a href="/wiki/Michael_Garey" title="Michael Garey">Garey, Michael R.</a>; <a href="/wiki/David_S._Johnson" title="David S. Johnson">Johnson, David S.</a> (1979), <i><a href="/wiki/Computers_and_Intractability" title="Computers and Intractability">Computers and Intractability: A Guide to the Theory of NP-Completeness</a></i>, Series of Books in the Mathematical Sciences (1st ed.), New York: <a href="/wiki/W._H._Freeman_and_Company" title="W. H. Freeman and Company">W. H. Freeman and Company</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780716710455" title="Special:BookSources/9780716710455"><bdi>9780716710455</bdi></a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066">0519066</a>, <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/247570676">247570676</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computers+and+Intractability%3A+A+Guide+to+the+Theory+of+NP-Completeness&rft.place=New+York&rft.series=Series+of+Books+in+the+Mathematical+Sciences&rft.edition=1st&rft.pub=W.+H.+Freeman+and+Company&rft.date=1979&rft_id=info%3Aoclcnum%2F247570676&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D519066%23id-name%3DMR&rft.isbn=9780716710455&rft.aulast=Garey&rft.aufirst=Michael+R.&rft.au=Johnson%2C+David+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>, Problems GT7 and GT8, pp. 191–192.</span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHararyNormanCartwright1965" class="citation cs2"><a href="/wiki/Frank_Harary" title="Frank Harary">Harary, Frank</a>; Norman, Robert Z.; Cartwright, Dorwin (1965), <i>Structural Models: An Introduction to the Theory of Directed Graphs</i>, John Wiley & Sons, p. 63</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Structural+Models%3A+An+Introduction+to+the+Theory+of+Directed+Graphs&rft.pages=63&rft.pub=John+Wiley+%26+Sons&rft.date=1965&rft.aulast=Harary&rft.aufirst=Frank&rft.au=Norman%2C+Robert+Z.&rft.au=Cartwright%2C+Dorwin&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><a href="#CITEREFSkiena2009">Skiena (2009)</a>, p. 495.</span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><a href="#CITEREFSkiena2009">Skiena (2009)</a>, p. 496.</span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><a href="#CITEREFBang-JensenGutin2008">Bang-Jensen & Gutin (2008)</a>, p. 38.</span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPicard1976" class="citation cs2">Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", <i><a href="/wiki/Management_Science_(journal)" title="Management Science (journal)">Management Science</a></i>, <b>22</b> (11): <span class="nowrap">1268–</span>1272, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmnsc.22.11.1268">10.1287/mnsc.22.11.1268</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0403596">0403596</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Management+Science&rft.atitle=Maximal+closure+of+a+graph+and+applications+to+combinatorial+problems&rft.volume=22&rft.issue=11&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1268-%3C%2Fspan%3E1272&rft.date=1976&rft_id=info%3Adoi%2F10.1287%2Fmnsc.22.11.1268&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0403596%23id-name%3DMR&rft.aulast=Picard&rft.aufirst=Jean-Claude&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text">Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</span> </li> <li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text">Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</span> </li> <li id="cite_note-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text">Cormen et al. 2001, p. 966.</span> </li> <li id="cite_note-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-29">^</a></b></span> <span class="reference-text"><a href="#CITEREFSkiena2009">Skiena (2009)</a>, p. 469.</span> </li> <li id="cite_note-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-30">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFAl-MutawaDietrichMarslandMcCartin2014" class="citation cs2">Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C. (2014), "On the shape of circular dependencies in Java programs", <i>23rd Australian Software Engineering Conference</i>, IEEE, pp. <span class="nowrap">48–</span>57, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FASWEC.2014.15">10.1109/ASWEC.2014.15</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4799-3149-1" title="Special:BookSources/978-1-4799-3149-1"><bdi>978-1-4799-3149-1</bdi></a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17570052">17570052</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=On+the+shape+of+circular+dependencies+in+Java+programs&rft.btitle=23rd+Australian+Software+Engineering+Conference&rft.pages=%3Cspan+class%3D%22nowrap%22%3E48-%3C%2Fspan%3E57&rft.pub=IEEE&rft.date=2014&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A17570052%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FASWEC.2014.15&rft.isbn=978-1-4799-3149-1&rft.aulast=Al-Mutawa&rft.aufirst=H.+A.&rft.au=Dietrich%2C+J.&rft.au=Marsland%2C+S.&rft.au=McCartin%2C+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-hgt1181-31"><span class="mw-cite-backlink">^ <a href="#cite_ref-hgt1181_31-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-hgt1181_31-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFGrossYellenZhang2013" class="citation cs2">Gross, Jonathan L.; Yellen, Jay; <a href="/wiki/Ping_Zhang_(graph_theorist)" title="Ping Zhang (graph theorist)">Zhang, Ping</a> (2013), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181"><i>Handbook of Graph Theory</i></a> (2nd ed.), CRC Press, p. 1181, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4398-8018-0" title="Special:BookSources/978-1-4398-8018-0"><bdi>978-1-4398-8018-0</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Handbook+of+Graph+Theory&rft.pages=1181&rft.edition=2nd&rft.pub=CRC+Press&rft.date=2013&rft.isbn=978-1-4398-8018-0&rft.aulast=Gross&rft.aufirst=Jonathan+L.&rft.au=Yellen%2C+Jay&rft.au=Zhang%2C+Ping&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DcntcAgAAQBAJ%26pg%3DPA1181&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-32"><span class="mw-cite-backlink"><b><a href="#cite_ref-32">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSrikantShankar2007" class="citation cs2">Srikant, Y. N.; Shankar, Priti (2007), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39"><i>The Compiler Design Handbook: Optimizations and Machine Code Generation</i></a> (2nd ed.), CRC Press, pp. <span class="nowrap">19–</span>39, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4200-4383-9" title="Special:BookSources/978-1-4200-4383-9"><bdi>978-1-4200-4383-9</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Compiler+Design+Handbook%3A+Optimizations+and+Machine+Code+Generation&rft.pages=%3Cspan+class%3D%22nowrap%22%3E19-%3C%2Fspan%3E39&rft.edition=2nd&rft.pub=CRC+Press&rft.date=2007&rft.isbn=978-1-4200-4383-9&rft.aulast=Srikant&rft.aufirst=Y.+N.&rft.au=Shankar%2C+Priti&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D1kqAv-uDEPEC%26pg%3DSA19-PA39&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-33"><span class="mw-cite-backlink"><b><a href="#cite_ref-33">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFWang2002" class="citation cs2">Wang, John X. (2002), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160"><i>What Every Engineer Should Know About Decision Making Under Uncertainty</i></a>, CRC Press, p. 160, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8247-4373-4" title="Special:BookSources/978-0-8247-4373-4"><bdi>978-0-8247-4373-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=What+Every+Engineer+Should+Know+About+Decision+Making+Under+Uncertainty&rft.pages=160&rft.pub=CRC+Press&rft.date=2002&rft.isbn=978-0-8247-4373-4&rft.aulast=Wang&rft.aufirst=John+X.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DC3yKML0dUVIC%26pg%3DPA160&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-34"><span class="mw-cite-backlink"><b><a href="#cite_ref-34">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSapatnekar2004" class="citation cs2">Sapatnekar, Sachin (2004), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=fL9k-VkZVr0C&pg=PA133"><i>Timing</i></a>, Springer, p. 133, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4020-7671-8" title="Special:BookSources/978-1-4020-7671-8"><bdi>978-1-4020-7671-8</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Timing&rft.pages=133&rft.pub=Springer&rft.date=2004&rft.isbn=978-1-4020-7671-8&rft.aulast=Sapatnekar&rft.aufirst=Sachin&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DfL9k-VkZVr0C%26pg%3DPA133&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-35"><span class="mw-cite-backlink"><b><a href="#cite_ref-35">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFDennis1974" class="citation cs2">Dennis, Jack B. (1974), "First version of a data flow procedure language", <i>Programming Symposium</i>, Lecture Notes in Computer Science, vol. 19, pp. <span class="nowrap">362–</span>376, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-06859-7_145">10.1007/3-540-06859-7_145</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-06859-4" title="Special:BookSources/978-3-540-06859-4"><bdi>978-3-540-06859-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=First+version+of+a+data+flow+procedure+language&rft.btitle=Programming+Symposium&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E362-%3C%2Fspan%3E376&rft.date=1974&rft_id=info%3Adoi%2F10.1007%2F3-540-06859-7_145&rft.isbn=978-3-540-06859-4&rft.aulast=Dennis&rft.aufirst=Jack+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-36"><span class="mw-cite-backlink"><b><a href="#cite_ref-36">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFTouatide_Dinechin2014" class="citation cs2">Touati, Sid; de Dinechin, Benoit (2014), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=nO2-AwAAQBAJ&pg=PA123"><i>Advanced Backend Optimization</i></a>, John Wiley & Sons, p. 123, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-118-64894-0" title="Special:BookSources/978-1-118-64894-0"><bdi>978-1-118-64894-0</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Advanced+Backend+Optimization&rft.pages=123&rft.pub=John+Wiley+%26+Sons&rft.date=2014&rft.isbn=978-1-118-64894-0&rft.aulast=Touati&rft.aufirst=Sid&rft.au=de+Dinechin%2C+Benoit&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DnO2-AwAAQBAJ%26pg%3DPA123&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-37"><span class="mw-cite-backlink"><b><a href="#cite_ref-37">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFGarlandAnthony2003" class="citation cs2">Garland, Jeff; Anthony, Richard (2003), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=_2oQLLSqZ88C&pg=PA215"><i>Large-Scale Software Architecture: A Practical Guide using UML</i></a>, John Wiley & Sons, p. 215, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780470856383" title="Special:BookSources/9780470856383"><bdi>9780470856383</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Large-Scale+Software+Architecture%3A+A+Practical+Guide+using+UML&rft.pages=215&rft.pub=John+Wiley+%26+Sons&rft.date=2003&rft.isbn=9780470856383&rft.aulast=Garland&rft.aufirst=Jeff&rft.au=Anthony%2C+Richard&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D_2oQLLSqZ88C%26pg%3DPA215&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-38"><span class="mw-cite-backlink"><b><a href="#cite_ref-38">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFGopnikSchulz2007" class="citation cs2"><a href="/wiki/Alison_Gopnik" title="Alison Gopnik">Gopnik, Alison</a>; <a href="/wiki/Laura_Schulz" title="Laura Schulz">Schulz, Laura</a> (2007), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=35MKXlKoXIUC&pg=PA4"><i>Causal Learning</i></a>, Oxford University Press, p. 4, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-19-803928-0" title="Special:BookSources/978-0-19-803928-0"><bdi>978-0-19-803928-0</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Causal+Learning&rft.pages=4&rft.pub=Oxford+University+Press&rft.date=2007&rft.isbn=978-0-19-803928-0&rft.aulast=Gopnik&rft.aufirst=Alison&rft.au=Schulz%2C+Laura&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D35MKXlKoXIUC%26pg%3DPA4&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-39"><span class="mw-cite-backlink"><b><a href="#cite_ref-39">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFShmulevichDougherty2010" class="citation cs2">Shmulevich, Ilya; Dougherty, Edward R. (2010), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=RfshqEgO7KgC&pg=PA58"><i>Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks</i></a>, Society for Industrial and Applied Mathematics, p. 58, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-89871-692-4" title="Special:BookSources/978-0-89871-692-4"><bdi>978-0-89871-692-4</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Probabilistic+Boolean+Networks%3A+The+Modeling+and+Control+of+Gene+Regulatory+Networks&rft.pages=58&rft.pub=Society+for+Industrial+and+Applied+Mathematics&rft.date=2010&rft.isbn=978-0-89871-692-4&rft.aulast=Shmulevich&rft.aufirst=Ilya&rft.au=Dougherty%2C+Edward+R.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DRfshqEgO7KgC%26pg%3DPA58&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-40"><span class="mw-cite-backlink"><b><a href="#cite_ref-40">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCowellDawidLauritzenSpiegelhalter1999" class="citation cs2">Cowell, Robert G.; <a href="/wiki/Philip_Dawid" title="Philip Dawid">Dawid, A. Philip</a>; <a href="/wiki/Steffen_Lauritzen" title="Steffen Lauritzen">Lauritzen, Steffen L.</a>; <a href="/wiki/David_Spiegelhalter" title="David Spiegelhalter">Spiegelhalter, David J.</a> (1999), "3.2.1 Moralization", <i>Probabilistic Networks and Expert Systems</i>, Springer, pp. <span class="nowrap">31–</span>33, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-98767-5" title="Special:BookSources/978-0-387-98767-5"><bdi>978-0-387-98767-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=3.2.1+Moralization&rft.btitle=Probabilistic+Networks+and+Expert+Systems&rft.pages=%3Cspan+class%3D%22nowrap%22%3E31-%3C%2Fspan%3E33&rft.pub=Springer&rft.date=1999&rft.isbn=978-0-387-98767-5&rft.aulast=Cowell&rft.aufirst=Robert+G.&rft.au=Dawid%2C+A.+Philip&rft.au=Lauritzen%2C+Steffen+L.&rft.au=Spiegelhalter%2C+David+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-41"><span class="mw-cite-backlink"><b><a href="#cite_ref-41">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFDorf1998" class="citation cs2">Dorf, Richard C. (1998), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7"><i>The Technology Management Handbook</i></a>, CRC Press, p. 9-7, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8493-8577-3" title="Special:BookSources/978-0-8493-8577-3"><bdi>978-0-8493-8577-3</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Technology+Management+Handbook&rft.pages=9%26%2345%3B7&rft.pub=CRC+Press&rft.date=1998&rft.isbn=978-0-8493-8577-3&rft.aulast=Dorf&rft.aufirst=Richard+C.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DC2u8I0DFo4IC%26pg%3DSA9-PA7&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-42"><span class="mw-cite-backlink"><b><a href="#cite_ref-42">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBoslaugh2008" class="citation cs2">Boslaugh, Sarah (2008), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=wObgnN3x14kC&pg=PA255"><i>Encyclopedia of Epidemiology, Volume 1</i></a>, SAGE, p. 255, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4129-2816-8" title="Special:BookSources/978-1-4129-2816-8"><bdi>978-1-4129-2816-8</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Encyclopedia+of+Epidemiology%2C+Volume+1&rft.pages=255&rft.pub=SAGE&rft.date=2008&rft.isbn=978-1-4129-2816-8&rft.aulast=Boslaugh&rft.aufirst=Sarah&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DwObgnN3x14kC%26pg%3DPA255&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-pearl:95-43"><span class="mw-cite-backlink"><b><a href="#cite_ref-pearl:95_43-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPearl1995" class="citation cs2">Pearl, Judea (1995), <a rel="nofollow" class="external text" href="https://escholarship.org/uc/item/6gv9n38c">"Causal diagrams for empirical research"</a>, <i>Biometrika</i>, <b>82</b> (4): <span class="nowrap">669–</span>709, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fbiomet%2F82.4.669">10.1093/biomet/82.4.669</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Biometrika&rft.atitle=Causal+diagrams+for+empirical+research&rft.volume=82&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E669-%3C%2Fspan%3E709&rft.date=1995&rft_id=info%3Adoi%2F10.1093%2Fbiomet%2F82.4.669&rft.aulast=Pearl&rft.aufirst=Judea&rft_id=https%3A%2F%2Fescholarship.org%2Fuc%2Fitem%2F6gv9n38c&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-44"><span class="mw-cite-backlink"><b><a href="#cite_ref-44">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFKirkpatrick2011" class="citation cs2">Kirkpatrick, Bonnie B. (April 2011), "Haplotypes versus genotypes on pedigrees", <i>Algorithms for Molecular Biology</i>, <b>6</b> (10): 10, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1186%2F1748-7188-6-10">10.1186/1748-7188-6-10</a></span>, <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3102622">3102622</a></span>, <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21504603">21504603</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Algorithms+for+Molecular+Biology&rft.atitle=Haplotypes+versus+genotypes+on+pedigrees&rft.volume=6&rft.issue=10&rft.pages=10&rft.date=2011-04&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3102622%23id-name%3DPMC&rft_id=info%3Apmid%2F21504603&rft_id=info%3Adoi%2F10.1186%2F1748-7188-6-10&rft.aulast=Kirkpatrick&rft.aufirst=Bonnie+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-45"><span class="mw-cite-backlink"><b><a href="#cite_ref-45">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFMcGuffinBalakrishnan2005" class="citation cs2">McGuffin, M. J.; Balakrishnan, R. (2005), <a rel="nofollow" class="external text" href="http://profs.etsmtl.ca/mMcGuffin/research/genealogyVis/genealogyVis.pdf">"Interactive visualization of genealogical graphs"</a> <span class="cs1-format">(PDF)</span>, <i>IEEE Symposium on Information Visualization (INFOVIS 2005)</i>, pp. <span class="nowrap">16–</span>23, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FINFVIS.2005.1532124">10.1109/INFVIS.2005.1532124</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7803-9464-3" title="Special:BookSources/978-0-7803-9464-3"><bdi>978-0-7803-9464-3</bdi></a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15449409">15449409</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Interactive+visualization+of+genealogical+graphs&rft.btitle=IEEE+Symposium+on+Information+Visualization+%28INFOVIS+2005%29&rft.pages=%3Cspan+class%3D%22nowrap%22%3E16-%3C%2Fspan%3E23&rft.date=2005&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A15449409%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FINFVIS.2005.1532124&rft.isbn=978-0-7803-9464-3&rft.aulast=McGuffin&rft.aufirst=M.+J.&rft.au=Balakrishnan%2C+R.&rft_id=http%3A%2F%2Fprofs.etsmtl.ca%2FmMcGuffin%2Fresearch%2FgenealogyVis%2FgenealogyVis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-46"><span class="mw-cite-backlink"><b><a href="#cite_ref-46">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBenderPemmasaniSkienaSumazin2001" class="citation cs2">Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001), <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=365411.365795">"Finding least common ancestors in directed acyclic graphs"</a>, <i>Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01)</i>, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. <span class="nowrap">845–</span>854, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-89871-490-6" title="Special:BookSources/978-0-89871-490-6"><bdi>978-0-89871-490-6</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Finding+least+common+ancestors+in+directed+acyclic+graphs&rft.btitle=Proceedings+of+the+Twelfth+Annual+ACM-SIAM+Symposium+on+Discrete+Algorithms+%28SODA+%2701%29&rft.place=Philadelphia%2C+PA%2C+USA&rft.pages=%3Cspan+class%3D%22nowrap%22%3E845-%3C%2Fspan%3E854&rft.pub=Society+for+Industrial+and+Applied+Mathematics&rft.date=2001&rft.isbn=978-0-89871-490-6&rft.aulast=Bender&rft.aufirst=Michael+A.&rft.au=Pemmasani%2C+Giridhar&rft.au=Skiena%2C+Steven&rft.au=Sumazin%2C+Pavel&rft_id=http%3A%2F%2Fdl.acm.org%2Fcitation.cfm%3Fid%3D365411.365795&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-47"><span class="mw-cite-backlink"><b><a href="#cite_ref-47">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBartlang2010" class="citation cs2">Bartlang, Udo (2010), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=vXdEAAAAQBAJ&pg=PA59"><i>Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems</i></a>, Springer, p. 59, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010aamf.book.....B">2010aamf.book.....B</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-8348-9645-2" title="Special:BookSources/978-3-8348-9645-2"><bdi>978-3-8348-9645-2</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Architecture+and+Methods+for+Flexible+Content+Management+in+Peer-to-Peer+Systems&rft.pages=59&rft.pub=Springer&rft.date=2010&rft_id=info%3Abibcode%2F2010aamf.book.....B&rft.isbn=978-3-8348-9645-2&rft.aulast=Bartlang&rft.aufirst=Udo&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DvXdEAAAAQBAJ%26pg%3DPA59&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-48"><span class="mw-cite-backlink"><b><a href="#cite_ref-48">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPachSharir" class="citation cs2"><a href="/wiki/J%C3%A1nos_Pach" title="János Pach">Pach, János</a>; <a href="/wiki/Micha_Sharir" title="Micha Sharir">Sharir, Micha</a>, <a rel="nofollow" class="external text" href="https://books.google.com/books?id=-fguzNaYoqcC&pg=PA93"><i>Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures</i></a>, Mathematical surveys and monographs, vol. 152, American Mathematical Society, pp. <span class="nowrap">93–</span>94, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8218-7533-9" title="Special:BookSources/978-0-8218-7533-9"><bdi>978-0-8218-7533-9</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Combinatorial+Geometry+and+Its+Algorithmic+Applications%3A+The+Alcal%C3%A1+Lectures&rft.series=Mathematical+surveys+and+monographs&rft.pages=%3Cspan+class%3D%22nowrap%22%3E93-%3C%2Fspan%3E94&rft.pub=American+Mathematical+Society&rft.isbn=978-0-8218-7533-9&rft.aulast=Pach&rft.aufirst=J%C3%A1nos&rft.au=Sharir%2C+Micha&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D-fguzNaYoqcC%26pg%3DPA93&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-49"><span class="mw-cite-backlink"><b><a href="#cite_ref-49">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPrice1965" class="citation cs2">Price, Derek J. de Solla (July 30, 1965), <a rel="nofollow" class="external text" href="http://garfield.library.upenn.edu/papers/pricenetworks1965.pdf">"Networks of Scientific Papers"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Science_(journal)" title="Science (journal)">Science</a></i>, <b>149</b> (3683): <span class="nowrap">510–</span>515, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1965Sci...149..510D">1965Sci...149..510D</a>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1126%2Fscience.149.3683.510">10.1126/science.149.3683.510</a>, <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/14325149">14325149</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Science&rft.atitle=Networks+of+Scientific+Papers&rft.volume=149&rft.issue=3683&rft.pages=%3Cspan+class%3D%22nowrap%22%3E510-%3C%2Fspan%3E515&rft.date=1965-07-30&rft_id=info%3Apmid%2F14325149&rft_id=info%3Adoi%2F10.1126%2Fscience.149.3683.510&rft_id=info%3Abibcode%2F1965Sci...149..510D&rft.aulast=Price&rft.aufirst=Derek+J.+de+Solla&rft_id=http%3A%2F%2Fgarfield.library.upenn.edu%2Fpapers%2Fpricenetworks1965.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-50"><span class="mw-cite-backlink"><b><a href="#cite_ref-50">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPrice1976" class="citation cs2">Price, Derek J. de Solla (1976), "A general theory of bibliometric and other cumulative advantage processes", <i><a href="/wiki/Journal_of_the_American_Society_for_Information_Science" class="mw-redirect" title="Journal of the American Society for Information Science">Journal of the American Society for Information Science</a></i>, <b>27</b> (5): <span class="nowrap">292–</span>306, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fasi.4630270505">10.1002/asi.4630270505</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8536863">8536863</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+American+Society+for+Information+Science&rft.atitle=A+general+theory+of+bibliometric+and+other+cumulative+advantage+processes&rft.volume=27&rft.issue=5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E292-%3C%2Fspan%3E306&rft.date=1976&rft_id=info%3Adoi%2F10.1002%2Fasi.4630270505&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A8536863%23id-name%3DS2CID&rft.aulast=Price&rft.aufirst=Derek+J.+de+Solla&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-51"><span class="mw-cite-backlink"><b><a href="#cite_ref-51">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCloughGollingsLoachEvans2015" class="citation cs2">Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S. (2015), "Transitive reduction of citation networks", <i>Journal of Complex Networks</i>, <b>3</b> (2): <span class="nowrap">189–</span>203, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1310.8224">1310.8224</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomnet%2Fcnu039">10.1093/comnet/cnu039</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10228152">10228152</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Complex+Networks&rft.atitle=Transitive+reduction+of+citation+networks&rft.volume=3&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E189-%3C%2Fspan%3E203&rft.date=2015&rft_id=info%3Aarxiv%2F1310.8224&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10228152%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1093%2Fcomnet%2Fcnu039&rft.aulast=Clough&rft.aufirst=James+R.&rft.au=Gollings%2C+Jamie&rft.au=Loach%2C+Tamar+V.&rft.au=Evans%2C+Tim+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-ECV-52"><span class="mw-cite-backlink"><b><a href="#cite_ref-ECV_52-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFEvansCalmonVasiliauskaite2020" class="citation cs2">Evans, T.S.; Calmon, L.; Vasiliauskaite, V. (2020), "The Longest Path in the Price Model", <i>Scientific Reports</i>, <b>10</b> (1): 10503, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1903.03667">1903.03667</a></span>, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2020NatSR..1010503E">2020NatSR..1010503E</a>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fs41598-020-67421-8">10.1038/s41598-020-67421-8</a>, <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7324613">7324613</a></span>, <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/32601403">32601403</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Scientific+Reports&rft.atitle=The+Longest+Path+in+the+Price+Model&rft.volume=10&rft.issue=1&rft.pages=10503&rft.date=2020&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC7324613%23id-name%3DPMC&rft_id=info%3Abibcode%2F2020NatSR..1010503E&rft_id=info%3Aarxiv%2F1903.03667&rft_id=info%3Apmid%2F32601403&rft_id=info%3Adoi%2F10.1038%2Fs41598-020-67421-8&rft.aulast=Evans&rft.aufirst=T.S.&rft.au=Calmon%2C+L.&rft.au=Vasiliauskaite%2C+V.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span></span> </li> <li id="cite_note-53"><span class="mw-cite-backlink"><b><a href="#cite_ref-53">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCrochemoreVérin1997" class="citation cs2">Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs", <i>Combinatorial Pattern Matching</i>, Lecture Notes in Computer Science, vol. 1264, Springer, pp. <span class="nowrap">116–</span>129, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6273">10.1.1.53.6273</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-63220-4_55">10.1007/3-540-63220-4_55</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-63220-7" title="Special:BookSources/978-3-540-63220-7"><bdi>978-3-540-63220-7</bdi></a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17045308">17045308</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Direct+construction+of+compact+directed+acyclic+word+graphs&rft.btitle=Combinatorial+Pattern+Matching&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E116-%3C%2Fspan%3E129&rft.pub=Springer&rft.date=1997&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.53.6273%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A17045308%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2F3-540-63220-4_55&rft.isbn=978-3-540-63220-7&rft.aulast=Crochemore&rft.aufirst=Maxime&rft.au=V%C3%A9rin%2C+Renaud&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-54"><span class="mw-cite-backlink"><b><a href="#cite_ref-54">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFLothaire2005" class="citation cs2"><a href="/wiki/M._Lothaire" title="M. Lothaire">Lothaire, M.</a> (2005), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=fpLUNkj1T1EC&pg=PA18"><i>Applied Combinatorics on Words</i></a>, Encyclopedia of Mathematics and its Applications, vol. 105, Cambridge University Press, p. 18, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521848022" title="Special:BookSources/9780521848022"><bdi>9780521848022</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Applied+Combinatorics+on+Words&rft.series=Encyclopedia+of+Mathematics+and+its+Applications&rft.pages=18&rft.pub=Cambridge+University+Press&rft.date=2005&rft.isbn=9780521848022&rft.aulast=Lothaire&rft.aufirst=M.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DfpLUNkj1T1EC%26pg%3DPA18&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-55"><span class="mw-cite-backlink"><b><a href="#cite_ref-55">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFLee1959" class="citation cs2">Lee, C. Y. (1959), "Representation of switching circuits by binary-decision programs", <i>Bell System Technical Journal</i>, <b>38</b> (4): <span class="nowrap">985–</span>999, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fj.1538-7305.1959.tb01585.x">10.1002/j.1538-7305.1959.tb01585.x</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Bell+System+Technical+Journal&rft.atitle=Representation+of+switching+circuits+by+binary-decision+programs&rft.volume=38&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E985-%3C%2Fspan%3E999&rft.date=1959&rft_id=info%3Adoi%2F10.1002%2Fj.1538-7305.1959.tb01585.x&rft.aulast=Lee&rft.aufirst=C.+Y.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-56"><span class="mw-cite-backlink"><b><a href="#cite_ref-56">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFAkers1978" class="citation cs2">Akers, Sheldon B. (1978), "Binary decision diagrams", <i>IEEE Transactions on Computers</i>, <b>C-27</b> (6): <span class="nowrap">509–</span>516, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTC.1978.1675141">10.1109/TC.1978.1675141</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:21028055">21028055</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Computers&rft.atitle=Binary+decision+diagrams&rft.volume=C-27&rft.issue=6&rft.pages=%3Cspan+class%3D%22nowrap%22%3E509-%3C%2Fspan%3E516&rft.date=1978&rft_id=info%3Adoi%2F10.1109%2FTC.1978.1675141&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A21028055%23id-name%3DS2CID&rft.aulast=Akers&rft.aufirst=Sheldon+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> <li id="cite_note-57"><span class="mw-cite-backlink"><b><a href="#cite_ref-57">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFFriedmanSupowit1987" class="citation cs2">Friedman, S. J.; Supowit, K. J. (1987), "Finding the optimal variable ordering for binary decision diagrams", <i>Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)</i>, New York, NY, USA: ACM, pp. <span class="nowrap">348–</span>356, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F37888.37941">10.1145/37888.37941</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8186-0781-3" title="Special:BookSources/978-0-8186-0781-3"><bdi>978-0-8186-0781-3</bdi></a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14796451">14796451</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Finding+the+optimal+variable+ordering+for+binary+decision+diagrams&rft.btitle=Proc.+24th+ACM%2FIEEE+Design+Automation+Conference+%28DAC+%2787%29&rft.place=New+York%2C+NY%2C+USA&rft.pages=%3Cspan+class%3D%22nowrap%22%3E348-%3C%2Fspan%3E356&rft.pub=ACM&rft.date=1987&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A14796451%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F37888.37941&rft.isbn=978-0-8186-0781-3&rft.aulast=Friedman&rft.aufirst=S.+J.&rft.au=Supowit%2C+K.+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span>.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Directed_acyclic_graph&action=edit&section=21" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Commons-logo.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></a></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Directed_acyclic_graphs" class="extiw" title="commons:Category:Directed acyclic graphs">directed acyclic graphs</a></span>.</div></div> </div> <ul><li><span class="citation mathworld" id="Reference-Mathworld-Acyclic_Digraph"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFWeisstein" class="citation web cs2"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a>, <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/AcyclicDigraph.html">"Acyclic Digraph"</a>, <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Acyclic+Digraph&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FAcyclicDigraph.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADirected+acyclic+graph" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_web" title="Template:Cite web">cite web</a>}}</code>: CS1 maint: overridden setting (<a href="/wiki/Category:CS1_maint:_overridden_setting" title="Category:CS1 maint: overridden setting">link</a>)</span></span></li> <li><a rel="nofollow" class="external text" href="http://www.dagitty.net/">DAGitty</a> – an online tool for creating DAGs</li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Directed_acyclic_graph&oldid=1261432631">https://en.wikipedia.org/w/index.php?title=Directed_acyclic_graph&oldid=1261432631</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Directed_graphs" title="Category:Directed graphs">Directed graphs</a></li><li><a href="/wiki/Category:Directed_acyclic_graphs" title="Category:Directed acyclic graphs">Directed acyclic graphs</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_maint:_overridden_setting" title="Category:CS1 maint: overridden setting">CS1 maint: overridden setting</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Good_articles" title="Category:Good articles">Good articles</a></li><li><a href="/wiki/Category:Commons_category_link_is_on_Wikidata" title="Category:Commons category link is on Wikidata">Commons category link is on Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 6 December 2024, at 02:14<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Directed_acyclic_graph&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Directed acyclic graph</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>22 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-76d4c66f66-swv52","wgBackendResponseTime":144,"wgPageParseReport":{"limitreport":{"cputime":"0.782","walltime":"0.909","ppvisitednodes":{"value":5251,"limit":1000000},"postexpandincludesize":{"value":126381,"limit":2097152},"templateargumentsize":{"value":3393,"limit":2097152},"expansiondepth":{"value":13,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":198563,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 749.444 1 -total"," 56.12% 420.623 1 Template:Reflist"," 45.12% 338.183 47 Template:Citation"," 9.63% 72.164 1 Template:Short_description"," 8.06% 60.421 1 Template:Commons_category"," 7.70% 57.715 7 Template:Harvtxt"," 7.43% 55.686 1 Template:Sister_project"," 7.21% 54.001 1 Template:Side_box"," 6.20% 46.489 30 Template:Main_other"," 5.80% 43.435 2 Template:Pagetype"]},"scribunto":{"limitreport-timeusage":{"value":"0.495","limit":"10.000"},"limitreport-memusage":{"value":7319967,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREF\"] = 1,\n [\"CITEREFAkers1978\"] = 1,\n [\"CITEREFAl-MutawaDietrichMarslandMcCartin2014\"] = 1,\n [\"CITEREFBanerjee1993\"] = 1,\n [\"CITEREFBang-Jensen2008\"] = 1,\n [\"CITEREFBang-JensenGutin2008\"] = 1,\n [\"CITEREFBartlang2010\"] = 1,\n [\"CITEREFBenderPemmasaniSkienaSumazin2001\"] = 1,\n [\"CITEREFBenderWilliamson2005\"] = 1,\n [\"CITEREFBoslaugh2008\"] = 1,\n [\"CITEREFChristofides1975\"] = 1,\n [\"CITEREFCloughGollingsLoachEvans2015\"] = 1,\n [\"CITEREFCowellDawidLauritzenSpiegelhalter1999\"] = 1,\n [\"CITEREFCrochemoreVérin1997\"] = 1,\n [\"CITEREFDennis1974\"] = 1,\n [\"CITEREFDorf1998\"] = 1,\n [\"CITEREFEvansCalmonVasiliauskaite2020\"] = 1,\n [\"CITEREFFriedmanSupowit1987\"] = 1,\n [\"CITEREFFurnasZacks1994\"] = 1,\n [\"CITEREFGarlandAnthony2003\"] = 1,\n [\"CITEREFGopnikSchulz2007\"] = 1,\n [\"CITEREFGrossYellenZhang2013\"] = 1,\n [\"CITEREFHararyNormanCartwright1965\"] = 1,\n [\"CITEREFHararyPalmer1973\"] = 1,\n [\"CITEREFJungnickel2012\"] = 1,\n [\"CITEREFKirkpatrick2011\"] = 1,\n [\"CITEREFKozen1992\"] = 1,\n [\"CITEREFLee1959\"] = 1,\n [\"CITEREFLothaire2005\"] = 1,\n [\"CITEREFMcGuffinBalakrishnan2005\"] = 1,\n [\"CITEREFMcKayRoyleWanlessOggier2004\"] = 1,\n [\"CITEREFMitrani1982\"] = 1,\n [\"CITEREFPachSharir\"] = 1,\n [\"CITEREFPearl1995\"] = 1,\n [\"CITEREFPicard1976\"] = 1,\n [\"CITEREFPrice1965\"] = 1,\n [\"CITEREFPrice1976\"] = 1,\n [\"CITEREFRebanePearl1987\"] = 1,\n [\"CITEREFRobinson1973\"] = 1,\n [\"CITEREFSapatnekar2004\"] = 1,\n [\"CITEREFSedgewickWayne2011\"] = 1,\n [\"CITEREFShmulevichDougherty2010\"] = 1,\n [\"CITEREFSkiena2009\"] = 1,\n [\"CITEREFSrikantShankar2007\"] = 1,\n [\"CITEREFStanley1973\"] = 1,\n [\"CITEREFThulasiramanSwamy1992\"] = 1,\n [\"CITEREFTouatide_Dinechin2014\"] = 1,\n [\"CITEREFWang2002\"] = 1,\n}\ntemplate_list = table#1 {\n [\"!\"] = 2,\n [\"CS1 config\"] = 1,\n [\"Citation\"] = 47,\n [\"Commons category\"] = 1,\n [\"Garey-Johnson\"] = 1,\n [\"Good article\"] = 1,\n [\"Harvtxt\"] = 7,\n [\"Hyphen\"] = 1,\n [\"Introduction to Algorithms\"] = 1,\n [\"Main\"] = 3,\n [\"Math\"] = 26,\n [\"MathWorld\"] = 2,\n [\"Multiple image\"] = 3,\n [\"Mvar\"] = 34,\n [\"Not a typo\"] = 1,\n [\"OEIS\"] = 1,\n [\"Reflist\"] = 1,\n [\"Short description\"] = 1,\n}\narticle_whitelist = table#1 {\n}\nciteref_patterns = table#1 {\n}\n"},"cachereport":{"origin":"mw-api-int.codfw.main-5f44755944-gts2x","timestamp":"20250302033331","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Directed acyclic graph","url":"https:\/\/en.wikipedia.org\/wiki\/Directed_acyclic_graph","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1195339","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1195339","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-03-31T11:24:59Z","dateModified":"2024-12-06T02:14:48Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/f\/fe\/Tred-G.svg","headline":"directed graph with no directed cycles"}</script> </body> </html>