How can self-references (recursion) in Java generics be used correctly?

Question

Let's say I have two Java interfaces. One is a node interface that is supposed to manage its outgoing and incoming edges, so it is parameterized with an edge type. The other one is an edge interface that has a source node and a target node, so it is parameterized with a node type.

I could start defining it like this:

public interface Node<E extends Edge> {
    List<E> getOutgoingEdges();
    List<E> getIncomingEdges();
}

public interface Edge<N extends Node> {
    N getSource();
    N getTarget();
}

This is only partially correct, because Edge and Node have parameters, and they have been omitted.

So I could try this:

public interface Node<E extends Edge<Node<E>> {
public interface Edge<N extends Node<Edge<N>> {

However, this causes compiler errors.

This works, but it doesn't quite seem to be what I want:

public interface Node<E extends Edge<?>> {
public interface Edge<N extends Node<?>> {

And least it also allows implementing the interfaces with two classes:

public class NodeImpl<E extends Edge<NodeImpl<E>>> implements Node<E> {
public class EdgeImpl<N extends Node<EdgeImpl<N>>> implements Edge<N> {

What is then the correct way to declare and instantiate NodeImpl and EdgeImpl? None of this works without warnings/errors:

Node<?> node = new NodeImpl<>();
Node<EdgeImpl<?>> node = new NodeImpl<>();
Node<EdgeImpl<? extends Node>> node = new NodeImpl<>();
NodeImpl<?> node = new NodeImpl<>();
NodeImpl<EdgeImpl<?>> node = new NodeImpl<>();
NodeImpl<EdgeImpl<? extends Node>> node = new NodeImpl<>();

How shall the interfaces be declared, how do the implementations need to be declared and how can I declare/instantiate the implementations?

The idea is the following:

I may have different types of node implementations. For example, they could have different position information (x and y coordinate, GPS coordinates, 3D coordinates, or whatever). The length of an edge is then defined on some distance function between two nodes, but that only works if the nodes are compatible with each other.

Let's say I want to run A* search on a graph, provided as a list of nodes (which then also define the edges between the nodes), and a provided distance function, which estimates the distance between two nodes. The distance function would be dependent on the node type used. I could have nodes that contain a 2D coordinate, GPS coordinates, 3D coordinates or whatever.

Using typed nodes and edges, I would be able to enforce that the graph only contains a specific node and edge type and would be able to run a generic A* search on it that uses a custom distance function between two nodes.

Answer 1

If you want to have two implementation classes that are linked, you can declare the interfaces as:

public interface Node<N extends Node<N,E>, E extends Edge<N,E>> {
public interface Edge<N extends Node<N,E>, E extends Edge<N,E>> {

Then you can declare implementation classes as:

public class NodeImpl implements Node<NodeImpl, EdgeImpl> {
public class EdgeImpl implements Edge<NodeImpl, EdgeImpl> {