Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Discussion: Graph] Consider removing storage assumptions from GraphProtocol #197

Open
jsbean opened this issue Nov 2, 2018 · 0 comments

Comments

@jsbean
Copy link
Member

jsbean commented Nov 2, 2018

cc @bwetherfield.

Currently, GraphProtocol requires a hash-based storage of nodes and edges:

protocol GraphProtocol {
    associatedtype Node: Hashable
    associatedtype Edge: SymmetricPair & Hashable where Edge.A == Node
    var nodes: Set<Node> { get set }
    var edges: Set<Edge> { get }
    mutating func remove(_ edge: Edge)
}

First, I propose that we get rid of any assumption of storage type, hashed or otherwise. Instead, we should leave only an abstract API for modifying the graph.

protocol GraphProtocol {
    associatedtype Node
    associatedtype Edge
    mutating func insert(_ edge: Edge)
    mutating func remove(_ edge: Edge)
    // perhaps `insert(_ node: Node)`, `remove(_ node: Node)`
}

In order to adapt this more abstract model to the current working concrete graph types, we could lower the hash-based storage assumptions to HashGraphProtocol:

protocol HashGraphProtocol: GraphProtocol {
    var nodes: Set<Node> { get set }
    var edges: Set<Edge> { get }    
}

We can move the default implementations for the current GraphProtocol onto the HashGraphProtocol.

We may need to do a little juggling to make all of the downstream protocols and types work, but hopefully very little.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant