cartesian product of directed graphs

[fchapoton]

The Cartesian product of directed graphs does not work. For example

sage: P=DiGraph([[0,1]])          
sage: Q=P.cartesian_product(P)
sage: len(Q.edges())         
0

The result is a disconnected union of 4 points.
This should be a commutative square, with 4 edges.

CC: @rlmill @nathanncohen @dcoudert

Component: graph theory

Keywords: directed graph, product

Author: David Coudert

Reviewer: Frédéric Chapoton, Nicolas M. Thiéry

Merged: sage-5.1.beta1

Issue created by migration from https://trac.sagemath.org/ticket/12770

[dcoudert]

Author: David Coudert

[dcoudert]

comment:2

This patch should solve the problem.

[dcoudert]

comment:3

Small modification to allow loops in directed graphs.

[fchapoton]

comment:4

Replying to @dcoudert:

Small modification to allow loops in directed graphs.

• It would be better if the examples given check something else than the fact that the number of vertices is correct. One can for example count the edges.

• Maybe remove the plot in the examples, which has not much to do there.

• Maybe check the commutativity of the product

• Maybe it would be good to have a test with loops ?

[dcoudert]

comment:5

• It would be better if the examples given check something else than the fact that the number of vertices is correct. One can for example count the edges.

• Maybe remove the plot in the examples, which has not much to do there.

It was original examples. I removed them. They are not so useful.

• Maybe check the commutativity of the product

Already done with is_isomorphic tests.

• Maybe it would be good to have a test with loops ?

I added a test with loops: small De Bruijn product an arc. The resulting digraph contains 2 copies of the debruijn and arcs from vertices in one copy to corresponding vertex in other copy.

Should be better now.

[fchapoton]

comment:6

• I would rather keep a short examples section, with a very simple example, just to display the syntax.

• I would like the following sentence

raise TypeError('Both arguments must be of the same class.')

to be more precise : 'The graphs should be both directed or both undirected.'

• Maybe one should correct similarly also tensor_product, which seems to fail for digraphs too ?

[dcoudert]

comment:7

Replying to @fchapoton:

• I would rather keep a short examples section, with a very simple example, just to display the syntax.

Since the tests are displayed both in the documentation and in the g.cartesian_product? page, I don't see the need for a specific example section that will have similar stuff than the tests section.

• I would like the following sentence raise TypeError ('Both arguments must be of the same class.') to be more precise : 'The graphs should be both directed or both undirected.'

Done in new version.

• Maybe one should correct similarly also tensor_product, which seems to fail for digraphs too ?

Done in patch #12791.

[fchapoton]

comment:8

Replying to @dcoudert:

• I would like the following sentence raise TypeError ('Both arguments must be of the same class.') to be more precise : 'The graphs should be both directed or both undirected.'

Done in new version.

Please upload the new version, and I will give a positive review.

[dcoudert]

comment:9

here it is, sorry.

[fchapoton]

comment:10

According to Nicolas Thiery :

Once the graph G is created, the whole end of this method would be
best rewritten as something like:

    G.add_vertices( (u,v) for u in self.vertex_iterator() for v in        other.vertex_iterator() )
    G.add_edges( ((u,v), (u1,v)) for (u,u1) in self .edge_iterator() for v in other.vertex_iterator() )
    G.add_edges( ((u,v), (u,v1)) for (v,v1) in other.edge_iterator() for u in self .vertex_iterator() )

I do not know if this is better, in any way, than what you wrote. Maybe faster ?

If you do not want to spend more time on this ticket, I can give a positive review for the current patch.

[dcoudert]

comment:11

Unfortunately your proposal is slower than the implementation of this patch.

With this patch:

sage: g = graphs.GridGraph([10,10]); g
Grid Graph for []: Graph on 100 vertices
sage: h = graphs.CubeGraph(8); h
8-Cube: Graph on 256 vertices
sage: %timeit gg = g.cartesian_product(h)
5 loops, best of 3: 1.31 s per loop
sage: %timeit gg = h.cartesian_product(g)
5 loops, best of 3: 1.31 s per loop

With your proposal on the same graphs:

sage: %timeit gg = g.cartesian_product(h)
5 loops, best of 3: 1.9 s per loop
sage: %timeit gg = h.cartesian_product(g)
5 loops, best of 3: 1.9 s per loop

So I propose to stay with current implementation.

[fchapoton]

comment:12

ok, I give a positive review. Thanks for your work.

[fchapoton]

Reviewer: Frédéric Chapoton

[dcoudert]

comment:13

You are welcome !

[nthiery]

comment:14

Replying to @dcoudert:

Unfortunately your proposal is slower than the implementation of this patch.

Interesting that calling repeatedly add_edge is faster than add_edges!

I am fine with the current implementation, though maybe using edge_iterator would be faster, since the former does a sort (which I don't like but that's another story). I let you see if you want to do that.

[dcoudert]

Attachment: trac_12770_cartesian_product.patch.gz

[dcoudert]

comment:15

Replying to @nthiery:

Replying to @dcoudert:

Unfortunately your proposal is slower than the implementation of this patch.

Interesting that calling repeatedly add_edge is faster than add_edges!

The point is that using add_edges, we first create a new list of edges, and then iterate this list to add edges to the new graph. So somehow we do the job twice. My tests suggest that current implementation is a bit faster.

I am fine with the current implementation, though maybe using edge_iterator would be faster, since the former does a sort (which I don't like but that's another story). I let you see if you want to do that.

I have changed the patch to use the edge_iterator. It is now slightly faster (few ms less on large graphs).

[jdemeyer]

comment:17

This change still needs review.

[nthiery]

Changed reviewer from Frédéric Chapoton to Frédéric Chapoton, Nicolas M. Thiéry

[nthiery]

comment:18

Replying to @dcoudert:

The point is that using add_edges, we first create a new list of edges, and then iterate this list to add edges to the new graph.

Actually the code did not create a list: just an iterator over those edges. But it might well be that using an iterator induces some overhead.

So somehow we do the job twice. My tests suggest that current implementation is a bit faster.

A good reason :-)

I have changed the patch to use the edge_iterator. It is now slightly faster (few ms less on large graphs).

Thanks! Positive review.

[jdemeyer]

Merged: sage-5.1.beta1