New public API

[dominikbraun]

At version 0.8.0, there is a central Graph interface that offers two kinds of methods: Methods to build, modify, and "read" the graph, and methods to perform operations and algorithms on the graph. These two things should be separated. Algorithms shouldn't be the graph's concern.

What I mean by "reading" is to retrieve vertices and edges.

I'm thinking of a lighter Graph interface that only has methods for building and reading the graph itself, and standalone package functions for algorithms such as pathfinding, that accept a Graph instance and do the rest themselves.

The obvious challenge is to find an interface surface for Graph that satisfies the needs of pretty much all algorithms, which was the reason why I didn't go for this approach in the first place. Now that there are many functions and methods in place, figuring out the needs for the algorithms should be a bit easier.

Example for finding SCCs:

Old:

g := graph.New(graph.IntHash, graph.Directed())
scc := g.StronglyConnectedComponents()

New:

g := graph.New(graph.IntHash, graph.Directed())
scc := graph.StronglyConnectedComponents(g)

Why?

The advantage is that this scales much better. For 20 new algorithms, the Graph interface doesn't grow by 20 new methods.

This is relevant in that there are many algorithms that roughly look the same for directed and undirected graphs, and yet they need to be implemented twice. A standalone package function would not only make the Graph interface simpler but also prevent code and test duplication.

[dominikbraun]

Draft for new Graph interface (updated)

type Graph[K comparable, T any] interface {
	Traits() *Traits
	AddVertex(value T) error
        Vertex(hash K) (T, error)
	AddEdge(source, target K, options ...func(*EdgeProperties)) error
	Edge(source, target T) (Edge[T], error)
	AdjacencyMap() (map[K]map[K]Edge[K], error)
        Predecessors(vertex K) (map[K]Edge[K], error)
}

All the DFS, BFS, Shortest Path, and SCC methods are removed. The Graph interface only provides "CRUD" operations for the graphs and its vertices and edges.

[geoah]

That sounds like a really nice separation!!

Can I take this opportunity to raise a couple of small points that seemed a bit weird when I first saw the graph api?

1. Are both the X() and the XByHash() methods really needed? Is it useful enough to the developer that warrants doubling the number of methods on the graph interface?

This is not a big deal by any means, mostly bringing this up out of curiosity, the love of bikeshedding, and an interest in clean interfaces :D

2. Any chance we could prefix all methods with a verb and not just some? It's a weird experience when you first see a method Vertex() and are not sure if it gets or puts.

In the new API there are also some discrepancies in the naming.

• Traits() gets
• Edge() puts
• Vertex() puts
• Degree() gets
• etc

3. Could all methods return an error? It's a bit weird that some return just a value, some also return bool, and some also return an error. - This would also be really useful for features such as adding more persistence layers etc.

---

ie. Maybe something like this?

type Graph[K comparable, T any] interface {
	GetTraits() Traits
	AddVertex(value T) error
        GetVertex(hash K) (T, error)
	AddEdge(sourceHash, targetHash K, options ...func(*EdgeProperties)) error
	GetEdge(sourceHash, targetHash K) (Edge[T], error)
	GetDegree(vertexHash K) (int, error)
	GetAdjacencyMap() (map[K]map[K]Edge[K], error)
}

---

Looking forward to whatever the new API looks like :D

[dominikbraun]

Thanks for your thoughts!

1. I'm having a hard time deciding for the user when they want to work with a hash value and when they want to work with the vertex value, hence I simply created a method for either way. With #24, we could make it configurable whether the user wants to work with hashes or vertices and cut those duplicated methods. If the user opts in to using hash values, the passed arguments to methods like GetEgde would be interpreted as hashes, not vertices.

2. Yes. The naming of Vertex and Edge was supposed to make the API more declarative and less imperative, but I see that this mixed form might be a bit confusing.

3. I think with the new Store interfaces, all of these methods will need to return an error anyway.

[dominikbraun]

@geoah I've updated the draft for the new Graph interface to the extent that all methods return an error and "adding" methods have an Add prefix.

As to the Get methods, while it makes sense to prefix all the methods with a verb, there is also the convention of Getters without the Get prefix. What would you prefer here?

[geoah]

@dominikbraun prefixing the Add ones and keeping the getters without a verb sounds like a good solution!

Doesn't look half bad.

type Graph[K comparable, T any] interface {
	Traits() Traits
	AddVertex(value T) error
        Vertex(hash K) (T, error)
	AddEdge(sourceHash, targetHash K, options ...func(*EdgeProperties)) error
	Edge(sourceHash, targetHash K) (Edge[T], error)
	Degree(vertexHash K) (int, error)
	AdjacencyMap() (map[K]map[K]Edge[K], error)
}```

[dominikbraun]

Another possibility would be to only prefix non-trivial "getters" with Get, which are getters that involve some computation at runtime or return an error, e.g. GetEdge; and omit the prefix for "real" getters such as Degree. We'll see.

[dominikbraun]

Alright, I've updated the new Graph interface draft and opened a corresponding PR: #27