Opened 5 years ago
Closed 5 years ago
#24216 closed enhancement (fixed)
Add crossing number of a graph
Reported by:  Jori Mäntysalo  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  graph theory  Keywords:  
Cc:  David Coudert  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 5 years ago by
Branch:  → u/jmantysalo/crossing_number 

comment:2 Changed 5 years ago by
Commit:  → c2773a69229f4f658abccf697caf313aef0c84bc 

Status:  new → needs_review 
comment:3 followup: 4 Changed 5 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 followup: 6 Changed 5 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 5 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 Changed 5 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 Changed 5 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 5 years ago by
Commit:  c2773a69229f4f658abccf697caf313aef0c84bc → 669bb34dff3f87b76dfb42bd2c1032a450f1ff83 

Branch pushed to git repo; I updated commit sha1. New commits:
669bb34  Reformat testsblock.

comment:9 followup: 10 Changed 5 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 followup: 12 Changed 5 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 5 years ago by
Commit:  669bb34dff3f87b76dfb42bd2c1032a450f1ff83 → 8de878c35236cdc359e163f7e9e4838a74b192ad 

Branch pushed to git repo; I updated commit sha1. New commits:
8de878c  Shortcut for planar graphs.

comment:12 Changed 5 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 5 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 5 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 5 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:17 Changed 5 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 5 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 5 years ago by
Commit:  8de878c35236cdc359e163f7e9e4838a74b192ad → 51fbdbaf3f31bde8c25a993928bbe5bed78870c4 

Branch pushed to git repo; I updated commit sha1. New commits:
51fbdba  Another optimization, bug correction etc.

comment:20 Changed 5 years ago by
Status:  needs_review → 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 5 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:23 Changed 5 years ago by
Commit:  51fbdbaf3f31bde8c25a993928bbe5bed78870c4 → 7ed0501e8e0a8192f7687300fc732bca7ed1ce26 

Branch pushed to git repo; I updated commit sha1. New commits:
7ed0501  Merge branch 'develop' into crossing_number

comment:24 Changed 5 years ago by
Commit:  7ed0501e8e0a8192f7687300fc732bca7ed1ce26 → af2da9ecae0e0bc856ee7e740986d17b7a9a4b52 

Branch pushed to git repo; I updated commit sha1. New commits:
af2da9e  Use blocks_and_cut_vertices().

comment:25 Changed 5 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 5 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 5 years ago by
Commit:  af2da9ecae0e0bc856ee7e740986d17b7a9a4b52 → ddf5d2764a3eae9714160a66716baad611e551cb 

Branch pushed to git repo; I updated commit sha1. New commits:
ddf5d27  Merge branch 'develop' into t/24216/crossing_number

comment:28 Changed 5 years ago by
Commit:  ddf5d2764a3eae9714160a66716baad611e551cb → 344798051ecbd2179d472956b844a9679e66e4e1 

Branch pushed to git repo; I updated commit sha1. New commits:
3447980  Better "unedgesplitting" code.

comment:29 Changed 5 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 5 years ago by
Commit:  344798051ecbd2179d472956b844a9679e66e4e1 → 8b87b5971279186a510ca35342bdb5c4ab7b0367 

Branch pushed to git repo; I updated commit sha1. New commits:
8b87b59  Merge branch 'develop' into t/24216/crossing_number

comment:31 Changed 5 years ago by
Status:  needs_work → needs_review 

Merged, pass tests, needs review.
comment:32 Changed 5 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 5 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 followup: 35 Changed 5 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 Changed 5 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 5 years ago by
Btw, here is another paper on topic: http://www.sciencedirect.com/science/article/pii/S1572528607000497
comment:37 Changed 5 years ago by
Commit:  8b87b5971279186a510ca35342bdb5c4ab7b0367 → 6736953723bcfbf724f64bfe6c2e7f5573d0dade 

Branch pushed to git repo; I updated commit sha1. New commits:
6736953  Merge branch 'develop' into t/24216/crossing_number

comment:38 Changed 5 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 5 years ago by
Status:  needs_review → positive_review 

Those values I could compute coincide with the ones from findstat, so I'll set it to "positive review".
comment:41 Changed 5 years ago by
Reviewers:  → Martin Rubey 

comment:42 Changed 5 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 5 years ago by
Branch:  u/jmantysalo/crossing_number → 6736953723bcfbf724f64bfe6c2e7f5573d0dade 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Add crossing number.