{"id":116,"date":"2008-12-12T21:44:55","date_gmt":"2008-12-13T04:44:55","guid":{"rendered":"http:\/\/thesmithfam.org\/blog\/?p=116"},"modified":"2019-08-12T07:15:58","modified_gmt":"2019-08-12T13:15:58","slug":"graph-theory-problem","status":"publish","type":"post","link":"https:\/\/thesmithfam.org\/blog\/2008\/12\/12\/graph-theory-problem\/","title":{"rendered":"Graph Theory Problem"},"content":{"rendered":"<p>I came across a graph theory problem at work this week, and decided to blog about it to help me sort it out. At first I didn&#8217;t think of it as a graph problem, but that&#8217;s how these problems often go, shrouded in disguise and all. But I digress.<\/p>\n<p>The problem is this. Considering the following directed graph, which nodes are the most senior ancestors (speaking in tree terms, of course)?<\/p>\n<p><img decoding=\"async\" src=\"\/images\/graph-theory-1.png\" \/><\/p>\n<p>The answer is that nodes <b>A<\/b> and <b>B<\/b> are the most senior, meaning they have the most number of descendants in their sub-trees. This becomes obvious if we draw the same graph this way:<\/p>\n<p><img decoding=\"async\" src=\"\/images\/graph-theory-2.png\" \/><\/p>\n<p>I&#8217;m trying to discover an algorithm to identify the senior most nodes given any directed graph. The graph is given as an edge list, like this:<\/p>\n<ul style=\"font-size: 18px\">\n<li>A -> B<\/li>\n<li>A -> F<\/li>\n<li>A -> E<\/li>\n<li>E -> H<\/li>\n<li>E -> G<\/li>\n<li>B -> A <span style=\"color:gray\">(notice the cycle here back to A)<\/span><\/li>\n<li>B -> D<\/li>\n<li>B -> C<\/li>\n<li>H -> I<\/li>\n<\/ul>\n<p>So there&#8217;s the problem. I&#8217;m looking for an algorithm that will find the top-most nodes given <b>any<\/b> directed graph. In the case where there is only a single top-most node, it&#8217;s easy, but that&#8217;s just one case, and I want a general solution. Also, the graph need not be fully reachable from any node. It could be two or more non-connected graphs.<\/p>\n<p>If you have an idea for an elegant solution, please post it in the comments below. I&#8217;ll post my own solution next week.<\/p>\n<p>Happy graphing!<\/p>\n<p>Edit:<\/p>\n<p>After thinking about the problem a bit more, I thought I&#8217;d add another example with some corner cases that my solution will need to consider. If you look below, you&#8217;ll see a graph with a more complicated cycle and a non-contiguous section. The nodes I expect the algorithm to discover are shown in green:<\/p>\n<p><img decoding=\"async\" src=\"\/images\/graph-theory-3.png\" \/><\/p>\n<p>Here are the edge pairs:<\/p>\n<ul style=\"font-size: 18px\">\n<li>A -> B<\/li>\n<li>A -> E<\/li>\n<li>A -> F<\/li>\n<li>E -> H<\/li>\n<li>E -> G<\/li>\n<li>B -> A<\/li>\n<li>B -> C<\/li>\n<li>C -> B<\/li>\n<li>C -> D<\/li>\n<li>I -> J<\/li>\n<li>I -> K<\/li>\n<li>H -> L<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>I came across a graph theory problem at work this week, and decided to blog about it to help me sort it out. At first I didn&#8217;t think of it as a graph problem, but that&#8217;s how these problems often go, shrouded in disguise and all. But I digress. The problem is this. Considering the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-116","post","type-post","status-publish","format-standard","hentry","category-code-and-cruft"],"_links":{"self":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/comments?post=116"}],"version-history":[{"count":17,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/116\/revisions"}],"predecessor-version":[{"id":1550,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/116\/revisions\/1550"}],"wp:attachment":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/media?parent=116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/categories?post=116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/tags?post=116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}