Introduction - moving Sage forward

[Jernej]

Hello!

My name is Jernej Azarija. I am a PHD student studying graph theory. I have included my background and technical skills in my GSOC application hence I won't elaborate on that here (please take a look on the application for further info).

As one of the potential GSOC projects I would like to improve the graph theory/combinatorics module of Sage.

The fact that I use Sage for research on a daily basis and that I already contributed to Sage, I know many things that can be done in this area. There is a short list of what I think could be corrected that you can find here (a dump from my personal wiki) : http://azi.dev.si/GSOC2013_proposal.html

I can extend the list further and also provide more motivation on why I think this project is important, but somehow I would first like to get a "green" flag that this it is interesting enough..

Being suitable for projects involving C I am also very very interested in the proposed projects especially M1RI and Speeding up Sage's startup time.

Somehow I am not really sure which project to pick (mine, M1RI, Speeding up the startup time or some of the others listed in the application) since they are almost equally interesting to me. The only added benefit of the graph theory project is that it affects my field of work more directly.

Hence I would like to participate in something that you guys think is most appropriate for the overall enhancement of Sage.


Best regards,

Jernej

[Harald Schilly]

On Tue, Apr 23, 2013 at 1:44 PM, Jernej <azi.s...@gmail.com> wrote:
> The fact that I use Sage for research on a daily basis and that I already
> contributed to Sage, I know many things that can be done in this area.

That sounds good! What have you contributed?
he hardest part is probably to figure out who could be a mentor for
you. Do you already have a someone in mind? Since this is also related
to graph theory, you should maybe crosspost this to sage-combinat.
They haven't shown interest in GSoC so far – at least that I would be
aware of – but it's still worth a try.
http://wiki.sagemath.org/combinat

Harald

[Jernej]

On Tuesday, 23 April 2013 13:59:23 UTC+2, Harald Schilly wrote:

On Tue, Apr 23, 2013 at 1:44 PM, Jernej <azi.s...@gmail.com> wrote:
> The fact that I use Sage for research on a daily basis and that I already
> contributed to Sage, I know many things that can be done in this area.


That sounds good! What have you contributed?

Plenty of (small) things. I fixed a segfault in the Cython code for subgraph_search_*, added tests for arc and edge transitive graphs, added code to count/detect triangles in graphs etc.... I also reviewed some of the patches others created.
 

he hardest part is probably to figure out who could be a mentor for
you. Do you already have a someone in mind?

No. In the Sage social network I somehow related the most with Nathann Cohen and Rob Beezer so they come to mind as potential mentors but I am not sure they even care to participate.

Also, as I said, the main thing is that I do not know if I should try to push this graph theory project forward or stick with some of the projects already proposed. They are all equally fine to me and I would like to work on the one that has the biggest impact on the overall project.
 

[Stefan van Zwam]

Hi Jernej,

You are definitely proposing the right kinds of problems! I, for one, would really like to see automorphism_group work for arbitrary vertex labels.

You may have seen that I proposed work on matroids for GSoC. One of the features that needs to be added is computing the automorphism group of a matroid. If you modified the method for graphs as you proposed, and maybe the one for linear codes, then that would put you in prime position for implementing that.

You asked about the slowness of the basic combinatorics routines in Sage. I ran into that myself; they're just not usable for matroids because of the lack of speed. When you profile them, you'll find that almost 100% of the execution time is spent in the constructor of Set (and in particular in the category framework). See here:

https://groups.google.com/forum/?fromgroups=#!topic/sage-devel/Jzpq7g2bQLU

and also here:

https://groups.google.com/forum/?fromgroups=#!topic/sage-combinat-devel/e-PWc_2gNU4 

I'd say push your project forward. It addresses stuff I care about.

Cheers,

Stefan.

[Jernej]

On Tuesday, 23 April 2013 17:18:38 UTC+2, Stefan van Zwam wrote:

On Tuesday, 23 April 2013 13:59:23 UTC+2, Harald Schilly wrote:

On Tue, Apr 23, 2013 at 1:44 PM, Jernej <azi.s...@gmail.com> wrote:
> The fact that I use Sage for research on a daily basis and that I already
> contributed to Sage, I know many things that can be done in this area.


That sounds good! What have you contributed?

Plenty of (small) things. I fixed a segfault in the Cython code for subgraph_search_*, added tests for arc and edge transitive graphs, added code to count/detect triangles in graphs etc.... I also reviewed some of the patches others created.
 

he hardest part is probably to figure out who could be a mentor for
you. Do you already have a someone in mind?

No. In the Sage social network I somehow related the most with Nathann Cohen and Rob Beezer so they come to mind as potential mentors but I am not sure they even care to participate.

Also, as I said, the main thing is that I do not know if I should try to push this graph theory project forward or stick with some of the projects already proposed. They are all equally fine to me and I would like to work on the one that has the biggest impact on the overall project.
 

Since this is also related
to graph theory, you should maybe crosspost this to sage-combinat.
They haven't shown interest in GSoC so far – at least that I would be
aware of – but it's still worth a try.
http://wiki.sagemath.org/combinat

 

 

Harald

Hi Jernej,

Hello!
 

You are definitely proposing the right kinds of problems! I, for one, would really like to see automorphism_group work for arbitrary vertex labels.

Somehow it appears (thanks Nathann) that my track ticket for this issue got ignored (or deleted??) and a new one was opened in which this issue was resolved 5 weeks ago. See http://trac.sagemath.org/sage_trac/ticket/14319
 

You may have seen that I proposed work on matroids for GSoC. One of the features that needs to be added is computing the automorphism group of a matroid. If you modified the method for graphs as you proposed, and maybe the one for linear codes, then that would put you in prime position for implementing that.

Actually I haven't seen this the last time I was looking. I've now looked on it and the only issue that I see is that I am not really comfortable with matroid theory per se. The problem my be quite doable from a programming standpoint but I am afraid the quality of the code my suffer from my lack of understanding?
 

You asked about the slowness of the basic combinatorics routines in Sage. I ran into that myself; they're just not usable for matroids because of the lack of speed. When you profile them, you'll find that almost 100% of the execution time is spent in the constructor of Set (and in particular in the category framework). See here:

https://groups.google.com/forum/?fromgroups=#!topic/sage-devel/Jzpq7g2bQLU

and also here:

https://groups.google.com/forum/?fromgroups=#!topic/sage-combinat-devel/e-PWc_2gNU4 

I'd say push your project forward. It addresses stuff I care about.

If that is so, then I would need a mentor. Up to now, nobody really shown up. Do you happen to have any ideas?

Perhaps we could rephrase the project into "Optimizing various core things in Sage" and then deal with the stated issues including the Speed the runtime thing?
 

Cheers,

Stefan.

[Jernej]

Here is a proposal of a slightly modified project that would address performance issues in Sage: http://azi.dev.si/GSOC2013_proposal2.html 

The priority of the listed issues would of course be adjusted in relation to what others think is most important. I have now also opened a disccusion on sage-devel asking for a mentor https://groups.google.com/forum/?fromgroups=#!topic/sage-devel/e6Gw8o2oYPA

Hopefully someone will show up that can help with it.

[Jernej]

Hello!

I am still unable to find someone willing to be a mentor of this project.

Since the application deadline is coming soon and since guys on IRC advised me to do something about it ( :-) ) I am bumping this thread once again. It is kind of hard to extend the proposal or do anything with it without getting any feedback.

Is anyone interested in mentoring me with the proposed project (improving the graph data structure, speeding up the combinatorial functions,..)? Or at least knows someone that may be directed to this thread?

Also in the proposal that I put on melange I've stated some other projects that I would be willing to participate in (for example M1RI,Numerical Optimization,Mathematical Function Library,..) Hence If nobody really cares about the combinatorial things, is one of the mentors of the mentioned projects willing to give some feedback?

Best,

Jernej

[Stefan van Zwam]

Dear Jernej,

I've been reluctant to step forward as a mentor because I think you have more experience with Sage development than I do, and because I'd rather supervise someone who does at least some work on matroids. But I'd rather see you do work on the Graph theory part of Sage, than not to see you work on Sage at all.

Maybe you can build some support into Sage for graphic matroids and signed-graphic matroids. These would be mainly shells around Sage's Graph class, providing an interface to create minors, extensions, customized show() method (with colored edges in the case of signed-graphic matroids), and so on. This does not require much in terms of matroid theory (you'd have to learn the rank functions of these matroids, which are formulated in terms of forests and similar graph-theoretic constructs).

Cheers,

Stefan.

[Nathann Cohen]

Helloooooooooooo !!!

> I've been reluctant to step forward as a mentor because I think you have more experience with Sage development than I do, and because I'd rather supervise someone who does at least some work on matroids. But I'd rather see you do work on the Graph theory part of Sage, than not to see you work on Sage at all.
>
> Maybe you can build some support into Sage for graphic matroids and signed-graphic matroids. These would be mainly shells around Sage's Graph class, providing an interface to create minors, extensions, customized show() method (with colored edges in the case of signed-graphic matroids), and so on. This does not require much in terms of matroid theory (you'd have to learn the rank functions of these matroids, which are formulated in terms of forests and similar graph-theoretic constructs).

I've been reluctant to step forward as a mentor because to me working
on Sage is a hobby, and when I do it for Google it becomes work. But I
just created an account on GSOC's website to act as a mentor for
Jernej's application and I was just remembering that Harald said at
some point that we needed two mentors for each project. Would you
agree to do that with me ?

I'll be glad to do whatever I can for anything related with graph
theory, you can handle the matroids parts if Jernej wants to give it a
try too (good idea !), and because that's one of our common interests
we could also work on some.... Hypergraphs ? I've been willing to
write this for ages but never walked the first step ! If you feel like
working on that, if Jernej feels like working on that too. Otherwise
I'll do it myself someday. I'd love that. There are already plenty of
bisets in my head :-P

I also wanted to implement Binary Decision Diagrams in order to store
hypergraphs... Just another idea.

Tell me what you think ! You too Jernej !

Have fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuun !

Nathann

[Stefan van Zwam]

Hi Nathann, Jernej,

I've been reluctant to step forward as a mentor because to me working
on Sage is a hobby, and when I do it for Google it becomes work. But I
just created an account on GSOC's website to act as a mentor for
Jernej's application and I was just remembering that Harald said at
some point that we needed two mentors for each project. Would you
agree to do that with me ?

That would be fine with me!

 

I'll be glad to do whatever I can for anything related with graph
theory, you can handle the matroids parts if Jernej wants to give it a
try too (good idea !), and because that's one of our common interests
we could also work on some.... Hypergraphs ? I've been willing to
write this for ages but never walked the first step ! If you feel like
working on that, if Jernej feels like working on that too. Otherwise
I'll do it myself someday. I'd love that. There are already plenty of
bisets in my head :-P

Well... I'd rather stick with graphs and matroids: currently I don't think I need hypergraphs in my own research, and needing something is the best drive to producing something good.

--Stefan van Zwam.

[Nathann Cohen]

Heyyyyyyyyyyyyyyy !!

> Well... I'd rather stick with graphs and matroids: currently I don't think I need hypergraphs in my own research, and needing something is the best drive to producing something good.

Ahahah. As you want ! Then I will implement my subhypergraph_search()
method myself. But I'm pretty sure that you will steal it one day for
your matroids ;-)

Nathann