Added forest cover function

[JoeyT1994]

This PR adds functionality for creating a forest cover of a graph g (see wiki page ). Specifically, a forest cover is a set of forests which collectively cover all the edges in g. In our case, each forest in the forest cover covers all vertices in g (although this is not strictly necessary).

Testing is included and the number of forests appears fairly lightweight. Whilst our algorithm does not construct the minimum number of forests it appears competitive and reasonable.

[JoeyT1994]

Okay I am confused. These tests are all passing on my local machine? Including testing on Ubuntu w/ Julia 1.7.2?

[mtfishman]

Do the tests rely on some randomness? That can change between Julia versions.

For example, I see one test that is comparing sets of vertices and they are the same up to a reordering, so to make that more robust you could use issetequal.

[mtfishman]

Does this cover edges in both directions? Or would that be handled through the input, i.e. inputting a directed graph that has both edge directions?

[mtfishman]

My main suggestion would be choosing an ordering for the vertices, since that appears to be arbitrary with the current implementation.

What about sorting from largest to smallest eccentricity (https://juliagraphs.org/Graphs.jl/dev/algorithms/distance/), with the intuition that you move inward from the periphery of the graph? Unfortunately it seems like eccentricity is broken for NamedGraphs but that should be easy to fix.

[mtfishman]

Here's an example of sorting vertices from largest to smallest eccentricity:

julia> g = named_grid((4, 4));

julia> sort(Dictionary(vertices(g), eccentricity(g.parent_graph)); rev=true)
16-element Dictionary{Tuple{Int64, Int64}, Int64}
 (1, 1) │ 6
 (4, 1) │ 6
 (1, 4) │ 6
 (4, 4) │ 6
 (2, 1) │ 5
 (3, 1) │ 5
 (1, 2) │ 5
 (4, 2) │ 5
 (1, 3) │ 5
 (4, 3) │ 5
 (2, 4) │ 5
 (3, 4) │ 5
 (2, 2) │ 4
 (3, 2) │ 4
 (2, 3) │ 4
 (3, 3) │ 4

which seems like a reasonable ordering. For grids that looks like it could give a minimal number of spanning trees.

[JoeyT1994]

Yeah there is no randomness in the tests? It was just picking the first vertex in the list of the graph's vertices to do a spanning tree over. Switching to eccentricity sounds reasonable. On my end eccentricities(g::NamedGraph) seems to work. The failing test seems to come from test_namedgraph.jl as opposed to the new ones I introduced?

[JoeyT1994]

This doesn't cover edges in both directions and the arboricity is not really defined for Directed graphs. Hence I have added an assertion that the graph is undirected. I think if the user really wanted to cover a directed graph they could split it into two undirected graphs and pass them to the function and concatenate the result.

[JoeyT1994]

Okay this is breaking because of Graphs.jl changing from 1.8.0 to 1.9.0 (https://github.com/JuliaGraphs/Graphs.jl/releases/tag/v1.9.0). Those changes have broken the relevant tests (as opposed to anything in this PR), you can see that they directly effect functions like topological_sort_by_dfs in the change list.

[codecov-commenter]

Codecov Report

Merging #39 (888e80b) into main (c4170a3) will increase coverage by 1.94%. The diff coverage is 100.00%.

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

@@            Coverage Diff             @@
##             main      #39      +/-   ##
==========================================
+ Coverage   80.92%   82.86%   +1.94%     
==========================================
  Files          21       22       +1     
  Lines         907      934      +27     
==========================================
+ Hits          734      774      +40     
+ Misses        173      160      -13     

Files	Coverage Δ
src/NamedGraphs.jl	100.00% <ø> (ø)
src/traversals/trees_and_forests.jl	100.00% <100.00%> (ø)

... and 3 files with indirect coverage changes

[JoeyT1994]

Okay these are all passing now as I made the failing tests just test they get a correct solution as opposed to a specific solution with specific orderings etc... which can change depending on algorithmic implementations. These tests will now pass for both Graphs 1.8 and Graphs 1.9

[JoeyT1994]

Okay I updated the interface a bit like we discussed. Although I didn't do it in terms of thealgorithm type because is that not an ITensor feature which we don't want to import here? Unless I am missing something.

[mtfishman]

Okay I updated the interface a bit like we discussed. Although I didn't do it in terms of thealgorithm type because is that not an ITensor feature which we don't want to import here? Unless I am missing something.

Good point.

Instead we could just define types, for example:

abstract type SpanningTreeAlgorithm end

struct BFS <: SpanningTreeAlgorithm end
struct RandomBFS <: SpanningTreeAlgorithm end
struct DFS <: SpanningTreeAlgorithm end

default_spanning_tree_alg() = BFS()
spanning_tree(g::AbstractNamedGraph, src) = spanning_tree(g, src, default_spanning_tree_alg())
spanning_tree(g::AbstractNamedGraph, alg::SpanningTreeAlgorithm=default_spanning_tree_alg()) = spanning_tree(g, default_root_vertex(), alg)

# Implementations
spanning_tree(g::AbstractNamedGraph, src, ::BFS) = undirected_graph(bfs_tree(g, src))

[mtfishman]

See https://github.com/JuliaGraphs/Graphs.jl/blob/v1.9.0/src/Experimental/Traversals/bfs.jl for some inspiration for the proposed interface.

[JoeyT1994]

Okay I have done it by defining types as you suggested. Let me know what you think about that? I put the algorithm as the first argument and left the root_vertex as keyword.

Also seeming as I am asserting the graph is not directed when calling spanning_tree should I make them trait functions instead?

[mtfishman]

Yeah makes sense to make them trait functions.

[JoeyT1994]

Okay I changed them to traits

[mtfishman]

Looks like it just needs a formatting fix and then good to merge. Thanks for sticking with the comments!