Search code examples
javaalgorithmgraphopenstreetmapadjacency-list

How to build undirected graph with adjacency list from a large OSM map in a linear time

This my first time programming web application with maps.

I am trying to create undirected graph with adjacency list for each node from a given OSM map.

Everything works fine when I tested it on small maps.
I unmarshal the OSM map (which is equal to XML file) and then create from the OSM object I received an undirected graph.

The problem starts when I try to create the graph from larger maps.

For example, took map with size of 6MB:
Number of nodes: 24828
Number of ways: 4535
In each way avearage number of 5 nodes.
All these together will be: 24828 * 4535 * 5 = 562,974,900 iterations !

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.
If node1 equal node2 I need to take the next & previous node in the way to be its neighbors.
It took me approximately 1:30 minute to do it:

enter image description here

I am building web application which will run on smart phones and calculates random path to run.
If the user needs to wait 1:30 minute only for the creation of the graph it will be unusable.

I am familiar with BFS \ DFS but they won't help me in this case because I need to build the graph.

Maybe there is other efficient way to create the adjacency list for the nodes ?

How I build adjacency list: 

public static List<Node> GetNodesFromXML(Osm i_Osm) {
        List<Node> o_Nodes = new ArrayList<Node>();
        long id;
        double latitude;
        double longtitude;
        Map<Node, List<Node>> o_AdjList = new HashMap<Node, List<Node>>();


        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<Long> nodeAdjacenciesByRef = getNodeAdjacenciesByRef(node, i_Osm.getWay(), i_Osm.getNode());
           // List<Edge> nodeAdjacencies = getNodeAdjacencies1(node, i_Osm.getWay(), i_Osm.getNode());
          // List<Edge> 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;
    }

Classes I used for the graph: 

// Node.java
public class Node implements Comparable<Node>
{

    private long m_Id;
    private List<Edge> m_Adjacencies = new ArrayList<Edge>();
    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<Node> m_Nodes = new ArrayList<>();
    private List<Way> m_Ways = new ArrayList<>();
    private List<Relation> m_Relations = new ArrayList<>();
    private Bounds m_Bounds;

    public Graph(List<Node> i_Nodes, List<Way> i_Ways, List<Relation> 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;
    }
    ...
}

EDIT: Solved:
I used HashMap. This way I will be able to get every node in O(1).
So I run one time on all the nodes (1 second or less) and create this map.
After I have this mapping I can pass on each node in every Way without the external loop.
After this redesign the whole thing took something like 3 seconds.

So here is the solution: 

   public static List<Node> GetNodesFromXML(Osm i_Osm) {
        List<Node> o_Nodes = new ArrayList<Node>();
        long id;
        double latitude;
        double longtitude;
        Map<Long, Node> o_NodesByRef = new HashMap<Long, Node>();


        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<Node> addAdjacencies(Map<Long, Node> i_NodesByRef , List<Osm.Way> i_Ways) {
        List<Node> o_Nodes = new ArrayList<Node>();
        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() > 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 -> 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 -> nextNode
                            edge2 = new Edge(node, nextNode, weight); 
                            i_NodesByRef.get(node.getNodeId()).getAdjacencies().add(edge2);


                        }
                    }
                }
            }
        }

        for(Map.Entry<Long, Node> entry : i_NodesByRef.entrySet())
         {
                o_Nodes.add(entry.getValue());
         }

        return o_Nodes;
    }
Solution

  • The problem is that you are trying to store an adjacency list where the elements are entire nodes. 

    Map<Node, List<Node>> o_AdjList = new HashMap<Node, List<Node>>();

    And that is not efficient, because that graph store all of the node information and takes up a lot of memory.

    Instead I would make a graph using just node ids, as integer:

    Map<Integer, TreeSet<Integer>> o_AdjList = new HashMap<Integer, TreeSet<Integer>>();

    And keep the remaining node information in a separate more efficient structure, like a HashSet.

    This means you will have a graph representation using only integer ids, which is MANY times smaller object than the first graph. Now the processor can cache more of them and run SSSP faster.

    If you really wanted a graph with actual Nodes, you can construct it afterward. This what I would do to build a graph from way: 

    for (Osm.Way way : i_Osm.getWay()) {
//I will asume the getNd() returns some sort of array or list an you can access the next or previous element
     for (Osm.Way.Nd nd : way.getNd()) {
                if(o_AdjList contains key nd){
                  o.AdjList.get(nd).add(nextNd);
                } else {
                  o.AdjList.put(nd,nextNd);
     }
}

    Of course, you will have to implement some walk method, but after that...you have your node set.