title: How to build undirected graph with adjacency list from a large OSM map in a linear time
body: <p>This my first time programming web application with maps.  </p>
  
  <p>I am trying to create undirected graph with adjacency list for each node from a given OSM map.  </p>
  
  <p>Everything works fine when I tested it on small maps.<br>
  I unmarshal the OSM map (which is equal to XML file) and then create from the OSM object I received an undirected graph.  </p>
  
  <p>The problem starts when I try to create the graph from larger maps.  </p>
  
  <p>For example, took map with size of 6MB:<br>
  Number of nodes: 24828<br>
  Number of ways: 4535<br>
  In each way avearage number of 5 nodes.<br>
  All these together will be: 24828 *  4535 * 5 = 562,974,900 iterations !  </p>
  
  <p>Intuitively, in order to find neighbour for each node I need to go over each node1 in each way in each node2 from list of nodes.<br>
  If node1 equal node2 I need to take the next &amp; previous node in the way to be its neighbors.<br>
   It took me approximately 1:30 minute to do it:  </p>
  
  <p><a href="https://i.stack.imgur.com/GZhOe.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/GZhOe.png" alt="enter image description here"></a></p>
  
  <p>I am building web application which will run on smart phones and calculates random path to run.<br>
  If the user needs to wait 1:30 minute only for the creation of the graph it will be unusable.  </p>
  
  <p>I am familiar with BFS \ DFS but they won't help me in this case because I need to build the graph.  </p>
  
  <p>Maybe there is other efficient way to create the adjacency list for the nodes ?  </p>
  
  <p><strong>How I build adjacency list:</strong>  </p>
  
  <pre><code>public static List&lt;Node&gt; GetNodesFromXML(Osm i_Osm) {
          List&lt;Node&gt; o_Nodes = new ArrayList&lt;Node&gt;();
          long id;
          double latitude;
          double longtitude;
          Map&lt;Node, List&lt;Node&gt;&gt; o_AdjList = new HashMap&lt;Node, List&lt;Node&gt;&gt;();
  
  
          for (Osm.Node nodeChild : i_Osm.getNode()) {
              id = nodeChild.getId();
              latitude = nodeChild.getLat();
              longtitude = nodeChild.getLon();
              Node node = new Node(id, latitude, longtitude);
  
               for (Osm.Way way : i_Osm.getWay()) // go over the node list of the specific way objects
                {
                  for (Osm.Way.Nd nd : way.getNd()) {
                      // some manipulation to create the adjacency list
                  }
               }
  
              //List&lt;Long&gt; nodeAdjacenciesByRef = getNodeAdjacenciesByRef(node, i_Osm.getWay(), i_Osm.getNode());
             // List&lt;Edge&gt; nodeAdjacencies = getNodeAdjacencies1(node, i_Osm.getWay(), i_Osm.getNode());
            // List&lt;Edge&gt; nodeAdjacencies = getAdjacenciesListFromRefList(node, nodeAdjacenciesByRef, i_Osm.getNode());
            // node.SetAdjacencies(nodeAdjacencies);
              o_Nodes.add(node);
          }
  
          for(Node node : o_Nodes)
          {
  
          }
  
  
  
          o_Nodes = updateAdjacenciesToAllNodes(o_Nodes);
  
          return o_Nodes;
      }
  </code></pre>
  
  <p><strong>Classes I used for the graph:</strong>  </p>
  
  <pre><code>// Node.java
  public class Node implements Comparable&lt;Node&gt;
  {
  
      private long m_Id;
      private List&lt;Edge&gt; m_Adjacencies = new ArrayList&lt;Edge&gt;();
      private double m_Longtitude;
      private double m_Latitude;
      private Node m_Prev; 
      private double m_MinDistance = Double.POSITIVE_INFINITY;  // this is for Dijkstra Algorithm
      //used to reconstruct the track when we found the  approproate length of the user request
      //from the current level to the destination
  
      public Node(long i_Id, double i_Latitude, double i_Longtitude) 
      {
          m_Id = i_Id;
          m_Latitude = i_Latitude;
          m_Longtitude = i_Longtitude;
      }
      ...
  }
  
  // Graph.java
    private List&lt;Node&gt; m_Nodes = new ArrayList&lt;&gt;();
      private List&lt;Way&gt; m_Ways = new ArrayList&lt;&gt;();
      private List&lt;Relation&gt; m_Relations = new ArrayList&lt;&gt;();
      private Bounds m_Bounds;
  
      public Graph(List&lt;Node&gt; i_Nodes, List&lt;Way&gt; i_Ways, List&lt;Relation&gt; i_Relations, Bounds i_Bounds) {
          m_Nodes = i_Nodes;
          m_Ways = i_Ways;
          m_Relations = i_Relations;
          m_Bounds = i_Bounds;
      }
      ...
  }
  // Edge.java
  public class Edge {
  
      Node m_Source;
      Node m_Destination;
  
      double m_Weight;
  
      public Edge(Node i_Source, Node i_Destination, double i_Weight) {
          m_Source = i_Source;
          m_Destination = i_Destination;
          m_Weight = i_Weight;
      }
      ...
  }
  </code></pre>
  
  <p><strong>EDIT: Solved:</strong><br>
  I used HashMap. This way I will be able to get every node in O(1).<br>
  So I run one time on all the nodes (1 second or less) and create this map.<br>
  After I have this mapping I can pass on each node in every Way without the external loop.<br>
  After this redesign the whole thing took something like 3 seconds.  </p>
  
  <p>So here is the solution:  </p>
  
  <pre><code>   public static List&lt;Node&gt; GetNodesFromXML(Osm i_Osm) {
          List&lt;Node&gt; o_Nodes = new ArrayList&lt;Node&gt;();
          long id;
          double latitude;
          double longtitude;
          Map&lt;Long, Node&gt; o_NodesByRef = new HashMap&lt;Long, Node&gt;();
  
  
          for (Osm.Node nodeChild : i_Osm.getNode()) {
              id = nodeChild.getId();
              latitude = nodeChild.getLat();
              longtitude = nodeChild.getLon();
              Node node = new Node(id, latitude, longtitude);
              //o_Nodes.add(node);
              o_NodesByRef.put(id, node);
          }
  
          o_Nodes = addAdjacencies(o_NodesByRef, i_Osm.getWay());
  
  
          //o_Nodes = updateAdjacenciesToAllNodes(o_Nodes);
  
          return o_Nodes;
      }
  
  
       private static List&lt;Node&gt; addAdjacencies(Map&lt;Long, Node&gt; i_NodesByRef , List&lt;Osm.Way&gt; i_Ways) {
          List&lt;Node&gt; o_Nodes = new ArrayList&lt;Node&gt;();
          long ndId;
          int nodeIndex;
          int lastNodeIndex;
          Node previousNode;
          Node nextNode;
          double weight;
          //System.out.println(i_SourceNode.getNodeId());
          for (Osm.Way way : i_Ways) // go over the node list of the specific way objects
                  {
              if (way.getNd().size() &gt; 1) {
                  for (Osm.Way.Nd nd : way.getNd()) {
  
                      if(i_NodesByRef.containsKey(nd.getRef()))// found node in way
                      {
                          Node node = i_NodesByRef.get(nd.getRef());
                          nodeIndex = way.getNd().indexOf(nd);
                          Edge edge1;
                          Edge edge2;
                          Osm.Way.Nd temp_nd;
                          lastNodeIndex = way.getNd().size() - 1;
  
                          if (nodeIndex == 0) // node is the first in the way
                          {
                              temp_nd = way.getNd().get(nodeIndex + 1);
                              nextNode = i_NodesByRef.get(temp_nd.getRef());
                              weight = CoordinateMath.getDistanceBetweenTwoNodes(node, nextNode);
                              edge1 = new Edge(node, nextNode, weight); 
                              i_NodesByRef.get(node.getNodeId()).getAdjacencies().add(edge1);
  
  
                          } else if (lastNodeIndex == nodeIndex) // node is the last
                          {
                              temp_nd = way.getNd().get(nodeIndex - 1);
                              previousNode = i_NodesByRef.get(temp_nd.getRef());
  
                              weight = CoordinateMath.getDistanceBetweenTwoNodes(node, previousNode);
                              edge1 = new Edge(node, previousNode, weight); 
                              i_NodesByRef.get(node.getNodeId()).getAdjacencies().add(edge1);
  
                          } else // node is in the middle
                          {
                              temp_nd = way.getNd().get(nodeIndex - 1);
                              previousNode = i_NodesByRef.get(temp_nd.getRef());
  
                              weight = CoordinateMath.getDistanceBetweenTwoNodes(node, previousNode);
                              // node -&gt; previousNode
                              edge1 = new Edge(node, previousNode, weight); 
                              i_NodesByRef.get(node.getNodeId()).getAdjacencies().add(edge1);
  
                              temp_nd = way.getNd().get(nodeIndex + 1);
                              nextNode = i_NodesByRef.get(temp_nd.getRef());
                              weight = CoordinateMath.getDistanceBetweenTwoNodes(node, nextNode);
                              // node -&gt; nextNode
                              edge2 = new Edge(node, nextNode, weight); 
                              i_NodesByRef.get(node.getNodeId()).getAdjacencies().add(edge2);
  
  
                          }
                      }
                  }
              }
          }
  
          for(Map.Entry&lt;Long, Node&gt; entry : i_NodesByRef.entrySet())
           {
                  o_Nodes.add(entry.getValue());
           }
  
          return o_Nodes;
      }
  </code></pre>