Opened 2 years ago

Closed 23 months ago

#24216 closed enhancement (fixed)

Add crossing number of a graph

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-8.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) 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 2 years ago by jmantysalo

  • Branch set to u/jmantysalo/crossing_number

comment:2 Changed 2 years ago by jmantysalo

  • Commit set to c2773a69229f4f658abccf697caf313aef0c84bc
  • Status changed from new to needs_review

New commits:

c2773a6Add crossing number.

comment:3 follow-up: Changed 2 years ago by mantepse

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 ; follow-up: Changed 2 years ago by jmantysalo

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 follow-ups: Changed 2 years ago by 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.
  • 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 1-core
    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 2 years ago by dcoudert

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 2 years ago by tscrim

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 2 years ago by git

  • Commit changed from c2773a69229f4f658abccf697caf313aef0c84bc to 669bb34dff3f87b76dfb42bd2c1032a450f1ff83

Branch pushed to git repo; I updated commit sha1. New commits:

669bb34Reformat tests-block.

comment:9 in reply to: ↑ 5 ; follow-up: Changed 2 years ago by 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?

  • 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 ; follow-up: Changed 2 years ago by dcoudert

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 2 years ago by git

  • Commit changed from 669bb34dff3f87b76dfb42bd2c1032a450f1ff83 to 8de878c35236cdc359e163f7e9e4838a74b192ad

Branch pushed to git repo; I updated commit sha1. New commits:

8de878cShortcut for planar graphs.

comment:12 in reply to: ↑ 10 Changed 2 years ago by jmantysalo

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 2 years ago by dcoudert

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 2 years ago by jmantysalo

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 2 years ago by dcoudert

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 2 years ago by jmantysalo

Sorry, my bad. I'll check this.

comment:17 Changed 2 years ago by jmantysalo

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 part-relation -diagram where most important relations would be seen as edges with more weight.)

comment:18 Changed 2 years ago by dcoudert

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 2 years ago by git

  • Commit changed from 8de878c35236cdc359e163f7e9e4838a74b192ad to 51fbdbaf3f31bde8c25a993928bbe5bed78870c4

Branch pushed to git repo; I updated commit sha1. New commits:

51fbdbaAnother optimization, bug correction etc.

comment:20 Changed 2 years ago by jmantysalo

  • 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 2 years ago by jmantysalo

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 non-connected graphs separately.

After separating blocks we must only do the optimization of shrinking some edges.

comment:22 Changed 2 years ago by dcoudert

Right, you can consider blocks of size > 4 only.

comment:23 Changed 2 years ago by git

  • Commit changed from 51fbdbaf3f31bde8c25a993928bbe5bed78870c4 to 7ed0501e8e0a8192f7687300fc732bca7ed1ce26

Branch pushed to git repo; I updated commit sha1. New commits:

7ed0501Merge branch 'develop' into crossing_number

comment:24 Changed 2 years ago by git

  • Commit changed from 7ed0501e8e0a8192f7687300fc732bca7ed1ce26 to af2da9ecae0e0bc856ee7e740986d17b7a9a4b52

Branch pushed to git repo; I updated commit sha1. New commits:

af2da9eUse blocks_and_cut_vertices().

comment:25 Changed 2 years ago by jmantysalo

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 non-connected graphs.

When doing this I also broke #24163, got to see how to undo changes... arghs.

comment:26 follow-up: Changed 2 years ago by dcoudert

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 2 years ago by git

  • Commit changed from af2da9ecae0e0bc856ee7e740986d17b7a9a4b52 to ddf5d2764a3eae9714160a66716baad611e551cb

Branch pushed to git repo; I updated commit sha1. New commits:

ddf5d27Merge branch 'develop' into t/24216/crossing_number

comment:28 Changed 2 years ago by git

  • Commit changed from ddf5d2764a3eae9714160a66716baad611e551cb to 344798051ecbd2179d472956b844a9679e66e4e1

Branch pushed to git repo; I updated commit sha1. New commits:

3447980Better "un-edgesplitting" code.

comment:29 in reply to: ↑ 26 Changed 2 years ago by jmantysalo

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_review-phase.

...Graph thickness would be logical next step.

comment:30 Changed 23 months ago by git

  • Commit changed from 344798051ecbd2179d472956b844a9679e66e4e1 to 8b87b5971279186a510ca35342bdb5c4ab7b0367

Branch pushed to git repo; I updated commit sha1. New commits:

8b87b59Merge branch 'develop' into t/24216/crossing_number

comment:31 Changed 23 months ago by jmantysalo

  • Status changed from needs_work to needs_review

Merged, pass tests, needs review.

comment:32 Changed 23 months ago by mantepse

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 follow-up: Changed 23 months ago by jmantysalo

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 NP-complete. But if you want more speed, try to use automorphisms of the graph.

comment:34 in reply to: ↑ 33 ; follow-up: Changed 23 months ago by mantepse

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 23 months ago by jmantysalo

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 k-1. (And k-2 and k-3 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 k-1 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 23 months ago by jmantysalo

comment:37 Changed 23 months ago by git

  • Commit changed from 8b87b5971279186a510ca35342bdb5c4ab7b0367 to 6736953723bcfbf724f64bfe6c2e7f5573d0dade

Branch pushed to git repo; I updated commit sha1. New commits:

6736953Merge branch 'develop' into t/24216/crossing_number

comment:38 Changed 23 months ago by jmantysalo

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:

6736953Merge branch 'develop' into t/24216/crossing_number

comment:39 Changed 23 months ago by mantepse

  • 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 23 months ago by chapoton

reviewer's name, please

comment:41 Changed 23 months ago by mantepse

  • Reviewers set to Martin Rubey

comment:42 Changed 23 months ago by dcoudert

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 23 months ago by vbraun

  • Branch changed from u/jmantysalo/crossing_number to 6736953723bcfbf724f64bfe6c2e7f5573d0dade
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.