{"action":"created","comment":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/217900008","pull_request_review_id":155729631,"id":217900008,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIxNzkwMDAwOA==","diff_hunk":"@@ -0,0 +1,302 @@\n+/*\n+ * (C) Copyright 2018-2018, by Joris Kinable 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+import org.jgrapht.GraphPath;\n+import org.jgrapht.GraphTests;\n+import org.jgrapht.Graphs;\n+import org.jgrapht.alg.interfaces.EulerianCycleAlgorithm;\n+import org.jgrapht.alg.interfaces.MatchingAlgorithm;\n+import org.jgrapht.alg.interfaces.ShortestPathAlgorithm;\n+import org.jgrapht.alg.matching.KuhnMunkresMinimalWeightBipartitePerfectMatching;\n+import org.jgrapht.alg.matching.blossom.v5.*;\n+import org.jgrapht.alg.shortestpath.DijkstraShortestPath;\n+import org.jgrapht.alg.util.Pair;\n+import org.jgrapht.alg.util.UnorderedPair;\n+import org.jgrapht.graph.*;\n+\n+import java.util.*;\n+import java.util.stream.Collectors;\n+\n+/**\n+ * This class solves the Chinese Postman Problem (CPP), also known as the Route Inspection Problem.\n+ * The CPP asks to find a shortest closed path or circuit that visits every edge of a graph. In\n+ * weighted graphs, the circuit of minimal total weight is returned; in unweighted graphs, a circuit\n+ * of minimum total length (total number of edges) is returned.\n+ * <p>\n+ * The algorithm works with directed and undirected graphs which may contain loops and/or multiple\n+ * edges. The runtime complexity is O(N^3) where N is the number of vertices in the graph. Mixed\n+ * graphs are currently not supported, as solving the CPP for mixed graphs is NP-hard. The graph on\n+ * which this algorithm is invoked must be strongly connected; invoking this algorithm on a graph\n+ * which is not strongly connected may result in undefined behavior. In case of weighted graphs, all\n+ * edge weights must be positive.\n+ *\n+ * If the input graph is Eulerian (see {@link GraphTests#isEulerian(Graph)} for details) use\n+ * {@link HierholzerEulerianCycle} instead.\n+ * <p>\n+ * The implementation is based on the following paper:<br>\n+ * Edmonds, J., Johnson, E.L. Matching, Euler tours and the Chinese postman, Mathematical\n+ * Programming (1973) 5: 88. doi:10.1007/BF01580113<br>\n+ *\n+ * More concise descriptions of the algorithms can be found here:\n+ * <ul>\n+ * <li><a href=\n+ * \"http://www.suffolkmaths.co.uk/pages/Maths%20Projects/Projects/Topology%20and%20Graph%20Theory/Chinese%20Postman%20Problem.pdf\">CPP\n+ * for Undirected graphs</a>\n+ * <li><a href=\n+ * \"https://www-m9.ma.tum.de/graph-algorithms/directed-chinese-postman/index_en.html\">CPP for\n+ * Directed graphs</a>\n+ * </ul>\n+ * \n+ * @param <V> the graph vertex type\n+ * @param <E> the graph edge type\n+ *\n+ * @author Joris Kinable\n+ * @since September 2018\n+ */\n+public class ChinesePostman<V, E>\n+    implements\n+    EulerianCycleAlgorithm<V, E>\n+{\n+\n+    /**\n+     * Solves the Chinese Postman Problem on the given graph.\n+     * For Undirected graph, this implementation uses the @{@link KolmogorovMinimumWeightPerfectMatching} matching algorithm;\n+     * for directed graphs, @{@link KuhnMunkresMinimalWeightBipartitePerfectMatching} is used instead.\n+     * \n+     * @param graph the input graph (must be a strongly connected graph)\n+     * @return Eulerian circuit of minimum weight.\n+     */\n+    @Override\n+    public GraphPath<V, E> getEulerianCycle(Graph<V, E> graph)\n+    {\n+\n+        // Mixed graphs are currently not supported. Solving the CPP for mixed graphs is NP-Hard\n+        GraphTests.requireDirectedOrUndirected(graph);\n+\n+        // If graph has no vertices, or no edges, instantly return.\n+        if (graph.vertexSet().isEmpty() || graph.edgeSet().isEmpty())\n+            return new HierholzerEulerianCycle<V, E>().getEulerianCycle(graph);\n+\n+        if (graph.getType().isUndirected())\n+            return solveCPPUndirected(graph);\n+        else\n+            return solveCPPDirected(graph);\n+\n+    }\n+\n+    /**\n+     * Solves the CPP for undirected graphs\n+     *\n+     * @param graph input graph\n+     * @return Eulerian Circuit\n+     */\n+    private GraphPath<V,E> solveCPPUndirected(Graph<V, E> graph){\n+\n+        //1. Find all odd degree vertices (there should be an odd number of those)\n+        List<V> oddDegreeVertices=graph.vertexSet().stream().filter(v ->graph.degreeOf(v)%2==1).collect(Collectors.toList());\n+\n+        //2. Compute all pairwise shortest paths for the oddDegreeVertices\n+        Map<Pair<V,V>, GraphPath<V,E>> shortestPaths=new HashMap<>();\n+        ShortestPathAlgorithm<V,E> sp=new DijkstraShortestPath<>(graph);","path":"jgrapht-core/src/main/java/org/jgrapht/alg/cycle/ChinesePostman.java","position":118,"original_position":117,"commit_id":"a3e5c6cc925ccd3adfc323f51be4cab35c984d38","original_commit_id":"f57c73c4ba928249dbe0675fd292a3d3ab5bbf42","user":{"login":"jsichi","id":632737,"node_id":"MDQ6VXNlcjYzMjczNw==","avatar_url":"https://avatars0.githubusercontent.com/u/632737?v=4","gravatar_id":"","url":"https://api.github.com/users/jsichi","html_url":"https://github.com/jsichi","followers_url":"https://api.github.com/users/jsichi/followers","following_url":"https://api.github.com/users/jsichi/following{/other_user}","gists_url":"https://api.github.com/users/jsichi/gists{/gist_id}","starred_url":"https://api.github.com/users/jsichi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jsichi/subscriptions","organizations_url":"https://api.github.com/users/jsichi/orgs","repos_url":"https://api.github.com/users/jsichi/repos","events_url":"https://api.github.com/users/jsichi/events{/privacy}","received_events_url":"https://api.github.com/users/jsichi/received_events","type":"User","site_admin":false},"body":"Got it; I forgot about the package privacy.","created_at":"2018-09-16T02:05:30Z","updated_at":"2018-09-16T02:05:30Z","html_url":"https://github.com/jgrapht/jgrapht/pull/385#discussion_r217900008","pull_request_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385","author_association":"MEMBER","_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/217900008"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/385#discussion_r217900008"},"pull_request":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385"}},"in_reply_to_id":217492720},"pull_request":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385","id":112642994,"node_id":"MDExOlB1bGxSZXF1ZXN0MTEyNjQyOTk0","html_url":"https://github.com/jgrapht/jgrapht/pull/385","diff_url":"https://github.com/jgrapht/jgrapht/pull/385.diff","patch_url":"https://github.com/jgrapht/jgrapht/pull/385.patch","issue_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/385","number":385,"state":"open","locked":false,"title":"Chinese Postman Problem","user":{"login":"jkinable","id":2742474,"node_id":"MDQ6VXNlcjI3NDI0NzQ=","avatar_url":"https://avatars1.githubusercontent.com/u/2742474?v=4","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"body":"- Added algorithm which solves the Chinese Postman Problem for both directed and undirected graphs.","created_at":"2017-03-26T20:31:18Z","updated_at":"2018-09-16T02:05:30Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0a2288f49c9c6c9cbbba74b38105475d9a2926d6","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385/commits","review_comments_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385/comments","review_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/385/comments","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/a3e5c6cc925ccd3adfc323f51be4cab35c984d38","head":{"label":"jkinable:CPP","ref":"CPP","sha":"a3e5c6cc925ccd3adfc323f51be4cab35c984d38","user":{"login":"jkinable","id":2742474,"node_id":"MDQ6VXNlcjI3NDI0NzQ=","avatar_url":"https://avatars1.githubusercontent.com/u/2742474?v=4","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"repo":{"id":6578121,"node_id":"MDEwOlJlcG9zaXRvcnk2NTc4MTIx","name":"jgrapht","full_name":"jkinable/jgrapht","private":false,"owner":{"login":"jkinable","id":2742474,"node_id":"MDQ6VXNlcjI3NDI0NzQ=","avatar_url":"https://avatars1.githubusercontent.com/u/2742474?v=4","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"html_url":"https://github.com/jkinable/jgrapht","description":"Master repository for the JGraphT project","fork":true,"url":"https://api.github.com/repos/jkinable/jgrapht","forks_url":"https://api.github.com/repos/jkinable/jgrapht/forks","keys_url":"https://api.github.com/repos/jkinable/jgrapht/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jkinable/jgrapht/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jkinable/jgrapht/teams","hooks_url":"https://api.github.com/repos/jkinable/jgrapht/hooks","issue_events_url":"https://api.github.com/repos/jkinable/jgrapht/issues/events{/number}","events_url":"https://api.github.com/repos/jkinable/jgrapht/events","assignees_url":"https://api.github.com/repos/jkinable/jgrapht/assignees{/user}","branches_url":"https://api.github.com/repos/jkinable/jgrapht/branches{/branch}","tags_url":"https://api.github.com/repos/jkinable/jgrapht/tags","blobs_url":"https://api.github.com/repos/jkinable/jgrapht/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jkinable/jgrapht/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jkinable/jgrapht/git/refs{/sha}","trees_url":"https://api.github.com/repos/jkinable/jgrapht/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jkinable/jgrapht/statuses/{sha}","languages_url":"https://api.github.com/repos/jkinable/jgrapht/languages","stargazers_url":"https://api.github.com/repos/jkinable/jgrapht/stargazers","contributors_url":"https://api.github.com/repos/jkinable/jgrapht/contributors","subscribers_url":"https://api.github.com/repos/jkinable/jgrapht/subscribers","subscription_url":"https://api.github.com/repos/jkinable/jgrapht/subscription","commits_url":"https://api.github.com/repos/jkinable/jgrapht/commits{/sha}","git_commits_url":"https://api.github.com/repos/jkinable/jgrapht/git/commits{/sha}","comments_url":"https://api.github.com/repos/jkinable/jgrapht/comments{/number}","issue_comment_url":"https://api.github.com/repos/jkinable/jgrapht/issues/comments{/number}","contents_url":"https://api.github.com/repos/jkinable/jgrapht/contents/{+path}","compare_url":"https://api.github.com/repos/jkinable/jgrapht/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jkinable/jgrapht/merges","archive_url":"https://api.github.com/repos/jkinable/jgrapht/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jkinable/jgrapht/downloads","issues_url":"https://api.github.com/repos/jkinable/jgrapht/issues{/number}","pulls_url":"https://api.github.com/repos/jkinable/jgrapht/pulls{/number}","milestones_url":"https://api.github.com/repos/jkinable/jgrapht/milestones{/number}","notifications_url":"https://api.github.com/repos/jkinable/jgrapht/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jkinable/jgrapht/labels{/name}","releases_url":"https://api.github.com/repos/jkinable/jgrapht/releases{/id}","deployments_url":"https://api.github.com/repos/jkinable/jgrapht/deployments","created_at":"2012-11-07T11:18:31Z","updated_at":"2018-09-07T18:10:31Z","pushed_at":"2018-09-15T20:21:12Z","git_url":"git://github.com/jkinable/jgrapht.git","ssh_url":"git@github.com:jkinable/jgrapht.git","clone_url":"https://github.com/jkinable/jgrapht.git","svn_url":"https://github.com/jkinable/jgrapht","homepage":"http://www.jgrapht.org","size":12052,"stargazers_count":2,"watchers_count":2,"language":"Java","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":1,"open_issues":0,"watchers":2,"default_branch":"master"}},"base":{"label":"jgrapht:master","ref":"master","sha":"60b012f849f8a8e43a1667229094fe8604e09440","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","private":false,"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},"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-09-15T20:08:52Z","pushed_at":"2018-09-15T20:21:14Z","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":59552,"stargazers_count":1231,"watchers_count":1231,"language":"Java","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":490,"mirror_url":null,"archived":false,"open_issues_count":53,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":490,"open_issues":53,"watchers":1231,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/385"},"issue":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/385"},"comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/385/comments"},"review_comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385/comments"},"review_comment":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/385/commits"},"statuses":{"href":"https://api.github.com/repos/jgrapht/jgrapht/statuses/a3e5c6cc925ccd3adfc323f51be4cab35c984d38"}},"author_association":"COLLABORATOR"}}
{"actor":{"display_login":"jsichi"}}