java - 如何遍历对象列表并分配 child ？

Question

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

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

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

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

基本上，我想知道如何迭代 Location 对象的列表，以及如何在每个顺序位置上调用 addChild？

下面是我用来将 Location 映射到对象表示的 Location 类:

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

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

1. E -> 边缘
2. V -> 顶点(又名节点)

关键属性:

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

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

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[] -> 所有连接的 Locations(顶点)，其中 location[i] 中的 i 是边

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

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

如果你实现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 有效。但它很接近