New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
equality of graphs is 60 times slower than equality of their list of edges #30641
Comments
Changed keywords from none to thursdaysbdx |
comment:2
So far, Furthermore, since the switch to Python3, we can no longer rely on sorted list of edges (vertices and edge labels may be of different types, leading to an error when trying to sort the list). One objective is to deprecate this behavior. I think that the only way to speed up the test |
comment:3
The reason why I created this ticket is that I have code which creates a big list of graphs and where I want to remove duplicates. Currently, the program spends more than 50% of its time in graph equality which is ridiculous. |
comment:4
I agree. I recently made a #30510 to speed up method Here, I don't know how to speed up the method without going deep into the backends... |
comment:5
I am fine with "going deep into the backends". My graphs have vertices |
comment:6
Already the edge iterator is pretty slow. It takes 76 µs out 175 for me. |
comment:7
for your code, it could be better to work with immutable graphs.
But of course it would be better to improve the backends to get faster edge iterator, edge membership tests, equality test, etc. |
This comment has been minimized.
This comment has been minimized.
comment:9
I wrote a quick dirty solution that counts compares two vertices at a time and counts how much the out arcs differ. This takes about 34 µs instead of 175 using |
comment:10
I will start with a tiny ticket that does some trivial optimizations for |
comment:13
Nice. Thanks Jonathan for your efforts! I also wonder if we could implement a comparison that would bypass the translation between "vertex labels" and "integers in {0, ..., n-1}". Namely have a comparison of the internal representations (assuming the backend is the same). |
comment:14
Does it make sense ? Currently, we check that the graphs have same settings and sets of vertices and edges. However, the internal representation might differ a lot. Suppose one graph G is the result of many additions/deletions of vertices of edges. Typically, at some point it has 100000 vertices, but at the end of the sequence of operations, it remains only 2. Internal bitsets/data structures might be very large. Now, if H is a copy of G, it has a very compact internal representation. The 2 graphs are equal, but have different internal representations. |
comment:15
That is one use case. Here is another. I am considering all trivalent graphs up to isomorphism on
In order to generate this flip graph, one has to be able to identify the graph after a move. Since canonical labels are computed we need to compare graphs on |
comment:16
I see, not easy to do it efficiently. |
comment:17
To check whether one After this initial step is pretty much the same as #30665. Just that you check If you can guarantee the vertices to match, things should be really fast for dense graphs, but of course only, if you are somewhat dense (e.g. if |
comment:18
Things are improving, I think. IMO what would still improve things here:
So instead of just Does this sound plausible? Does anyone have good suggestions for a naming scheme? |
comment:19
Btw, dense graphs should really use bitsets. I don't understand why it isn't. Eventually this might be sped up with intrinsics. E.g. an iterator over a bitset should be much faster with an improved leading zero count ( |
comment:20
I don't know if it's better to use bitsets for dense graphs. In case, we can use |
comment:21
Replying to @kliem:
This is how
in the sense that I don't know if the naming scheme |
comment:23
Timing with 9.3.beta5 on a macbook air. It seems we are much better now !
|
comment:24
Setting new milestone based on a cursory review of ticket status, priority, and last modification date. |
On sage 9.1
Using immutable graphs is better by a factor 2 (and hence "only" 30x slower than list comparisons)
Depends on #30645
Depends on #30665
Depends on #30776
CC: @kliem @dimpase @dcoudert
Component: graph theory
Keywords: thursdaysbdx
Issue created by migration from https://trac.sagemath.org/ticket/30641
The text was updated successfully, but these errors were encountered: