gonum/graph

Graph packages for the Go language [DEPRECATED]

Gonum

Installation

The core packages of the Gonum suite are written in pure Go with some assembly. Installation is done using go get.

go get -u gonum.org/v1/gonum/...

Supported Go versions

Gonum supports and tests using the gc compiler on the two most recent Go releases on Linux (386, amd64 and arm64), macOS and Windows (both on amd64).

Note that floating point behavior may differ between compiler versions and between architectures due to differences in floating point operation implementations.

Release schedule

The Gonum modules are released on a six-month release schedule, aligned with the Go releases. i.e.: when Go-1.x is released, Gonum-v0.n.0 is released around the same time. Six months after, Go-1.x+1 is released, and Gonum-v0.n+1.0 as well.

The release schedule, based on the current Go release schedule is thus:

• Gonum-v0.n.0: February
• Gonum-v0.n+1.0: August

Build tags

The Gonum packages use a variety of build tags to set non-standard build conditions. Building Gonum applications will work without knowing how to use these tags, but they can be used during testing and to control the use of assembly and CGO code.

The current list of non-internal tags is as follows:

• safe — do not use assembly or unsafe
• bounds — use bounds checks even in internal calls
• noasm — do not use assembly implementations
• tomita — use Tomita, Tanaka, Takahashi pivot choice for maximimal clique calculation, otherwise use random pivot (only in topo package)

Issues

If you find any bugs, feel free to file an issue on the github issue tracker. Discussions on API changes, added features, code review, or similar requests are preferred on the gonum-dev Google Group.

https://groups.google.com/forum/#!forum/gonum-dev

License

Original code is licensed under the Gonum License found in the LICENSE file. Portions of the code are subject to the additional licenses found in THIRD_PARTY_LICENSES. All third party code is licensed either under a BSD or MIT license.

Code in graph/formats/dot is dual licensed Public Domain Dedication and Gonum License, and users are free to choose the license which suits their needs for this code.

The W3C test suites in graph/formats/rdf are distributed under both the W3C Test Suite License and the W3C 3-clause BSD License.

graph's Issues

graph: Get rid of function overriding nonsense

Let's look at A*:

func AStar(start, goal graph.Node, g graph.Graph, cost graph.CostFunc, heuristicCost graph.HeuristicCostFunc)

The rules for cost and heuristic function overriding are, while consistent, a bit labyrinthine. The precedence goes function argument -> graph method -> package default (unit cost/null heuristic).

While it seemed like an elegant solution at the time for some reason to me, I think it's a bit silly. Since we're doing #41, we may as well improve upon this as well, despite breaking pretty much all existing search code.

It occurs to me that one can trivially "override" cost and heuristic behavior via a simple struct wrapper:

type UnitNullGraph struct {
    Graph
}

func (g *UnitNullGraph) HeuristicCost(n1, n2 Node) float64 {
    return 0
}

func (g *UnitNullGraph) Cost(e Edge) float64 {
    return 1
}

Along with #41, A* would require an interface such as:

type HeuristicSearchable {
    Cost(e Edge) float64
    HeuristicCost(n1, n2 Node) float64
    OutgoingEdges(n Node) []Edge
}

We can provide concrete wrappers such as the UnitNullGraph for ease of use, however, if users want to override cost behavior, they can simply embed their graph in a struct with a different Cost function, which is a lot cleaner IMO.

concrete: dense graphs assume Inf is the non-edge state

This is related to #52.

In the case where a graph is being used to analyse a correlation matrix this is not the correct behaviour - a 0 edge weight is an absent edge.

I propose the dense graph types expose a float64 field that indicates the value associated with an absent edge. Then clients may choose between states that are appropriate for their domain (the most obvious choices being 0, Inf and NaN).

graph: define a minimum set of tests to implement for each concrete graph type

This looks like it should be a 2x2[x2] table: mut/const x dir/undir [x weighted/unweighted]. In which case the tests can be defined on the interfaces and just have calls out based on the concrete type.

However, this is blocked on the outcome of #21.

all: move tests from package_test to package in many cases

At the moment many of the test packages are named package_test. While this enforces use of the public API it makes much of the test debugging harder (in some cases impossible), so unless using he name package introduces import cycles, make the test package use this name.

propose: rename concrete -> simple

This makes way for the possibility of including multigraphs at a later stage and is arguably a more informative name.

graph: remove Remove*Edge

We have an opportunity to greatly simplify the edge handling API by removing RemoveUndirectedEdge and RemoveDirectedEdge by changing the corresponding AddUndirectEdge/AddDirectedEdge to SetUndirectedEdge/SetDirctedEdge. With this name change we can pass a nil graph.Edge to indicate edge deletion.

The trade-off here is that would then be possible to accidentally delete an edge if passed a nil graph.Edge. I think this is worth it for the improved API.

graph: consider adding multigraph support/API

When the API has stabilised somewhat we can consider adding multigraph API support. This will have API flow-on consequences.

The main difference from an API perspective is that instead of an Edge method, the graph has an Edges(u, v Node) []Edge method. It is not entirely clear how the Weighter interface should work, but that can be defined as implementation dependent (min/max of edges, sum of edges, mean of edges etc).

Then from the perspective of graph mutation, adding edges is easy, the distinction from simple graphs being that they SetEdges while multi-graphs AddEdges. The issue of edge deletion is more complicated since currently edges are not distinguishable via the API except for their From and To nodes and their Weight. This may not be a problem, since if an Edge is Go language comparable, that test could be made (if two edges are identical, there is no issue and if they are otherwise distinguishable then the correct edge will be deleted); following this path requires that we specify that an Edge must be a Go comparable type. The alternative is to make Edge have an ID method and use that.

/cc @vladimir-ch

unexpected number of neighbor nodes

Hello,

im not sure why the following example generates 5 neighbor nodes...
node2 should only have 3 neighbor nodes!

edit:
after some debugging i figured out that this is caused by the self-loops (a vertex that is connected to itself), can you fix this issue?

number of neighbors: 5
1
2
0
<nil>
<nil>

test program:

package main

import (
    "github.com/gonum/graph/concrete"
    "fmt
)

type Node struct {
    srcId    int64
    targetId int64
}

func GenerateDummyGraph() *concrete.DirectedGraph {
    nodes := [5]Node{
        {2, 1},
        {2, 2},
        {1, 0},
        {2, 0},
        {0, 2},
    }

    g := concrete.NewDirectedGraph()

    for _, n := range nodes {
        g.AddDirectedEdge(concrete.Edge{concrete.Node(n.srcId), concrete.Node(n.targetId)}, 1)
    }

    return g
}

func main() {
    g := GenerateDummyGraph()

    neighbors := g.Neighbors(concrete.Node(2))
    fmt.Println("number of neighbors:",len(neighbors))

    for _, n := range neighbors {
        fmt.Println(n)
    }
}

search: Prim and Kruskal need tests

search: split into functionally meaningful packages

The original search package was really mainly just path search. Now we have path search and topology analysis (and arguably flow, but that can stay in path search until that area expands further when flow, control or similar would be created).

I think we would benefit by doing search => {path,topo} where A*, the various SSSP and APSP functions, Kruskal and Prim are in path (along with Dominators and PostDominators), and TarjanSCC, ConnectedComponents, Sort, VertexOrdering, BronKerbosch and IsPath (renamed to IsPathIn(graph.Graph, []graph.Node) are in topo.

graph: remove Cruncher

It should be up the the algorithm to decide the most appropriate representation of a dense ID graph, not the client. This will also reduce the API surface.

search: BronKerbosch gives sporadic failures on go tip

I have been seeing sporadic failures of the BronKerbosch tests in the tip build of the matrix. The most recent was with go devel golang/go@0b9866f. I never see this with 1.4.2 or 1.3.3 (have run ~100 continuous tests on 1.4.2 without failure).

I am not yet sure whether this is a problem with BronKerbosch or something that is wrong with the new runtime. Do we wait for 1.5 to be released and then hit this hard, or try to exclude the possibility of error in BronKerbosch now?

Thoughts?

search: Johnson all pairs shortest paths function returns incorrect path weights

The weights are not adjusted after the return from Dijkstra to account for the graph reweighting.

I will be writing a new Johnson function that will also not require copying of the input graph. This will require also rewriting BellmanFord to return a single source shortest-path tree (I have one already in the case for the single source DijkstraFrom func I have in the dijkstra branch).

graph.DStarGraph still exists but DStar does not

DStar was removed in commit 4055978, but the relevant interface, DStarGraph still exists.

The removal of D* seems to have been the resolution for issue #2 which is now marked as closed. Should this type be removed? I think probably #2 should be reopened too; the test does not fail, but there is no DStar - this is an issue.

Why NewNode() and AddNode() in Mutable interface?

Hi. Can't think of a use case for creating a new node but not adding it to the graph. What was the reason for creating two methods for adding nodes to a graph?

search: remove weight graph.CostFunc parameter from path search functions

This can be done by, e.g.

type costModGraph struct {
    graph.Graph
    cost graph.CostFunc
}

func (g costModGraph) Cost(e graph.Edge) float64 {
    return g.cost(e)
}

and wrapping the graph.

This simplifies the API and the internal code and reduces the number of times we do search.PathFinder(g, nil), which seems pretty common (I see no case in our code where the cost function is provided as a graph.CostFunc rather than as intrinsic to the graph).

simple: DirectedDenseGraph.Edge() is incorrect

DirectedDenseGraph.Edge(u, v) returns an edge from u to v even when only an edge from v to u exists.

dead code in search.Dijkstra

The closedSet set is not used productively. Is it there for a reason?

It looks like it was originally a short circuit that was incompletely removed.

Is there justification for removing that fast path? If so, can we clean out that set?

DStarLite not implemented

See issues #2 and #14.

graph/simple: node retrieval from edges is subtle

Currently when a concrete graph that stores nodes returns a graph.Edge the edge holds its own copies of the edge end points. In the cases where they are used in tests this is not an issue because one concrete.Node is indistiguishable from another if they are converted from the same int. However we say that we will look after graph.Node interface values too (otherwise why is graph.Node not just an int).

The consequence of these things is that I add two nodes and set an edge between them, it is possible to return nodes which are not the node that is stored in the graph's node list.

For example:

type node struct {
    id int
    v  string
}

func (n node) ID() int { return n.id }

func main() {
    g := concrete.NewDirectedGraph()
    g.AddNode(node{id: 1, v: "foo"})
    g.AddNode(node{id: 2, v: "bar"})
    g.AddDirectedEdge(concrete.Edge{F: concrete.Node(1), T: concrete.Node(2)}, 0)
    fmt.Println(g.EdgeTo(concrete.Node(1), concrete.Node(2)))
}

prints

{1 2}

when I would expect it to print

{{1 foo} {2 bar}}

It's not obvious how to fix this while retaining the simplicity of the graph.Edge interface, at least when using the current approach to edge handling. The issue is that there is no way for the graph to be able to mutate a graph.Edge that is guaranteed to work; either the edge needs to be stored as a pair of node IDs and a weight (maybe) and then the edge is constructed when g.Edge* is called (we can't do this at the moment) or we take the edge we are handed, mutate it to ensure it is holding the nodes that the graph has (again we can't do this at the moment) and store it. Of these two impossible options, I prefer the first.

One possible approach is say that concrete graphs we provide always return a concrete.Edge (of whatever variety depending on other issues #53). This also solves another issue that I have been mulling over but not yet filed. If clients want other edge types to be returned they must define their own type.

Alternatively, we add SetFrom and SetTo methods to graph.Edge (and not just mutable edges - whatever that might be - all edges). While this adds further methods to the API, I think it is probably the better answer, though it opens the possibility for clients to do bad things like changing the From or To values of an edge without telling the graph. Because of this, it should be documented that an edge must not be modified outside the graph's API if it is held by a graph.

graph: Graph.AddNode is subtly unsafe

When I was writing the tests for the Bron-Kerbosch clique finding function I stumbled across a behaviour/user interaction that I think we should avoid.

The documentation for Graph.AddNode states that adding a node that already exists replaces the node, this is at odds with the name "add" and how that is normally interpreted.

The situation was that in constructing the test graph from the input data I did not check for existence of u nodes in a directed pair from a []search.set, thus overwriting v nodes in cases where subsequent edges where v < u. This gave obviously unexpected test results and because there is no noisy response to doing this, it took a fair bit of debugging to remember that nodes are replaced (this prompted #36 for the Tarjan tests which just happen to be in a forward order and so don't fail - by luck). In the case where a client is perhaps even less well versed in the graph package, this would be very frustrating.

I don't think the current behaviour is tenable in the long term.

In line with the general approach in gonum packages we should either disallow node replacement noisily or make AddNode to an existing node a no-op.

1. Panic on adding an existing node after having replaced it. This allows existing behaviour after a recover. I think this is awful.
2. Do a no-op and require that node replacement be a RemoveNode/AddNode pair. This explicitness fits well with the broader gonum approach for explicitness. Possibly this would return a added bool, indicating whether a node had been added.

DStarLite test fails

Test function commented out for now. Uncommented test result:

--- FAIL: TestDStarLite-8 (0.00 seconds)
graph_test.go:260: Got erroneous error: %s
Path before error encountered: %#v No path exists [5]

The error message could be cleaned up but presumably it indicates a bug in DStarLite.

concrete: use mat64.Dense and mat64.SymDense for dense graphs

We already have well tested logic for directed and undirected graph representation in the mat64 package, we should use this.

Making this change allows us to leverage all the matrix operations that gonum/matrix (and others) provides for dense graph operations.

{path,dynamic}: Consider implementing the priority queue for A* and D* Lite without map[int]int

... in a similar way to the priority queue example in the standard library.

internal: consider using Reflect instead of unsafe for fast path set comparison

@btracey raised this in #85 (comment).

Travis go versions and Coverage

The go versions currently built by Travis-CI are set to only use 1.2. Would you mind if I added in 1.3.3, release, tip, and coverage calculations?

Bug with EdgeTo in concrete.Graph/implied mutable design issue

When I started thinking on a redesign of the mutable graph interface, I came across a subtle bug with the adding of Edges in concrete.Graph. It stems from a tricky interaction of contracts the library makes.

The first contract is that EdgeTo of graph.DirectedGraph always ensures that Head is the first argument and Tail is the second (if any edge exists, that is). This is reasonable, and I believe it was generally agreed upon that this is sensible behavior for a directed graph.

The second contract is that MutableGraph always returns the user's edges. That is, calling SetEdgeTo(Edge) will always return whatever the user called. This works fine in the case of a directed addition, but in the case of an undirected addition, a call to concrete.Graph.EdgeTo(tail, head) will return an edge with head head and tail tail -- the opposite of what should happen.

So, okay, this is a good argument for a Directed/Undirected Mutable split, fair enough. That's what I was doing in the first place. However: one potential issue that needs thinking on -- the Directed and Undirected mutable graphs cannot interact. Unlike Graph/DirectedGraph the MutableDirectedGraph interface CANNOT embed MutableGraph. Using the MutableGraph behavior (with the proposed AddEdgeBetween), with the current "return the user's edge" contract will enforce us to break at least one contract: either always returning the user's edge or else returning a directed edge.

In fact, a(n undirected) MutableGraph cannot be a DirectedGraph, period. If it's treated as a DirectedGraph it will be forced to break one of the two contracts. This isn't a problem internally, but even if documented could result in confusing behavior. I suspect users will be very confused that if they implement MutableGraph they simply cannot safely use it as a DirectedGraph. Period.

I'm thinking of calling this an "acceptable limitation". However, it does mean that concrete.Graph needs a heavy redesign to account for the fact that it can either be Mutable and undirected, or MutableDirected and directed; but absolutely not both. This limitation also needs to be very clearly and thoroughly documented to prevent confusion.

search: FloydWarshall is incorrect

I have been working on cleaning up various things, and part of that is to generalise the FloydWarshall function.

The current state of that is in the api-explore branch. There is a requirement for an id sort of the nodes on input. I've spent a few hours trying to sort out why this is - at first I thought it was because of the changes I have made, but I have come to the belief that the implementation is based on an incorrect interpretation of the algorithm, one that makes the outcome dependent on the order of the adjacency matrix iterations (i.e. the order the nodes are explored). This does not show up in the current master test case because the order is deterministic, but does in mine because it is based on a map iteration.

This can be demonstrated by inverting the order of nodes in the graph input to TestFWConfoundingPath (0, 1, 2, 3, 4, 5 => 5, 4, 3, 2, 1, 0) and amending the test expectations appropriately.

The test fails spectacularly with too many paths being returned by all paths func (the single path return is correct).

I believe that the tests used to store multiple paths in the shortest path tree is incorrect - depending on distance matrix state that has been mutated since, and I cannot find anywhere else that does this. If I could see another implementation or a paper that uses this technique, I would be happier, but at this stage I am thinking the function should not attempt to do this at all.

graph: Graph.NodeList should not demand that returned []Node be newly allocated

In general, gonum packages that are computationally intensive (e.g. mat64, blas, stat, optimize) do not allocate unless necessary. We should not demand that returned []Node from Graph.NodeList are safe to mutate.

There is a potential extension to this; we could modify Graph.NodeList to take a []Node that is slices to len==0 and then appended to. This would further prevent unnecessary allocations.

(\*.*Graph).Degree returns 0 for absent node

I don't believe that the Degree of an absent node can justifiably be returned. This should either panic or return an (n int, ok bool) multiple. Arguments go either way on which is better.

all: semantics of head and tail are reversed cf. the rest of the world

I just noticed this today. From what I can see (this is not specified in the interface definition), graph.Edge.Head() returns the node at the non-pointy end of an edge, while graph.Edge.Tail() returns the node at the pointy end.

This is demonstrated, by the following:

package main

import (
    "fmt"

    "github.com/gonum/graph/concrete"
)

func main() {
    g := concrete.NewDirectedGraph()
    g.AddNode(concrete.Node(0))
    g.AddNode(concrete.Node(1))
    g.AddNode(concrete.Node(2))

    g.AddDirectedEdge(concrete.Edge{H: concrete.Node(0), T: concrete.Node(1)}, 0)
    g.AddDirectedEdge(concrete.Edge{H: concrete.Node(0), T: concrete.Node(2)}, 0)

    fmt.Println(g.Successors(concrete.Node(0)))
}

outputs:

[1 2]

This is the reverse of the normal interpretation.

An arc e = (x, y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x, and x is said to be a direct predecessor of y.

I propose that we use simpler completely unambiguous terminology: From (conventionally tail) and To (conventionally head).

go version: drop 1.3 support

A number of the routines in graph depend on golang.org/x/tools/container/intsets. This has recently just added asm code which means the build breaks on 1.3 because of the textflag.h issue.

Does anyone have any drastic objection to this? The alternative is to vendor a version of intsets with the hack we use elsewhere to keep 1.3 happy.

@gonum/developers

graph: finite graphs should have an Order() int method

Currently finding the order of a graph requires a potentially very expensive call to Graph.NodeList and then taking the length of the returned slice, potentially in some cases then discarding the slice. This should not be necessary.

graph: decide whether we support pseudo graphs or not

At the moment, we do-ish; the interfaces are silent on the behaviour of implementations with respect to self edges and it falls to implementation details (when it's possible it's done). We should either properly handle pseudo graphs or not allow them at all, requiring that an implementation panics when someone says g.AddEdge(concrete.Edge{n, n}, w) for example.

There are obvious costs to handling pseudo-graphs; returning edges would require more space and many of the path finding code would need to find minimum cost edges for each pair of nodes, making much of this code slower.

An alternative is to ban self edges added by AddEdge (probably renamed to SetEdge) as part of the basic mutable graph interfaces, but have another set of interfaces that augment the basic interfaces with methods to handle multiple and self edges - the behaviour of the basic interfaces then would be defined as being implementation dependent. So for example a pseudo graph intended for path finding would return the minimum cost edge when EdgeBetween was called. We would not initially provide any implementations for these graphs except for testing. I suspect there are details to this that I'm missing (mainly around naming and interface conflict/multiplication), but it seems feasible.

The driver for this though should be what use cases there are for justifying doing this.

A* test fails

New A* test against Dijkstra shows incorrect result. See commit 0c533c0 on branch tests.

(Correct) path by Dijkstra is [5 4 2] with path length 21. Path returned by A* is [5 6 3 4 2] with path length 21.

Note [5 6 3 2] is also length 21. That would be a valid answer showing the test should be improved, but [5 6 3 4 2] is incorrect.

Node ID return type int -> uint64

Is it possible to change the return type of Node ID method from int to uint64 ? The size of type int depends on architecture where as uint64 would be more portable.

Side note: Hash algorithms like SipHash return uint64 by default ( https://github.com/dchest/siphash ) I am thinking to use that, if you change the return type.

concrete.Graph edge representation: consider reducing memory load

I have been thinking about ways to halve the amount of memory (and map lookup time) required to store edges in the undirected graph type.

The approach I think is worth examining is to canonicalise edges such that the id of the head is always less or equal to the id of the tail. This requires a simple int comparison and reordering during a number of methods which is cheaper than two map lookups and halves the number of edges that need to be stored. It also has the advantage that the possibility for error edge handling is reduced. I had a quick play with this and the approach broke Dijsktra, so I'm missing something subtle. I'll have another go later.

graph: Determining the order of a graph is too expensive

Currently, the only way to determine the order of a graph is to call len(NodeList()). This is excessively expensive for an operation that fundamentally should not require allocation. I suggest we add an Order() method (Len() would be the idiomatic Go name, but we collide with graph terminilogy here - this is certainly open for discussion though).

concrete: Directed.Edges is incorrect

The function:

func edgesOf(g concrete.Directed) []graph.Edge {
    var e []graph.Edge
    for _, u := range g.Nodes() {
        for _, v := range g.From(u) {
            e = append(e, g.Edge(u, v))
        }
    }
    return e
}

returns a larger set of edges than the Edges method. The set returned by the function above is correct.

graph: Atomize interfaces

At the moment, we've been operating under the conceit that directed/undirected graphs are special cases of one another. We started with the idea that an undirected graph was essentially a directed graph that was symmetric. Later, we inverted this due to necessity (for reasons I don't quite recall), and decided that a directed graph was more or less an undirected graph with edges with an ordered head and tail.

This caused its own problems, for instance, a graph cannot safely implement both directed and undirected mutability, which is a bit silly given that directed graph is a sub-interface of graph.

In addition, Graph dictates that all graphs can provide a slice of all nodes and edges, but this isn't always a fair assumption.

I propose splitting interfaces far more atomically, and having functions only use interfaces specifying which methods they need. For instance, search only requires knowing outgoing edges given a node; a 1 method interface (pro: implemented correctly this means A* can now effortlessly handle multigraphs). Kruskal's requires an undirected edge list.

This will reduce or eliminate the weird smart-switching between interface methods at the beginning of most algorithms, but may increase implementation burden on users who want to build more general graphs. HOWEVER, it will also make it easier to write graphs if you only need a small part of the functionality (like A*).

Reconsider the inclusion of Cost(.*)Graph in Mutable\1Graph interfaces

This breaks composability and makes is necessary for clients who are not interested in costs to implement the Coster interface. A better approach would be to remove those requirements and compose costs into two new interfaces based on Mutable.*Graph (comments elided):

type MutableDirectedGraph interface {
    DirectedGraph
    Mutable

    AddDirectedEdge(e Edge, cost float64)

    RemoveDirectedEdge(Edge)
}

type MutableGraph interface {
    Graph
    Mutable

    AddUndirectedEdge(e Edge, cost float64)

    RemoveUndirectedEdge(Edge)
}

type MutableDirectedCostGraph interface {
    MutableDirectedGraph
    Coster
}

type MutableCostGraph interface {
    MutableGraph
    Coster
}

If cost is important for a search and the caller provides a non-Coster, then a unit cost is subbed in. This only requires a single type assertion at the call.

internal: break package into conceptually related types and functions

At the moment it's a grab bag of things. It could be broken into set, sortutils ordered (picking up some copied types distributed throughout the repo), and linear.

search: ShortestPaths.AllBetween does not cope with zero length cycles

Currently calling AllBetween on a ShortestPaths that was created by FloydWarshall on a graph with zero-weight cycles that are on a shortest path may results in a stack exhaustion. Non-halting is formally what the documentation says should happen in this case, but it is not very useful. In addition it is not clear yet why this does not always happen (it is likely due to node ordering in FloydWarshall).

The following code demonstrates the issue:

package main

import (
    "fmt"

    "github.com/gonum/graph/concrete"
    "github.com/gonum/graph/search"
)

func main() {
    edges := []concrete.WeightedEdge{
        // Add a path from 0->5 of weight 4
        {concrete.Edge{concrete.Node(0), concrete.Node(1)}, 1},
        {concrete.Edge{concrete.Node(1), concrete.Node(2)}, 1},
        {concrete.Edge{concrete.Node(2), concrete.Node(3)}, 1},
        {concrete.Edge{concrete.Node(3), concrete.Node(5)}, 1},

        // Add a zero weight cycle.
        {concrete.Edge{concrete.Node(1), concrete.Node(6)}, -1},
        {concrete.Edge{concrete.Node(6), concrete.Node(1)}, 1},
    }

    g := concrete.NewDirectedGraph()
    for _, e := range edges {
        g.AddDirectedEdge(e, e.Cost)
    }

    pt, ok := search.FloydWarshall(g, nil)
    fmt.Printf("no negative cycles=%t\n", ok)

    fmt.Println("recover 10 paths from 0 to 5:")
    for i := 0; i < 10; i++ {
        fmt.Println(pt.Between(concrete.Node(0), concrete.Node(5)))
    }

    fmt.Println("attempt to recover all paths from 0 to 5:")
    fmt.Println(pt.AllBetween(concrete.Node(0), concrete.Node(5)))
}

e.g. output

$ go run Desktop/zero-cycle.go 
no negative cycles=true
recover 10 paths from 0 to 5:
[0 1 6 1 6 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 6 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 2 3 5] 4 false
[0 1 6 1 6 1 2 3 5] 4 false
attempt to recover all paths from 0 to 5:
fatal error: runtime: out of memory
...

There are two options:

1. Fix the FloydWarshall implementation so that it always returns a ShortestPaths with the non-terminating paths and document that graphs with zero-length cycles have infinitely many shortest paths.
2. Change the behaviour of AllBetween (and probably Between since it is only probabilistically likely to terminate in this case - here FloydWarshall also needs fixing so that we can return that a path is not actually unique since there are infinitely many alternatives) so that zero length cycles are not returned. This entails keeping a []bool of nodes that have been visited and not choosing those for each path being constructed. This exclusion must then be documented.

I think 2 is the better option.

Confirm that unguarded reduction in concrete.Graph.maxID is safe

This line troubles me.

If a caller has deleted a single node then g.maxID may now be less than the current maximum node id. If the caller then adds a node, the id will be taken from the freeMap. Another addition finds the freeMap empty, so in NewNode the returned node is given an id that may be being used.

This needs a test that passes.

On a related note. We need to prohibit negative node ids.

topological sort

Not sure if I just can't find it, but it would be nice to have a topological sort function in here.

graph/all: consider using golang.org/x/tools/container/intsets

When we have some benchmarks we should check the claim at golang.org/x/tools/container/intsets that it is in practice faster than using a map and if it is replace internal.IntSet use.

graph: edge weights should be part of the Edge type

This has been discussed before, but I'm still not convinced that the current approach is correct. The rationale behind not having a weight method on the edge was that the cost/weight function needs to be provided by the graph to allow interface type switching on the graph's capabilities.

I propose that Weighted be an interface (optional on Edge) and weighted graphs type switch on that interface in their cost/weight function (if the Edge is not Weighted then the graph makes up a number for the default unweighted edge).

This removes the need to add a number at the end of the SetEdge methods.

Remove/Add node bug in simple.DirectedGraph

In the implementation of simple.DirectedGraph.RemoveNode() there is a bug that causes NewNodeID() to panic. Here is an example that will cause the panic:

package main

import (
    "math"

    "github.com/gonum/graph/simple"
)

func main() {
    g := NewDirectedGraph(0, math.Inf(1))

    n0 := Node(g.NewNodeID())
    g.AddNode(n0)

    n1 := Node(g.NewNodeID())
    g.AddNode(n1)

    g.RemoveNode(n0)

    n2 := Node(g.NewNodeID())
    g.AddNode(n2)

}

panic: simple: node ID collision: 2

goroutine 1 [running]:
github.com/gonum/graph/simple.(*DirectedGraph).AddNode(0xc820045d20, 0x4a1318, 0xc82000ad90)
    /go/src/github.com/gonum/graph/simple/directed.go:73 +0x1b8

I have a simple pull request to fix this, but if you would want a more robust fix to deal with Node ID wrap around with better performance, let me know.

graph: current API is too focussed on path finding algorithms

Edge weights are described by the name "Cost". This semantically limits the range of ideas that can elegantly be expressed by the API (nearly all the uses I have for graph analysis that have any conception of edge strength have that represent a benefit).

I propose Cost be replaced with Weight, which is more general (weight to bear - cost, and weight of evidence - strength).

path: sort out a sensible way of sharing test cases between dynamic and static path finders

Two options are to 1) move the dynamic functions into path proper or 2) export the test cases from path/internal.