java - 通过 java 中的继承为不同的实现重用算法逻辑

Question

我正在尝试在 java 中实现图形数据结构。 以下是类:

interface Graph<N,E> {
    addNode(N nodeData);
    createEdge(N src, N dest, E edgeData);
    //and many more api methods
}

class GenericGraph<N,E> implements Graph<N,E> {

    Set<Node<N,E>> vertices;

    static class Node<N,E> {
        private N node;
        private Set<Edge<N, E>> adjacencyList;

        // getters and setters
    }

    static class Edge<N, E> {

        private E edgeData;
        private Node<N, E> src;
        private Node<N, E> dest;

        // getters and setters
    }

    //******** API methods implementation*********

    Node<N, E> findNode(N nodeData) {
        Node<N, E> node = new Node<>(nodeData);
        if (vertices.contains(node)) {
            for (Node<N, E> tempNode : vertices) {
                if (Objects.equals(tempNode, node)) {
                    node = tempNode;
                    return node;
                }
            }
        }
        return null;
    }

    Node<N, E> createNode(N nodeData) {
        Node<N, E> node = findNode(nodeData);
        if (node == null) {
            node = new Node<>(nodeData);
            vertices.add(node);
        }
        return node;
    }

    @Override
    public void addNode(N nodeData) {
        createNode(nodeData);
    }

    // other api methods
}

这里我创建了两个嵌套类:Node 和 Edge

一个图形对象可以有多个节点。

一个节点对象可以有一个相邻顶点的列表。

相邻的顶点被认为是 Edge ，其中包含

->src node
->dest node
->edge relation bw the two

GenericGraph api 方法使用类 Node 和 Edge 进行实现。

到目前为止一切正常。

现在我想制作一些比 GenericGraph 具有额外功能的其他类，例如 BfsGraph 、 DfsGraph 等。

BFS 算法的节点需要 3 个额外参数:

->color 
->parent
->distance

我想像这样创建 BfsGraph :

class BfsGraph<N,E> extends GenericGraph<N,E> {

    //access public,protected and default methods of GenericGraph

    private enum NodeColor {
        WHITE, GRAY, BLACK;
    }

    static class BfsNode<N,E> extends GenericGraph.Node<N,E> {
        private NodeColor color = NodeColor.WHITE;
        private Integer distance = Integer.MAX_VALUE;
        private Node<N, E> parent;

        BfsNode(N node) {
            super(node);
        }
    }
}

这个设计的问题是，我必须从 GenericGraph 复制每个方法，并根据自己的需要在 BfsGraph 中重新实现它(节点将更改为 BfsNode)。

以后如果我想做一些其他的实现，那么我又需要复制和修改所有的方法。

用 GenericGraph 编写的算法/逻辑必须重用而不是重写。

请给我建议一个新的解决方案或任何修改。

Answer 1

从您的描述来看，子类似乎需要能够控制两件事:

• 创建的 Node 实例必须是 Node 子类型的实例。
  • 这可以通过在 GenericGraph 中创建一个 protected 方法来处理，称为 createNode，它只是实例化 Node。 GenericGraph 可以在需要 Node 实例时调用该方法；子类可以覆盖该方法以提供 Node 的正确子类型。
  • 我注意到您已经有了一个createNode 方法，但它除了创建节点之外还有其他逻辑。您应该将该方法重命名为能够体现其全部用途的名称。

• findNode 方法需要声明为返回 Node 的适当子类型。

  • 这可以通过让子类覆盖 findNode 来处理，但是覆盖只是委托(delegate)给父类(super class)并执行适当的转换，如下所示:

    BsfNode<N, E> findNode(N nodeData) {
        return (BsfNode<N, E>) super.findNode(nodeData);
    }
    

  • 如果您有一堆这样的方法，那么您可能会考虑让 GenericGraph 实际上将其节点类型作为类型参数，这样就可以通过泛型的魔力来处理，而不是而不是要求显式覆盖。但听起来您还没有达到这种方法值得的地步。