{"action":"created","comment":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/71821880","id":71821880,"diff_hunk":"@@ -0,0 +1,490 @@\n+/* ==========================================\n+ * JGraphT : a free Java graph-theory library\n+ * ==========================================\n+ *\n+ * Project Info:  http://jgrapht.sourceforge.net/\n+ * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)\n+ *\n+ * (C) Copyright 2003-2008, by Barak Naveh and Contributors.\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+/* -------------------------\n+* BidirectionalDijkstraShortestPath.java\n+* -------------------------\n+* (C) Copyright 2016, by Dimitrios Michail and Contributors.\n+*\n+* Original Author:  Dimitrios Michail\n+* Contributor(s):   - \n+*\n+* $Id$\n+*\n+* Changes\n+* -------\n+* 19-July-2016: Initial revision (DM);\n+*\n+*/\n+package org.jgrapht.alg;\n+\n+import java.util.ArrayList;\n+import java.util.Arrays;\n+import java.util.HashMap;\n+import java.util.LinkedList;\n+import java.util.List;\n+import java.util.Map;\n+import java.util.Set;\n+\n+import org.jgrapht.DirectedGraph;\n+import org.jgrapht.Graph;\n+import org.jgrapht.GraphPath;\n+import org.jgrapht.Graphs;\n+import org.jgrapht.graph.EdgeReversedGraph;\n+import org.jgrapht.graph.GraphWalk;\n+import org.jgrapht.util.FibonacciHeap;\n+import org.jgrapht.util.FibonacciHeapNode;\n+\n+/**\n+ * A bidirectional version of Dijkstra's algorithm.\n+ * \n+ * <p>\n+ * See the Wikipedia article for details and references about\n+ * <a href=\"https://en.wikipedia.org/wiki/Bidirectional_search\">bidirectional\n+ * search</a>. This technique does not change the worst-case behavior of the\n+ * algorithm but reduces, in some cases, the number of visited vertices in\n+ * practice. This implementation alternatively constructs forward and reverse\n+ * paths from the source and target vertices respectively.\n+ * </p>\n+ * \n+ * @param <V> the graph vertex type\n+ * @param <E> the graph edge type\n+ *\n+ * @see DijkstraShortestPath\n+ *\n+ * @author Dimitrios Michail\n+ * @since July 2016\n+ */\n+public final class BidirectionalDijkstraShortestPath<V, E>\n+{\n+\n+    private final GraphPath<V, E> path;\n+\n+    /**\n+     * Creates the instance and executes the bidirectional Dijkstra shortest\n+     * path algorithm. An instance is only good for a single search; after\n+     * construction, it can be accessed to retrieve information about the found\n+     * path.\n+     *\n+     * @param graph the input graph\n+     * @param startVertex the vertex at which the path should start\n+     * @param endVertex the vertex at which the path should end\n+     */\n+    public BidirectionalDijkstraShortestPath(\n+        Graph<V, E> graph,\n+        V startVertex,\n+        V endVertex)\n+    {\n+        this(graph, startVertex, endVertex, Double.POSITIVE_INFINITY);\n+    }\n+\n+    /**\n+     * Creates the instance and executes the bidirectional Dijkstra shortest\n+     * path algorithm. An instance is only good for a single search; after\n+     * construction, it can be accessed to retrieve information about the found\n+     * path.\n+     *\n+     * @param graph the input graph\n+     * @param startVertex the vertex at which the path should start\n+     * @param endVertex the vertex at which the path should end\n+     * @param radius limit on weighted path length, or Double.POSITIVE_INFINITY\n+     *        for unbounded search\n+     */\n+    public BidirectionalDijkstraShortestPath(\n+        Graph<V, E> graph,\n+        V startVertex,\n+        V endVertex,\n+        double radius)\n+    {\n+        if (graph == null) {\n+            throw new IllegalArgumentException(\"Input graph cannot be null\");\n+        }\n+        if (startVertex == null || !graph.containsVertex(startVertex)) {\n+            throw new IllegalArgumentException(\n+                \"Invalid graph vertex as source\");\n+        }\n+        if (endVertex == null || !graph.containsVertex(endVertex)) {\n+            throw new IllegalArgumentException(\n+                \"Invalid graph vertex as target\");\n+        }\n+        if (radius < 0.0) {\n+            throw new IllegalArgumentException(\"Radius must be non-negative\");\n+        }\n+\n+        this.path = new BidirectionalDijkstraShortestPathDetails<V, E>(\n+            graph,\n+            startVertex,\n+            endVertex,\n+            radius).run();\n+    }\n+\n+    /**\n+     * Return the edges making up the path.\n+     *\n+     * @return List of edges, or null if no path exists\n+     */\n+    public List<E> getPathEdgeList()\n+    {\n+        if (path == null) {\n+            return null;\n+        } else {\n+            return path.getEdgeList();\n+        }\n+    }\n+\n+    /**\n+     * Return the path found.\n+     *\n+     * @return path representation, or null if no path exists\n+     */\n+    public GraphPath<V, E> getPath()\n+    {\n+        return path;\n+    }\n+\n+    /**\n+     * Return the weighted length of the path found.\n+     *\n+     * @return path length, or Double.POSITIVE_INFINITY if no path exists\n+     */\n+    public double getPathLength()\n+    {\n+        if (path == null) {\n+            return Double.POSITIVE_INFINITY;\n+        } else {\n+            return path.getWeight();\n+        }\n+    }\n+\n+}\n+\n+/**\n+ * The implementation details\n+ */\n+class BidirectionalDijkstraShortestPathDetails<V, E>\n+{\n+    private final SearchFrontier<V, E> forwardFrontier;\n+    private final SearchFrontier<V, E> reversedFrontier;\n+\n+    private final V source;\n+    private final V target;\n+    private final double radius;\n+\n+    public BidirectionalDijkstraShortestPathDetails(\n+        Graph<V, E> graph,\n+        V source,\n+        V target,\n+        double radius)\n+    {\n+        this.forwardFrontier = new SearchFrontier<V, E>(graph);\n+        if (graph instanceof DirectedGraph) {\n+            this.reversedFrontier = new SearchFrontier<V, E>(\n+                new EdgeReversedGraph<>(((DirectedGraph<V, E>) graph)));\n+        } else {\n+            this.reversedFrontier = new SearchFrontier<V, E>(graph);\n+        }\n+        this.source = source;\n+        this.target = target;\n+        this.radius = radius;\n+    }\n+\n+    public GraphPath<V, E> run()\n+    {\n+        // handle special case if source equals target\n+        if (source.equals(target)) {\n+            return new GraphWalk<>(\n+                forwardFrontier.graph,\n+                source,\n+                target,\n+                Arrays.asList(source),","path":"jgrapht-core/src/main/java/org/jgrapht/alg/BidirectionalDijkstraShortestPath.java","position":217,"original_position":217,"commit_id":"90a8feda4a552dbc5df29ddb227e01b9dc742f7c","original_commit_id":"90a8feda4a552dbc5df29ddb227e01b9dc742f7c","user":{"login":"jkinable","id":2742474,"avatar_url":"https://avatars.githubusercontent.com/u/2742474?v=3","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":"Consider Collections.singletonList(source)\r\n","created_at":"2016-07-22T03:17:13Z","updated_at":"2016-07-22T03:17:13Z","html_url":"https://github.com/jgrapht/jgrapht/pull/222#discussion_r71821880","pull_request_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222","_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments/71821880"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/222#discussion_r71821880"},"pull_request":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222"}}},"pull_request":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222","id":78195191,"html_url":"https://github.com/jgrapht/jgrapht/pull/222","diff_url":"https://github.com/jgrapht/jgrapht/pull/222.diff","patch_url":"https://github.com/jgrapht/jgrapht/pull/222.patch","issue_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/222","number":222,"state":"open","locked":false,"title":"Bidirectional version of Dijkstra's shortest path","user":{"login":"d-michail","id":15940875,"avatar_url":"https://avatars.githubusercontent.com/u/15940875?v=3","gravatar_id":"","url":"https://api.github.com/users/d-michail","html_url":"https://github.com/d-michail","followers_url":"https://api.github.com/users/d-michail/followers","following_url":"https://api.github.com/users/d-michail/following{/other_user}","gists_url":"https://api.github.com/users/d-michail/gists{/gist_id}","starred_url":"https://api.github.com/users/d-michail/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/d-michail/subscriptions","organizations_url":"https://api.github.com/users/d-michail/orgs","repos_url":"https://api.github.com/users/d-michail/repos","events_url":"https://api.github.com/users/d-michail/events{/privacy}","received_events_url":"https://api.github.com/users/d-michail/received_events","type":"User","site_admin":false},"body":"This is an implementation of a bidirectional version of Dijkstra's shortest path algorithm (closes issue #135).\r\n\r\nThe algorithm maintains two frontiers and alternates between them until they meet.\r\n","created_at":"2016-07-20T18:23:36Z","updated_at":"2016-07-22T03:17:13Z","closed_at":null,"merged_at":null,"merge_commit_sha":"ae4acc263b83a842dbd15e9056f9a89a6ce13f83","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222/commits","review_comments_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222/comments","review_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/222/comments","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/90a8feda4a552dbc5df29ddb227e01b9dc742f7c","head":{"label":"d-michail:bidirectional-dijkstra","ref":"bidirectional-dijkstra","sha":"90a8feda4a552dbc5df29ddb227e01b9dc742f7c","user":{"login":"d-michail","id":15940875,"avatar_url":"https://avatars.githubusercontent.com/u/15940875?v=3","gravatar_id":"","url":"https://api.github.com/users/d-michail","html_url":"https://github.com/d-michail","followers_url":"https://api.github.com/users/d-michail/followers","following_url":"https://api.github.com/users/d-michail/following{/other_user}","gists_url":"https://api.github.com/users/d-michail/gists{/gist_id}","starred_url":"https://api.github.com/users/d-michail/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/d-michail/subscriptions","organizations_url":"https://api.github.com/users/d-michail/orgs","repos_url":"https://api.github.com/users/d-michail/repos","events_url":"https://api.github.com/users/d-michail/events{/privacy}","received_events_url":"https://api.github.com/users/d-michail/received_events","type":"User","site_admin":false},"repo":{"id":63318196,"name":"jgrapht","full_name":"d-michail/jgrapht","owner":{"login":"d-michail","id":15940875,"avatar_url":"https://avatars.githubusercontent.com/u/15940875?v=3","gravatar_id":"","url":"https://api.github.com/users/d-michail","html_url":"https://github.com/d-michail","followers_url":"https://api.github.com/users/d-michail/followers","following_url":"https://api.github.com/users/d-michail/following{/other_user}","gists_url":"https://api.github.com/users/d-michail/gists{/gist_id}","starred_url":"https://api.github.com/users/d-michail/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/d-michail/subscriptions","organizations_url":"https://api.github.com/users/d-michail/orgs","repos_url":"https://api.github.com/users/d-michail/repos","events_url":"https://api.github.com/users/d-michail/events{/privacy}","received_events_url":"https://api.github.com/users/d-michail/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/d-michail/jgrapht","description":"Master repository for the JGraphT project","fork":true,"url":"https://api.github.com/repos/d-michail/jgrapht","forks_url":"https://api.github.com/repos/d-michail/jgrapht/forks","keys_url":"https://api.github.com/repos/d-michail/jgrapht/keys{/key_id}","collaborators_url":"https://api.github.com/repos/d-michail/jgrapht/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/d-michail/jgrapht/teams","hooks_url":"https://api.github.com/repos/d-michail/jgrapht/hooks","issue_events_url":"https://api.github.com/repos/d-michail/jgrapht/issues/events{/number}","events_url":"https://api.github.com/repos/d-michail/jgrapht/events","assignees_url":"https://api.github.com/repos/d-michail/jgrapht/assignees{/user}","branches_url":"https://api.github.com/repos/d-michail/jgrapht/branches{/branch}","tags_url":"https://api.github.com/repos/d-michail/jgrapht/tags","blobs_url":"https://api.github.com/repos/d-michail/jgrapht/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/d-michail/jgrapht/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/d-michail/jgrapht/git/refs{/sha}","trees_url":"https://api.github.com/repos/d-michail/jgrapht/git/trees{/sha}","statuses_url":"https://api.github.com/repos/d-michail/jgrapht/statuses/{sha}","languages_url":"https://api.github.com/repos/d-michail/jgrapht/languages","stargazers_url":"https://api.github.com/repos/d-michail/jgrapht/stargazers","contributors_url":"https://api.github.com/repos/d-michail/jgrapht/contributors","subscribers_url":"https://api.github.com/repos/d-michail/jgrapht/subscribers","subscription_url":"https://api.github.com/repos/d-michail/jgrapht/subscription","commits_url":"https://api.github.com/repos/d-michail/jgrapht/commits{/sha}","git_commits_url":"https://api.github.com/repos/d-michail/jgrapht/git/commits{/sha}","comments_url":"https://api.github.com/repos/d-michail/jgrapht/comments{/number}","issue_comment_url":"https://api.github.com/repos/d-michail/jgrapht/issues/comments{/number}","contents_url":"https://api.github.com/repos/d-michail/jgrapht/contents/{+path}","compare_url":"https://api.github.com/repos/d-michail/jgrapht/compare/{base}...{head}","merges_url":"https://api.github.com/repos/d-michail/jgrapht/merges","archive_url":"https://api.github.com/repos/d-michail/jgrapht/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/d-michail/jgrapht/downloads","issues_url":"https://api.github.com/repos/d-michail/jgrapht/issues{/number}","pulls_url":"https://api.github.com/repos/d-michail/jgrapht/pulls{/number}","milestones_url":"https://api.github.com/repos/d-michail/jgrapht/milestones{/number}","notifications_url":"https://api.github.com/repos/d-michail/jgrapht/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/d-michail/jgrapht/labels{/name}","releases_url":"https://api.github.com/repos/d-michail/jgrapht/releases{/id}","deployments_url":"https://api.github.com/repos/d-michail/jgrapht/deployments","created_at":"2016-07-14T08:35:27Z","updated_at":"2016-07-14T08:35:29Z","pushed_at":"2016-07-21T23:08:44Z","git_url":"git://github.com/d-michail/jgrapht.git","ssh_url":"git@github.com:d-michail/jgrapht.git","clone_url":"https://github.com/d-michail/jgrapht.git","svn_url":"https://github.com/d-michail/jgrapht","homepage":"http://www.jgrapht.org","size":6002,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"jgrapht:master","ref":"master","sha":"b18f56c7c5e84729b6b8b2fe60e8316c06331d3c","user":{"login":"jgrapht","id":1624681,"avatar_url":"https://avatars.githubusercontent.com/u/1624681?v=3","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,"name":"jgrapht","full_name":"jgrapht/jgrapht","owner":{"login":"jgrapht","id":1624681,"avatar_url":"https://avatars.githubusercontent.com/u/1624681?v=3","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":"2016-07-21T09:25:54Z","pushed_at":"2016-07-21T23:08:45Z","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":7662,"stargazers_count":703,"watchers_count":703,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":301,"mirror_url":null,"open_issues_count":66,"forks":301,"open_issues":66,"watchers":703,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/222"},"issue":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/222"},"comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/222/comments"},"review_comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222/comments"},"review_comment":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/222/commits"},"statuses":{"href":"https://api.github.com/repos/jgrapht/jgrapht/statuses/90a8feda4a552dbc5df29ddb227e01b9dc742f7c"}}}}
{"actor":{"display_login":"jkinable"}}