Opened 14 months ago

Closed 14 months ago

Last modified 14 months ago

#26428 closed enhancement (fixed)

improve is_weakly_chordal

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.5
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 66a1ed9 (Commits) Commit: 66a1ed9a6521c26e3354b53ca5aaa9bb2f1e4c59
Dependencies: Stopgaps:

Description (last modified by dcoudert)

This ticket do:

  • Remove recursion in methods is_long_hole_free and is_long_antihole_free
  • Avoid modifying the input graph
  • Cythonize parts of the code

Change History (8)

comment:1 Changed 14 months ago by dcoudert

  • Branch set to public/26428_weakly_chordal
  • Commit set to f3fc0614c1311e4437d83766156ff077d89a2ac3
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

f3fc061trac #26428: multiple improvements

comment:2 Changed 14 months ago by git

  • Commit changed from f3fc0614c1311e4437d83766156ff077d89a2ac3 to 1537dfd70f0aab5fbc2a8a34c99325e5aa2a1581

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

1537dfdtrac #26428: remove useless imports

comment:3 Changed 14 months ago by tscrim

I think you should move process out as a separate cdef inline function and pass the data you need. It is likely equivalent to a Python function call, and since it is in the heart of the algorithm, it should be made to be called quickly (the inline hopefully will make it avoid the function call altogether).

I was going to say the same thing for the dist, but since that is processing on the way out, it is only done once and should not contribute much time.

A few quick notes on style. For pointers, the * is better next to the type, e.g., int* as it makes it look less like multiplication. Also lambda X : foo -> lambda X: foo.

Otherwise LGTM. Have you run some timings?

comment:4 Changed 14 months ago by git

  • Commit changed from 1537dfd70f0aab5fbc2a8a34c99325e5aa2a1581 to 66a1ed9a6521c26e3354b53ca5aaa9bb2f1e4c59

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

66a1ed9trac #26428: cdef methods process

comment:5 follow-up: Changed 14 months ago by dcoudert

I have cdef the methods process and perform other suggestions.

I have not done clear timings. It is now faster on large cliques for instance, but very similar for graphs like the Petersen graph. My main motivation was not timing but 1) no sorting on original vertex labels, 2) no modification of the input graph (very bad), and 3) avoid recursive calls.

I also tried to use the has_edge method of short_digraph to avoid copying the graph in a n^2 length bitset (dense_graph), but it was slightly slower. This is certainly something to consider if we have very large sparse graphs (i.e., when memory matters).

comment:6 in reply to: ↑ 5 Changed 14 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Replying to dcoudert:

I have cdef the methods process and perform other suggestions.

Thank you for doing that. I didn't realize process needed so many of the local variables.

I have not done clear timings. It is now faster on large cliques for instance, but very similar for graphs like the Petersen graph. My main motivation was not timing but 1) no sorting on original vertex labels, 2) no modification of the input graph (very bad), and 3) avoid recursive calls.

Speed gains is a consequence of all of those things. _

I also tried to use the has_edge method of short_digraph to avoid copying the graph in a n^2 length bitset (dense_graph), but it was slightly slower. This is certainly something to consider if we have very large sparse graphs (i.e., when memory matters).

It is good to care about these things as well. Sometimes we do have to sacrifice speed so that sparse graphs will work well too. We can also potentially try to do things differently for each those cases, but I think what you have done here is more than enough.

comment:7 Changed 14 months ago by vbraun

  • Branch changed from public/26428_weakly_chordal to 66a1ed9a6521c26e3354b53ca5aaa9bb2f1e4c59
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:8 Changed 14 months ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.