Opened 4 years ago
Closed 4 years ago
#24216 closed enhancement (fixed)
Add crossing number of a graph
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Martin Rubey 
Report Upstream:  N/A  Work issues:  
Branch:  6736953 (Commits, GitHub, GitLab)  Commit:  6736953723bcfbf724f64bfe6c2e7f5573d0dade 
Dependencies:  Stopgaps: 
Description
This patch adds a function to compute the crossing number of a graph.
Implementation is slow and unusable for most graphs, but then, so is genus()
already. And it is easier to make better code when we have any reference code to compare results.
Change History (43)
comment:1 Changed 4 years ago by
 Branch set to u/jmantysalo/crossing_number
comment:2 Changed 4 years ago by
 Commit set to c2773a69229f4f658abccf697caf313aef0c84bc
 Status changed from new to needs_review
comment:3 followup: ↓ 4 Changed 4 years ago by
Hi Joris!
I suspect that this is http://www.findstat.org/StatisticsDatabase/St000323, right? If so, you might want to contact Markus Chimani.
comment:4 in reply to: ↑ 3 ; followup: ↓ 6 Changed 4 years ago by
Replying to mantepse:
I suspect that this is http://www.findstat.org/StatisticsDatabase/St000323, right? If so, you might want to contact Markus Chimani.
So we could implement https://arxiv.org/pdf/1612.03854.pdf, maybe. Maybe I take a look of those later, but for now I think that this code could be a little useful addition.
comment:5 followups: ↓ 7 ↓ 9 Changed 4 years ago by
Hello,
I agree that your code do the job and is not optimized.
 This is not a good idea to use
sage: C4 = graphs.CompleteGraph(4) # Planar
as the# blah
are often used for special treatments, e.g.,# long time
or# optional  bliss
. It's more usual to have a full sentence before the test.
 You could add a test for trivial graphs and planar graphs
 You can do better for degree 1 vertices since you want to keep the 1core
one = self.cores(k=1)[0] if one: G = Graph(self.edges()) G.delete_vertices(one) else: G = self
 For degree 2, it's easier
two = [u for u in G if G.degree(u) == 2] if two: if G is self: G = self.copy() for u in two: v,w = G.neighbors(u) G.add_edge(v, w) G.delete_vertex(u)
 I realize that your
edgepairs
are in fact (but this might be slower to produce. Don't know):edgepairs = [Set(e) for e in G.line_graph(labels=0).complement().edge_iterator(labels=0)]
 for the while loop, I don't see how to make it faster.
comment:6 in reply to: ↑ 4 Changed 4 years ago by
So we could implement https://arxiv.org/pdf/1612.03854.pdf, maybe. Maybe I take a look of those later, but for now I think that this code could be a little useful addition.
It's for graphs with pathwidth 3. Not sure it's easy to implement or fast...
This paper Computing crossing number in linear time is promising. I don't know if it has already been implemented .
An ILP formulation could also be a good addition (for another ticket).
comment:7 in reply to: ↑ 5 Changed 4 years ago by
Replying to dcoudert:
Hello,
I agree that your code do the job and is not optimized.
 This is not a good idea to use
sage: C4 = graphs.CompleteGraph(4) # Planar
as the# blah
are often used for special treatments, e.g.,# long time
or# optional  bliss
. It's more usual to have a full sentence before the test.
There can be good reason to add a comment to a single line like that in a doctest where a full description is not ideal. So I would not say it is not a good idea (in general), although the latter is more common. However, in this case, I do think it better to have
Check for a planar graph:: sage: C4 = graphs.CompleteGraph(4) sage: C4.crossing_number() 0
comment:8 Changed 4 years ago by
 Commit changed from c2773a69229f4f658abccf697caf313aef0c84bc to 669bb34dff3f87b76dfb42bd2c1032a450f1ff83
Branch pushed to git repo; I updated commit sha1. New commits:
669bb34  Reformat testsblock.

comment:9 in reply to: ↑ 5 ; followup: ↓ 10 Changed 4 years ago by
Replying to dcoudert:
I modified TESTS
and will do more changes. Two questions:
 You could add a test for trivial graphs and planar graphs
In the code or as a test?
 For degree 2, it's easier
But for example Graph('FhEK_')
will be reduced to the empty graph with iterative process.
(What we could do is to use automorphisms, but maybe it's not worth doing now.)
comment:10 in reply to: ↑ 9 ; followup: ↓ 12 Changed 4 years ago by
Replying to jmantysalo:
Replying to dcoudert:
I modified
TESTS
and will do more changes. Two questions:
 You could add a test for trivial graphs and planar graphs
In the code or as a test?
In the code. When it's trivial or low cost to answer, we should do it.
 For degree 2, it's easier
But for example
Graph('FhEK_')
will be reduced to the empty graph with iterative process.
Are you sure of that ? since you allow multiple edges, you will get a triple edge and no further reduction.
You raise an interesting point: if you forbid multiedges, then you can reduce further.
The preprocessing could be
two = {u for u in G if G.degree(u) == 2} while two: if two and G is self: G = self.copy() while two: u = two.pop() if G.degree(u) < 2: if G.degree(u) == 1: two.add(next(G.neighbor_iterator(u))) G.delete_vertex(u) continue v,w = G.neighbors(u) G.add_edge(v, w) G.delete_vertex(u) if G.degree(v) <= 2: two.add(v) if G.degree(w) <= 2: two.add(w)
comment:11 Changed 4 years ago by
 Commit changed from 669bb34dff3f87b76dfb42bd2c1032a450f1ff83 to 8de878c35236cdc359e163f7e9e4838a74b192ad
Branch pushed to git repo; I updated commit sha1. New commits:
8de878c  Shortcut for planar graphs.

comment:12 in reply to: ↑ 10 Changed 4 years ago by
Replying to dcoudert:
 You could add a test for trivial graphs and planar graphs
In the code or as a test?
In the code. When it's trivial or low cost to answer, we should do it.
I added a test for planar graph.
Are you sure of that ? since you allow multiple edges, you will get a triple edge and no further reduction.
?? There is _scream_if_not_simple()
in the code.
You raise an interesting point: if you forbid multiedges, then you can reduce further.
I will do some timings with reduction. In any case it won't help much, as most of the time is used to check planarity. Doing this closely tied with planarity.pyx
could do more, maybe.
comment:13 Changed 4 years ago by
Concerning the reduction steps for vertices of degree 2. Take a K5, double the edges and subdivide them. What's the crossing number ? I suspect that reduction steps should be done more carefully...
This is not correct, right ?
sage: G = graphs.CompleteGraph(5) sage: G.allow_multiple_edges(True) sage: G.add_edges(G.edges()) sage: G.subdivide_edges(G.edges(),1) sage: G.allow_multiple_edges(False) sage: G.crossing_number() 1
comment:14 Changed 4 years ago by
It the last example you intentionally break things. Same happens with other functons, like
sage: g = Graph({0: [1]}) sage: g.allow_multiple_edges(True) sage: g.subdivide_edges(g.edges(), 1) sage: g.allow_multiple_edges(False) sage: g.graph6_string() 'BW' sage: g.allow_multiple_edges(True) sage: g.graph6_string()  ValueError Traceback (most recent call last)
comment:15 Changed 4 years ago by
I'm not breaking things at all. What I wrote is equivalent to:
sage: K5 = graphs.CompleteGraph(5) sage: H = Graph() sage: H.add_vertices(K5.vertices()) sage: for u,v in K5.edges(labels=0): ....: H.add_path([u,H.add_vertex(),v]) ....: H.add_path([u,H.add_vertex(),v]) ....: sage: H.is_isomorphic(G) True
comment:16 Changed 4 years ago by
Sorry, my bad. I'll check this.
comment:17 Changed 4 years ago by
Random thought: we can allow loops, as they do nothing to the crossing number. We can allow multiedges, as the definition can be applied to those too.
What about weighted graphs? We could even support those, but there are at least three definitions: for every crossing we can take smaller weight, bigger weight or sum of both edges, and try to minimize the sum of those.
(A natural use would be a partrelation diagram where most important relations would be seen as edges with more weight.)
comment:18 Changed 4 years ago by
Right, we can accept loops. For multiple edges, we have to find a way to handle them without excessively increasing the number of subsets to test. For weighted graph, it seems much more complicated, so we could let them for another ticket. Let's first try to have a method working for unweighted graphs.
comment:19 Changed 4 years ago by
 Commit changed from 8de878c35236cdc359e163f7e9e4838a74b192ad to 51fbdbaf3f31bde8c25a993928bbe5bed78870c4
Branch pushed to git repo; I updated commit sha1. New commits:
51fbdba  Another optimization, bug correction etc.

comment:20 Changed 4 years ago by
 Status changed from needs_review to needs_work
Here is a code that should work, and has yet another optimization: remove uninteresting cycles, i.e. blocks where only one vertex has degree greater than two.
Timings for some minor optimizations are still to do.
comment:21 Changed 4 years ago by
And still more thinking: Isn't the crossing number just the sum of crossing numbers of blocks, that we can compute with blocks_and_cut_vertices()
? And after #24163 there is no need to check nonconnected graphs separately.
After separating blocks we must only do the optimization of shrinking some edges.
comment:22 Changed 4 years ago by
Right, you can consider blocks of size > 4 only.
comment:23 Changed 4 years ago by
 Commit changed from 51fbdbaf3f31bde8c25a993928bbe5bed78870c4 to 7ed0501e8e0a8192f7687300fc732bca7ed1ce26
Branch pushed to git repo; I updated commit sha1. New commits:
7ed0501  Merge branch 'develop' into crossing_number

comment:24 Changed 4 years ago by
 Commit changed from 7ed0501e8e0a8192f7687300fc732bca7ed1ce26 to af2da9ecae0e0bc856ee7e740986d17b7a9a4b52
Branch pushed to git repo; I updated commit sha1. New commits:
af2da9e  Use blocks_and_cut_vertices().

comment:25 Changed 4 years ago by
I did some timing tests, but did not get noticeable speedup from using line_graph()
etc. Hence I think this is reade when blocks_and_cut_vertices
will handle nonconnected graphs.
When doing this I also broke #24163, got to see how to undo changes... arghs.
comment:26 followup: ↓ 29 Changed 4 years ago by
As I already said, I would do the following. Indeed, when add an edge between the neighbors of v and then remove v from the graph, you don't change the degree of u and w. So you don't create new vertex of degree 2.
 while True:  for v in G:  if G.degree(v) == 2:  if not G.has_edge(G.neighbors(v)):  G.add_edge(G.neighbors(v))  G.delete_vertex(v)  break  else:  break + two = [v for v in G if G.degree(v) == 2] + for v in two: + u,w = G.neighbors(v) + if not G.has_edge(u, w): + G.add_edge(u, w) + G.delete_vertex(v)
Other modifications are very good and the code is simpler and certainly more efficient now.
comment:27 Changed 4 years ago by
 Commit changed from af2da9ecae0e0bc856ee7e740986d17b7a9a4b52 to ddf5d2764a3eae9714160a66716baad611e551cb
Branch pushed to git repo; I updated commit sha1. New commits:
ddf5d27  Merge branch 'develop' into t/24216/crossing_number

comment:28 Changed 4 years ago by
 Commit changed from ddf5d2764a3eae9714160a66716baad611e551cb to 344798051ecbd2179d472956b844a9679e66e4e1
Branch pushed to git repo; I updated commit sha1. New commits:
3447980  Better "unedgesplitting" code.

comment:29 in reply to: ↑ 26 Changed 4 years ago by
Replying to dcoudert:
As I already said, I would do the following.  
I think I tried that and got errors. But now it works and I see no error in the code, so I must have made some trivial copypaste error.
So, now I just wait until 8.2 or 8.3beta1 to get out, and then put this to need_reviewphase.
...Graph thickness would be logical next step.
comment:30 Changed 4 years ago by
 Commit changed from 344798051ecbd2179d472956b844a9679e66e4e1 to 8b87b5971279186a510ca35342bdb5c4ab7b0367
Branch pushed to git repo; I updated commit sha1. New commits:
8b87b59  Merge branch 'develop' into t/24216/crossing_number

comment:31 Changed 4 years ago by
 Status changed from needs_work to needs_review
Merged, pass tests, needs review.
comment:32 Changed 4 years ago by
I checked with findstat's values for all graphs of at most 6 vertices.
I am currently checking for which graphs it takes a long time to compute the crossing number. For 6 vertices, only the complete graph takes (much) longer than all the others.
For 7 vertices, the graph with edges
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 6), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]
seems to be quite bad (it is still computing on this one...)
comment:33 followup: ↓ 34 Changed 4 years ago by
For biconnected graphs with same crossing number the speed should be exponential to the number of edges. As I wrote in the description: "Implementation is slow and unusable for most graphs  ".
This has been proven to be NPcomplete. But if you want more speed, try to use automorphisms of the graph.
comment:34 in reply to: ↑ 33 ; followup: ↓ 35 Changed 4 years ago by
Sorry, I should have said first that what I wrote is just a comment, it might or might not be helpful or interesting. So, from my part positive review
, but since I am neither an expert in graph theory nor very familiar with sage, I think it's better if someone else does it.
What made me curious is that for 6 vertices, there are 112 connected graphs, and only the complete graph needs more time (25 times longer than the second worst).
Also, removing the edge (3,6)
from the graph above (still biconnected), the crossing number is computed in almost no time (1.5 seconds), whereas the crossing number of the other graph is still not determined... (according to findstat it should be 5)
comment:35 in reply to: ↑ 34 Changed 4 years ago by
Replying to mantepse:
What made me curious is that for 6 vertices, there are 112 connected graphs, and only the complete graph needs more time (25 times longer than the second worst).
The crossing number of K_6
is "strictly 3", removing any edge will make it 2. That explains what you noticed.
For a (biconnected) graph of crossing number k
the code will check every possibility to add crossing points to have crossing number k1
. (And k2
and k3
etc, but they take so less time that it does not make real difference.) I do not know any other way to check the crossing number not being k1
than trying all possibilities after using automorphism.
But it may be that there is a heuristic to find faster a solution for crossing number k
. Maybe selecting edges so that the distance between their end vertices is so big as possible, or so small as possible, or something else.
So, there are two possible optimizations to use. They are very different, and each one can be used without the other.
comment:36 Changed 4 years ago by
Btw, here is another paper on topic: http://www.sciencedirect.com/science/article/pii/S1572528607000497
comment:37 Changed 4 years ago by
 Commit changed from 8b87b5971279186a510ca35342bdb5c4ab7b0367 to 6736953723bcfbf724f64bfe6c2e7f5573d0dade
Branch pushed to git repo; I updated commit sha1. New commits:
6736953  Merge branch 'develop' into t/24216/crossing_number

comment:38 Changed 4 years ago by
Anyways, I think this can be reviewed now, and we can think about better algorithms later.
I also merged this to the latest beta.
New commits:
6736953  Merge branch 'develop' into t/24216/crossing_number

comment:39 Changed 4 years ago by
 Status changed from needs_review to positive_review
Those values I could compute coincide with the ones from findstat, so I'll set it to "positive review".
comment:40 Changed 4 years ago by
reviewer's name, please
comment:41 Changed 4 years ago by
 Reviewers set to Martin Rubey
comment:42 Changed 4 years ago by
Sorry for not helping finalizing the review. I was away from email for a few days. I'm fine with the ticket. Thank you.
comment:43 Changed 4 years ago by
 Branch changed from u/jmantysalo/crossing_number to 6736953723bcfbf724f64bfe6c2e7f5573d0dade
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Add crossing number.