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: |
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)
Change History (22)
comment:1 Changed 10 years ago by
- Cc rlm ncohen added
comment:2 Changed 10 years ago by
- Cc dcoudert added
- Status changed from new to needs_review
comment:3 follow-up: ↓ 4 Changed 10 years ago by
Small modification to allow loops in directed graphs.
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 10 years ago by
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
- 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: ↓ 7 Changed 10 years ago by
- 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: ↓ 8 Changed 10 years ago by
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
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
here it is, sorry.
comment:10 Changed 10 years ago by
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: ↓ 14 Changed 10 years ago by
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.
comment:12 Changed 10 years ago by
- 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
You are welcome !
comment:14 in reply to: ↑ 11 ; follow-up: ↓ 15 Changed 10 years ago by
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
comment:15 in reply to: ↑ 14 ; follow-up: ↓ 18 Changed 10 years ago by
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
- Status changed from positive_review to needs_work
comment:17 Changed 10 years ago by
- Status changed from needs_work to needs_review
This change still needs review.
comment:18 in reply to: ↑ 15 Changed 10 years ago by
- 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
- Status changed from needs_review to positive_review
comment:20 Changed 10 years ago by
- Milestone changed from sage-5.0 to sage-5.1
comment:21 Changed 10 years ago by
- Merged in set to sage-5.1.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
This patch should solve the problem.