Opened 10 years ago

Closed 10 years ago

#12770 closed defect (fixed)

cartesian product of directed graphs

Reported by: chapoton Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.1
Component: graph theory Keywords: directed graph, product
Cc: rlm, ncohen, dcoudert Merged in: sage-5.1.beta1
Authors: David Coudert Reviewers: Frédéric Chapoton, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Attachments (1)

trac_12770_cartesian_product.patch (4.7 KB) - added by dcoudert 10 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 10 years ago by dimpase

  • Cc rlm ncohen added

comment:2 Changed 10 years ago by dcoudert

  • Authors set to David Coudert
  • Cc dcoudert added
  • Status changed from new to needs_review

This patch should solve the problem.

comment:3 follow-up: Changed 10 years ago by dcoudert

Small modification to allow loops in directed graphs.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 10 years ago by chapoton

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 ?

comment:5 in reply to: ↑ 4 Changed 10 years ago by dcoudert

  • 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.

comment:6 follow-up: Changed 10 years ago by chapoton

  • 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 ?

comment:7 in reply to: ↑ 6 ; follow-up: Changed 10 years ago by dcoudert

Replying to chapoton:

  • 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.

comment:8 in reply to: ↑ 7 Changed 10 years ago by chapoton

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.

comment:9 Changed 10 years ago by dcoudert

here it is, sorry.

comment:10 Changed 10 years ago by chapoton

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.

comment:11 follow-up: Changed 10 years ago by dcoudert

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.

Last edited 10 years ago by dcoudert (previous) (diff)

comment:12 Changed 10 years ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

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

comment:13 Changed 10 years ago by dcoudert

You are welcome !

comment:14 in reply to: ↑ 11 ; follow-up: Changed 10 years ago by 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!

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.

Changed 10 years ago by dcoudert

comment:15 in reply to: ↑ 14 ; follow-up: Changed 10 years ago by dcoudert

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).

comment:16 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:17 Changed 10 years ago by jdemeyer

  • Status changed from needs_work to needs_review

This change still needs review.

comment:18 in reply to: ↑ 15 Changed 10 years ago by nthiery

  • Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Nicolas M. Thiéry

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.

comment:19 Changed 10 years ago by nthiery

  • Status changed from needs_review to positive_review

comment:20 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-5.0 to sage-5.1

comment:21 Changed 10 years ago by jdemeyer

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