Opened 11 years ago

Closed 10 years ago

#12917 closed enhancement (fixed)

is_cartesian_product

Reported by: Nathann Cohen Owned by: tbd
Priority: major Milestone: sage-5.2
Component: graph theory Keywords:
Cc: David Joyner, Dima Pasechnik, Rob Beezer Merged in: sage-5.2.beta0
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

This patch implements a new method that lets one recognize whether a graph can be written as the cartesian products of some others. A new module is created because the documentation is rather long, and because the first aim was to write the method much more efficiently, at a much lower level.

As usual, the patch would be much harder to review if it were done all at once, and we would need two versions anyway to check the correction of the trickier algorithm.

The aim of this patch is also to obtain better plots of very symmetrical graphs.

Nathann

Attachments (1)

trac_12917.patch (14.9 KB) - added by Jeroen Demeyer 10 years ago.
Rebased to sage-5.1.rc0

Download all attachments as: .zip

Change History (10)

comment:1 Changed 11 years ago by Nathann Cohen

Component: PLEASE CHANGEgraph theory
Status: newneeds_review
Type: PLEASE CHANGEenhancement

comment:2 Changed 10 years ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewneeds_work

Hello,

I'm unable to install the patch with sage.5.1.beta1.

--- generic_graph.py
+++ generic_graph.py
@@ -13093,25 +13093,33 @@
     def cartesian_product(self, other):
         """
         Returns the Cartesian product of self and other.
-        
+
         The Cartesian product of `G` and `H` is the graph `L` with vertex set
         `V(L)` equal to the Cartesian product of the vertices `V(G)` and `V(H)`,
         and `((u,v), (w,x))` is an edge iff either - `(u, w)` is an edge of
         self and `v = x`, or - `(v, x)` is an edge of other and `u = w`.
-        
-        EXAMPLES::
-        
+
+        .. SEEALSO::
+
+            - :meth:`~sage.graphs.graph_decompositions.graph_products.is_cartesian_product`
+              -- factorization of graphs according to the cartesian product
+
+            - :mod:`~sage.graphs.graph_decompositions.graph_products`
+              -- a module on graph products.
+
+        EXAMPLES::
+
             sage: Z = graphs.CompleteGraph(2)
             sage: C = graphs.CycleGraph(5)
             sage: P = C.cartesian_product(Z); P
             Graph on 10 vertices
             sage: P.plot() # long time
-        
-        ::
-        
+
+        ::
+
             sage: D = graphs.DodecahedralGraph()
             sage: P = graphs.PetersenGraph()
-            sage: C = D.cartesian_product(P); C    
+            sage: C = D.cartesian_product(P); C
             Graph on 200 vertices
             sage: C.plot() # long time
         """

comment:3 Changed 10 years ago by Nathann Cohen

Status: needs_workneeds_review

Updated ! It probably needed a rebase after your patch on graph products got merged ! ;-)

Nathann

comment:4 Changed 10 years ago by David Coudert

Status: needs_reviewpositive_review

The patch is working perfectly (install, tests, functionality, docbuild and display). Nice work!

In another patch, one should do the same for digraphs.

comment:5 Changed 10 years ago by Nathann Cohen

Wouhouuuuuuuu !! Thanks !

I am not sure the algorith would work for digraphs though.. Or it is probably easier, I do not know :-)

Nathann

comment:6 Changed 10 years ago by Jeroen Demeyer

Please fill in your real name in the Author / Reviewer fields.

comment:7 Changed 10 years ago by David Coudert

Authors: Nathann Cohen

comment:8 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.1sage-5.2

Changed 10 years ago by Jeroen Demeyer

Attachment: trac_12917.patch added

Rebased to sage-5.1.rc0

comment:9 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.2.beta0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.