#21942 closed enhancement (fixed)
Cheeger constant(s) of graphs
Reported by:  pelegm  Owned by:  pelegm 

Priority:  major  Milestone:  sage9.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: 
Description (last modified by )
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
 Branch set to u/pelegm/cheeger
 Commit set to 05ab2786fdb220852888e0619a31950e55f84ad7
 Owner changed from (none) to pelegm
comment:2 Changed 5 years ago by
 Commit changed from 05ab2786fdb220852888e0619a31950e55f84ad7 to 0cb6192693a25a4e39ee596f1e8a8fe9935213a3
Branch pushed to git repo; I updated commit sha1. New commits:
0cb6192  Implementing edge isoperimetric number (#21942)

comment:3 Changed 5 years ago by
 Commit changed from 0cb6192693a25a4e39ee596f1e8a8fe9935213a3 to bbe6ecff8244507164515aca053123126efd0879
comment:4 Changed 5 years ago by
 Status changed from new to needs_review
 Summary changed from Cheeger constant to Cheeger constant(s)
comment:5 Changed 5 years ago by
Will rebase to develop
.
comment:6 Changed 5 years ago by
 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
 Cc jepperlein added
comment:8 Changed 5 years ago by
I know nothing about those functions. However, two general notes:
 Onesentence descriptions will be used in the toc and they should really be just one sentence. It is kind of dull to have "Return the edgeisoperimetric number of a graph." when the name is
edge_isoperimetric_number()
, but there is no good alternative. (When there is no real oneline description like for examplesize()
has.)
 Please test for empty graphs. See #21741 for bugs we already have had.
comment:9 Changed 5 years ago by
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
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
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
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
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
Let me try it now.
comment:15 Changed 5 years ago by
 Commit changed from bbe6ecff8244507164515aca053123126efd0879 to 4f86191169e3c732292af2bd4356bc4ff097b8fd
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
1988a75  Cheeger constant (#21942)

6214e44  Implementing edge isoperimetric number (#21942)

94f8a45  Fixing some documentation bugs #21942

f07babf  Vertex isoperimetric number #21942

4f86191  Check the cases empty graph and single vertex WIP

comment:16 Changed 5 years ago by
In the meanwhile, I have rebased to 7.5beta4 and added some heuristics.
comment:17 Changed 5 years ago by
 Commit changed from 4f86191169e3c732292af2bd4356bc4ff097b8fd to a06c7dee8fd4d072921a5f9e09e06b3b5da73a08
Branch pushed to git repo; I updated commit sha1. New commits:
a06c7de  Better docstrings & aliases, references moved

comment:18 followup: ↓ 19 Changed 5 years ago by
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
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
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
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
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
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
Well, I guess that at least for trees the algorithm can be vastly improved.
comment:25 Changed 5 years ago by
This paper: http://ac.elscdn.com/0095895689900294/1s2.00095895689900294main.pdf?_tid=c92aa55eb88011e6a64e00000aab0f02&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
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
The algorithm works in general and is linear on trees!
comment:28 Changed 5 years ago by
I think the following algorithm works for trees:
comment:29 Changed 5 years ago by
The algorithm now also finds Cheeger constant (and not only edge isoperimetric number) of trees.
comment:30 Changed 5 years ago by
 Commit changed from a06c7dee8fd4d072921a5f9e09e06b3b5da73a08 to 4e097b7e2870b56dd3ad3ad8e790074c8b51ecdc
comment:31 Changed 5 years ago by
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
 Cc slelievre added
comment:33 Changed 3 years ago by
 Branch changed from u/pelegm/cheeger to u/vdelecroix/21942
 Commit changed from 4e097b7e2870b56dd3ad3ad8e790074c8b51ecdc to 42b83fb86a93a97cb25d83dcdccc9643b0208591
 Milestone changed from sage7.5 to sage8.3
comment:34 Changed 3 years ago by
TODO:
 implement the backtracker for the 3 versions
 use branch and bound (ie cut branches)
comment:35 Changed 3 years ago by
 Commit changed from 42b83fb86a93a97cb25d83dcdccc9643b0208591 to 8e9f2ee1d7e60a4ec02caad2672f70b4fda846c8
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8e9f2ee  C backtracker for Cheeger constant

comment:36 Changed 3 years ago by
 Commit changed from 8e9f2ee1d7e60a4ec02caad2672f70b4fda846c8 to 8484a373b28c8b0abdc4ed95ef307dd34d57659d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8484a37  21942: Cheeger constant

comment:37 Changed 3 years ago by
 Keywords MathExp2018 added; isoperimetric random walk days79 removed
 Status changed from needs_work to needs_review
comment:38 Changed 3 years ago by
 Description modified (diff)
 Summary changed from Cheeger constant(s) to Cheeger constant(s) of graphs
comment:39 followup: ↓ 40 Changed 3 years ago by
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/sitepackages/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
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/sitepackages/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 docclean
before building the doc?
comment:41 Changed 3 years ago by
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 docclean ... Sage build/upgrade complete! peleg@etti:21942:~/sage$ sage docbuild reference/graphs html ... [graphs ] /media/peleg/peleg/sage/local/lib/python2.7/sitepackages/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/sitepackages/sage_setup/docbuild/__main__.py", line 2, in <module> [graphs ] main() [graphs ] File "/media/peleg/peleg/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 1713, in main [graphs ] builder() [graphs ] File "/media/peleg/peleg/sage/local/lib/python2.7/sitepackages/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/sitepackages/sage_setup/docbuild/__init__.py", line 130, in f [graphs ] runsphinx() [graphs ] File "/media/peleg/peleg/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/sphinxbuild.py", line 276, in runsphinx [graphs ] sys.stderr.raise_errors() [graphs ] File "/media/peleg/peleg/sage/local/lib/python2.7/sitepackages/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/sitepackages/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
After make docclean
you should be using make doc
.
comment:43 Changed 3 years ago by
Works, thanks (took 2.5 hours, though...).
Some minor suggestions:
 In the cheeger constant docs, I'd replace
S(X)
withVol(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
 Commit changed from 8484a373b28c8b0abdc4ed95ef307dd34d57659d to 10c362ea66dfa6d50e3b7b341e09fd14db71afb7
Branch pushed to git repo; I updated commit sha1. New commits:
10c362e  21942: better documentation

comment:47 Changed 3 years ago by
 Reviewers set to Peleg Michaeli
 Status changed from needs_work to positive_review
Sorry
comment:48 Changed 3 years ago by
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 nonconnected 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
 Status changed from positive_review to needs_work
comment:50 Changed 3 years ago by
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
, methodvertex_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
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
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 nonempty 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 followup: ↓ 57 Changed 3 years ago by
I am not 100% convinced by FastDigraph
:
 why
FastDiagraph
is not merged withbase/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 auint_fast32_t
that is exactly what you want here.
 Many processors offer a
popcount
thatpopcount32
is just ignoring.
comment:54 Changed 3 years ago by
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
 Commit changed from 10c362ea66dfa6d50e3b7b341e09fd14db71afb7 to b981a8dc9e40577e326c1008ad073370ca192e48
comment:56 Changed 3 years ago by
 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
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 nonzero/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
incheeger_constant
: use an array to store the degree of vertices, and then, instead of doingvol += 1
inside the for loop, dovol += 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
 Commit changed from b981a8dc9e40577e326c1008ad073370ca192e48 to 8bcb4973ccf2365b8aba3d8f829f366b5d1990ec
Branch pushed to git repo; I updated commit sha1. New commits:
8bcb497  21942: typo in doc

comment:59 Changed 3 years ago by
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
 Commit changed from 8bcb4973ccf2365b8aba3d8f829f366b5d1990ec to 83f5c802f79d518f5158ea1d4876566d7ee2beb3
Branch pushed to git repo; I updated commit sha1. New commits:
83f5c80  21942: small optimization

comment:61 Changed 3 years ago by
An algorithm for iterating over connected subgraphs is described here https://stackoverflow.com/questions/15658245/efficientlyfindallconnectedinducedsubgraphs. 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 followup: ↓ 63 Changed 3 years ago by
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
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 followup: ↓ 65 Changed 3 years ago by
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
Replying to vdelecroix:
Note that I can easily factor
cheeger_constant
andedge_isoperimetric_number
(exact same computation except the small difference forvol
). 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 followup: ↓ 67 Changed 3 years ago by
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
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
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
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
 Commit changed from 83f5c802f79d518f5158ea1d4876566d7ee2beb3 to 50c186331bd54b8042cf7dce8c2f9c2e3e74a65d
Branch pushed to git repo; I updated commit sha1. New commits:
50c1863  21942: code interruptible with sig_on/sig_off

comment:71 Changed 3 years ago by
I have a much better implementation for vertex_isoperimetric_number
using the ideas from https://stackoverflow.com/questions/15658245/efficientlyfindallconnectedinducedsubgraphs. 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 nonrecursive 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("vertexisoperimetric number is only defined on nonoriented graph") if G.order() == 0: raise ValueError("vertexisoperimetric 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
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:73 Changed 2 years ago by
Does not apply anymore.
comment:74 Changed 2 years ago by
 Status changed from needs_review to needs_work
 Work issues set to merge confict
comment:75 Changed 2 years ago by
 Work issues changed from merge confict to merge conflict
comment:76 Changed 2 years ago by
 Milestone changed from sage8.4 to sage8.8
Note that we now have a connected subgraph iterator #25553.
comment:77 Changed 2 years ago by
 Commit changed from 50c186331bd54b8042cf7dce8c2f9c2e3e74a65d to 487bee9864dca76779e58abc3b5024abc85c4790
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
487bee9  21942: Cheeger constants

comment:78 Changed 2 years ago by
(just a rebase, need to adapt the code to use the connected subgraph iterator)
comment:79 followup: ↓ 80 Changed 2 years ago by
@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
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
 Milestone changed from sage8.8 to sage8.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
 Milestone changed from sage8.9 to sage9.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
 Milestone changed from sage9.0 to sage9.1
Ticket retargeted after milestone closed
comment:84 Changed 16 months ago by
 Milestone changed from sage9.1 to sage9.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
 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/edgeisoperimetricnumber/
I have rebased the branch
New commits:
1fb6f64  Merge branch 'u/vdelecroix/21942' in 9.2.b4

comment:86 Changed 13 months ago by
 Commit changed from 1fb6f64b8c828fd55a6fd49ac89c15c5bb1f1b19 to 9a0062d887faa15d6e694f7143bd37514f31d790
Branch pushed to git repo; I updated commit sha1. New commits:
9a0062d  some fixes in references

comment:87 Changed 13 months ago by
 Commit changed from 9a0062d887faa15d6e694f7143bd37514f31d790 to d508cb51905ca50b71af869aca687a92dc3c28ad
Branch pushed to git repo; I updated commit sha1. New commits:
d508cb5  fix missing comma

comment:88 Changed 13 months ago by
 Commit changed from d508cb51905ca50b71af869aca687a92dc3c28ad to 838919667a0dd289c9dc3121573d1733ca33f312
Branch pushed to git repo; I updated commit sha1. New commits:
8389196  trac #21942: better implementation of vertex isoperimetric number

comment:89 Changed 13 months ago by
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
 Status changed from needs_work to needs_review
 Work issues merge conflict deleted
comment:91 Changed 13 months ago by
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
 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
C'est très bien comme ça. Thanks.
comment:94 Changed 12 months ago by
 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
 Commit 838919667a0dd289c9dc3121573d1733ca33f312 deleted
New commits:
Cheeger constant (#21942)