如何在线性时间内从大型 OSM 地图构建具有邻接表的无向图

Question

这是我第一次使用地图编写 Web 应用程序。

我正在尝试为来自给定 OSM 映射的每个节点创建具有邻接表的无向图。

我在小地图上测试时一切正常。
我解组 OSM 映射（等于 XML 文件），然后从 OSM 对象创建我收到的无向图。

当我尝试从较大的地图创建图表时，问题就出现了。

例如，取大小为6MB的地图：
节点数：24828
路数：4535
每种方式平均5个节点数。
所有这些加起来就是：24828 * 4535 * 5 = 562,974,900 次迭代！

直觉上，为了找到每个节点的邻居，我需要从节点列表中的每个节点 2 中以各种方式遍历每个节点 1。
如果 node1 等于 node2 我需要将下一个和上一个节点作为它的邻居。
我花了大约 1:30 分钟才完成：

我正在构建将在智能手机上运行并计算到运行的随机路径的网络应用程序。
如果用户只需要等待 1:30 分钟来创建图形，它将无法使用。

我熟悉 BFS \ DFS，但在这种情况下它们不会帮助我，因为我需要构建图形。

也许还有其他有效的方法来为节点创建邻接表？

我如何建立邻接表：

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;
    }

类我用的图表：

// 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;
    }
    ...
}

编辑：已解决：
我使用了哈希表。这样我就可以得到 O(1) 中的每个节点。
所以我运行在所有节点上执行一次（1 秒或更短时间）并创建这张地图。
在我有了这个映射之后，我可以在没有外部循环的情况下以各种方式传递每个节点。
重新设计后，整个过程大约需要 3 秒。

所以这里是解决方案：

   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;
    }

Answer 1

问题是您试图存储一个邻接表，其中的元素是整个节点。

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

而且效率不高，因为该图存储了所有节点信息并占用了大量内存。

相反，我将只使用节点 id 作为整数来制作图表：

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

并将剩余的节点信息保存在一个单独的更高效的结构中，例如 HashSet。

这意味着您将拥有一个仅使用整数 id 的图形表示，该对象比第一个图形小很多倍。现在处理器可以缓存更多它们并且运行 SSSP 更快。

如果你真的想要一个有实际节点的图，你可以在之后构建它。这就是我要从 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);
     }
}

当然，你必须实现一些 walk 方法，但在那之后......你已经设置好了节点。

如何在线性时间内从大型 OSM 地图构建具有邻接表的无向图

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

java

algorithm

graph

openstreetmap

adjacency-list