5

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?

4 Answers 4

1

Just make your lists have type NcgNode, eg

private List<NcgNode> nodeListSrc_ = null;

You can still put subclasses of NcgNode into these lists.

1

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.

2
  • What if you also want to extend DcgNode or DagNode?
    – Sarevok
    Mar 18, 2013 at 17:41
  • If I want to store a List<NcgNode> that can store both DcgNode's and DagNode's, should I declare it? The compiler shows a warning if I declare it like that since I'm using the raw type.
    – Sarevok
    Mar 18, 2013 at 18:38
0

modify your method as such below:

public NcgNode getNode(int n) {
  if ((nodeList_ == null) || (n >= nodeList_.size())) {
  return null;
}

return (NcgNode) nodeListSrc_.get(n);
} 
1
  • 3
    This solution doesn't allow the caller to use the specifics of the concrete subclass it returns without performing an unsafe cast. Kicking the can down the road. Dec 19, 2012 at 2:14
0

Check out "self-bounded types". (EDIT: not sure I understand the down-votes here)

Your root class should be abstract and the actual node type N should be a type parameter to the class, as in

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

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

    public N getNode( int n ) {
        if ( nodeList_ == null || n >= nodeList_.size() )
            throw new NoSuchElementException();
        return nodeList_.get( n );
    }
}

Concrete subclasses can then supply their own types as N. For deep inheritance hierarchies, keep the "My Type" alive with another abstract class.

class NcgNode extends AbstractNode< NcgNode > {
}

abstract class AbstractDcgNode< N extends AbstractDcgNode< N > > extends AbstractNode< N > {
    // enables DCG algorithms, etc
}

class DcgNode extends AbstractDcgNode< DcgNode > {
}

class DagNode extends AbstractDcgNode< DagNode > {
    // enables DAG algorithms, etc
}
2
  • 1) "self-bounded types" do not work in Java. 2) if you replaced AbstractNode<N extends AbstractNode<N>> with AbstractNode<N> and AbstractDcgNode<N extends AbstractDcgNode<N>> with AbstractDcgNode<N> it would work the same way
    – newacct
    Mar 18, 2013 at 18:33
  • Can you be more specific about comment 1) ? One cannot enforce exactly that a type parameter bounds the class declaring it, but it's closer than the comment 2) suggestion which allows strictly more programs to compile than mine does -- and more than the OP was looking for. Mar 19, 2013 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.