Opened 5 years ago

Closed 12 months ago

Last modified 9 months ago

#21942 closed enhancement (fixed)

Cheeger constant(s) of graphs

Reported by: pelegm Owned by: pelegm
Priority: major Milestone: sage-9.2
Component: graph theory Keywords: cheeger, MathExp2018
Cc: vdelecroix, jepperlein, slelievre Merged in:
Authors: Vincent Delecroix, David Coudert Reviewers: Peleg Michaeli, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 8389196 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by vdelecroix)

This ticket adds three methods to graphs to compute three variations of the Cheeger constant:

  • the "transition isoperimetric number" (cheeger_constant)
  • the edge isoperimetric number (edge_isoperimetric_number)
  • the vertex isoperimetric number or magnifying constant (vertex_isoperimetric_number)

Note that the implemented Cheeger constant is also the conductance of the simple random walk on the graph.

Change History (95)

comment:1 Changed 5 years ago by pelegm

  • Branch set to u/pelegm/cheeger
  • Commit set to 05ab2786fdb220852888e0619a31950e55f84ad7
  • Owner changed from (none) to pelegm

New commits:

05ab278Cheeger constant (#21942)

comment:2 Changed 5 years ago by git

  • Commit changed from 05ab2786fdb220852888e0619a31950e55f84ad7 to 0cb6192693a25a4e39ee596f1e8a8fe9935213a3

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

0cb6192Implementing edge isoperimetric number (#21942)

comment:3 Changed 5 years ago by git

  • Commit changed from 0cb6192693a25a4e39ee596f1e8a8fe9935213a3 to bbe6ecff8244507164515aca053123126efd0879

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

dd908c0Fixing some documentation bugs #21942
bbe6ecfVertex isoperimetric number #21942

comment:4 Changed 5 years ago by pelegm

  • Status changed from new to needs_review
  • Summary changed from Cheeger constant to Cheeger constant(s)

comment:5 Changed 5 years ago by pelegm

Will rebase to develop.

comment:6 Changed 5 years ago by pelegm

  • Cc vdelecroix added
  • Status changed from needs_review to needs_work

@vdelecroix, perhaps we can work on this together on some notebook on the cloud or somewhere else?

comment:7 Changed 5 years ago by jepperlein

  • Cc jepperlein added

comment:8 Changed 5 years ago by jmantysalo

I know nothing about those functions. However, two general notes:

  • One-sentence descriptions will be used in the toc and they should really be just one sentence. It is kind of dull to have "Return the edge-isoperimetric number of a graph." when the name is edge_isoperimetric_number(), but there is no good alternative. (When there is no real one-line description like for example size() has.)
  • Please test for empty graphs. See #21741 for bugs we already have had.

comment:9 Changed 5 years ago by pelegm

Thanks for the feedback. I am currently testing a better algorithm, based on gray codes. I will also modify the docstrings appropriately, and test/fix the method for empty graphs (and, in general, for graphs with no edges).

comment:10 Changed 5 years ago by pelegm

There is no consensus about the definition of Cheeger constants for the empty graph and the graph with 1 vertex. I suggest that we will raise an exception if the graph is empty, and return infinity if the graph contains a single vertex (so that usual lower bounds on the mixing time of the random walk on the graph will not fail).

The Cheeger constant of a disconnected graph is 0. I should add that as a heuristic at the beginning of each of the methods.

comment:11 Changed 5 years ago by dcoudert

You could do the following to reduce overall computation time:

for k in range(1, self.order()//2):
    for s in Subsets(self.vertices(), k):
         ....

and of course start methods testing the trivial cases.

comment:12 Changed 5 years ago by vdelecroix

I strongly believe that the best way to go is a C backtracker implemented on sparse C graphs. It will be at least 100x faster. With the current code it is not even possible to make computation with graphs with 20 vertices.

comment:13 Changed 5 years ago by pelegm

You could do the following to reduce overall computation time:

Well, this will not do for the Cheeger constant, but might help the isoperimetric numbers.

I strongly believe that the best way to go is a C backtracker implemented on sparse C graphs. It will be at least 100x faster. With the current code it is not even possible to make computation with graphs with 20 vertices.

You are right: it is very slow. However, I must say that I have no idea how to implement stuff in C. About the backtracker you've offered: do you think that we should simply use a gray code which traverses the entire lattice, or should we really think of something smarter that traverses (mostly) only the relevant subsets? This is probably just a matter of a X2 speed factor, I believe (probably even much less).

comment:14 Changed 5 years ago by vdelecroix

Let me try it now.

comment:15 Changed 5 years ago by git

  • Commit changed from bbe6ecff8244507164515aca053123126efd0879 to 4f86191169e3c732292af2bd4356bc4ff097b8fd

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1988a75Cheeger constant (#21942)
6214e44Implementing edge isoperimetric number (#21942)
94f8a45Fixing some documentation bugs #21942
f07babfVertex isoperimetric number #21942
4f86191Check the cases empty graph and single vertex WIP

comment:16 Changed 5 years ago by pelegm

In the meanwhile, I have rebased to 7.5beta4 and added some heuristics.

comment:17 Changed 5 years ago by git

  • Commit changed from 4f86191169e3c732292af2bd4356bc4ff097b8fd to a06c7dee8fd4d072921a5f9e09e06b3b5da73a08

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

a06c7deBetter docstrings & aliases, references moved

comment:18 follow-up: Changed 5 years ago by pelegm

I am considering changing the doc index from Algorithmically hard stuff to Expansion properties. What do you think?

comment:19 in reply to: ↑ 18 Changed 5 years ago by jmantysalo

Replying to pelegm:

I am considering changing the doc index from Algorithmically hard stuff to Expansion properties. What do you think?

Whole idea of Algorithmically hard stuff as a TOC headear is odd. To compare, posets have Properties of the poset, even when height is trivial, width is harder but polynomial and dimension is proven to not be in P.

So yes, please do that.

comment:20 Changed 5 years ago by vdelecroix

I push a C implementation at u/vdelecroix/cheeger which seems to coincide with the one here ;-)

sage: from sage.graphs.isoperimetric_inequalities import cheeger
sage: G = graphs.CubeGraph(4)
sage: %time G.cheeger_constant()
CPU times: user 4.12 s, sys: 52 ms, total: 4.18 s
Wall time: 4.1 s
1/4
sage: %time cheeger(G)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.97 ms
1/4

comment:21 Changed 5 years ago by vdelecroix

but not all ;-(

sage: G = graphs.FibonacciTree(6)
sage: %time G.cheeger_constant()
CPU times: user 1min 3s, sys: 28 ms, total: 1min 3s
Wall time: 1min 3s
1/15
sage: %time cheeger(G)
CPU times: user 16 ms, sys: 0 ns, total: 16 ms
Wall time: 14.5 ms
1/13

I can not work on it right now. I will debug later.

comment:22 Changed 5 years ago by pelegm

I will verify my algorithm for the Fibonacci tree, and if it looks fine I will have a look at your code. Thanks!

comment:23 Changed 5 years ago by vdelecroix

I believe that mine is wrong. Anyway it is worth to look at the code. In particular are there situations were we can perform cheap branch cut?

comment:24 Changed 5 years ago by pelegm

Well, I guess that at least for trees the algorithm can be vastly improved.

comment:25 Changed 5 years ago by pelegm

This paper: http://ac.els-cdn.com/0095895689900294/1-s2.0-0095895689900294-main.pdf?_tid=c92aa55e-b880-11e6-a64e-00000aab0f02&acdnat=1480677575_44a9c4d6e1d9a6be9b2770c5d14f7ecf claims there is a linear algorithm for calculating the edge isoperimetric number of trees. It is a corollary of a more general statement, according to which for every connected graph there exists a partition of its vertex set to X and Y such that the subgraphs induced by these sets are both connected and the (edge) isoperimetric number equals |E(X,Y)|/min{|X|,|Y|}.

comment:26 Changed 5 years ago by vdelecroix

Indeed, if we can restrict to connected X and Y in the parition then it is much better! I was not expecting something that strong. However I do not see linearity coming in. There are many partitions X,Y of the vertices so that both induced graphs are connected.

comment:27 Changed 5 years ago by vdelecroix

The algorithm works in general and is linear on trees!

comment:28 Changed 5 years ago by pelegm

I think the following algorithm works for trees:

https://github.com/pelegm/iso

comment:29 Changed 5 years ago by pelegm

The algorithm now also finds Cheeger constant (and not only edge isoperimetric number) of trees.

comment:30 Changed 5 years ago by git

  • Commit changed from a06c7dee8fd4d072921a5f9e09e06b3b5da73a08 to 4e097b7e2870b56dd3ad3ad8e790074c8b51ecdc

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

1c87b03Added a relevant reference
4e097b7Doc index - expansion properties

comment:31 Changed 5 years ago by vdelecroix

1) You should test the case with 1 vertex.

2) I fixed the backtracker in C. It is still available at u/vdelecroix/cheeger. It would be easy to adapt to the other constants.

comment:32 Changed 4 years ago by slelievre

  • Cc slelievre added

comment:33 Changed 3 years ago by vdelecroix

  • Branch changed from u/pelegm/cheeger to u/vdelecroix/21942
  • Commit changed from 4e097b7e2870b56dd3ad3ad8e790074c8b51ecdc to 42b83fb86a93a97cb25d83dcdccc9643b0208591
  • Milestone changed from sage-7.5 to sage-8.3

rebased on 8.3.beta3


New commits:

22bf38cCheeger constant (#21942)
42b83fbC backtracker for Cheeger constant
Last edited 3 years ago by vdelecroix (previous) (diff)

comment:34 Changed 3 years ago by vdelecroix

TODO:

  • implement the backtracker for the 3 versions
  • use branch and bound (ie cut branches)

comment:35 Changed 3 years ago by git

  • Commit changed from 42b83fb86a93a97cb25d83dcdccc9643b0208591 to 8e9f2ee1d7e60a4ec02caad2672f70b4fda846c8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8e9f2eeC backtracker for Cheeger constant

comment:36 Changed 3 years ago by git

  • Commit changed from 8e9f2ee1d7e60a4ec02caad2672f70b4fda846c8 to 8484a373b28c8b0abdc4ed95ef307dd34d57659d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8484a3721942: Cheeger constant

comment:37 Changed 3 years ago by vdelecroix

  • Authors changed from Peleg Michaeli to Vincent Delecroix
  • Keywords MathExp2018 added; isoperimetric random walk days79 removed
  • Status changed from needs_work to needs_review

comment:38 Changed 3 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from Cheeger constant(s) to Cheeger constant(s) of graphs

comment:39 follow-up: Changed 3 years ago by pelegm

Thanks for all your work on this!

The code looks fine, testing a couple of cases on my machine works great, however, I cannot build the docs, but it seems like the issue is not with your new code (I get [graphs ] OSError: [graphs ] /media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage/combinat/designs/incidence_structures.py:docstring of sage.combinat.designs.incidence_structures.IncidenceStructure.is_generalized_quadrangle:3: WARNING: citation not found: BH12).

Would you call it a positive review?

comment:40 in reply to: ↑ 39 Changed 3 years ago by vdelecroix

Replying to pelegm:

The code looks fine, testing a couple of cases on my machine works great, however, I cannot build the docs, but it seems like the issue is not with your new code (I get [graphs ] OSError: [graphs ] /media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage/combinat/designs/incidence_structures.py:docstring of sage.combinat.designs.incidence_structures.IncidenceStructure.is_generalized_quadrangle:3: WARNING: citation not found: BH12).

It might be something on your computer. It looks fine with the patchbot as well as on my computer. Did you do a make doc-clean before building the doc?

comment:41 Changed 3 years ago by pelegm

This is how it looks like:

peleg@etti:develop:~/sage$ git fetch trac u/vdelecroix/21942
From git://trac.sagemath.org/sage
 * branch                  u/vdelecroix/21942 -> FETCH_HEAD
peleg@etti:develop:~/sage$ git checkout -b 21942 FETCH_HEAD 
Switched to a new branch '21942'
peleg@etti:21942:~/sage$ make doc-clean

...

Sage build/upgrade complete!
peleg@etti:21942:~/sage$ sage --docbuild reference/graphs html

...

[graphs   ] /media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage/combinat/designs/incidence_structures.py:docstring of sage.combinat.designs.incidence_structures.IncidenceStructure.is_generalized_quadrangle:3: WARNING: citation not found: BH12

...

[graphs   ] WARNING: Error building the documentation.
[graphs   ] Traceback (most recent call last):
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main
[graphs   ]     "__main__", fname, loader, pkg_name)
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/runpy.py", line 72, in _run_code
[graphs   ]     exec code in run_globals
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[graphs   ]     main()
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1713, in main
[graphs   ]     builder()
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 749, in _wrapper
[graphs   ]     getattr(DocBuilder, build_type)(self, *args, **kwds)
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 130, in f
[graphs   ]     runsphinx()
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 276, in runsphinx
[graphs   ]     sys.stderr.raise_errors()
[graphs   ]   File "/media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 216, in raise_errors
[graphs   ]     raise OSError(self._error)
[graphs   ] OSError: [graphs   ] /media/peleg/peleg/sage/local/lib/python2.7/site-packages/sage/combinat/designs/incidence_structures.py:docstring of sage.combinat.designs.incidence_structures.IncidenceStructure.is_generalized_quadrangle:3: WARNING: citation not found: BH12

comment:42 Changed 3 years ago by vdelecroix

After make doc-clean you should be using make doc.

comment:43 Changed 3 years ago by pelegm

Works, thanks (took 2.5 hours, though...).

Some minor suggestions:

  • In the cheeger constant docs, I'd replace S(X) with Vol(X) (it's a more common notation)
  • I'd add "SEE ALSO" sections from each of the isoperimetric constants to the others.

Other than that, everything looks great. You may switch to positive review after you apply the suggestions, or if you decide not to apply them.

comment:44 Changed 3 years ago by git

  • Commit changed from 8484a373b28c8b0abdc4ed95ef307dd34d57659d to 10c362ea66dfa6d50e3b7b341e09fd14db71afb7

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

10c362e21942: better documentation

comment:45 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Done!

comment:46 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name?

comment:47 Changed 3 years ago by vdelecroix

  • Reviewers set to Peleg Michaeli
  • Status changed from needs_work to positive_review

Sorry

comment:48 Changed 3 years ago by pelegm

Hi, I apologize for yet another late response, but just wanted to ask: for graphs without edges (and at least 2 vertices) you set the Cheeger constant to be 1.

It is correct that the constant is not well defined for graphs without edges, but still I would maybe set it to be 0, to be consistent with the general idea that larger Cheeger constant means higher connectivity, and the specific idea that non-connected graphs have Cheeger constant 0.

In fact, if you agree with this then we may add a quick heuristic at the beginning of the method, which checks whether the graph is connected, and returns 0 otherwise.

comment:49 Changed 3 years ago by vdelecroix

  • Status changed from positive_review to needs_work

comment:50 Changed 3 years ago by dcoudert

I also agree that you should test that the input graph is connected.

Some remarks:

  • Why not cythonizing method vertex_isoperimetric_number ?
  • in file index.rst, I think that the first initial of a ref needs a \, like in .. [ADKF1970] \V. Arlazarov
  • At the top of file isoperimetric_inequalities.pyx, you should add some words on the kind of methods that are in this file.
  • in graph.py, method vertex_isoperimetric_number: and the sum is taken over the subsets -> and the minimum is taken over the subsets
  • in method cheeger_constant, please add definition of \partial X
  • similarly, in edge_isoperimetric_number, please define \partial S

comment:51 Changed 3 years ago by dcoudert

from sage.rings import infinity -> from sage.rings.infinity import Infinity or from sage.rings.infinity import infinity, I don't know which is best.

comment:52 Changed 3 years ago by dcoudert

For vertex_isoperimetric_number, it is not realistic to try to compute this value for large graphs. For up to 31 vertices, you can do in Cython:

from sage.graphs.graph_decompositions.fast_digraph cimport FastDigraph, compute_out_neighborhood_cardinality, popcount32
from sage.rings.integer cimport Integer

def vertex_isoperimetric_number_fast(self):
    """
    """
    cdef FastDigraph FG = FastDigraph(self)

    cdef int card, boundary, S
    cdef int mc = FG.n // 2
    cdef int p = FG.n
    cdef int q = 0
    
    for S in range(1, 2**FG.n):
        card = popcount32(S)
        if card <= mc:
            boundary = compute_out_neighborhood_cardinality(FG, S)
            if boundary * q < p * card:
                p = boundary
                q = card

    return Integer(p) / Integer(q)

it iterates over all the non-empty subsets of vertices. popcount32(S) counts the number of 1's and so of vertices in the current subset S, and compute_out_neighborhood_cardinality computes the number of vertices in N(S)\S.

sage: %time vertex_isoperimetric_number(G) # your method
CPU times: user 4.36 ms, sys: 1.76 ms, total: 6.13 ms
Wall time: 9.11 ms
3/2
sage: G = graphs.CompleteGraph(5)
sage: %time vertex_isoperimetric_number_fast(G)
CPU times: user 83 µs, sys: 5 µs, total: 88 µs
Wall time: 88.9 µs
3/2

sage: G = graphs.CycleGraph(10)
sage: %time vertex_isoperimetric_number_fast(G)
CPU times: user 114 µs, sys: 17 µs, total: 131 µs
Wall time: 117 µs
2/5
sage: G = graphs.CycleGraph(20)
sage: %time vertex_isoperimetric_number_fast(G)
CPU times: user 34.7 ms, sys: 90 µs, total: 34.8 ms
Wall time: 34.8 ms
1/5
sage: G = graphs.CycleGraph(30)
sage: %time vertex_isoperimetric_number_fast(G)
CPU times: user 33.3 s, sys: 121 ms, total: 33.4 s
Wall time: 33.9 s
2/15

We can certainly do something similar for the other methods. We just need a smart way to compute |\partial X| / |Vol(X)| and |E(X)| (which is not properly defined in the method) and |\partial S| / |S|.

It is of course possible to add a parameter k to compute the value only over all subsets of order k (see https://en.wikipedia.org/wiki/Isoperimetric_inequality)

comment:53 follow-up: Changed 3 years ago by vdelecroix

I am not 100% convinced by FastDigraph:

  • why FastDiagraph is not merged with base/static_dense_graph? Both uses a bitset matrix and binary matrices are not limited to 32 vertices. Of course, if you have one limb you can perform some optimization but it would be nicer to have the same API (and use the same directory).
  • Using int might not be the best option. The library stdint proposes a uint_fast32_t that is exactly what you want here.
  • Many processors offer a popcount that popcount32 is just ignoring.

comment:54 Changed 3 years ago by vdelecroix

With dense representation and bit operations one can indeed remove the inner loops from the already cythonized cheeger_constant and edge_isoperimetric_number. On the other hand, these methods

  • perform incremental step in the construction of the subsets (so that updating volume/boundary is cheap)
  • do not go through all subsets but only through the one relevant to the definition (this is only a factor x2)

comment:55 Changed 3 years ago by git

  • Commit changed from 10c362ea66dfa6d50e3b7b341e09fd14db71afb7 to b981a8dc9e40577e326c1008ad073370ca192e48

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

36807eb21942: Cheeger constant
67881a321942: better documentation
b981a8d21942: cythonize vertex_isoperimetric_number

comment:56 Changed 3 years ago by vdelecroix

  • Status changed from needs_work to needs_review

rebased on 8.3.beta4 + extra commit taking care of some of the remarks of David.

comment:57 in reply to: ↑ 53 Changed 3 years ago by dcoudert

I'm not claiming that FastDigraph is perfect. It was useful for implementing vertex separation and cutwidth. It can certainly be cleaned/improved/etc. (e.g., using __builtin_popcount and uint_fast32_t). However, for such algorithms, the extra cost of using bitsets is not justified since we can hardly go above 32 nodes: huge computation time and memory usage.
Here, if you think it is possible to compute the vertex_isoperimetric_number on larger graphs, then you can use binary_matrix. Another idea could be to use short_digraph and the same structure as for other methods, and maintain the vertices in the boundary (e.g., use an array to store the number of edges from S to each vertex outside S, and increase/decrease vol each time a cell becomes non-zero/zero).

I did some tests using static_dense_graph, and so binary_matrix, for cheeger_constant and edge_isoperimetric_number. My code is slightly faster for dense graphs but slower for sparse graphs. Not so interesting here.

There are a small improvements you can do:

  • to update vol in cheeger_constant: use an array to store the degree of vertices, and then, instead of doing vol += 1 inside the for loop, do vol += degree[u] outside.
  • add definition of E(S).
  • have you tried maintaining the value E(S) ?
  • you use a bitset to maintain the set of vertices in the subgraph. Wouldn't it be faster to use an array of bint ? You don't use bitset operations here, and memory usage is clearly not an issue.

comment:58 Changed 3 years ago by git

  • Commit changed from b981a8dc9e40577e326c1008ad073370ca192e48 to 8bcb4973ccf2365b8aba3d8f829f366b5d1990ec

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

8bcb49721942: typo in doc

comment:59 Changed 3 years ago by vdelecroix

I agree with your suggestions. Though, a much more needed improvement would be to be able to iterate through subsets S of vertices with S and V \ S connected.

comment:60 Changed 3 years ago by git

  • Commit changed from 8bcb4973ccf2365b8aba3d8f829f366b5d1990ec to 83f5c802f79d518f5158ea1d4876566d7ee2beb3

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

83f5c8021942: small optimization

comment:61 Changed 3 years ago by dcoudert

An algorithm for iterating over connected subgraphs is described here https://stackoverflow.com/questions/15658245/efficiently-find-all-connected-induced-subgraphs. May be we can adapt it...

At least, it is possible to avoid the recursion and so to have a connected subgraph iterator. Not clear how to get an efficient implementation. I'll think about it.

comment:62 follow-up: Changed 3 years ago by dcoudert

I have implemented an iterator over connected subgraphs is Cython. It is reasonably fast. I should open a ticket for it, but I don't know yet in which file to add it. Any suggestion ?

It can certainly help improving this ticket, although current implementations are quite good.

comment:63 in reply to: ↑ 62 Changed 3 years ago by vdelecroix

Replying to dcoudert:

I have implemented an iterator over connected subgraphs in Cython. It is reasonably fast. I should open a ticket for it, but I don't know yet in which file to add it. Any suggestion ?

connected_subgraphs_iterator.pyx? Please, cc me.

It can certainly help improving this ticket, although current implementations are quite good.

To improve even more the computation of Cheeger constant, there should be an iterator over connected subgraph so that the complement is also connected! I can comment on this when your ticket is open.

Are you ok setting this ticket in positive review as it is? It will serve as a base for further improvements.

comment:64 follow-up: Changed 3 years ago by vdelecroix

Note that I can easily factor cheeger_constant and edge_isoperimetric_number (exact same computation except the small difference for vol). It might be worth not duplicating code.

comment:65 in reply to: ↑ 64 Changed 3 years ago by vdelecroix

Replying to vdelecroix:

Note that I can easily factor cheeger_constant and edge_isoperimetric_number (exact same computation except the small difference for vol). It might be worth not duplicating code.

What let me hesitate is that we can cut branches in the backtracking and when to cut will differ. What do you think?

comment:66 follow-up: Changed 3 years ago by dcoudert

Do you plan to add cuts in a near future ? and is the current structure of the code appropriate to add cuts ? if not, you can factor the code.

comment:67 in reply to: ↑ 66 Changed 3 years ago by vdelecroix

Replying to dcoudert:

Do you plan to add cuts in a near future ? and is the current structure of the code appropriate to add cuts ? if not, you can factor the code.

As my answers are "no" and "no" let me factor and add a note.

comment:68 Changed 3 years ago by vdelecroix

I spoke too fast: there are already two different cuts! By the definition of Cheeger constant, you cut when Vol(s) > m while for the isoperimetric number you cut 2*|S| > n (where m and n are as usual number of edges and number of vertices).

comment:69 Changed 3 years ago by dcoudert

Right.

Don't forget to add sig_on sig_off so that we can kill computation if needed.

comment:70 Changed 3 years ago by git

  • Commit changed from 83f5c802f79d518f5158ea1d4876566d7ee2beb3 to 50c186331bd54b8042cf7dce8c2f9c2e3e74a65d

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

50c186321942: code interruptible with sig_on/sig_off

comment:71 Changed 3 years ago by dcoudert

I have a much better implementation for vertex_isoperimetric_number using the ideas from https://stackoverflow.com/questions/15658245/efficiently-find-all-connected-induced-subgraphs. You can use it on a multigraph with loops. No limit on the number of vertices, but of course the time complexity remains.

Roughly, it uses a non-recursive version of the algorithm to generate all connected subgraphs of order at most n/2. I'm therefore using a binary matrix as a stack of bitsets.

from sage.rings.rational_field import QQ
from sage.rings.infinity import Infinity
from cysignals.signals cimport sig_on, sig_off

include "sage/data_structures/binary_matrix.pxi"
from sage.graphs.base.static_dense_graph cimport dense_graph_init

def vertex_isoperimetric_number_iter(G):
    """
    """
    if G.is_directed():
        raise ValueError("vertex-isoperimetric number is only defined on non-oriented graph")
    if G.order() == 0:
        raise ValueError("vertex-isoperimetric number not defined for the empty graph")
    elif G.order() == 1:
        return Infinity
    elif not G.is_connected():
        return QQ((0,1))

    # We convert the graph to a static dense graph
    cdef binary_matrix_t DG
    dense_graph_init(DG, G)
    cdef int n = G.order()
    cdef int k = n / 2   # maximum size of a subset

    sig_on()

    # We use a stack of bitsets. For that, we need 3 bitsets per level with at
    # most n/2 + 1 levels, so 3 * (n / 2) + 3 bitsets. We also need 1 bitset that
    # we create at the same time, so so overall 3 * (n / 2) + 4 bitsets
    cdef binary_matrix_t stack
    binary_matrix_init(stack, 3 * (n / 2) + 4, n)

    cdef bitset_t candidates = stack.rows[3 * (n / 2) + 3]
    cdef bitset_t left     # vertices not yet explored
    cdef bitset_t current  # vertices in the current subset
    cdef bitset_t boundary # union of neighbors of vertices in current subset

    cdef int l = 0
    cdef int p = n
    cdef int q = 0
    cdef int c, b, v

    # We initialize the first level
    for v in range(3):
        bitset_clear(stack.rows[v])
    bitset_complement(stack.rows[0], stack.rows[0])

    while l >= 0:

        # We take the values at the top of the stack
        left = stack.rows[l]
        current = stack.rows[l + 1]
        boundary = stack.rows[l + 2]

        if bitset_isempty(current):
            bitset_copy(candidates, left)
        else:
            bitset_and(candidates, left, boundary)

        if bitset_isempty(candidates):
            # We decrease l to pop the stack
            l -= 3

            # If the current set if non empty, we update the lower bound
            c = bitset_len(current)
            if c:
                bitset_difference(boundary, boundary, current)
                b = bitset_len(boundary)
                if b * q < p * c:
                    p = b
                    q = c

        else:
            # Choose a candidate vertex v
            v = bitset_first(candidates)
            bitset_discard(left, v)

            # Since we have not modified l, the bitsets for iterating without v
            # in the subset current are now at the top of the stack, with 
            # correct values

            if bitset_len(current) < k:
                # We continue with v in the subset current
                l += 3
                bitset_copy(stack.rows[l], left)
                bitset_copy(stack.rows[l + 1], current)
                bitset_add(stack.rows[l + 1], v)
                bitset_union(stack.rows[l + 2], boundary, DG.rows[v])

    binary_matrix_free(stack)
    binary_matrix_free(DG)
    sig_off()

    return QQ((p, q))

comment:72 Changed 3 years ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:73 Changed 2 years ago by dkrenn

Does not apply anymore.

comment:74 Changed 2 years ago by dkrenn

  • Status changed from needs_review to needs_work
  • Work issues set to merge confict

comment:75 Changed 2 years ago by dkrenn

  • Work issues changed from merge confict to merge conflict

comment:76 Changed 2 years ago by dcoudert

  • Milestone changed from sage-8.4 to sage-8.8

Note that we now have a connected subgraph iterator #25553.

comment:77 Changed 2 years ago by git

  • Commit changed from 50c186331bd54b8042cf7dce8c2f9c2e3e74a65d to 487bee9864dca76779e58abc3b5024abc85c4790

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

487bee921942: Cheeger constants

comment:78 Changed 2 years ago by vdelecroix

(just a rebase, need to adapt the code to use the connected subgraph iterator)

comment:79 follow-up: Changed 2 years ago by vdelecroix

@dcoudert: I would be happy to use the subgraph iterator from #25553 however

  • it is only implemented for dense graphs
  • the iterator carries many information that would be extremely useful for implementing isoperimetric constants (such as boundary)
  • passing around lists of vertices (the output of the iterator) is a big waste

One possible way to proceed is to make a proper Cython class for the subgraph iterator so that we can grab information (at C level) at each step of the iteration.

What do you think?

comment:80 in reply to: ↑ 79 Changed 2 years ago by dcoudert

Replying to vdelecroix:

@dcoudert: I would be happy to use the subgraph iterator from #25553 however

  • it is only implemented for dense graphs

It's reasonably fast this way :P But of course we could implement a sparse graph counter part.

  • the iterator carries many information that would be extremely useful for implementing isoperimetric constants (such as boundary)
  • passing around lists of vertices (the output of the iterator) is a big waste

One possible way to proceed is to make a proper Cython class for the subgraph iterator so that we can grab information (at C level) at each step of the iteration.

What do you think?

We can certainly add such a class if it's needed. However, you have to be very careful if you want to access extra data. May be it's easier to copy/paste the code of the iterator, so that you can use the information you want safely at the time you need it. The advantage of the class is to silently switch between sparse and dense representations.

comment:81 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

comment:82 Changed 22 months ago by dcoudert

  • Milestone changed from sage-8.9 to sage-9.0

Moving to 9.0. We can also work on a proper cython class for subgraph iterator if useful.

comment:83 Changed 19 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:84 Changed 16 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:85 Changed 13 months ago by chapoton

  • Branch changed from u/vdelecroix/21942 to public/ticket/21942
  • Commit changed from 487bee9864dca76779e58abc3b5024abc85c4790 to 1fb6f64b8c828fd55a6fd49ac89c15c5bb1f1b19

There is some interest for this code : https://ask.sagemath.org/question/52410/edge-isoperimetric-number/

I have rebased the branch


New commits:

1fb6f64Merge branch 'u/vdelecroix/21942' in 9.2.b4

comment:86 Changed 13 months ago by git

  • Commit changed from 1fb6f64b8c828fd55a6fd49ac89c15c5bb1f1b19 to 9a0062d887faa15d6e694f7143bd37514f31d790

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

9a0062dsome fixes in references

comment:87 Changed 13 months ago by git

  • Commit changed from 9a0062d887faa15d6e694f7143bd37514f31d790 to d508cb51905ca50b71af869aca687a92dc3c28ad

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

d508cb5fix missing comma

comment:88 Changed 13 months ago by git

  • Commit changed from d508cb51905ca50b71af869aca687a92dc3c28ad to 838919667a0dd289c9dc3121573d1733ca33f312

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

8389196trac #21942: better implementation of vertex isoperimetric number

comment:89 Changed 13 months ago by dcoudert

I changed the code of vertex isoperimetric number. The new code is way faster on sparse graphs and can handle (multi-) graphs of any size. Of course, the running time can be significant on large graphs.

sage: G = graphs.Grid2dGraph(5,6)
sage: %time G.vertex_isoperimetric_number()
CPU times: user 328 ms, sys: 712 µs, total: 329 ms
Wall time: 329 ms
1/3
sage: G = graphs.Grid2dGraph(6, 6)
sage: %time G.vertex_isoperimetric_number()
CPU times: user 9.25 s, sys: 24.6 ms, total: 9.28 s
Wall time: 9.28 s
1/3
sage: G = graphs.CompleteGraph(10)
sage: %time G.vertex_isoperimetric_number()
CPU times: user 254 µs, sys: 4 µs, total: 258 µs
Wall time: 264 µs
1
sage: G = graphs.CompleteGraph(20)
sage: %time G.vertex_isoperimetric_number()
CPU times: user 32.3 ms, sys: 185 µs, total: 32.5 ms
Wall time: 32.5 ms
1
sage: G = graphs.CompleteGraph(30)
sage: %time G.vertex_isoperimetric_number()
CPU times: user 31.8 s, sys: 111 ms, total: 31.9 s
Wall time: 32 s
1

comment:90 Changed 13 months ago by chapoton

  • Status changed from needs_work to needs_review
  • Work issues merge conflict deleted

comment:91 Changed 13 months ago by dcoudert

For me this patch is good to go as is and we can let possible improvements for future tickets like:

  • algorithms for specific graph classes such as trees (#comment:28) or cliques
  • make a class for connected subgraphs iterator and use it to speed up / simplify some parts (#comment:59)

I'm a bit lost in who should be in authors or reviewers or both...

comment:92 Changed 13 months ago by chapoton

  • Authors changed from Vincent Delecroix to Vincent Delecroix, David Coudert
  • Reviewers changed from Peleg Michaeli to Peleg Michaeli, Frédéric Chapoton
  • Status changed from needs_review to positive_review

On peut faire comme ça, par exemple. Tu peux te rajouter comme rapporteur si tu veux.

comment:93 Changed 13 months ago by dcoudert

C'est très bien comme ça. Thanks.

comment:94 Changed 12 months ago by vbraun

  • Branch changed from public/ticket/21942 to 838919667a0dd289c9dc3121573d1733ca33f312
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:95 Changed 9 months ago by mkoeppe

  • Authors changed from Vincent Delecroix, David Coudert to Vincent Delecroix, David Coudert
  • Commit 838919667a0dd289c9dc3121573d1733ca33f312 deleted
Note: See TracTickets for help on using tickets.