Inheritance and generics

Question

I have an application that performs various analysis algorithms on graphs of nodes and edges G(N,E). The attributes of the nodes and edges vary with the application and form an inheritance hierarchy based on the type of graph and nature of the attributes. For example the root of the Node hierarchy could represent the most general Non-directed Cyclic Graphs (NcgNode). A sub-class of NcgNode might represent directed cyclic graphs (DcgNode), followed by DagNode, etc. The algorithms that can be applied to DAGs are different from those of NCGs, but not visa-versa. A key behavior of the root of the tree is to add and retrieve adjacent nodes of the graph. The question is how to do this without creating an "unchecked" exception?

A terse version of the code might look like this:

import java.util.ArrayList;
import java.util.List;

public class NcgNode {
    private List<NcgNode> nodeList_ = null;
    private List<? extends NcgNode> nodeListSrc_ = null;
    private List<? super NcgNode> nodeListSink_ = null;

    public <N extends NcgNode> void addNode(N node) {
        if (nodeList_ == null) {
            nodeList_ = new ArrayList<NcgNode>();
            nodeListSrc_ = nodeList_;
            nodeListSink_ = nodeList_;
        }
        nodeListSink_.add(node);
    }

    @SuppressWarnings("unchecked")
    // Any way to avoid this?
    public <N extends NcgNode> N getNode(int n) {
        if ((nodeList_ == null) || (n >= nodeList_.size()))
            return null;
        // causes unchecked warning:
        return (N) nodeListSrc_.get(n);
    }
}

class DcgNode extends NcgNode {
    // enables DCG algorithms, etc
}

class DagNode extends DcgNode {
    // enables DAG algorithms, etc.
}

Is there a better way to design this?

Answer 1

Just make your lists have type NcgNode, eg

private List<NcgNode> nodeListSrc_ = null;

You can still put subclasses of NcgNode into these lists.

Answer 2

You should do it something like the following. Have the methods defined in an abstract class (NcgNode), parameterized on the type of the children. Thus, addNode and getNode can be easily written. Then you will have specific implementations (I used DcgNode and DagNode; not sure if this is what you want) be a subclass of this, parameterized on itself. This allows you to have later (see below) algorithms that require that a node's children is the same type as the node.

public abstract class NcgNode<N> {
    private List<N> nodeList_ = null;

    public void addNode(N node) {
        if (nodeList_ == null) {
            nodeList_ = new ArrayList<N>();
        }
        nodeList_.add(node);
    }

    // Any way to avoid this?
    public N getNode(int n) {
        if ((nodeList_ == null) || (n >= nodeList_.size()))
            return null;
        return nodeList_.get(n);
    }
}

class DcgNode extends NcgNode<DcgNode> {
    // enables DCG algorithms, etc
}

class DagNode extends NcgNode<DagNode> {
    // enables DAG algorithms, etc.
}

//...
static <N extends NcgNode<N>> void someAlgorithm(N node) { }

Your idea of DagNode being a subclass of DcgNode cannot be safe, because if a DagNode "is-a" DcgNode, then that means you can put any DcgNode into it as its child, which is not what you want.