数组列表的数组列表作为关系的表示

Question

我有几个值，像这样：（一行中的元素是有关系的。）

       Vertex relationships(edges)
    Source vertex   Destination vertex

    x1 26   y1 287   x2 154   y2 303
    x1 22   y1 114   x2 115   y2 185
    x1 26   y1 287   x2 375   y2 338
    x1 26   y1 287   x2 260   y2 393
    x1 115  y1 185   x2 121   y2 7
    x1 200  y1 101   x2 392   y2 238
    x1 99   y1 394   x2 375   y2 338
    x1 99   y1 394   x2 121   y2 7
    x1 274  y1 28    x2 22    y2 114
    x1 296  y1 185   x2 200   y2 101
    x1 115  y1 185   x2 154   y2 303

我应该找到所有相关的值并将它们放入列表中，如下所示：[26,287 154,303 375,338 260,393] 我曾尝试使用此代码：

    for (int i=0; i<vertexnum; i++) {
        adjLists.add(new ArrayList<Integer>());
    }

    for (int j=0; j<vertexnum; j++) {
        for (Point p : nodes) {
            for (Edge e : edges) {
                adjLists.get(j).add(e.p1.x);
                adjLists.get(j).add(e.p1.y);
                adjLists.get(j).add(0);

                adjLists.get(j).add(e.p2.x);
                adjLists.get(j).add(e.p2.y);
                adjLists.get(j).add(0);
                for (Point p1 : nodes) {
                    for (Edge e1 : edges) {
                        if (e1.p1.x == e.p1.x && e1.p1.y == e.p1.y && !adjLists.get(j).contains(e1.p2.x) && !adjLists.get(j).contains(e1.p2.y)) {
                            adjLists.get(j).add(e1.p2.x);
                            adjLists.get(j).add(e1.p2.y);
                            adjLists.get(j).add(0);
                        } else if(e1.p2.x == e.p1.x && e1.p2.y == e.p1.y && !adjLists.contains(e1.p1.x) && !adjLists.contains(e1.p1.y)){
                            adjLists.get(j).add(e1.p1.x);
                            adjLists.get(j).add(e1.p1.y);
                            adjLists.get(j).add(0);
                        }
                    }
                }
            }
        }
    }

它只创建一个ArrayList，它把所有的元素排成一行而不是单独给出。我试过调试，但我看不出是什么原因造成的。

我想要的示例：

Answer 1

我将分三步进行：定义数据结构、定义问题、提供解决方案。

定义数据结构

顶点：在您的示例中，顶点似乎是一对唯一的整数。 Point 应该很合适
关系：这似乎是由两个顶点定义的边。您应该为此编写一个简单的 pojo，但为了简洁起见，我们将使用来自 apache commons 的 Pair。让我们声明关系从右到左。因此 Pair<Point, Point> relationship = new ImmutablePair<Point, Point>(new Point(26, 287), new Point(154, 303)); 相当于示例数据中的第一行。

定义问题

您需要一种方法，该方法接受关系列表并吐出列表列表，显示可以从任何给定顶点到达的位置。我将更进一步，return 以 from 点作为键并以可能的点集作为值进行映射。 IE。 Map<Point,Set<Point>>

解决方案

至此背景已经明确，找到解决方案很容易

public static Map<Point, Set<Point>> createTraversalMap(List<Pair<Point, Point>> relationshipList) {
    Map<Point, Set<Point>> traversalMap = new HashMap<Point, Set<Point>>();
    for (Pair<Point, Point> relationship : relationshipList) {
        Point fromVertex = relationship.getLeft(), toVertex = relationship.getRight();
        Set<Point> toSet = traversalMap.get(fromVertex);// set of Vertexes we've found so far for the current "from" Vertex
        if (toSet == null) {// bootstrap the set
            toSet = new HashSet<Point>();
            traversalMap.put(fromVertex, toSet);
        }
        toSet.add(toVertex);
        // traversalMap.put(fromVertex, toSet); //not needed, but good to keep in mind
    }
    return traversalMap;
}

注意，我没有以任何方式测试过

数组列表的数组列表作为关系的表示

Arraylists of arraylist as a representation of relationships

java

arraylist

graph-algorithm

定义数据结构

定义问题

解决方案