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

Provide non-normalized directed laplacian matrix calculation #7148

Closed
dschult opened this issue Dec 9, 2023 · 1 comment
Closed

Provide non-normalized directed laplacian matrix calculation #7148

dschult opened this issue Dec 9, 2023 · 1 comment

Comments

@dschult
Copy link
Member

dschult commented Dec 9, 2023

When we created the directed versions of the laplacian_matrix function, we included the two normalized matrices, but we didn't include the non-normalized laplacian matrix. See #3297, #2404, #741
At the time of #741, the laplacian_matrix worked for directed and undirected graphs and returned the non-normalized version of the matrix. (A single stream of code can be used for either Graph or DiGraph in the non-normalized case.) The restriction to only undirected came later #833 and without discussion about the distinction between normalized and non-normalized. The recent activity about total_spanning_tree_weight in #7100 and number_of_spanning_trees in #7065 shows that the original non-normalized version of the laplacian matrix works for directed and is needed for calculations like the number of spanning trees.

I propose that we use the existing code for laplacian_matrix to return the matrix for either undirected or directed graphs. The doc_string should include "See Also" pointers to the directed_laplacian_matrix, directed_combinatorial_laplacian_matrix, and normalized_laplacian_matrix. In the doc_strings for those functions (or maybe in the module level doc_string, or maybe both: We should describe how all these relate. (The non-normalized version is produced by the main function, and normalized versions for undirected and the two normalizations for the directed case are provided by the other functions.) We should also point out that another possible non-normalized directed version would have the in-degree of each node on the main diagonal instead of the out-degree. That can be obtained by applying the function to G.reverse(copy=False) instead of G. Perhaps an example would be useful to include showing this.

This issue is proposing to do one change for code, add some tests, update docs:

  • remove the not_implemented_for("directed") decorator on laplacian_matrix
  • add some tests for laplacian_matrix as applied to directed graphs
  • change the docs s described above

This is perhaps more involved than some "good first issue" items, but only in that it has more steps. I think each item is "straight-forward" (which in many math classes means "possibly difficult but using known methods"). So I've put the good-first-issue label on here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Development

No branches or pull requests

2 participants