{"action":"created","comment":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/210652847","pull_request_review_id":146913952,"id":210652847,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIxMDY1Mjg0Nw==","diff_hunk":"@@ -0,0 +1,210 @@\n+/*\n+ * (C) Copyright 2018-2018, by Ira Justus Fesefeldt and Contributors.\n+ *\n+ * JGraphT : a free Java graph-theory library\n+ *\n+ * This program and the accompanying materials are dual-licensed under\n+ * either\n+ *\n+ * (a) the terms of the GNU Lesser General Public License version 2.1\n+ * as published by the Free Software Foundation, or (at your option) any\n+ * later version.\n+ *\n+ * or (per the licensee's choosing)\n+ *\n+ * (b) the terms of the Eclipse Public License v1.0 as published by\n+ * the Eclipse Foundation.\n+ */\n+package org.jgrapht.alg.decomposition;\n+\n+import java.util.*;\n+\n+import org.jgrapht.*;\n+import org.jgrapht.alg.cycle.*;\n+\n+/**\n+ * A builder for a nice decomposition for chordal graphs. See {@link NiceDecompositionBuilder} for\n+ * an explanation of nice decomposition.\n+ * <p>\n+ * This builder uses the perfect elimination order from {@link ChordalityInspector} to iterate over\n+ * the graph. For every node it generates a node for the predecessors of the current node according\n+ * to the perfect elimination order and builds a path to such a node from the node where the\n+ * greatest predecessor was introduced.\n+ * <p>\n+ * The complexity of this algorithm is in $\\mathcal{O}(|V|(|V|+|E|))$.<br>\n+ * Consider the every node in the nice tree decomposition: There are exactly $|V|$ many forget\n+ * nodes. There are at most $2|V|$ additionally nodes because of a join nodes. Every join node\n+ * creates one additional path from root to a leaf, every such path can contain for every vertex at\n+ * most one introduce node, which yields $|V|^2$ introduce nodes. Now considering the bags of the\n+ * introduce nodes. On a path from root to a leaf we have at most one introduce node for every\n+ * introduced vertex. Since this introduced vertex is part of the clique of the least ancestor\n+ * forget node, the corresponding bag of the introduce node is smaller than the set of neighbors of\n+ * this vertex. Thus the time complexity is in $\\mathcal{O}(|V|(|V|+|E|))$.\n+ * <p>\n+ * This is a non-recursive adaption for nice tree decomposition of algorithm 2 from here: <br>\n+ * Hans L. Bodlaender, Arie M.C.A. Koster, Treewidth computations I. Upper bounds, Information and\n+ * Computation, Volume 208, Issue 3, 2010, Pages 259-275,\n+ * \n+ * @author Ira Justus Fesefeldt (PhoenixIra)\n+ * @author Timofey Chudakov\n+ *\n+ * @since June 2018\n+ *\n+ * @param <V> the vertex type of the graph\n+ * @param <E> the edge type of the graph\n+ */\n+public class ChordalNiceDecompositionBuilder<V, E>\n+    extends\n+    NiceDecompositionBuilder<V>\n+{\n+    // the chordal graph\n+    private Graph<V, E> graph;\n+\n+    // the perfect elimination order of graph\n+    private List<V> perfectOrder;\n+\n+    // another representation of the perfect elimination order of graph\n+    private Map<V, Integer> vertexInOrder;\n+\n+    /**\n+     * Constructor for the nice decomposition builder of chordal graphs. The constructor\n+     * already computes the decomposition.\n+     * \n+     * @throws IllegalArgumentException if the graph is not chordal.\n+     * @param graph the chordal graph for which a decomposition should be created\n+     */\n+    public ChordalNiceDecompositionBuilder(Graph<V, E> graph)\n+    {\n+        super();\n+        ChordalityInspector<V, E> inspec = new ChordalityInspector<>(graph);\n+        if (!inspec.isChordal())\n+            throw new IllegalArgumentException(\"The given graph is not chordal.\");\n+        this.graph = graph;\n+        this.perfectOrder = inspec.getPerfectEliminationOrder();\n+        vertexInOrder = getVertexInOrder();\n+        computeNiceDecomposition();","path":"jgrapht-core/src/main/java/org/jgrapht/alg/decomposition/ChordalNiceDecompositionBuilder.java","position":85,"original_position":85,"commit_id":"6f9d6f90c9ff12687e86bd368f01a9de3c079543","original_commit_id":"6f9d6f90c9ff12687e86bd368f01a9de3c079543","user":{"login":"Toptachamann","id":29632641,"node_id":"MDQ6VXNlcjI5NjMyNjQx","avatar_url":"https://avatars1.githubusercontent.com/u/29632641?v=4","gravatar_id":"","url":"https://api.github.com/users/Toptachamann","html_url":"https://github.com/Toptachamann","followers_url":"https://api.github.com/users/Toptachamann/followers","following_url":"https://api.github.com/users/Toptachamann/following{/other_user}","gists_url":"https://api.github.com/users/Toptachamann/gists{/gist_id}","starred_url":"https://api.github.com/users/Toptachamann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Toptachamann/subscriptions","organizations_url":"https://api.github.com/users/Toptachamann/orgs","repos_url":"https://api.github.com/users/Toptachamann/repos","events_url":"https://api.github.com/users/Toptachamann/events{/privacy}","received_events_url":"https://api.github.com/users/Toptachamann/received_events","type":"User","site_admin":false},"body":"Should we run the algorithm at the construction time or after the first call to some getter method? @jkinable @jsichi @d-michail what do you think?","created_at":"2018-08-16T16:01:40Z","updated_at":"2018-08-16T16:45:01Z","html_url":"https://github.com/jgrapht/jgrapht/pull/616#discussion_r210652847","pull_request_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616","author_association":"COLLABORATOR","_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/210652847"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/616#discussion_r210652847"},"pull_request":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616"}}},"pull_request":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616","id":198464066,"node_id":"MDExOlB1bGxSZXF1ZXN0MTk4NDY0MDY2","html_url":"https://github.com/jgrapht/jgrapht/pull/616","diff_url":"https://github.com/jgrapht/jgrapht/pull/616.diff","patch_url":"https://github.com/jgrapht/jgrapht/pull/616.patch","issue_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/616","number":616,"state":"open","locked":false,"title":"Nice tree decomposition for chordal graph","user":{"login":"PhoenixIra","id":9974411,"node_id":"MDQ6VXNlcjk5NzQ0MTE=","avatar_url":"https://avatars1.githubusercontent.com/u/9974411?v=4","gravatar_id":"","url":"https://api.github.com/users/PhoenixIra","html_url":"https://github.com/PhoenixIra","followers_url":"https://api.github.com/users/PhoenixIra/followers","following_url":"https://api.github.com/users/PhoenixIra/following{/other_user}","gists_url":"https://api.github.com/users/PhoenixIra/gists{/gist_id}","starred_url":"https://api.github.com/users/PhoenixIra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/PhoenixIra/subscriptions","organizations_url":"https://api.github.com/users/PhoenixIra/orgs","repos_url":"https://api.github.com/users/PhoenixIra/repos","events_url":"https://api.github.com/users/PhoenixIra/events{/privacy}","received_events_url":"https://api.github.com/users/PhoenixIra/received_events","type":"User","site_admin":false},"body":"<!-- describe the changes you have made here: what, why, …\r\n     Link issues by using the following pattern: [#333](https://github.com/JabRef/jabref/issues/333).\r\n     The title of the PR must not reference an issue, because GitHub does not support autolinking there. -->\r\nRegarding the issue [#586](https://github.com/jgrapht/jgrapht/issues/586) we created also a nice tree decomposition builder for chordal graphs, which computes a nice tree decomposition with size and time complexity in O(|V|(|V|+|E|)).\r\nWe used the idea of an algorithm which outputs a non-nice tree decomposition of size and time complexity in O(|V|+|E|), but adapting it to nice tree decomposition gives here an additional cost (which we do not get for interval graphs).\r\n\r\nWe also squashed the commit history for a cleaner history and with better readable commits.\r\n\r\n\r\n----\r\n\r\n- [x] I read and understood <https://github.com/jgrapht/jgrapht/wiki/Become-a-Contributor>\r\n- [x] I read and understood <https://github.com/jgrapht/jgrapht/wiki/How-to-make-your-first-%28code%29-contribution>\r\n- [x] I added [unit tests](https://github.com/jgrapht/jgrapht/wiki/Unit-testing)\r\n- [x] I added [documentation](https://github.com/jgrapht/jgrapht/wiki/How-to-write-documentation)\r\n- [x] I followed the [Coding and Style Conventions](https://github.com/jgrapht/jgrapht/wiki/Coding-and-Style-Conventions)\r\n- [x] I **have not** modified `HISTORY.md` or `CONTRIBUTORS.md`\r\n- [x] I ensured that [the git commit message is a good one](https://github.com/joelparkerhenderson/git_commit_message)\r\n","created_at":"2018-06-30T07:12:13Z","updated_at":"2018-08-16T16:45:01Z","closed_at":null,"merged_at":null,"merge_commit_sha":"e3f687b266c5b60472b418146a3ef2a10cf1b3f4","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616/commits","review_comments_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616/comments","review_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/616/comments","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/6f9d6f90c9ff12687e86bd368f01a9de3c079543","head":{"label":"tj-developers:chordalDecompositionPR","ref":"chordalDecompositionPR","sha":"6f9d6f90c9ff12687e86bd368f01a9de3c079543","user":{"login":"tj-developers","id":38179805,"node_id":"MDEyOk9yZ2FuaXphdGlvbjM4MTc5ODA1","avatar_url":"https://avatars2.githubusercontent.com/u/38179805?v=4","gravatar_id":"","url":"https://api.github.com/users/tj-developers","html_url":"https://github.com/tj-developers","followers_url":"https://api.github.com/users/tj-developers/followers","following_url":"https://api.github.com/users/tj-developers/following{/other_user}","gists_url":"https://api.github.com/users/tj-developers/gists{/gist_id}","starred_url":"https://api.github.com/users/tj-developers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tj-developers/subscriptions","organizations_url":"https://api.github.com/users/tj-developers/orgs","repos_url":"https://api.github.com/users/tj-developers/repos","events_url":"https://api.github.com/users/tj-developers/events{/privacy}","received_events_url":"https://api.github.com/users/tj-developers/received_events","type":"Organization","site_admin":false},"repo":{"id":128627460,"node_id":"MDEwOlJlcG9zaXRvcnkxMjg2Mjc0NjA=","name":"jgrapht","full_name":"tj-developers/jgrapht","owner":{"login":"tj-developers","id":38179805,"node_id":"MDEyOk9yZ2FuaXphdGlvbjM4MTc5ODA1","avatar_url":"https://avatars2.githubusercontent.com/u/38179805?v=4","gravatar_id":"","url":"https://api.github.com/users/tj-developers","html_url":"https://github.com/tj-developers","followers_url":"https://api.github.com/users/tj-developers/followers","following_url":"https://api.github.com/users/tj-developers/following{/other_user}","gists_url":"https://api.github.com/users/tj-developers/gists{/gist_id}","starred_url":"https://api.github.com/users/tj-developers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tj-developers/subscriptions","organizations_url":"https://api.github.com/users/tj-developers/orgs","repos_url":"https://api.github.com/users/tj-developers/repos","events_url":"https://api.github.com/users/tj-developers/events{/privacy}","received_events_url":"https://api.github.com/users/tj-developers/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/tj-developers/jgrapht","description":"Master repository for the JGraphT project","fork":true,"url":"https://api.github.com/repos/tj-developers/jgrapht","forks_url":"https://api.github.com/repos/tj-developers/jgrapht/forks","keys_url":"https://api.github.com/repos/tj-developers/jgrapht/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tj-developers/jgrapht/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tj-developers/jgrapht/teams","hooks_url":"https://api.github.com/repos/tj-developers/jgrapht/hooks","issue_events_url":"https://api.github.com/repos/tj-developers/jgrapht/issues/events{/number}","events_url":"https://api.github.com/repos/tj-developers/jgrapht/events","assignees_url":"https://api.github.com/repos/tj-developers/jgrapht/assignees{/user}","branches_url":"https://api.github.com/repos/tj-developers/jgrapht/branches{/branch}","tags_url":"https://api.github.com/repos/tj-developers/jgrapht/tags","blobs_url":"https://api.github.com/repos/tj-developers/jgrapht/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tj-developers/jgrapht/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tj-developers/jgrapht/git/refs{/sha}","trees_url":"https://api.github.com/repos/tj-developers/jgrapht/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tj-developers/jgrapht/statuses/{sha}","languages_url":"https://api.github.com/repos/tj-developers/jgrapht/languages","stargazers_url":"https://api.github.com/repos/tj-developers/jgrapht/stargazers","contributors_url":"https://api.github.com/repos/tj-developers/jgrapht/contributors","subscribers_url":"https://api.github.com/repos/tj-developers/jgrapht/subscribers","subscription_url":"https://api.github.com/repos/tj-developers/jgrapht/subscription","commits_url":"https://api.github.com/repos/tj-developers/jgrapht/commits{/sha}","git_commits_url":"https://api.github.com/repos/tj-developers/jgrapht/git/commits{/sha}","comments_url":"https://api.github.com/repos/tj-developers/jgrapht/comments{/number}","issue_comment_url":"https://api.github.com/repos/tj-developers/jgrapht/issues/comments{/number}","contents_url":"https://api.github.com/repos/tj-developers/jgrapht/contents/{+path}","compare_url":"https://api.github.com/repos/tj-developers/jgrapht/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tj-developers/jgrapht/merges","archive_url":"https://api.github.com/repos/tj-developers/jgrapht/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tj-developers/jgrapht/downloads","issues_url":"https://api.github.com/repos/tj-developers/jgrapht/issues{/number}","pulls_url":"https://api.github.com/repos/tj-developers/jgrapht/pulls{/number}","milestones_url":"https://api.github.com/repos/tj-developers/jgrapht/milestones{/number}","notifications_url":"https://api.github.com/repos/tj-developers/jgrapht/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tj-developers/jgrapht/labels{/name}","releases_url":"https://api.github.com/repos/tj-developers/jgrapht/releases{/id}","deployments_url":"https://api.github.com/repos/tj-developers/jgrapht/deployments","created_at":"2018-04-08T10:04:42Z","updated_at":"2018-06-12T13:25:26Z","pushed_at":"2018-08-16T09:57:45Z","git_url":"git://github.com/tj-developers/jgrapht.git","ssh_url":"git@github.com:tj-developers/jgrapht.git","clone_url":"https://github.com/tj-developers/jgrapht.git","svn_url":"https://github.com/tj-developers/jgrapht","homepage":"http://www.jgrapht.org","size":12241,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":6,"mirror_url":null,"archived":false,"open_issues_count":12,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":6,"open_issues":12,"watchers":0,"default_branch":"master"}},"base":{"label":"jgrapht:master","ref":"master","sha":"642dbd37a8709f58ff9e0ee870fb1f04b24754ad","user":{"login":"jgrapht","id":1624681,"node_id":"MDEyOk9yZ2FuaXphdGlvbjE2MjQ2ODE=","avatar_url":"https://avatars3.githubusercontent.com/u/1624681?v=4","gravatar_id":"","url":"https://api.github.com/users/jgrapht","html_url":"https://github.com/jgrapht","followers_url":"https://api.github.com/users/jgrapht/followers","following_url":"https://api.github.com/users/jgrapht/following{/other_user}","gists_url":"https://api.github.com/users/jgrapht/gists{/gist_id}","starred_url":"https://api.github.com/users/jgrapht/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jgrapht/subscriptions","organizations_url":"https://api.github.com/users/jgrapht/orgs","repos_url":"https://api.github.com/users/jgrapht/repos","events_url":"https://api.github.com/users/jgrapht/events{/privacy}","received_events_url":"https://api.github.com/users/jgrapht/received_events","type":"Organization","site_admin":false},"repo":{"id":3969325,"node_id":"MDEwOlJlcG9zaXRvcnkzOTY5MzI1","name":"jgrapht","full_name":"jgrapht/jgrapht","owner":{"login":"jgrapht","id":1624681,"node_id":"MDEyOk9yZ2FuaXphdGlvbjE2MjQ2ODE=","avatar_url":"https://avatars3.githubusercontent.com/u/1624681?v=4","gravatar_id":"","url":"https://api.github.com/users/jgrapht","html_url":"https://github.com/jgrapht","followers_url":"https://api.github.com/users/jgrapht/followers","following_url":"https://api.github.com/users/jgrapht/following{/other_user}","gists_url":"https://api.github.com/users/jgrapht/gists{/gist_id}","starred_url":"https://api.github.com/users/jgrapht/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jgrapht/subscriptions","organizations_url":"https://api.github.com/users/jgrapht/orgs","repos_url":"https://api.github.com/users/jgrapht/repos","events_url":"https://api.github.com/users/jgrapht/events{/privacy}","received_events_url":"https://api.github.com/users/jgrapht/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/jgrapht/jgrapht","description":"Master repository for the JGraphT project","fork":true,"url":"https://api.github.com/repos/jgrapht/jgrapht","forks_url":"https://api.github.com/repos/jgrapht/jgrapht/forks","keys_url":"https://api.github.com/repos/jgrapht/jgrapht/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jgrapht/jgrapht/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jgrapht/jgrapht/teams","hooks_url":"https://api.github.com/repos/jgrapht/jgrapht/hooks","issue_events_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/events{/number}","events_url":"https://api.github.com/repos/jgrapht/jgrapht/events","assignees_url":"https://api.github.com/repos/jgrapht/jgrapht/assignees{/user}","branches_url":"https://api.github.com/repos/jgrapht/jgrapht/branches{/branch}","tags_url":"https://api.github.com/repos/jgrapht/jgrapht/tags","blobs_url":"https://api.github.com/repos/jgrapht/jgrapht/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jgrapht/jgrapht/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jgrapht/jgrapht/git/refs{/sha}","trees_url":"https://api.github.com/repos/jgrapht/jgrapht/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/{sha}","languages_url":"https://api.github.com/repos/jgrapht/jgrapht/languages","stargazers_url":"https://api.github.com/repos/jgrapht/jgrapht/stargazers","contributors_url":"https://api.github.com/repos/jgrapht/jgrapht/contributors","subscribers_url":"https://api.github.com/repos/jgrapht/jgrapht/subscribers","subscription_url":"https://api.github.com/repos/jgrapht/jgrapht/subscription","commits_url":"https://api.github.com/repos/jgrapht/jgrapht/commits{/sha}","git_commits_url":"https://api.github.com/repos/jgrapht/jgrapht/git/commits{/sha}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/comments{/number}","issue_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/comments{/number}","contents_url":"https://api.github.com/repos/jgrapht/jgrapht/contents/{+path}","compare_url":"https://api.github.com/repos/jgrapht/jgrapht/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jgrapht/jgrapht/merges","archive_url":"https://api.github.com/repos/jgrapht/jgrapht/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jgrapht/jgrapht/downloads","issues_url":"https://api.github.com/repos/jgrapht/jgrapht/issues{/number}","pulls_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls{/number}","milestones_url":"https://api.github.com/repos/jgrapht/jgrapht/milestones{/number}","notifications_url":"https://api.github.com/repos/jgrapht/jgrapht/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jgrapht/jgrapht/labels{/name}","releases_url":"https://api.github.com/repos/jgrapht/jgrapht/releases{/id}","deployments_url":"https://api.github.com/repos/jgrapht/jgrapht/deployments","created_at":"2012-04-09T05:30:23Z","updated_at":"2018-08-16T05:57:58Z","pushed_at":"2018-08-16T10:32:01Z","git_url":"git://github.com/jgrapht/jgrapht.git","ssh_url":"git@github.com:jgrapht/jgrapht.git","clone_url":"https://github.com/jgrapht/jgrapht.git","svn_url":"https://github.com/jgrapht/jgrapht","homepage":"http://www.jgrapht.org","size":50892,"stargazers_count":1212,"watchers_count":1212,"language":"Java","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":487,"mirror_url":null,"archived":false,"open_issues_count":57,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":487,"open_issues":57,"watchers":1212,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/616"},"issue":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/616"},"comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/616/comments"},"review_comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616/comments"},"review_comment":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/616/commits"},"statuses":{"href":"https://api.github.com/repos/jgrapht/jgrapht/statuses/6f9d6f90c9ff12687e86bd368f01a9de3c079543"}},"author_association":"NONE"}}
{"actor":{"display_login":"Toptachamann"}}