Subclassing a set of inter-dependent classes in Ob

问题:

I've implemented a basic graph class (not as in "plotting" but as in "network"!), that's to be used for basic graph theoretical tasks. (see summarised header file snippets below)

In addition to the generic graph functionality it also implements functionality for node positioning in 3D space. And this extended 3D functionality I'd like to isolate into a subclass, resulting in:

• light-weight generic classes (MyGenericGraph, MyGenericGraphNode, MyGenericGraphEdge)
• heavier-weight specialized subclasses (My3DGraph, My3DGraphNode, My3DGraphEdge)

So far so good, in theory, that is.

Problem:

I'd have to ensure (and preferably at compile time) that one cannot add generic MyGenericGraphNodes to the spezialized My3DGraph, as it highly depends on the added 3D logic inside My3DGraphNode. (While the generic MyGenericGraph would simply not care.)

The core issue is as simple as this: I cannot override these methods from MyGenericGraph:

- (void)addNode:(MyGenericGraphNode *)aNode;
- (void)removeNode:(MyGenericGraphNode *)aNode;

with these methods in my subclass My3DGraph:

- (void)addNode:(My3DGraphNode *)aNode;
- (void)removeNode:(My3DGraphNode *)aNode;

I've so far come up with three possible solutions but before going for any of them I'd like to hear some opinions on them. (and hopefully spare me some unforeseen troubles on my way)

I'm wondering if there's another and superior solution or design pattern to this that I'm missing? Or if not: which of my solutions would you go for?
I'd love to hear your opinion on this.

Possible solution 1

• Adding an abstract class MyAbstractGraph that would basically be identical to the generic parts of my current implementation of MyGenericGraph (see below), but would lack any node-addition/removal methods. MyGenericGraph and My3DGraph would then simply be subclasses of MyAbstractGraph. And while MyGenericGraph would only implement the lacking node-addition/removal methods, My3DGraph would further more implement all 3D space functionality. Both requiring their respective node class types. (same for MyGenericGraphNode and MyGenericGraphEdge and their 3D counterparts)

Problems with this solution: It would add a significant amount of complexity to an otherwise rather simple problem.
Further more as My3DGraph should be able to deal with My3DGraphNodes AND MyGenericGraphNodes, I'd have to implement MyGenericGraph's method as:

- (void)addNode:(MyAbstractGraphNode *)aNode;`

but My3DGraph's method as:

- (void)addNode:(My3DGraphNode *)aNode;

as well, as otherwise my generic graph it wouldn't accept 3d nodes. This would expose the abstract class unnecessarily though.

Possible solution 2

True and simple subclasses + moving MyGenericGraphNode/My3DGraphNode allocation right into MyGenericGraph/My3DGraph, to get something like: - (MyGenericGraphNode *)newNode;, which would allocate and return a node of correct type and add it to the graph right away. One would then get rid of - (void)addNode:(MyGenericGraphNode *)aNode; entirely, leaving no chance to add nodes than from within the Graph itself (hence assuring proper class membership).

Problems with this solution: While it would not add any noteworthy complexity to the classes, it would on the other hand basically get me into the same predicament again, as soon as I—let's say—wanted to add functionality to my My3DGraph for moving a node from one graph to another. And imho a class should be able to deal with an object no matter who created it and why.

Possible solution 3

True and simple subclasses + adding specialized method for 3D nodes and disabling generic method, like so:

- (void)addNode:(MyGenericGraphNode *)aNode {
    [self doesNotRecognizeSelector:_cmd];
}

- (void)add3DNode:(My3DGraphNode *)aNode {
    //bla
}

Problems with this solution: The generic [a3DGraph addNode:aNode] method would still show up in Xcode's auto-complete, pass silently on compile, but unexpectedly throw exception on run. Frequent headaches foreseen.

Possible solution 4

True and simple subclasses for my graph and just the generic classes for node and edge, but with an additional ivar pointer My3DUnit *dimensionalUnit: in node class (defaulting to nil for MyGraph) that implements all the logic and properties and provides 3D functionality to the node class. My3DUnit can simply be silently created (with position (0,0,0) e.g.) and attached to generic nodes in case they get added to a 3d graph, and hence made compatible. Vice versa if a node with a DL3DUnitgets added to a generic graph it simply keeps it attached and adds the node.

Header Files

Here are the (shortened) headers of my classes:

@interface MyGraph : NSObject {
    // properties:
    NSMutableSet *nodes;
    //...

    //extended 3D properties:
double gravityStrength;
    //...
}
// functionality:
- (void)addNode:(MyGraphNode *)aNode;
- (void)removeNode:(MyGraphNode *)aNode;
//...

//extended 3D functionality:
- (double)kineticEnergy;
//...

@end

@interface MyGraphNode : NSObject { 
    // properties:
    MyGraph *graph;
    NSMutableSet *edges;
    //...

    //extended 3D properties:
    My3DVector position;
    //...
}
// properties:
@property (nonatomic, readonly) MyGraph *graph;
@property (nonatomic, readonly) NSSet *edges;
@property (nonatomic, readonly) NSSet *neighbors;
@property (nonatomic, readonly) NSUInteger degree;
//...

//extended 3D properties
@property (nonatomic, assign) My3DVector position;
//...

// functionality:
- (void)attachToGraph:(MyGraph *)aGraph;
- (void)detachFromGraph;
- (void)addNeighbor:(MyGraphNode *)aNode;
- (void)removeNeighbor:(MyGraphNode *)aNode;
- (BOOL)hasNeighbor:(MyGraphNode *)aNode;
- (NSSet *)neighbors;
- (NSUInteger)degree;
//...

//extended 3D functionality:
- (double)distanceToNode:(DLGraphNode *)aNode;
//...

@end

@interface MyGraphEdge : NSObject {
    // properties:
    MyGraphNode *predecessor;
    MyGraphNode *successor;
    //...
}

// properties:
@property (nonatomic, readonly) MyGraphNode *predecessor;
@property (nonatomic, readonly) MyGraphNode *successor;
//...

// functionality:
- (id)initWithPredecessorNode:(MyGraphNode *)predecessorNode successorNode:(MyGraphNode *)successorNode;
+ (MyGraphEdge *)edgeWithPredecessorNode:(MyGraphNode *)predecessorNode successorNode:(MyGraphNode *)successorNode;
- (BOOL)hasNeighbor:(MyGraphNode *)aNode;
- (BOOL)hasSuccessor:(MyGraphNode *)aNode;
- (BOOL)hasPredecessor:(MyGraphNode *)aNode;

@end

This is basically how my graph is implemented right now. There's obviously quite a bunch more to it, but you should get the idea.

(As you might have noticed MyGenericGraphEdge currently implements no 3D space functionality, but it might in the future, like computing its center point, e.g., hence I've included it here.)

[Edit: Added solution 4 inspired by ughoavgfhw; fixed a mistake in solution 1, sorry for that :(]

回答1:

Solution, quick and dirty:

After re-analysing my class structure and finding several previously unforeseen implications on potential pitfalls in future development on my planned graph class family I've come to the conclusion to go pretty much with my proposed solution 4 but accompany it by some major restructuring (see attached simplified ER diagram). My plan is to instead of having heavy multi-purpose über-classes, have several single-purpose components that (if well constructed) can be combined into various kinds of special-purpose (and relatively lightweight) toolsets.

Potential pitfalls of simple inheritance:

If I implement dimensional feature sets in a subclass of MyGenericGraph, then this makes it basically impossible for me to easily create more specific graph subclasses (for specialized trees e.g.) that can be either lightweight and generic (like MyGenericGraph) or dimensional (like My3DGraph). For a MyGenericTree class (for tree analysis e.g.) I'd have to subclass MyGenericGraph. For a My3DTree (for tree display e.g.) however I'd have to subclass My3DGraph. My3DTree could therefor not inherit any logic from MyGenericTree. I'd have implement the dimensional features redundantly. Bad. Pretty bad.

Proposed class structure architectures:

• Get rid of any "dimensional flavored" classes entirely. Keep classes strictly barebones data structures with just the basic and required logic.

• Introduce MyVertex class that provides dimensional attributes & methods to nodes if required (By adding a MyVertex *vertex ivar to MyGraphNode (defaulting to nil)). This also makes it much easier to re-use them in MyVertexCloud, a simple point cloud container, that should come in handy for improving my force-driven layout algorithm.

• Delegate any logic that's not strictly essential to the graphs' data-structure to special purpose helper classes. As such MyGraphNodeClusterRelaxer will be responsible for any logic specific to visual graph layout.

• Subclassing MyGraph will be quick and easy thanks to my single-chained inheritance chain and modularity.

• Utilizing an external MyGraphNodeClusterRelaxer will also allow me to relax a subset of graph nodes, not just an entire graph, as My3DGraph would have done it.

• MyGraphNodeCluster will be nothing more than a wrapper for basically a set of nodes (all of the same graph). Subclasses of it can be more specific in cluster membership criteria and algorithms.

• Getting a MyGraphNodeCluster from an entire graph will be as easy as calling (MyGraphNodeCluster *)[myGraph nodeCluster]; and from there you get a MyVertexCloud via (MyVertexCloud *)[myNodeCluster vertexCloud];. The reverse (for the latter) is not possible for obious reasons.

(Simplified) Entity Relational Model:

回答2:

Personally I wouldn't use any of these. I was going to suggest something similar to your second solution as an alternative, but I think this is a better way to it:

Declare addNode as - (void)addNode:(MyGenericGraphNode *)node. Then, in the implementation, make sure it is the right class. This is an even better choice since you mentioned in the problems with solution 1 section that you wanted the 3D graph to handle generic nodes too. I don't know how you want to handle them, but you could detect that the new node was not 3D and create a new 3D node from it, such as by just setting the z coordinate to 0 for everything.

Example:

//My3DGraph implementation
- (void)addNode:(MyGenericGraphNode *)node {
    if(![node isKindOfClass:[My3DGraphNode class]])
        node = [My3DGraphNode nodeWithNode:node];
    //add node
}

//My3DGraphNode class
+ (My3DGraphNode *)nodeWithNode:(MyGenericGraphNode *)otherNode {
    //Make sure you can create a 3D node from otherNode
    //Change 2D properties of otherNode to 3D properties, create new node with those properties
}