Repository: graphhopper/graphhopper (java)

Issue:
Sort graph edges
Currently `graph.do_sort: true` only sorts the nodes of a graph, but in `GHUtility.createSortedGraph` it is also possible to sort graph edges. I use `MMAP` storage so implemented this thinking that sorting edges would batch disk reads closer together and reduce page faults when checking edges in the location index, getting edge details for the route, etc.  I did get a performance boost and reduction in average page faults per request and will post a PR shortly.

Pull request description:
Sort edges
Fixes #1756 to sort edges in addition to nodes by iterating through edges to add them to the graph in the same order that we iterated through them during DFS. This improved some performance problems I was having (particularly around closest point lookup) and I started running this in production on 10/17.

There are a number of other changes included as well (ubuntu 16->18, graphhopper 0.8->0.13) but I do see a significant reduction in average major page faults per request which was the goal of this change:
![image](https://user-images.githubusercontent.com/1480504/67158376-56e8e380-f305-11e9-8a27-0810b9d4bb15.png)


Patch:
diff --git a/.github/ISSUE_TEMPLATE/config.yml b/.github/ISSUE_TEMPLATE/config.yml
new file mode 100644
index 000000000..ee61274b4
--- /dev/null
+++ b/.github/ISSUE_TEMPLATE/config.yml
@@ -0,0 +1,8 @@
+blank_issues_enabled: false
+contact_links:
+  - name: GraphHopper Forum
+    url: https://discuss.graphhopper.com/c/graphhopper
+    about: Please ask and answer questions here.
+  - name: GraphHopper Security Bug Reporting
+    url: https://www.graphhopper.com/contact-form/
+    about: Please report security vulnerabilities here.
\ No newline at end of file
diff --git a/docs/ISSUE_TEMPLATE/issue_template.md b/.github/ISSUE_TEMPLATE/issue_template.md
similarity index 93%
rename from docs/ISSUE_TEMPLATE/issue_template.md
rename to .github/ISSUE_TEMPLATE/issue_template.md
index 86228683a..01913b0d7 100644
--- a/docs/ISSUE_TEMPLATE/issue_template.md
+++ b/.github/ISSUE_TEMPLATE/issue_template.md
@@ -1,10 +1,6 @@
 ---
 name: Bug report
 about: Create a report to help us improve
-title: ''
-labels: ''
-assignees: ''
-
 ---
 
 **Describe the bug**
diff --git a/.gitignore b/.gitignore
index d656ebd9a..c766ce81d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,11 +1,9 @@
 target/
 *~
-TODO.txt
 *-gh/
 *.osm
 nbactions*.xml
-config.properties
-config.yml
+/config.yml
 build.xml
 queries.sh
 maven/
@@ -25,13 +23,10 @@ debug.sh
 !/reader-osm/src/test/resources/com/graphhopper/reader/osm/*.pbf
 *.dem
 *.log
-core/TODO*.txt
 srtmprovider/
-core/docs/
-.*#
 cgiarprovider/
+.*#
 /nbactions.xml
-tools/nb-configuration.xml
 android/build/
 android/app/build/
 android/.gradle
@@ -42,8 +37,5 @@ local.properties
 **/node_modules
 *.zip
 .DS_Store
-/core/nbproject/
-/reader-overlay-data/nbproject/
-!malta-latest.osm.pbf
 /graph-cache
 package-lock.json
\ No newline at end of file
diff --git a/core/src/main/java/com/graphhopper/util/GHUtility.java b/core/src/main/java/com/graphhopper/util/GHUtility.java
index 93b81e725..42179eacc 100644
--- a/core/src/main/java/com/graphhopper/util/GHUtility.java
+++ b/core/src/main/java/com/graphhopper/util/GHUtility.java
@@ -308,7 +308,16 @@ public class GHUtility {
             list.set(i, i);
         }
         list.shuffle(new Random());
-        return createSortedGraph(g, sortedGraph, list);
+
+        int edges = g.getEdges();
+        GHIntArrayList edgesList = new GHIntArrayList(edges);
+        edgesList.fill(edges, -1);
+        for (int i = 0; i < edges; i++) {
+            edgesList.set(i, i);
+        }
+        edgesList.shuffle(new Random());
+
+        return createSortedGraph(g, sortedGraph, list, edgesList);
     }
 
     /**
@@ -317,32 +326,55 @@ public class GHUtility {
      */
     public static Graph sortDFS(Graph g, Graph sortedGraph) {
         int nodes = g.getNodes();
-        final GHIntArrayList list = new GHIntArrayList(nodes);
-        list.fill(nodes, -1);
-        final GHBitSetImpl bitset = new GHBitSetImpl(nodes);
-        final AtomicInteger ref = new AtomicInteger(-1);
+        final GHIntArrayList nodeList = new GHIntArrayList(nodes);
+        nodeList.fill(nodes, -1);
+        final GHBitSetImpl nodeBitset = new GHBitSetImpl(nodes);
+        final AtomicInteger nodeRef = new AtomicInteger(-1);
+
+        int edges = g.getEdges();
+        final GHIntArrayList edgeList = new GHIntArrayList(edges);
+        edgeList.fill(edges, -1);
+        final GHBitSetImpl edgeBitset = new GHBitSetImpl(edges);
+        final AtomicInteger edgeRef = new AtomicInteger(-1);
+
         EdgeExplorer explorer = g.createEdgeExplorer();
         for (int startNode = 0; startNode >= 0 && startNode < nodes;
-             startNode = bitset.nextClear(startNode + 1)) {
+             startNode = nodeBitset.nextClear(startNode + 1)) {
             new DepthFirstSearch() {
                 @Override
                 protected GHBitSet createBitSet() {
-                    return bitset;
+                    return nodeBitset;
+                }
+
+                @Override
+                protected boolean checkAdjacent(EdgeIteratorState edge) {
+                    int edgeId = edge.getEdge();
+                    if (!edgeBitset.contains(edgeId)) {
+                        edgeBitset.add(edgeId);
+                        edgeList.set(edgeRef.incrementAndGet(), edgeId);
+                    }
+                    return super.checkAdjacent(edge);
                 }
 
                 @Override
                 protected boolean goFurther(int nodeId) {
-                    list.set(nodeId, ref.incrementAndGet());
+                    nodeList.set(nodeId, nodeRef.incrementAndGet());
                     return super.goFurther(nodeId);
                 }
             }.start(explorer, startNode);
         }
-        return createSortedGraph(g, sortedGraph, list);
+        return createSortedGraph(g, sortedGraph, nodeList, edgeList);
     }
 
-    static Graph createSortedGraph(Graph fromGraph, Graph toSortedGraph, final IntIndexedContainer oldToNewNodeList) {
-        AllEdgesIterator eIter = fromGraph.getAllEdges();
-        while (eIter.next()) {
+    static Graph createSortedGraph(Graph fromGraph, Graph toSortedGraph, final IntIndexedContainer oldToNewNodeList, final IntIndexedContainer newToOldEdgeList) {
+        int edges = fromGraph.getEdges();
+        for (int i = 0; i < edges; i++) {
+            int edgeId = newToOldEdgeList.get(i);
+            if (edgeId < 0)
+                continue;
+
+            EdgeIteratorState eIter = fromGraph.getEdgeIteratorState(edgeId, Integer.MIN_VALUE);
+
             int base = eIter.getBaseNode();
             int newBaseIndex = oldToNewNodeList.get(base);
             int adj = eIter.getAdjNode();


Test patch:
diff --git a/core/src/test/java/com/graphhopper/util/GHUtilityTest.java b/core/src/test/java/com/graphhopper/util/GHUtilityTest.java
index 5b3e140e6..1bb3ad584 100644
--- a/core/src/test/java/com/graphhopper/util/GHUtilityTest.java
+++ b/core/src/test/java/com/graphhopper/util/GHUtilityTest.java
@@ -86,6 +86,7 @@ public class GHUtilityTest {
         Graph g = initUnsorted(createGraph());
         Graph newG = GHUtility.sortDFS(g, createGraph());
         assertEquals(g.getNodes(), newG.getNodes());
+        assertEquals(g.getEdges(), newG.getEdges());
         NodeAccess na = newG.getNodeAccess();
         assertEquals(0, na.getLatitude(0), 1e-4); // 0
         assertEquals(2.5, na.getLatitude(1), 1e-4); // 1
@@ -95,18 +96,18 @@ public class GHUtilityTest {
         assertEquals(5.0, na.getLatitude(5), 1e-4); // 7
         assertEquals(4.2, na.getLatitude(6), 1e-4); // 5
         assertEquals(getLengthOfAllEdges(g), getLengthOfAllEdges(newG), 1e-4);
-    }
 
-    @Test
-    public void testSort2() {
-        Graph g = initUnsorted(createGraph());
-        Graph newG = GHUtility.sortDFS(g, createGraph());
-        assertEquals(g.getNodes(), newG.getNodes());
-        NodeAccess na = newG.getNodeAccess();
-        assertEquals(0, na.getLatitude(0), 1e-4); // 0
-        assertEquals(2.5, na.getLatitude(1), 1e-4); // 1
-        assertEquals(4.5, na.getLatitude(2), 1e-4); // 2
-        assertEquals(4.6, na.getLatitude(3), 1e-4); // 8        
+        // 0 => 1
+        assertEquals(0, newG.getEdgeIteratorState(0, Integer.MIN_VALUE).getAdjNode());
+        assertEquals(1, newG.getEdgeIteratorState(0, Integer.MIN_VALUE).getBaseNode());
+
+        // 1 => 3 (was 8)
+        assertEquals(1, newG.getEdgeIteratorState(1, Integer.MIN_VALUE).getAdjNode());
+        assertEquals(3, newG.getEdgeIteratorState(1, Integer.MIN_VALUE).getBaseNode());
+
+        // 2 => 1
+        assertEquals(2, newG.getEdgeIteratorState(2, Integer.MIN_VALUE).getAdjNode());
+        assertEquals(1, newG.getEdgeIteratorState(2, Integer.MIN_VALUE).getBaseNode());
     }
 
     @Test
diff --git a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
index e7b018c31..4c4c172b5 100644
--- a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
+++ b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
@@ -841,19 +841,20 @@ public class GraphHopperIT {
     @Test
     public void testIfCHIsUsed() {
         // route directly after import
-        executeCHFootRoute();
+        executeCHFootRoute(false);
 
         // now only load is called
-        executeCHFootRoute();
+        executeCHFootRoute(false);
     }
 
-    private void executeCHFootRoute() {
+    private void executeCHFootRoute(boolean sort) {
         String tmpOsmFile = DIR + "/monaco.osm.gz";
         String tmpImportVehicles = "foot";
 
         GraphHopper tmpHopper = new GraphHopperOSM().
                 setOSMFile(tmpOsmFile).
                 setStoreOnFlush(true).
+                setSortGraph(sort).
                 setGraphHopperLocation(tmpGraphFile).
                 setEncodingManager(EncodingManager.create(tmpImportVehicles));
         tmpHopper.getCHFactoryDecorator().setCHProfileStrings(weightCalcStr);
@@ -874,6 +875,15 @@ public class GraphHopperIT {
         tmpHopper.close();
     }
 
+    @Test
+    public void testSortWhileImporting() {
+        // route after importing a sorted graph
+        executeCHFootRoute(true);
+
+        // route after loading a sorted graph
+        executeCHFootRoute(false);
+    }
+
     @Test
     public void testRoundTour() {
         GHRequest rq = new GHRequest().