Opened 8 years ago

Closed 7 years ago

#12306 closed enhancement (fixed)

Static sparse graphs for fast low-level computations

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords: Cernay2012
Cc: dcoudert Merged in: sage-5.0.beta5
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12235 Stopgaps:

Description

Helloooooo !!

This extensively documented module implements a very basic data structure for graphs that is helpful for *EFFICIENT* implementations. It was actually used by Sage already in sage.graphs.distances_all_pairs, but it is better to have a proper documentation for such things.

And of course, this does not solve the current lack of a Python-level static graph class, that would handle loops/multiedges and labels... It will come, though :-)

Nathann

Attachments (2)

trac_12306_doc.patch (13.0 KB) - added by ncohen 7 years ago.
trac_12306.patch (28.4 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by dcoudert

I'm unable to install the patch on sage-5.0.beta1.

File digraph.py.rej:

--- digraph.py
+++ digraph.py
@@ -2565,18 +2574,24 @@
 
         TESTS:
 
-        Checking against NetworkX::
-
+        Checking against NetworkX, and another of Sage's implementations::
+
+            sage: from sage.graphs.base.static_sparse_graph import strongly_connected_components
             sage: import networkx
             sage: for i in range(100):                                     # long
             ...        g = digraphs.RandomDirectedGNP(100,.05)             # long
             ...        h = g.networkx_graph()                              # long
             ...        scc1 = g.strongly_connected_components()            # long
             ...        scc2 = networkx.strongly_connected_components(h)    # long
+            ...        scc3 = strongly_connected_components(g)             # long
             ...        s1 = Set(map(Set,scc1))                             # long
             ...        s2 = Set(map(Set,scc2))                             # long
+            ...        s3 = Set(map(Set,scc3))                             # long
             ...        if s1 != s2:                                        # long
             ...            print "Ooch !"                                  # long
+            ...        if s1 != s3:                                        # long
+            ...            print "Oooooch !"                               # long
+
         """
 
         try:

comment:3 Changed 7 years ago by ncohen

Oopps.. This patch needs #12235 to be applied first, though it is now merged with beta2 :-)

Nathann

comment:4 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert

I can now install the patch with sage-5.0.beta2.

No compilation error. Generation of the documentation is OK.

However, can you improve in section What does it take as input? the n^2sizeof(...) and the nsizeof(...). For instance you can add a \cdot between n and sizeof(...).

For functions returning a dictionnary of dictionnary, you should add an extra warning recalling that such structures are huge. I'm not sure most of us can use this for graphs with 10.000 nodes.

Best,

D.

comment:5 Changed 7 years ago by ncohen

  • Keywords Cernay2012 added

Here it is !!! :-)

I also removed some trailing whitespaces, as I learned here that they were evil :-P

Nathann

Changed 7 years ago by ncohen

comment:6 follow-up: Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

I can install both patch correctly and the documentation is now well presented and with enough details.

Good work !

D.

PS: what's the relation between this patch and the Cernay 2012 Music Festival ? ;-)

comment:7 in reply to: ↑ 6 Changed 7 years ago by ncohen

PS: what's the relation between this patch and the Cernay 2012 Music Festival ? ;-)

Some snow, and around 10 people in a tower coding Sage patches on their computers :-)

http://wiki.sagemath.org/combinat/SageCombinatDaysCernay2012

Nathann

comment:8 Changed 7 years ago by jdemeyer

  • Dependencies changed from 12235 to #12235

comment:9 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Please fix the commit message of the first patch.

Changed 7 years ago by ncohen

comment:10 Changed 7 years ago by ncohen

  • Status changed from needs_work to positive_review

Gloops... Done ! ^^;

Nathann

comment:11 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.