# Ticket #12917(closed enhancement: fixed)

Opened 14 months ago

## is_cartesian_product

Reported by: Owned by: ncohen tbd major sage-5.2 graph theory wdj, dimpase, rbeezer N/A David Coudert Nathann Cohen sage-5.2.beta0

### 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

## Change History

### comment:1 Changed 14 months ago by ncohen

• Status changed from new to needs_review
• Type changed from PLEASE CHANGE to enhancement
• Component changed from PLEASE CHANGE to graph theory

### comment:2 Changed 13 months ago by dcoudert

• Status changed from needs_review to needs_work
• Reviewers set to David Coudert

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 13 months ago by ncohen

• Status changed from needs_work to needs_review

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

Nathann

### comment:4 Changed 13 months ago by dcoudert

• Status changed from needs_review to positive_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 13 months ago by ncohen

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 12 months ago by jdemeyer

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

### comment:7 Changed 12 months ago by dcoudert

• Authors set to Nathann Cohen

### comment:8 Changed 12 months ago by jdemeyer

• Milestone changed from sage-5.1 to sage-5.2

### Changed 12 months ago by jdemeyer

Rebased to sage-5.1.rc0

### comment:9 Changed 12 months ago by jdemeyer

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