创建具有两种边的连通图

Question

我想构建一个连通图，并且只能有水平或垂直边。边缘是 tracks/track 个开关。

有两种曲目：NormalTrack 和 TrackSwitch。
- 法线轨迹：起点、终点。
- TrackSwitch：开始点、结束点、第二个结束点。
  - 第一个端点是标准设置，可以通过（有一个设置开关命令可以改变开关设置）。
所有曲目（switch也是曲目）都有一个从1开始的唯一标识符。
除第一条轨道外，起点或终点必须始终连接到现有轨道的起点或终点。只有一个其他轨道（普通轨道或轨道开关）可以连接到轨道上的一个点。

下面是一个示例以及图表的样子：

add track (1,1) -> (5,1)
ID -> 1
add switch (5,1) -> (8,1),(5,3)
ID -> 2
add track (1,1) -> (1,-3)
ID -> 3
add track (1,-3) -> (10,-3)
ID -> 4
add track (8,1) -> (10,1)
ID -> 5
add track (10,1) -> (10,-3)
ID -> 6
add track (5,3) -> (8,3)
ID -> 7

我有一个 class Point 代表笛卡尔点和一个 class RailNetwork 我要在其中实现图形。在我的 Register class 中，我有一个 Map<Integer, Track> tracks; 用于保存所有曲目。在这个class中我还实例化了RailNetwork network = new RailNetwork();

我已经实现了命令界面。现在，我想创建铁路网。

有人可以告诉我如何实现这种方式吗？

编辑

这是我当前的实现：

public class RailNetwork {
    private Map<Point, List<Point>> edges = new HashMap<>();

    // Add edge (two points)
    public void addEdge(Point firstCoordinate, Point secondCoordinate) {
        edges.computeIfAbsent(firstCoordinate, x -> new ArrayList<>()).add(secondCoordinate);
        edges.computeIfAbsent(secondCoordinate, x -> new ArrayList<>()).add(firstCoordinate);
    }

    // Return all edges
    public List<Point> getEdges(Point node) {
        return Collections.unmodifiableList(edges.get(node));
    }

    // Check if a set of edges is still connected after removing them
    public boolean isConnectedAfterRemoving(Set<Edge> toRemove) {
        Set<Point> notVisited = edges.entrySet()
                .stream()
                .filter(e -> e.getValue().stream().anyMatch(d -> !toRemove.contains(new Edge(e, d)) &&
                        !toRemove.contains(new Edge(d, e))))
                .map(Map.Entry::getKey).collect(java.util.stream.Collectors.toSet());
        if (notVisited.isEmpty())
            return true;
        visit(notVisited.iterator().next(), notVisited, toRemove);
        return notVisited.isEmpty();
    }


    private void visit(Point next, Set<Point> notVisited, Set<Edge> toRemove) {
        if (!notVisited.remove(next))
            return;
        for (Point point : edges.get(next))
            if (!toRemove.contains(new Edge(next, point)) &&
                    !toRemove.contains(new Edge(point, next)))
                visit(point, notVisited, toRemove);
    }

    private void visitAndRemove(Set<Point> nodes, Point node) {
        if (nodes.contains(node)) {
            nodes.remove(node);
            List<Point> nextNodes = getEdges(node);
            for (Point next : nextNodes) {
                visitAndRemove(nodes, next);
            }
        }
    }
}


public class Edge {
    private final Point source;
    private final Point dest;

    public Edge(Point source, Point dest) {
        this.source = source;
        this.dest = dest;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this || !(o instanceof Edge)) {
            return o == this;
        }

        Edge edge = (Edge) o;
        return Objects.equals(source, edge.source) &&
                Objects.equals(dest, edge.dest);
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, dest);
    }
}

我不确定为什么我的 isConnectedAfterRemoving() 方法不起作用。我怎样才能解决这个问题？

我还有一个摘要classTrack和两个子classesNormalTrack和TrackSwitch.

TrackSwitch(int id, Point startPoint, Point endPoint, Point secondEndPoint, int length, boolean switchEnabled)
NormalTrack(int id, Point startPoint, Point endPoint, int length)

我现在该如何继续..?

Answer 1

您可以创建两个 classes NormalTrack 和 TrackSwitch 并用 class 的实例表示每个轨道。 classes 存储轨道的 id、起点和终点。

那么您可能想要为每个点存储传入轨道列表以及传出轨道列表。在此设置中，开关有点复杂，因为它有两个端点。您可能还需要在开关中使用一个标志来告知哪个端点当前处于活动状态。然后，当您迭代一个点的 incoming/outgoing 轨迹并点击 TrackSwitch 时，您必须首先检查您正在迭代的点当前是否处于活动状态。如果没有，你必须跳过它。

创建具有两种边的连通图

Create a Connected Graph With Two Types Of Edges

java

point