Opened 11 years ago
Closed 11 years ago
#8922 closed enhancement (fixed)
induced subgraph search
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | critical | Milestone: | sage-4.4.4 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.4.4.alpha0 | |
Authors: | Nathann Cohen | Reviewers: | Minh Van Nguyen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch add to Sage the method Graph.induced_subgraph_search which looks for a given graph as an induced subgraph of "self".
This is done through exhaustive search, using a very basic new graph class hand-made to efficiently stand such repetitive operations !
I tried to document the code so that it could be somewhat easy to review, but feel free to ask any question about it ! :-)
Apply:
Attachments (2)
Change History (17)
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Priority changed from major to critical
comment:3 follow-up: ↓ 4 Changed 11 years ago by
comment:4 in reply to: ↑ 3 Changed 11 years ago by
Replying to ncohen:
- it took me some time, but I tested the new graph classes StaticDenseGraph? this patch introduced against the already implemented DenseGraph?.... Which turned out to be more efficient.. So this new class has disappeared, and the new code is now written into the usual Sage files instead of new ones
I have been reviewing your previous patch for over two days and went the same route as you have done in your current patch. That is, I rewrote your StaticDenseGraph to use the C graph based DenseGraph class, as it is very efficient in terms of storage. The reason why I have not uploaded my reviewer patch is that I was thinking about and playing with how to make the method adjacency_list
more efficient in terms of storage. An array of ints is wasteful for the intended purpose, when a bitset is more suited to the purpose. What has been bugging me is trying to get my bitset implementation of adjacency_list
to compile and work.
- a -- very nasty -- memory leak -- now fixed
Again, I went the same route in my reviewer patch.
- add functions to test for induced as well as non-induced subgraphs, as it is the same.. Also works with DiGraphs?, by the way !
Again, I went the same route in my reviewer patch.
Seems like you anticipated my changes. Anyway, I'll have a careful look at your updated patch.
comment:5 Changed 11 years ago by
Hello !!
Well, first thank you for your work on this patch... I know it's a bit heavy all at once, and I hope the comments were clear enough :-)
About the adjacency_list
method : I was more worried about speed than storage, but anyway DenseGraph? were faster than my matrix of integers.. Don't you think working on integers as it is done inside of DenseGraph? could be more efficient than it currently is ? I have never used operations such as << and >> as it is done in DenseGraph?, but I thought it would be the next step if one wanted to improve the speed for a bit. I'll trust you on this one !
I also took some notes for future improvements... For example several tricks to reduce the number of attempts, or the initial graph, but I intended to wait for this patch to be merged before adding them. It will be easier to read in another one anyway :-)
Thank you again
Nathann
comment:6 Changed 11 years ago by
- Description modified (diff)
comment:7 Changed 11 years ago by
- Status changed from needs_review to needs_work
I applied patches in the order suggested in the ticket description. Running doctests on the whole graph theory module resulted in these failures. This failure results from ncohen's updated patch, which does not update the doctests:
sage -t -long "devel/sage-main/sage/graphs/generic_graph_pyx.pyx" ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-main/sage/graphs/generic_graph_pyx.pyx", line 491: sage: from sage.graphs.induced_subgraphs.induced_subgraphs import find_induced Exception raised: Traceback (most recent call last): File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_10[2]>", line 1, in <module> from sage.graphs.induced_subgraphs.induced_subgraphs import find_induced###line 491: sage: from sage.graphs.induced_subgraphs.induced_subgraphs import find_induced ImportError: No module named induced_subgraphs.induced_subgraphs ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-main/sage/graphs/generic_graph_pyx.pyx", line 492: sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(5)) Exception raised: Traceback (most recent call last): File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_10[3]>", line 1, in <module> find_induced(graphs.PetersenGraph(), graphs.PathGraph(Integer(5)))###line 492: sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(5)) NameError: name 'find_induced' is not defined ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-main/sage/graphs/generic_graph_pyx.pyx", line 497: sage: find_induced(graphs.PetersenGraph(), graphs.ClawGraph()) Exception raised: Traceback (most recent call last): File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_10[4]>", line 1, in <module> find_induced(graphs.PetersenGraph(), graphs.ClawGraph())###line 497: sage: find_induced(graphs.PetersenGraph(), graphs.ClawGraph()) NameError: name 'find_induced' is not defined ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-main/sage/graphs/generic_graph_pyx.pyx", line 502: sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(6)) Exception raised: Traceback (most recent call last): File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_10[5]>", line 1, in <module> find_induced(graphs.PetersenGraph(), graphs.PathGraph(Integer(6)))###line 502: sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(6)) NameError: name 'find_induced' is not defined
This is a known failure:
sage -t -long "devel/sage-main/sage/graphs/generic_graph.py" ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-main/sage/graphs/generic_graph.py", line 10754: sage: print G.graphviz_string(labels="latex",edge_labels=True) Expected: digraph { node [shape="plaintext"]; "2/3" [label=" ", texlbl="$\frac{2}{3}$"]; "1/3" [label=" ", texlbl="$\frac{1}{3}$"]; "1/2" [label=" ", texlbl="$\frac{1}{2}$"]; "1" [label=" ", texlbl="$1$"]; "1/4" [label=" ", texlbl="$\frac{1}{4}$"]; "4/5" [label=" ", texlbl="$\frac{4}{5}$"]; "-4" [label=" ", texlbl="$-4$"]; "2" [label=" ", texlbl="$2$"]; "-2" [label=" ", texlbl="$-2$"]; "-1/2" [label=" ", texlbl="$-\frac{1}{2}$"]; "-1" [label=" ", texlbl="$-1$"]; <BLANKLINE> "1/2" -> "-2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"]; "1/2" -> "2/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; "1" -> "-1" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"]; "1" -> "1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; "1/4" -> "-4" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"]; "1/4" -> "4/5" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; "2" -> "-1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"]; "2" -> "1/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; } Got: digraph { node [shape="plaintext"]; "2/3" [label=" ", texlbl="$\frac{2}{3}$"]; "1/3" [label=" ", texlbl="$\frac{1}{3}$"]; "1/2" [label=" ", texlbl="$\frac{1}{2}$"]; "1" [label=" ", texlbl="$1$"]; "1/4" [label=" ", texlbl="$\frac{1}{4}$"]; "4/5" [label=" ", texlbl="$\frac{4}{5}$"]; "-4" [label=" ", texlbl="$-4$"]; "2" [label=" ", texlbl="$2$"]; "-2" [label=" ", texlbl="$-2$"]; "-1/2" [label=" ", texlbl="$-\frac{1}{2}$"]; "-1" [label=" ", texlbl="$-1$"]; <BLANKLINE> "1/2" -> "-2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; "1/2" -> "2/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; "1" -> "-1" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; "1" -> "1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; "1/4" -> "-4" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; "1/4" -> "4/5" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; "2" -> "-1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; "2" -> "1/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; }
This one should be optional, I think, and results from #8166:
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-main/sage/graphs/generic_graph.py", line 4213: sage: g.matching(algorithm="LP", value_only=True) Exception raised: Traceback (most recent call last): File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_70[5]>", line 1, in <module> g.matching(algorithm="LP", value_only=True)###line 4213: sage: g.matching(algorithm="LP", value_only=True) File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4264, in matching return p.solve(objective_only=True, solver=solver, log=verbose) File "mip.pyx", line 1051, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:7884) ValueError: There does not seem to be any (Mixed) Integer Linear Program solver installed. Please visit http://www.sagemath.org/doc/constructions/linear_programming.html to learn more about the solvers available.
comment:8 Changed 11 years ago by
- Status changed from needs_work to needs_review
Sorry for that Minh :-/
Here is an updated patch... God, I'm eager to have all these dependencies merged into Sage !
Nathann
Changed 11 years ago by
comment:9 follow-up: ↓ 10 Changed 11 years ago by
It looks like everything in the dependencies except this patch is now reviewed. Minh, are you reviewing this patch as well?
comment:10 in reply to: ↑ 9 Changed 11 years ago by
Replying to jason:
Minh, are you reviewing this patch as well?
Yes. I'm finalizing a reviewer patch.
Changed 11 years ago by
comment:11 follow-up: ↓ 13 Changed 11 years ago by
- Description modified (diff)
- Reviewers set to Minh Van Nguyen
Changes in reviewer patch:
- Move the method
adjacency_sequence()
to the classCGraph
, as I think that method is useful for both dense and sparse graphs. - Clean-up coding style in accordance with PEP 008.
- In describing the algorithm used in
subgraph_search()
of the modulegeneric_graph_pyx.pyx
, you have the formula:`\binom k!{|V(G)|}{k}`
That won't typeset in LaTeX as you expected. Do you mean this?`k! \binom{|V(G)|}{k}`
I have used the latter formula in my reviewer patch. Please correct me if I'm wrong. - Unit tests for the
cdef
functionsvectors_equal()
andvectors_inferior()
, and the methodadjacency_sequence()
. These functions/methods are defined usingcdef
and the doctest coverage script don't pick them up in its analysis. However, I still think it's important to provide unit tests for such functions/methods. - Amalgamate the methods
induced_subgraph_search()
andsubgraph_search()
. Their definitions are almost identical, except for the keywordinduced
. The combined method is defined to take the boolean keywordinduced
and pass it on to the relevant method.
Another pair of eyes is needed to look over my reviewer patch.
comment:12 Changed 11 years ago by
Wow, your reviewer patch is twice the size of the original patch!
comment:13 in reply to: ↑ 11 Changed 11 years ago by
Hello !!
First, I want to thank you for the amount of time your must have spent on this :-)
- Move the method
adjacency_sequence()
to the classCGraph
, as I think that method is useful for both dense and sparse graphs.
It can be, though systematically testing adjacencies (and most importantly -- non-adjacencies) in sparse graph can be a problem... Perhaps we will have to split this function in two copies, one for each class, one day or another. I have been talking with Alexandre Blondin Masse who could need such a feature for Sparse graphs :-)
- In describing the algorithm used in
subgraph_search()
of the modulegeneric_graph_pyx.pyx
, you have the formula:`\binom k!{|V(G)|}{k}`That won't typeset in LaTeX as you expected. Do you mean this?`k! \binom{|V(G)|}{k}`
Indeed
I have used the latter formula in my reviewer patch. Please correct me if I'm wrong.
You almost never are :-)
- Unit tests for the
cdef
functionsvectors_equal()
andvectors_inferior()
, and the methodadjacency_sequence()
. These functions/methods are defined usingcdef
and the doctest coverage script don't pick them up in its analysis. However, I still think it's important to provide unit tests for such functions/methods.
Well, if there is anything wrong in these functions your tests will show it, though given their length I wouldn't have thought necessary to add such tests.... Are you doubting Cython itself ? :-)
- Amalgamate the methods
induced_subgraph_search()
andsubgraph_search()
. Their definitions are almost identical, except for the keywordinduced
. The combined method is defined to take the boolean keywordinduced
and pass it on to the relevant method.
I was thinking of someone working on induced subgraphs, and not seeing any occurence of this word among the functions.... But he will get interested in subgraph search sooner or later ;-)
Another pair of eyes is needed to look over my reviewer patch.
I already spent some time over it, and agreed with what I saw.... Considering its length, I may do this once or twice again before setting it to "positive review". and... Thank you again :-)
Nathann
comment:14 Changed 11 years ago by
- Status changed from needs_review to positive_review
Agreeeeeeed !! I expect this function to receive a lot of improvements in future patches :-)
Nathann
comment:15 Changed 11 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
Updated ! Changes :
And once this patch will be merged into Sage... I will have many other things to write on top of it :-)
Nathann