{"id":26934,"date":"2016-11-22T10:29:48","date_gmt":"2016-11-22T08:29:48","guid":{"rendered":"https:\/\/mamchenkov.net\/wordpress\/?p=26934"},"modified":"2016-11-22T10:29:48","modified_gmt":"2016-11-22T08:29:48","slug":"dependency-resolution-with-graphs-in-php","status":"publish","type":"post","link":"https:\/\/mamchenkov.net\/wordpress\/2016\/11\/22\/dependency-resolution-with-graphs-in-php\/","title":{"rendered":"Dependency resolution with graphs in PHP"},"content":{"rendered":"\n

One of the projects I am working on at work presented an interesting problem. \u00a0I had a list of items with dependencies on one another and I needed to figure out the order in which to use those items, based on their dependencies.<\/p>\n

For the sake of the example, think of a list of database tables, which reference each other. \u00a0I need a way to export those tables in such a way, that when imported back in, tables that have dependencies will be imported after all those tables on which they depend. \u00a0(It’s not the real task I’m working on, but close enough.)<\/p>\n

Consider the following list as an example of input data:<\/p>\n

\r\n\/\/ List of items with dependencies.  Order is not important\r\n$tables = [ \r\n    'articles_meta' => ['articles'],\r\n    'articles' => ['users', 'categories', 'tags'],\r\n    'categories' => [],\r\n    'comments' => ['users', 'articles'],\r\n    'options' => [],\r\n    'tags' => [],\r\n    'users' => [],\r\n    'users_meta' => ['users'],\r\n];\r\n<\/pre>\n
The result of the dependency resolution should give me the list like this (there are variations in order, of course, as long as the dependencies are satisfied):<\/p>\n
\r\ncategories\r\noptions\r\ntags\r\nusers\r\nusers_meta\r\narticles\r\narticles_meta\r\ncomments\r\n<\/pre>\n
There are several ways to solve this problem. \u00a0My first attempt took about 50 lines of code and worked fine, but it lacked elegance. \u00a0It had too many nested loops and tricky conditions and was difficult to read. \u00a0My second attempt was slightly better, with a bit of a recursion, but still looked somewhat off. \u00a0It felt like there is a better way to do it, and that I’ve done something similar before, but I could put my finger on it.<\/p>\n
I thought I’d take a look at something that solves a similar problem. \u00a0Composer<\/a>, PHP package and dependency manager, surely had something to offer. \u00a0A brief check of the GitHub repository<\/a>, and that idea is out of my hand. \u00a0Composer deals with much more complex issues, so its Dependency Resolver<\/a>\u00a0code is not something I can grasp\u00a0in a few\u00a0minutes.<\/p>\n
It was time for some Googling. \u00a0Moments later, my deja vu feeling of “I’ve seen this before” was easily explained. \u00a0This problem fits into the graph theory<\/a>, which I probably used last back in my college years. \u00a0Of course, I could have grabbed the book off the shelf and refresh my knowledge, practicing the sacred art of the Real Programming. \u00a0But time was an issue, so I cheated.<\/p>\n
I found this “Dependency resolving algorithm<\/a>” blog post by Ferry Boender over at Electric Monk<\/a>\u00a0(thanks man!). \u00a0He had exactly what I needed – simple and straight forward recursive algorithm for walking the graph, circular dependency detection, and even some performance optimization.<\/p>\n
\"dep_graph1\"<\/p>\n
The only problem was that his code is all in Python. \u00a0But that’s not really a problem. \u00a0So I’ve rewritten his code in PHP and got exactly what I needed. \u00a0Here it is:<\/p>\n
\r\n\/\/ List of items with dependencies.  Order is not important\r\n$tables = [\r\n    'articles_meta' => ['articles'],\r\n    'articles' => ['users', 'categories', 'tags'],\r\n    'categories' => [],\r\n    'comments' => ['users', 'articles'],\r\n    'options' => [],\r\n    'tags' => [],\r\n    'users' => [],\r\n    'users_meta' => ['users'],\r\n];\r\n\r\n$resolved = []; \r\n$unresolved = []; \r\n\/\/ Resolve dependencies for each table\r\nforeach (array_keys($tables) as $table) {\r\n    try {\r\n        list ($resolved, $unresolved) = dep_resolve($table, $tables, $resolved, $unresolved);\r\n    } catch (\\Exception $e) {\r\n        die("Oops! " . $e->getMessage());\r\n    }   \r\n}\r\n\r\n\/\/ Print out result\r\nforeach ($resolved as $table) {\r\n    $deps = empty($tables[$table]) ? 'none' : join(',', $tables[$table]);\r\n    print "$table (deps: $deps)\\n";\r\n}\r\n\r\n\/**\r\n * Recursive dependency resolution\r\n * \r\n * @param string $item Item to resolve dependencies for\r\n * @param array $items List of all items with dependencies\r\n * @param array $resolved List of resolved items\r\n * @param array $unresolved List of unresolved items\r\n * @return array\r\n *\/\r\nfunction dep_resolve($item, array $items, array $resolved, array $unresolved) {\r\n    array_push($unresolved, $item);\r\n    foreach ($items[$item] as $dep) {\r\n        if (!in_array($dep, $resolved)) {\r\n            if (!in_array($dep, $unresolved)) {\r\n                array_push($unresolved, $dep);\r\n                list($resolved, $unresolved) = dep_resolve($dep, $items, $resolved, $unresolved);\r\n            } else {\r\n                throw new \\RuntimeException("Circular dependency: $item -> $dep");\r\n            }\r\n        }\r\n    }\r\n    \/\/ Add $item to $resolved if it's not already there\r\n    if (!in_array($item, $resolved)) {\r\n        array_push($resolved, $item);\r\n    }\r\n    \/\/ Remove all occurrences of $item in $unresolved\r\n    while (($index = array_search($item, $unresolved)) !== false) {\r\n        unset($unresolved[$index]);\r\n    }\r\n\r\n    return [$resolved, $unresolved];\r\n}\r\n<\/pre>\n
Running the above code produces the following result:<\/p>\n
\r\n$ php dependecy.php \r\nusers (deps: none)\r\ncategories (deps: none)\r\ntags (deps: none)\r\narticles (deps: users,categories,tags)\r\narticles_meta (deps: articles)\r\ncomments (deps: users,articles)\r\noptions (deps: none)\r\nusers_meta (deps: users)\r\n<\/pre>\n
Which is exactly what I was looking for. \u00a0And now that I have it here, I’ll probably be needing it again and again. \u00a0It’s an elegant hammer to a lot of my nails.<\/p>\n\n","protected":false},"excerpt":{"rendered":"\n
One of the projects I am working on at work presented an interesting problem. \u00a0I had a list of items with dependencies on one another and I needed to figure out the order in which to use those items, based on their dependencies. For the sake of the example, think of a list of database … Continue reading Dependency resolution with graphs in PHP<\/span><\/a><\/p>\n\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"Dependency resolution with graphs in PHP #PHP #WebDev #ComputerScience #algorithms #programming","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_links_to":"","_links_to_target":""},"categories":[1,18,62,1334],"tags":[850,1192,38,1330],"keyring_services":[],"class_list":["post-26934","post","type-post","status-publish","format-standard","hentry","category-general","category-programming","category-technology","category-web-work","tag-algorithms","tag-computer-science","tag-php","tag-web-development"],"aioseo_notices":[],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":44293,"url":"https:\/\/mamchenkov.net\/wordpress\/2019\/09\/23\/github-adds-php-and-composer-dependency-graphs\/","url_meta":{"origin":26934,"position":0},"title":"GitHub adds PHP and Composer dependency graphs","author":"Leonid Mamchenkov","date":"September 23, 2019","format":false,"excerpt":"Here are some great news from GitHub: Dependency graph support is now available for PHP repositories with Composer dependencies. You may see security alerts on your repositories as dependency graph support rolls out. When there\u2019s a published vulnerability on any of the Composer dependencies that your project lists in\u00a0composer.json\u00a0and\u00a0composer.lock\u00a0files, GitHub\u2026","rel":"","context":"In "All"","block_context":{"text":"All","link":"https:\/\/mamchenkov.net\/wordpress\/category\/general\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/09\/github-php-composer.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/09\/github-php-composer.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/09\/github-php-composer.png?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/09\/github-php-composer.png?resize=700%2C400&ssl=1 2x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/09\/github-php-composer.png?resize=1050%2C600&ssl=1 3x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/09\/github-php-composer.png?resize=1400%2C800&ssl=1 4x"},"classes":[]},{"id":27289,"url":"https:\/\/mamchenkov.net\/wordpress\/2017\/02\/03\/preparing-for-the-phpunit-6-and-php-7\/","url_meta":{"origin":26934,"position":1},"title":"Preparing for the PHPUnit 6 and PHP 7","author":"Leonid Mamchenkov","date":"February 3, 2017","format":false,"excerpt":"If you woke up today and found that most of your PHP projects' and libraries' tests break and fail, I have news for you: \u00a0you are doing something wrong. \u00a0How do I know? \u00a0Because I was doing something wrong too... First of all, let me save you all the extra\u2026","rel":"","context":"In "All"","block_context":{"text":"All","link":"https:\/\/mamchenkov.net\/wordpress\/category\/general\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2017\/02\/travis-phpunit-500x317.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":30254,"url":"https:\/\/mamchenkov.net\/wordpress\/2019\/01\/29\/php-composer-galaxy\/","url_meta":{"origin":26934,"position":2},"title":"PHP : Composer Galaxy","author":"Leonid Mamchenkov","date":"January 29, 2019","format":false,"excerpt":"PHP has one of the greatest, in my opinion, dependency managers - Composer. The tool works mostly with the public projects via the Packagist website (although it also supports private repositories). There are over 200,000 packages available on the Packagist to choose from. However, the stats could be a lot\u2026","rel":"","context":"In "All"","block_context":{"text":"All","link":"https:\/\/mamchenkov.net\/wordpress\/category\/general\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/01\/composer.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/01\/composer.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/01\/composer.png?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/01\/composer.png?resize=700%2C400&ssl=1 2x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/01\/composer.png?resize=1050%2C600&ssl=1 3x, https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2019\/01\/composer.png?resize=1400%2C800&ssl=1 4x"},"classes":[]},{"id":28182,"url":"https:\/\/mamchenkov.net\/wordpress\/2017\/11\/06\/object-graph-visualizing-php-objects\/","url_meta":{"origin":26934,"position":3},"title":"object-graph – visualizing PHP objects","author":"Leonid Mamchenkov","date":"November 6, 2017","format":false,"excerpt":"As you might know, I am a big fan of GraphViz.\u00a0 I've used numerous times for visualizing different parts of the project code and dependencies (see here and here for example). Today I came across a way to visualize PHP objects (not just classes) - object-graph library by Sebastian Bergmann,\u2026","rel":"","context":"In "All"","block_context":{"text":"All","link":"https:\/\/mamchenkov.net\/wordpress\/category\/general\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2017\/11\/object-graph-500x136.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":27280,"url":"https:\/\/mamchenkov.net\/wordpress\/2017\/01\/31\/composer-patches-simple-patches-plugin-for-composer\/","url_meta":{"origin":26934,"position":4},"title":"composer-patches – Simple patches plugin for Composer","author":"Leonid Mamchenkov","date":"January 31, 2017","format":false,"excerpt":"composer-patches is a plugin for Composer which helps with applying patches to the installed dependencies. \u00a0It supports patches from URLs, local files, and from other dependencies. I think this is absolutely brilliant! It's quite often that one finds bugs and issues in external dependencies. \u00a0Once the bug (or even the\u2026","rel":"","context":"In "All"","block_context":{"text":"All","link":"https:\/\/mamchenkov.net\/wordpress\/category\/general\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mamchenkov.net\/wordpress\/wp-content\/uploads\/2017\/01\/commit-500x263.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":26341,"url":"https:\/\/mamchenkov.net\/wordpress\/2016\/08\/12\/the-twelve-factor-app\/","url_meta":{"origin":26934,"position":5},"title":"The Twelve-Factor App","author":"Leonid Mamchenkov","date":"August 12, 2016","format":false,"excerpt":"I first heard about the twelve-factor app a couple of years ago, in Berlin, during the International PHP conference. \u00a0It was the basis for David Zulke (of Heroku fame) talk on the best practices for the modern day PHP applications. The twelve-factor app is a methodology for building software-as-a-service apps\u2026","rel":"","context":"In "All"","block_context":{"text":"All","link":"https:\/\/mamchenkov.net\/wordpress\/category\/general\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_sharing_enabled":true,"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/posts\/26934","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/comments?post=26934"}],"version-history":[{"count":0,"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/posts\/26934\/revisions"}],"wp:attachment":[{"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/media?parent=26934"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/categories?post=26934"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/tags?post=26934"},{"taxonomy":"keyring_services","embeddable":true,"href":"https:\/\/mamchenkov.net\/wordpress\/wp-json\/wp\/v2\/keyring_services?post=26934"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}