Definition of "correct"

[sbromberger]

Given the proposed adoption of C4, we need to come up with a definition of "correct" that encompasses the "spirit" of LightGraphs: a commitment to simplicity, correctness, and performance. This issue is intended to be a forum for creation of as unambiguous a definition as possible.

[jpfairbanks]

I will take a first crack.

How about a patch is "correct" if:

• It solves a specific problem as defined in the graph algorithm literature (with citation).
• Comes with tests that prove correctness of solution.
• Does not introduce performance regressions on CI.
• There is no simpler way to implement the proposed patch.

Maintainers will be able to ask for additional tests, benchmarks, and justifications of simplicity.

Features of julia that are considered complex: unnecessary code generation, tasks, heavily parameterized types, foreign function interfaces, binary dependencies.

[sbromberger]

How does this apply to enhancements (think abstraction or something else?) IMO, we need something akin to

• Adheres to the overall project goal of simplicity of use

That is, simplicity of code is addressed in your proposal, but something discussing simplicity of concept is not readily apparent.

Also, perhaps:

• does not introduce performance regressions or disruption to the core LightGraphs implementation (SimpleGraphs).

I know you've got "performance regressions on CI" but I think we should be explicit with respect to our "showcase" graph type, especially as it's the one that's being used by critical packages.

Also also: we should incorporate our development guidelines in there. Binary dependencies are one thing, but so are other package dependencies. If it's going into the core LightGraphs codebase, it should still minimize any external dependence. (My initial thought, btw, is to have the concrete implementation of any graph abstractions be separate packages; that way you do something like "using LightGraphs; using DictGraphs" or something like that. This idea is completely preliminary and not at all well-formed.)

[jpfairbanks]

(My initial thought, btw, is to have the concrete implementation of any graph abstractions be separate packages; that way you do something like "using LightGraphs; using DictGraphs" or something like that. This idea is completely preliminary and not at all well-formed.)

What if we made each implementing type a submodule of LG?

using LightGraphs
using LightGraphs.DictGraphs

g = DictGraph()
add_edge!(g, i,j)
set_property!(g,i,j,:weight, 3)

[sbromberger]

What if we made each implementing type a submodule of LG?

There are definitely advantages to that route, but I think there may be some disadvantages (both from organizational and maintainability perspectives):

1) Organizational: if we use separate repos, then we can have separate maintainers for that code. 2) Maintainability: if we use separate repos, then people who don't want/need a particular set of abstractions don't have to load them.

Shrug. It might be less complicated to roll in submodules. I'm not particularly swayed either way.

On the plus side, that's a really elegant interface you've sketched out for DictGraphs :)

[jpfairbanks]

I am bringing my experience with microrepos into this decision. I think we should design things in a way to support either multiple implementations in a single package, but also more than one package that provides implementations.

If we say that each implementation must be in its own module, but not necessarily its own package, then we can get the best of both worlds, and maximize the freedom of other developers.

[sbromberger]

If we say that each implementation must be in its own module, but not necessarily its own package, then we can get the best of both worlds, and maximize the freedom of other developers.

I like this approach the more I think about it. What it would allow us to do is to create (similar to Julia itself) a "base" package, into which mature, stable, and common abstractions could be placed. Newer / experimental abstractions could remain as separate packages until such time as they become fully-formed and useful to some larger group, when they would be migrated to a submodule within LightGraphs.jl.

Thoughts on this idea?

[jpfairbanks]

Yeah let's do it.

[sbromberger]

Closing this out since it looks like our current approach - separate modules for graph types - is working reasonably well and our need for C4 seems to be on hold.