Swift generics for graph classes

Question

I'm trying to create some classes in Swift 5 to represent a directed Graph. I'm finding Swift generics to be very confusing and restrictive.

This is what I've got so far, but no matter what I try, Swift seems to come up with some obscure error or other (two are shown below in comments).

Can I even achieve this kind of structure in Swift without hardcoding Node to a specific concrete type?

I want to allow the Node type to be changed, so that I can add additional properties to the Node and Edge types according to the needs of the problem.

public class Graph<N:Node>
{
    var nodeMap: [String: N] = [:]
    var edges: [Edge<N>] = []
    
    public func addEdge(_ parentName: String, _ childName: String, weight: Double = 0.0) throws {
        let parent:N? = nodeMap[parentName]
        let child:N? = nodeMap[childName]
        
        let newEdge = Edge(parent!, child!)
        
        parent!.outgoing.append(newEdge) // Cannot convert value of type 'Edge<N>' to expected argument type 'Edge<Node>'
        edges.append(newEdge)
    }
    
}

public class Edge<N:Node> {
    var parent: N
    var child: N
    
    init(_ parent: N, _ child: N) {
        self.parent = parent
        self.child = child
    }
}

public class Node {
    var name:String = ""
    var outgoing:[Edge<Self.Type>] = [] //'Edge' requires that 'Self.Type' inherit from 'Node'

}

I find your circular reference between Edge and Node confusing — Joakim Danielson, Sep 20 '20 at 13:24
Perhaps, but it worked for me in my application. It wasn't till I tried to make Graph and Edge generic that the problems started. Basically an Edge has a parent and a child Node, and a Node keeps track of the edges outgoing from it. It's a directed graph, BTW. — pnadeau, Sep 20 '20 at 13:31
You say you want to be able to add more properties to Node but since Node is a class you can only do this by subclassing and for that a non-generic solution will work just as well. — Joakim Danielson, Sep 20 '20 at 13:39
How would you suggest I do that? Remove the generics and then subclass all three classes in tandem so they match up you mean? Graph would have to know what kind of Node/Edge it's referring to, so I'm not sure that would work. — pnadeau, Sep 20 '20 at 13:43
Well I wouldn't really, I've been looking at a solution where Node is a protocol just like in the answer below. — Joakim Danielson, Sep 20 '20 at 13:50
If your `Node` is a `final` class, why do you want to make it a generic at all? You could just put `Node` directly where `N` is now. By the way, you are creating lots of strong reference cycles between your nodes and edges. — Sulthan, Sep 20 '20 at 13:50
By the way, this kind of graph representation is unusable for most graph algorithms. — Sulthan, Sep 20 '20 at 13:53
I totally agree with what Sulthan said in both comments. Have you considered using an adjacency list representation instead? You can still have your `Edge` and `Node` classes. The public interface doesn't have to change much. — Sweeper, Sep 20 '20 at 13:57
Sweeper and Sulthan, I see your point, and don't want to appear dismissive. I like the way I've got it implemented right now. And besides, whether or not is it a good representation of a graph, the question started to become interesting in its own right. — pnadeau, Sep 20 '20 at 17:14
Also the class Node wasn't meant to be final, because of course I wanted to subclass it as others have pointed out. I corrected the code above to reflect this. — pnadeau, Sep 20 '20 at 17:16

score 1 · Answer 1 · answered Mar 26 '22 at 22:14

I guess I'm a bit late to the party but for any future readers, the Final "issue" can be solved by making the Edge a protocol as well:

protocol Edge: class {
    associatedtype NodeType: Node where NodeType.EdgeType == Self
    var parent: NodeType {get set}
    var child: NodeType? {get set}
}

To make sure any classes implementing these protocols actually point to the correct counterpart I've added a type constraint on the associatedtype.

protocol Node: class {
    associatedtype EdgeType: Edge where EdgeType.NodeType == Self
    var name:String {get set}
    var outgoing:[EdgeType] {get set}
}

Just be careful of strong reference cycles as pointed out earlier. Hence the optional type of Edge.child to allow it to be weak. The reference arrangement can off course be different.

The main caveat of this method is that any subclasses to classes implementing these protocols will have properties pointing to their superclass. A proposed solution would be to not subclass but implement the protocols directly on the new class instead.

Sweeper · Accepted Answer · 2020-09-20T13:59:39.673

0

I think you need to make Node a protocol:

public protocol Node : class {
    var name:String { get set }
    var outgoing:[Edge<Self>] { get set }
}

Then, you can create concrete Node conformers that you can use as the generic argument for graph. e.g.

final public class ConcreteNode: Node {
    public var name = ""
    public var outgoing: [Edge<ConcreteNode>] = []
}

And you can create a Graph<ConcreteNode>. If you want to have a node with a foo property, you can create that class too:

final public class NodeWithFoo: Node {
    public var name = ""
    public var outgoing: [Edge<NodeWithFoo>] = []
    public var foo = ""
}

And you can have another Graph<NodeWithFoo>.

edited Sep 20 '20 at 13:59

answered Sep 20 '20 at 13:42

Sweeper

213,210
22
193
313

I assume your last class should have an array property of type `[Edge]` – Joakim Danielson Sep 20 '20 at 13:58
@JoakimDanielson haha nice spot :) – Sweeper Sep 20 '20 at 13:59
A quick check in a playground suggests this might work. I'll check more carefully and let you know in a bit. – pnadeau Sep 20 '20 at 16:15
Grr! It seems that the class implementing Node must be strictly final, which defeats the entire purpose. (Protocol 'Node' requirement 'outgoing' cannot be satisfied by a non-final class ('BasicNode') because it uses 'Self' in a non-parameter, non-result type position) – pnadeau Sep 20 '20 at 17:30
@pnadeau Then your model of a graph is fundamentally broken, because it violates the [Liskov Substitution Principle](https://en.wikipedia.org/wiki/Liskov_substitution_principle). Classes just _cannot_ have `Self` as property types, and protocol requirements with the `Self` type must be satisfied by final classes. For more info see this [recent answer](https://stackoverflow.com/questions/63964975/stored-variable-of-self-type-especially-when-subclassing/63965044#63965044) by me. It explains why this is not type safe. – Sweeper Sep 21 '20 at 00:11
Despite my suggested solution below, I ended up going with this solution. I don't consider it perfect because it makes the Node class final. But it's workable if you accept that to create alternative Node implementations you'll have to duplicate the properties methods of the 'base' node class. If the amount of boilerplate to be copied is small, then this is workable. Thanks to everyone for their help and suggestions. – pnadeau Sep 22 '20 at 14:01

pnadeau · Answer 3 · 2020-09-20T21:28:08.247

-3

Thanks for the responses.

The real end goal of this was to have Node and Edge types that could be specialized with additional fields to suit the application.

Sweeper's answer was a good answer to the specific implementation I posted in the question, and I learned a lot from it, so thanks for that.

However, what I ended up going with didn't use generics at all. This is what I did instead:


public class Node {
    var name:String = ""
    var outgoing:[Edge] = []
    
    // Added this catchall property here
    var data: Any?

}

I did a similar thing in the Edge class.

Now when I want to add some data to a Node, like say the price of an item as a Double field for example, I can simply create an extension like this:

extension Node {
    var price:Double? {
        get {
            return self.data as? Double
        }
        
        set {
            self.data = newValue
        }
    }
}

If I need to add more fields, I can always wrap them in a struct or class and set that via the extension.

edited Sep 20 '20 at 21:28

answered Sep 20 '20 at 20:16

pnadeau

427
5
8

`Edge` is a generic. – matt Sep 20 '20 at 20:29
Good catch @matt. I had copy/pasted the wrong code in my example. I've corrected it. – pnadeau Sep 20 '20 at 21:29
OK well this is not a good solution. Using generics is correct. Any time you say `Any` that's a bad smell, and `Any?` is a _really_ bad smell. – matt Sep 20 '20 at 21:56
Also, the "specialized with additional fields" was not in the original question - but the way to do that, as you've already been told, is to use a protocol. – matt Sep 20 '20 at 21:57
Yeah, the suggested answer is a good one for the example I posted, but there's more to the story than that. Swift generics simply don't work well for self referential data structures (see: https://stackoverflow.com/a/37141531/2065821), Since this is not intended to be library code that I'm sharing with others, I'd rather use Any and get on with my life rather than to create a lot of brittle generic code that will break every time I try to make a change and that I barely can reason about. I agree Any is a smell, but I can constrain it further. – pnadeau Sep 20 '20 at 22:25
And for the record, yes: "specialized with additional fields" was in the original question. (I expressed it differently, but equivalently, like this: "... so that I can add additional properties to the Node and Edge types") The proposed answer would leave me with a final class which gives me no way to achieve this without reapeating a lot of boilerplate code. – pnadeau Sep 20 '20 at 22:37

Swift generics for graph classes

3 Answers3