{"action":"created","comment":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/201020171","pull_request_review_id":135439185,"id":201020171,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIwMTAyMDE3MQ==","diff_hunk":"@@ -0,0 +1,161 @@\n+/*\n+ * (C) Copyright 2003-2018, by Christoph Grüne 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.cycle;\n+\n+import org.jgrapht.Graph;\n+\n+import java.util.*;\n+\n+/**\n+ * Implementation of an algorithm for the local augmentation problem for the cyclic exchange neighborhood,\n+ * i.e. it finds subset-disjoint negative cycles, based on the\n+ * <a href =\"http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.6758&rep=rep1&type=pdf\">paper</a>\n+ * by Ahuja et al.\n+ *\n+ * This algorithm may enumerate all paths up to the length given by the parameter <code>lengthBound</code>,\n+ * i.e the algorithm runs in exponential time.\n+ *\n+ * @param <V> the vertex type\n+ * @param <E> the edge type\n+ *\n+ * @author Christoph Grüne\n+ * @since June 7, 2018\n+ */\n+public class AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V, E> {\n+\n+    private Graph<V, E> graph;\n+    private Map<V, Integer> labels;\n+    private int lengthBound;\n+\n+    /**\n+     * Constructs an algorithm with given inputs\n+     *\n+     * @param graph the (improvement) graph on which to calculate the local augmentation\n+     * @param lengthBound the upper bound for the length of cycles to detect\n+     * @param labels the labels of the vertices encoding the subsets of vertices\n+     */\n+    public AhujaOrlinSharmaCyclicExchangeLocalAugmentation(Graph<V, E> graph, int lengthBound, Map<V, Integer> labels) {\n+        this.graph = graph;\n+        this.lengthBound = lengthBound;\n+        this.labels = labels;\n+    }\n+\n+    /**\n+     * calculates a valid subset-disjoint negative cycle.\n+     * If there is no such a cycle, it returns an empty LabeledPath instance with cost Double.MAX_VALUE.\n+     *\n+     * @return a valid subset-disjoint negative cycle encoded as LabeledPath\n+     */\n+    public LabeledPath<V> getLocalAugmentationCycle() {\n+\n+        int k = 1;\n+        LabeledPath<V> C = new LabeledPath<>();","path":"jgrapht-core/src/main/java/org/jgrapht/alg/cycle/AhujaOrlinSharmaCyclicExchangeLocalAugmentation.java","position":67,"original_position":67,"commit_id":"e8cdf07d056d50d07947d61247faf165dff4ab14","original_commit_id":"e8cdf07d056d50d07947d61247faf165dff4ab14","user":{"login":"christophgruene","id":32873046,"node_id":"MDQ6VXNlcjMyODczMDQ2","avatar_url":"https://avatars1.githubusercontent.com/u/32873046?v=4","gravatar_id":"","url":"https://api.github.com/users/christophgruene","html_url":"https://github.com/christophgruene","followers_url":"https://api.github.com/users/christophgruene/followers","following_url":"https://api.github.com/users/christophgruene/following{/other_user}","gists_url":"https://api.github.com/users/christophgruene/gists{/gist_id}","starred_url":"https://api.github.com/users/christophgruene/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/christophgruene/subscriptions","organizations_url":"https://api.github.com/users/christophgruene/orgs","repos_url":"https://api.github.com/users/christophgruene/repos","events_url":"https://api.github.com/users/christophgruene/events{/privacy}","received_events_url":"https://api.github.com/users/christophgruene/received_events","type":"User","site_admin":false},"body":"This is true and I know the convention but I want to use the notation of the paper. However, I will change this here.","created_at":"2018-07-09T14:22:29Z","updated_at":"2018-07-09T14:22:30Z","html_url":"https://github.com/jgrapht/jgrapht/pull/600#discussion_r201020171","pull_request_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600","author_association":"NONE","_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/201020171"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/600#discussion_r201020171"},"pull_request":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600"}},"in_reply_to_id":200905980},"pull_request":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600","id":194998209,"node_id":"MDExOlB1bGxSZXF1ZXN0MTk0OTk4MjA5","html_url":"https://github.com/jgrapht/jgrapht/pull/600","diff_url":"https://github.com/jgrapht/jgrapht/pull/600.diff","patch_url":"https://github.com/jgrapht/jgrapht/pull/600.patch","issue_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/600","number":600,"state":"open","locked":false,"title":"Algorithm for Finding Valid Cycles in an Improvement Graph ","user":{"login":"christophgruene","id":32873046,"node_id":"MDQ6VXNlcjMyODczMDQ2","avatar_url":"https://avatars1.githubusercontent.com/u/32873046?v=4","gravatar_id":"","url":"https://api.github.com/users/christophgruene","html_url":"https://github.com/christophgruene","followers_url":"https://api.github.com/users/christophgruene/followers","following_url":"https://api.github.com/users/christophgruene/following{/other_user}","gists_url":"https://api.github.com/users/christophgruene/gists{/gist_id}","starred_url":"https://api.github.com/users/christophgruene/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/christophgruene/subscriptions","organizations_url":"https://api.github.com/users/christophgruene/orgs","repos_url":"https://api.github.com/users/christophgruene/repos","events_url":"https://api.github.com/users/christophgruene/events{/privacy}","received_events_url":"https://api.github.com/users/christophgruene/received_events","type":"User","site_admin":false},"body":"This pull request fixes #588.\r\nThere is one question left. I introduced a class LabeledPath, in which I maintain necessary information for the algorithm. In these paths I do not have to store the edges, hence, I did not implement the interface GraphPath. Should I do this from your point of view or is it ok to leave it likes it is?","created_at":"2018-06-14T19:45:09Z","updated_at":"2018-07-09T14:22:30Z","closed_at":null,"merged_at":null,"merge_commit_sha":"07cc2b0ee7b1bd974dcec371eff4db1e23a39b77","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600/commits","review_comments_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600/comments","review_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/600/comments","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/e8cdf07d056d50d07947d61247faf165dff4ab14","head":{"label":"tj-developers:localAugmentationCycle","ref":"localAugmentationCycle","sha":"e8cdf07d056d50d07947d61247faf165dff4ab14","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-07-09T13:12:13Z","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":11860,"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":10,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":6,"open_issues":10,"watchers":0,"default_branch":"master"}},"base":{"label":"jgrapht:master","ref":"master","sha":"970a6e41a01fbd615c4302ed37b99ef90bde3d59","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-07-09T05:58:48Z","pushed_at":"2018-07-09T13:30:27Z","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":30872,"stargazers_count":1197,"watchers_count":1197,"language":"Java","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":478,"mirror_url":null,"archived":false,"open_issues_count":54,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":478,"open_issues":54,"watchers":1197,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/600"},"issue":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/600"},"comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/600/comments"},"review_comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600/comments"},"review_comment":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/600/commits"},"statuses":{"href":"https://api.github.com/repos/jgrapht/jgrapht/statuses/e8cdf07d056d50d07947d61247faf165dff4ab14"}},"author_association":"NONE"}}
{"actor":{"display_login":"christophgruene"}}