#8922: induced subgraph search
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: critical | Milestone: sage-4.4.3
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by newvalueoldvalue):
* author: => Nathann Cohen
Comment:
Replying to [comment:3 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.
[[BR]][[BR]]
> * a -- very nasty -- memory leak -- now fixed
Again, I went the same route in my reviewer patch.
[[BR]][[BR]]
> * 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.
[[BR]][[BR]]
Seems like you anticipated my changes. Anyway, I'll have a careful look at
your updated patch.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8922#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
