如何遍历 objects 的列表并分配 children？

Question

我有一个 Location POJO，它存储从 JSON 文件解析的 Location objects，我想将其映射到图形。图中每个节点的位置对应于它的 id 字段，其中 id="1" 是起始节点，id="10" 是目标节点。

为了解决这个问题，我修改了一个节点 class 以包含 setWeight()、addChildLocation() 等方法，但我不确定如何从我的列表中创建图表位置。我知道如何通过执行以下操作对位置进行硬编码并调用 addChildren 来创建图形，但不确定如何从已经可用的位置列表中创建它 objects:

    Node LocationOne= new Node("LocationOne", 170);
    LocationOne.addChildNode(LocationTwo, 105);

我对这个问题的想法是，应该使用 for..each 循环遍历列表中的位置，并将每个位置添加为前一个位置的 child。

基本上，我想知道如何迭代位置 object 的列表，并在每个顺序位置上调用 addChild？

下面是位置 class 我用来将位置映射到 object 表示：

public class Location {

    private Location[] location;

    private int id;

    private String description;

    private String weight;

    private String name;

    private Exit[] exit;

    private boolean visited = false;
    private boolean goalLocation;
    private int approximateDistanceFromGoal = 0;
    private Location parent;

    private Map<Location, Integer> children = new HashMap<Location, Integer>();




    public Location() {
        super();
    }

    public Location(String name){
        this.name = name;
    }

    public Location(String name, int goalDistance){
        this.name = name;
        this.approximateDistanceFromGoal = goalDistance;
    }

    public Location[] children(){
        return (Location[]) children.keySet().toArray(new Location[children.size()]);
    }

    public int getDistance(Location loc){
        if(children.get(loc) == null) System.out.println(this.name + ": " + loc.getName());
        return children.get(loc);
    }


    public int getChildLocationCount(){
        return children.size();
    }

    public void addChildLocation(Location child, int distance){
        children.put(child, distance);
    }

    public boolean isLeaf(){
        if (children.size() > 0){
            return false;
        }else{
            return true;
        }
    }


    public void removeChild(Location child){
        children.remove(child);
    }


    public Location[] getLocation() {
        return location;
    }

    public void setLocation(Location[] location) {
        this.location = location;
    }


    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getDescription ()
    {
        return description;
    }

    public void setDescription (String description)
    {
        this.description = description;
    }


    public String getWeight() {
        return weight;
    }

    public void setWeight(String weight) {
        this.weight = weight;
    }

    public String getName ()
    {
        return name;
    }

    public void setName (String name)
    {
        this.name = name;
    }

    public Exit[] getExit() {
        return exit;
    }

    public void setExit(Exit[] exit) {
        this.exit = exit;
    }


    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public boolean isGoalLocation() {
        return goalLocation;
    }

    public void setGoalLocation(boolean goalLocation) {
        this.goalLocation = goalLocation;
    }

    public int getApproximateDistanceFromGoal() {
        return approximateDistanceFromGoal;
    }

    public void setApproximateDistanceFromGoal(int approximateDistanceFromGoal) {
        this.approximateDistanceFromGoal = approximateDistanceFromGoal;
    }

    public Location getParent() {
        return parent;
    }

    public void setParent(Location parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "Location [location=" + Arrays.toString(location) + ", id=" + id
                + ", description=" + description + ", weight=" + weight
                + ", name=" + name + ", exit=" + Arrays.toString(exit)
                +"]";
    }


}

Answer 1

我不确定我是否完全理解，但是 'Exits' 数组中的名称是否成为子节点？不确定 Exit 对象上有哪些方法，或者这是否是最有效的解决方案，而且不幸的是我目前无法检查语法。

这个想法是该方法获取一个节点，找到子节点，然后有效地递归地在该节点上调用该方法 'walking' 在层次结构中向下。

ArrarList<Location> allNodes

// Create children for the specified node
public void createChildNodes(node n){
    // Fetch all available exits
    for(Exit e : n.getExit()){
        // Iterate through all possible nodes
        for(tempNode : allNodes) {
            // Check if the 'exit' node matches one of the available nodes
            if(tempNode.getName().equals(e.getName()){
                // Match found, add it
                n.addChildNode(tempNode, tempNode.getDistance));

                // Check for children nodes of the temp node
                createChildNodes(tempNode);
            }
        }
    }
}

Answer 2

如果您想构建任何类型的图表，请认识到图表由 2 个基本元素组成：

E -> 边
V -> 顶点（A.K.A 节点）

关键属性：

顶点可以有任意数量的边。
边只在单边之间节点（在我的实现中，为了记账我修改了它）。

实际上，您如何访问这些将取决于功能和性能之间的权衡。此外，如果图形节点不包含您的某些信息，它们将毫无价值。所以，我们添加

Map<String,Object> properties

所以我们可以存储一些数据，例如：

new Vertext().set("age",10);

我们还使用命名边，因此您可以执行以下操作：

Graph g = new Graph();
g.addVertex("Doctor",new DrVertex("Dr. Smith"));
g.addVertex("Doctor",new DrVertex("Dr. Cooper"));
List<Vertex> doctors = g.get("Doctor");
assertTrue("Dr. Smith",doctors.get(0));
assertTrue("Dr. Cooper",doctors.get(1));

我已经整理了如何实现通用图的基本结构。但有些人指出，有像 Neo 这样非常复杂的图形数据库。

下面是代码。如果您想为您的位置建模，请使用它。

/**
 * @author Christian Bongiorno
 */
public class Graph {

    private class Vertex {
        Map<String,Object> properties;
        private Map<String,Edge> edges;

        public Graph addVertex(String edgeName, Vertex v) {
            Edge e = edges.get(edgeName);
            if(e == null) {
                e = new Edge(this);
                edges.put(edgeName,e);
            }

            e.addVertex(v);
            return Graph.this;
        }

        public Graph addVertex(Vertex v) {
            return addVertex("anonymous",v);
        }

    }

    private static class Edge {
        Map<String,Object> properties;
        Vertex in;
        Collection<Vertex> out;

        private Edge(Vertex in) {
            this.in = in;
        }


        private void addVertex(Vertex v) {
            out.add(v);
        }
    }

}

您可以考虑将此问题移至 codereview.stackexchange.com

Edited

想象一下你的代码是这样的：

位置 -> 顶点
Location[] -> 所有连接的位置（顶点），其中 i 在 location[i] 是边

您的代码将难以使用，因为您没有声明边。边的属性之一是“权重”，但在这里您将其作为位置的属性.

至于实现“已访问”——这是一个调用状态，而不是图形范围的状态。但是，通过将其作为 Location 的一部分，您现在遇到了状态管理问题；想象一下再次尝试“找到”某物？您将不得不在每个节点上重置 'visited' 属性或丢弃并重新创建整个图。非常低效且容易出错。

如果您实现 DFS，这非常容易递归或什至使用尾循环，您可以将“已访问”状态与 dfs 方法调用一起传递。示例：

public Location find(Integer locationId) {
   Location result = null;
   for(Location l : locations) {
      // this hashset represents the visited state which only matters for this method call
      result = dfs(new HashSet(),l,locationId); 
      if(result != null)
          break;
   }
   return result;
}

请注意，下一个方法是 private。

private Location dfs(Set<Location> visitedAlready,Location current, Integer id){
   if(current.id == id)
      return current;
   visitedAlready.add(current); // instead of your boolean
   Location result = null;
   for(Location l : current.locations) {
      result = dfs(visitedAlready,l,id);
      if(result != null)
        break;
   }
   return result;
}

这是一个粗略的轮廓。如果您在 Java chat 中与我联系，我会提供更多意见，并最终提供更灵活和可重用的内容。我不主张上述 DFS 有效。但它很接近

如何遍历 objects 的列表并分配 children？

How to iterate through a list of objects and assign children?

java

object

pojo

java-5

graph-algorithm