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

Added forest cover function #39

Merged
merged 14 commits into from
Nov 1, 2023
Merged

Conversation

JoeyT1994
Copy link
Contributor

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
Copy link
Contributor Author

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

@mtfishman
Copy link
Member

mtfishman commented Oct 19, 2023

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
Copy link
Member

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
Copy link
Member

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.

src/traversals/dfs.jl Outdated Show resolved Hide resolved
@mtfishman
Copy link
Member

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
Copy link
Contributor Author

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
Copy link
Contributor Author

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
Copy link
Contributor Author

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
Copy link

codecov-commenter commented Oct 24, 2023

Codecov Report

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

❗ 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
Copy link
Contributor Author

JoeyT1994 commented Oct 24, 2023

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
Copy link
Contributor Author

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.

src/traversals/dfs.jl Outdated Show resolved Hide resolved
@mtfishman
Copy link
Member

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
Copy link
Member

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

@JoeyT1994
Copy link
Contributor Author

JoeyT1994 commented Oct 26, 2023

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
Copy link
Member

Yeah makes sense to make them trait functions.

@JoeyT1994
Copy link
Contributor Author

Okay I changed them to traits

@mtfishman
Copy link
Member

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

@mtfishman mtfishman merged commit a40bbdc into ITensor:main Nov 1, 2023
7 of 9 checks passed
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

Successfully merging this pull request may close these issues.

3 participants