Opened 2 years ago

Closed 2 years ago

#28142 closed enhancement (fixed)

Girth of directed graphs

Reported by: jaanos Owned by:
Priority: major Milestone: sage-8.9
Component: graph theory Keywords: fpsac2019
Cc: dcoudert Merged in:
Authors: Janoš Vidali Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 41a135a (Commits, GitHub, GitLab) Commit: 41a135a7bef75e259303731e8869073711fdf00c
Dependencies: Stopgaps:

Status badges

Description (last modified by jaanos)

This ticket adds a BFS-based computation of girth of directed graphs (i.e., length of shortest directed cycle). The existing algorithm, which did not work properly for directed graphs of girth larger than 2, is now moved to a hidden method in graph.py, and the same method in digraph.py now works properly for the directed case. The appropriate method is then called in generic_graph.py after checking some border cases.

Both methods also accept a parameter odd, which, when set to True, will make the methods compute the odd girth of a graph (length of shortest odd cycle). This was not previously available for directed graphs, while for undirected graphs, a method based on the characteristic polynomial was used. This is still available (in both the directed and undirected case) by setting the appropriate algorithm parameter - however, the default is now to use the above BFS-based algorithm. I have run some examples and the characteristic polynomial based method was almost always slower (it was only faster for bipartite graphs, which can be quickly checked), so I decided to set the "bfs" algorithm as default, with the other options available in case there is some class of graphs where it would be advantageous to use them.

Change History (21)

comment:1 Changed 2 years ago by jaanos

  • Branch set to u/jaanos/girth_of_directed_graphs

comment:2 Changed 2 years ago by jaanos

  • Authors set to Janoš Vidali
  • Commit set to 5663f7773fd12387687220c292c19a6190e48bde
  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Type changed from PLEASE CHANGE to enhancement

New commits:

5663f77Properly compute girth for directed graphs

comment:3 Changed 2 years ago by jaanos

  • Status changed from new to needs_info

I will add the doctests in the next commit. Should I also add a _girth_bfs method in generic_graphs.py (which would raise NotImplementedError)?

comment:4 Changed 2 years ago by git

  • Commit changed from 5663f7773fd12387687220c292c19a6190e48bde to 3e7f1da19d1d1c3e9deecf4de5f916c90eaccb35

Branch pushed to git repo; I updated commit sha1. New commits:

3e7f1daBugfixes and doctests

comment:5 Changed 2 years ago by dcoudert

Some quick comments:

  • references must be put in file src/doc/en/reference/references/index.rst. Then you can cite them in the documentation of the methods using [Har62]_ and [Biggs93]_.
  • in input blocks, the correct format is:
    -        - ``odd`` -- whether to compute the odd girth (default: ``False``).
    +        - ``odd`` -- boolean (default: ``False``); whether to compute the odd girth
    
  • in generic_graph.py, why not extending method girth by adding it parameter odd and then call the appropriate method for graph or digraph or bipartite graph or ...
  • Is it possible to add parameter certificate in these methods to return the cycle, if any ?

comment:6 follow-up: Changed 2 years ago by jaanos

Thanks for the feedback! Will fix the references and input.

Regarding the parameter: I was thinking about that, actually. I forgot about BipartiteGraph - I guess the way to go would be to have the algorithm for undirected graphs in generic_graph.py, so it would also work for bipartite graphs.

Regarding the certificate, a cycle would only show that the (odd) girth is at most its length. Would that be OK?

comment:7 in reply to: ↑ 6 Changed 2 years ago by dcoudert

Regarding the parameter: I was thinking about that, actually. I forgot about BipartiteGraph - I guess the way to go would be to have the algorithm for undirected graphs in generic_graph.py, so it would also work for bipartite graphs.

That would be nice. In case, we also have a specific class for bipartite graphs in bipartitie_graph.py

Regarding the certificate, a cycle would only show that the (odd) girth is at most its length. Would that be OK?

If the method only returns an upper bound, then yes, as long as it is clearly documented. Otherwise, you can simply add a todo block letting this task for future work.

comment:8 Changed 2 years ago by git

  • Commit changed from 3e7f1da19d1d1c3e9deecf4de5f916c90eaccb35 to 997bed97aab940bf5d6c0f1ba91e9f2df5b7580c

Branch pushed to git repo; I updated commit sha1. New commits:

f2f1713Move _girth_bfs to generic_graph.py to support BipartiteGraph
45e50b5Put references in reference list, docstring fixes
997bed9Add option to return certificate

comment:9 Changed 2 years ago by jaanos

  • Status changed from needs_info to needs_review

OK, I've moved the main algorithm to generic_graph.py, fixed the references, and added certificates. I'm not sure any more that having a parameter odd on the girth method would be good - it is there for _girth_bfs since the method is used for both, but as concepts (and therefore public methods) I think it's best to keep them separate.

comment:10 Changed 2 years ago by jaanos

  • Keywords fpsac2019 added

comment:11 Changed 2 years ago by dcoudert

  • Branch changed from u/jaanos/girth_of_directed_graphs to public/graphs/28142_odd_girth
  • Commit changed from 997bed97aab940bf5d6c0f1ba91e9f2df5b7580c to 301c12a4e1f0e1086873126b67e7f99c73a29332
  • Reviewers set to David Coudert

I took the liberty to edit your code and push it in a new branch (in public/ so that you can modify it as well).

I did various small corrections and added several doctests (for instance for small cases).

Please check that every think is fine and that the documentation builds properly and displays nicely.


New commits:

f00ebbetrac #28142: Merged with 8.9.beta2
cf5f636trac #28142: improve references
bd2de11trac #28142: minor edit in digraph.py
6562614trac #28142: review edit in generic_graph.py
301c12atrac #28142: review edit in generic_graph.py (2)

comment:12 Changed 2 years ago by git

  • Commit changed from 301c12a4e1f0e1086873126b67e7f99c73a29332 to 03b58397b97638062f5c0ba83b04ff61082ce73d

Branch pushed to git repo; I updated commit sha1. New commits:

03b5839"Compute" -> "Return" in method index

comment:13 Changed 2 years ago by jaanos

  • Cc dcoudert added

Thanks, everything looks fine to me! I have just changed two words in the Graph method index.

comment:14 Changed 2 years ago by dcoudert

  • Status changed from needs_review to needs_work

There is a failing doctest reported by the patchbot

sage -t --long src/sage/categories/category.py
**********************************************************************
File "src/sage/categories/category.py", line 806, in sage.categories.category.Category.is_abelian.category_graph
Failed example:
    G.girth()
Expected:
    4
Got:
    +Infinity

comment:15 Changed 2 years ago by git

  • Commit changed from 03b58397b97638062f5c0ba83b04ff61082ce73d to 71c7dce2afb1696899c4f3039727ff505a52883f

Branch pushed to git repo; I updated commit sha1. New commits:

71c7dceFix failing doctest

comment:16 Changed 2 years ago by jaanos

  • Status changed from needs_work to needs_review

The doctest generated a directed acyclic graph, so its girth is now correctly reported as infinite. I have changed the doctest to compute the girth of its underlying undirected graph.

comment:17 Changed 2 years ago by dcoudert

You should add a comment explaining that the girth of a DAG is infinite, and that the girth of the underlying undirected graph is 4 in this case.

comment:18 Changed 2 years ago by git

  • Commit changed from 71c7dce2afb1696899c4f3039727ff505a52883f to 41a135a7bef75e259303731e8869073711fdf00c

Branch pushed to git repo; I updated commit sha1. New commits:

41a135aAdd explanation for the girth of the category DAG

comment:19 Changed 2 years ago by jaanos

OK, done. I have also fixed the indenting of the category_graph method.

comment:20 Changed 2 years ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM. Thanks.

comment:21 Changed 2 years ago by vbraun

  • Branch changed from public/graphs/28142_odd_girth to 41a135a7bef75e259303731e8869073711fdf00c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.