Opened 4 years ago
Closed 3 years ago
#25891 closed enhancement (fixed)
Implementing generators for Hamming graphs, Egawa graphs and CaiFurerImmerman graphs
Reported by:  Vaush  Owned by:  

Priority:  minor  Milestone:  sage8.4 
Component:  graph theory  Keywords:  gsoc2018 generators Cai Furer Immerman Egawa Hamming 
Cc:  dimpase  Merged in:  
Authors:  Dario Asprone  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  1cdaa3f (Commits, GitHub, GitLab)  Commit:  1cdaa3f1fa4bd39ca846ec5560bd6b887dc78aaf 
Dependencies:  Stopgaps: 
Description (last modified by )
Adding generators for the following graph families:
Egawa graphs, which are not recognizable by kWeisfeilerLehman with k < 3, described in https://doi.org/10.1016/00973165(81)900078
Hamming graphs, which are Egawa graphs cospectral mates, and with a subset being isomorphic to them. More information at https://en.wikipedia.org/wiki/Hamming_graph
CaiFurerImmerman graphs, a family of graphs that is built based on another starting graph G. When the starting graph G doesn't have any balanced vertex separator with cardinality less than k+1, kWeisfeiler Lehman can't distinguish the generated CaiFurerImmerman graph and its twisted version, as described in http://people.mpiinf.mpg.de/~pascal/docs/thesis_pascal_schweitzer.pdf . The original paper that describes them can be found at https://doi.org/10.1007/BF01305232
Change History (49)
comment:1 Changed 4 years ago by
 Branch set to u/Vaush/HammingGraphs_EgawaGraphs_CaiGraphs
comment:2 Changed 4 years ago by
 Commit set to 335a794eb4b1dc5371ed58df795f89930a00b793
comment:3 Changed 4 years ago by
I added new files so that the code could be put in .pyx files and be compiled, and also use static typing to improve efficiency, since this graphs get very large very fast, and I wanted to speed the generation up a bit. What would be the best way to do this then?
As per the merged ticket, it's an error, I was testing something and merged it, but wanted to revert the merge before pushing, and I forgot to do it.
I'll fix it ASAP
comment:4 Changed 4 years ago by
I tried saving the CaiFurerImmermanGraph
in a python file and in a cython file to see if it is more efficient. Honestly, the differnce is not big enough to justify adding a new cython file (and in particular a 10 lines cython file).
sage: %timeit CaiFurerImmermanGraph_pyx(18) 1 loop, best of 3: 6.5 s per loop sage: %timeit CaiFurerImmermanGraph_py(18) 1 loop, best of 3: 6.86 s per loop
Note that you can write:
powerset = list(chain.from_iterable(combinations(range(k), r) for r in range(0, k+1, 2)))
I have not tried the EgawaGraph
or the HammingGraph
, but it should be exactly the same.
In input parameters of methods, avoid X=[]
and prefer X=None
.
comment:5 Changed 4 years ago by
I was talking about the other graphs, since for Egawa even (0,10) gives millions of nodes and edges. I'll change the rest as soon as I get home
comment:6 Changed 4 years ago by
How much memory you need for a graph with millions on vertices/edges in python ? What can we do with it ? Beyond a certain size, I usually use C/C++ code only: more efficient and reasonable memory consumption.
comment:7 Changed 4 years ago by
I suppose a lot of memory, but the reason I didn't put a limit to the parameter is for the sake of completeness, and I used the .pyx files to speed up generations.
I don't actually have a use for the graphs outside of performance testing for my implementation of the WeisfeilerLehman algorithm, so if you think using additional files to speed up generation is not worth it, I'll just move them to the normal .py file.
comment:8 Changed 4 years ago by
I think that fast generation has its merit. I'd start something like families_fast.pyx and start collecting such implementations there.
comment:9 Changed 4 years ago by
I agree that fast generation is very interesting, but here the speedup is less than 2%...
Note that we already have file src/sage/graphs/graph_generators_pyx.pyx
for this purpose.
comment:10 Changed 4 years ago by
 Commit changed from 335a794eb4b1dc5371ed58df795f89930a00b793 to d14ebad6ad135ecb2c07eff6c8ea3f495c0e38d1
Branch pushed to git repo; I updated commit sha1. New commits:
5a86f2e  Family of graphs I

f43a2f6  Hamming graphs

323b9f0  Improved efficiency and implemented the generators in cython

2eb47b1  Implemented a CaiFurerImmerman graphs generator

6187fb6  Added documentation. TODO: verify CaiFurerImmermanGraph implementation

d14ebad  Removed .pyx implementation, moved it to the common .py file for graph families generator

comment:11 Changed 4 years ago by
Ok, everything you asked is done. Anyway, about the implementation, there's basically no speedup because the code for CaiFurerImmerman? graphs is not yet optimised at all for Cython compilation, it's just a small sequence of itertools results passed to the methods of a Graph object.
In other cases, such as the Egawa graphs, it's quite more significant:
sage: %timeit EG_py(0,8) 1 loop, best of 3: 5.69 s per loop sage: %timeit EG_pyx(0,8) 1 loop, best of 3: 3.91 s per loop
Which is not a lot, but still around 31%.
I didn't use the src/sage/graphs/graph_generators_pyx.pyx
simply because there's only one method for a common random (di)graph, so I wasn't sure putting family generators there was inteneded usage.
comment:12 Changed 4 years ago by
 Description modified (diff)
comment:13 Changed 3 years ago by
 Description modified (diff)
comment:14 Changed 3 years ago by
 Description modified (diff)
comment:15 Changed 3 years ago by
 Commit changed from d14ebad6ad135ecb2c07eff6c8ea3f495c0e38d1 to 0f14c03aac747ff8d70a874e6b2fd4db6750e597
comment:16 followup: ↓ 19 Changed 3 years ago by
I noticed that in file graph_generators.py
you did changes like
########################################################################### # Random Graphs ########################################################################### + ########################################################################### + # Random Graphs + ###########################################################################
I don't understand the motivation for that.
comment:17 Changed 3 years ago by
 Commit changed from 0f14c03aac747ff8d70a874e6b2fd4db6750e597 to e18db39ce5f84fbc4977ed6ac5fb76e67c2914e9
Branch pushed to git repo; I updated commit sha1. New commits:
e18db39  Fixed indentation error

comment:18 Changed 3 years ago by
 Commit changed from e18db39ce5f84fbc4977ed6ac5fb76e67c2914e9 to aa7d7b85b98cf8aa01f593a2ce6619e6595a716a
Branch pushed to git repo; I updated commit sha1. New commits:
5a86f2e  Family of graphs I

f43a2f6  Hamming graphs

323b9f0  Improved efficiency and implemented the generators in cython

2eb47b1  Implemented a CaiFurerImmerman graphs generator

6187fb6  Added documentation. TODO: verify CaiFurerImmermanGraph implementation

d14ebad  Removed .pyx implementation, moved it to the common .py file for graph families generator

9432850  Adding partitioning to CaiFurerImmerman graphs

aa7d7b8  Fixed CaiFurerImmerman graphs generator, adding an actual generator for them and moving the Furer gadget generator to another method

comment:19 in reply to: ↑ 16 Changed 3 years ago by
Replying to dcoudert:
I noticed that in file
graph_generators.py
you did changes like########################################################################### # Random Graphs ########################################################################### + ########################################################################### + # Random Graphs + ###########################################################################I don't understand the motivation for that.
I'm not really sure. It surely wasn't intentional, I must have done something wrong while writing the new code, but I don't really know how. Anyway, I found a couple of these errors, and I should've fixed them all, thanks for spotting them! Also, I deleted the old branch and uploaded a new one, incorporating the fix in the last commit.
comment:20 Changed 3 years ago by
 Commit changed from aa7d7b85b98cf8aa01f593a2ce6619e6595a716a to 0aba4308772a3e5416811ee4e21d3de4db1f4494
Branch pushed to git repo; I updated commit sha1. New commits:
0aba430  Added documentation for the CaiFurerImmerman generator and for the Furer gadget generator

comment:21 Changed 3 years ago by
File "/home/dimpase/sagetracmirror/local/lib/python2.7/sitepackages/sage/graphs/generators/families.py", line 2993 return newG, total_partition SyntaxError: 'return' outside function
comment:22 followup: ↓ 26 Changed 3 years ago by
A few suggestions for EgawaGraph
:
 add an
INPUT:
block Any Egawa graph with parameters (0, s)
>The Egawa graph with parameters (0, s)
 You may add the reference of Agawa paper in file
src/doc/en/reference/references/index.rst
instead of putting linkhttps://doi.org/10.1016/00973165(81)900078
. At least, use:doi:`10.1016/00973165(81)900078`
 you don't need to import
DenseGraph
. not used  since
Y
is a graph, instead of the loopfor el in Y:
, you can do a loop likefor el in Y.neighbor_iterator(v[i]):
. Then, you can directly constructu
.  same for the loop
for el in X:
for j in range(s):
>for i in range(p, p+s):
 I'm not sure it is really useful to use set
used
.  add test to check that input parameters are ok
A few suggestions for HammingGraph
:
 add an
INPUT:
block  add test to check that input parameters are ok
 you don't need to import
DenseGraph
. not used  instead of having both
q
andX
, you could have a single parameterq
that could be either an integer, in which case you haveX = list(range(q))
or an iterable container (list, set, tuple, etc.) in which case you can doX = list(q)
.  you could add a link to the wikipedia page
 I don't think you need the set
used
. You can add several times the same edge.
In the documentation of all methods, since you use r""" some text """
, you can write latex equations. For instance, instead of writing `p` != 0
, write `p \neq 0`
. Write also `X^n`
to get nicer html rendering.
comment:23 followup: ↓ 24 Changed 3 years ago by
Please remove tabs from the source files. Sage uses spaces only (4 spaces per tab).
comment:24 in reply to: ↑ 23 Changed 3 years ago by
Replying to dimpase:
Please remove tabs from the source files. Sage uses spaces only (4 spaces per tab).
I've set up my editor to only use spaces, it's so weird a few slipped through.
Anyway, the only ones I've found are in the graph_generators.py file, did you find any others?
comment:25 Changed 3 years ago by
 Commit changed from 0aba4308772a3e5416811ee4e21d3de4db1f4494 to 6666e1b4da69bdf6e4bb1be244827973b508c136
Branch pushed to git repo; I updated commit sha1. New commits:
6666e1b  Improved implementation of the generators and added documentation and doctests

comment:26 in reply to: ↑ 22 Changed 3 years ago by
Replying to dcoudert:
A few suggestions for
EgawaGraph
:
 add an
INPUT:
blockAny Egawa graph with parameters (0, s)
>The Egawa graph with parameters (0, s)
 You may add the reference of Agawa paper in file
src/doc/en/reference/references/index.rst
instead of putting linkhttps://doi.org/10.1016/00973165(81)900078
. At least, use:doi:`10.1016/00973165(81)900078`
 you don't need to import
DenseGraph
. not used since
Y
is a graph, instead of the loopfor el in Y:
, you can do a loop likefor el in Y.neighbor_iterator(v[i]):
. Then, you can directly constructu
. same for the loop
for el in X:
for j in range(s):
>for i in range(p, p+s):
 I'm not sure it is really useful to use set
used
. add test to check that input parameters are ok
A few suggestions for
HammingGraph
:
 add an
INPUT:
block add test to check that input parameters are ok
 you don't need to import
DenseGraph
. not used instead of having both
q
andX
, you could have a single parameterq
that could be either an integer, in which case you haveX = list(range(q))
or an iterable container (list, set, tuple, etc.) in which case you can doX = list(q)
. you could add a link to the wikipedia page
 I don't think you need the set
used
. You can add several times the same edge.In the documentation of all methods, since you use
r""" some text """
, you can write latex equations. For instance, instead of writing`p` != 0
, write`p \neq 0`
. Write also`X^n`
to get nicer html rendering.
I've made the changes you suggested, save for the one about the parameters X and q. I see what you mean when you say one could use only one paramers, but I feel like it would be confusing to be able to pass either an integer or an iterable under the same name, and it's not like X needs to be passed most of the time anyway.
I'll add a check for the input soon too, but first I want to decide if there is a need to have this .pyx file for generators who need more speed.
Talking with dimpase, he told me he would like to see one, but in this particular case, after refactoring the code a bit, all my generators take more or less the same amount of time, .pyx or not, because most of the time is spent creating the actual graph, not computing edges and vertices.
There is some improvement mind you, but it's less than 10%. What should I do? Both versions are included in this commit, so that anyone can check for themselves what I mean, I'll simply delete the not needed ones when a decision has been made.
comment:27 followup: ↓ 29 Changed 3 years ago by
You should also check that the docs can be built.
Without your latest commit, I needed to change things to get docs built. Here is a diff (more changes  I guess the one that broke things was X
without ``):
diff git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py index 7101b881a6..c04edb2f53 100644  a/src/sage/graphs/generators/families.py +++ b/src/sage/graphs/generators/families.py @@ 142,10 +142,10 @@ def EgawaGraph(p, s): that is their orbits are not correctly returned by kWL for k lower than 3. Furthermore, all the graphs in this family are distanceregular, but they are  not distancetransitive if `p` != 0. + not distancetransitive if `p` is nonzero.  Any Egawa graph with parameters (0, s) is isomorphic to the Hamming graph  with parameters (s, 4) + Any Egawa graph with parameters `(0, s)` is isomorphic to the Hamming graph + with parameters `(s, 4)`. EXAMPLES: @@ 194,12 +194,12 @@ def HammingGraph(n, q, X=None): Returns the Hamming graph with parameters `n, q` over set `X`. Hamming graphs are graphs over the cartesian product of n copies of X,  where q = X, where the vertices, labelled with the corresponding tuple in X^n, + where `q = X`, where the vertices, labelled with the corresponding tuple in `X^n`, are connected if the Hamming distance between their labels is 1. All Hamming graphs are regular, vertextransitive and distanceregular.  Hamming graphs with parameters (1,q) represent the complete graph with  q vertices over the set X. + Hamming graphs with parameters `(1,q)` represent the complete graph with + `q` vertices over the set `X`. EXAMPLES: @@ 2990,7 +2990,7 @@ def CaiFurerImmermanGraph(G, twisted=False): else: s = "" newG.name("CaiFurerImmerman" + s + " graph constructed from a " + G.name()) return newG, total_partition + return newG, total_partition def MathonPseudocyclicMergingGraph(M, t):
comment:28 followup: ↓ 30 Changed 3 years ago by
to look for tabs in a given directory and all its subdirs, do e.g.
grep R P "\t" .
comment:29 in reply to: ↑ 27 Changed 3 years ago by
Replying to dimpase:
You should also check that the docs can be built. Without your latest commit, I needed to change things to get docs built. Here is a diff (more changes  I guess the one that broke things was
X
without ``):diff git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py index 7101b881a6..c04edb2f53 100644  a/src/sage/graphs/generators/families.py +++ b/src/sage/graphs/generators/families.py @@ 142,10 +142,10 @@ def EgawaGraph(p, s): that is their orbits are not correctly returned by kWL for k lower than 3. Furthermore, all the graphs in this family are distanceregular, but they are  not distancetransitive if `p` != 0. + not distancetransitive if `p` is nonzero.  Any Egawa graph with parameters (0, s) is isomorphic to the Hamming graph  with parameters (s, 4) + Any Egawa graph with parameters `(0, s)` is isomorphic to the Hamming graph + with parameters `(s, 4)`. EXAMPLES: @@ 194,12 +194,12 @@ def HammingGraph(n, q, X=None): Returns the Hamming graph with parameters `n, q` over set `X`. Hamming graphs are graphs over the cartesian product of n copies of X,  where q = X, where the vertices, labelled with the corresponding tuple in X^n, + where `q = X`, where the vertices, labelled with the corresponding tuple in `X^n`, are connected if the Hamming distance between their labels is 1. All Hamming graphs are regular, vertextransitive and distanceregular.  Hamming graphs with parameters (1,q) represent the complete graph with  q vertices over the set X. + Hamming graphs with parameters `(1,q)` represent the complete graph with + `q` vertices over the set `X`. EXAMPLES: @@ 2990,7 +2990,7 @@ def CaiFurerImmermanGraph(G, twisted=False): else: s = "" newG.name("CaiFurerImmerman" + s + " graph constructed from a " + G.name()) return newG, total_partition + return newG, total_partition def MathonPseudocyclicMergingGraph(M, t):
I know, I'm sorry.
This last commit was tested for docbuilding too, it works.
comment:30 in reply to: ↑ 28 Changed 3 years ago by
Replying to dimpase:
to look for tabs in a given directory and all its subdirs, do e.g.
grep R P "\t" .
I did that, that's how I found the ones in graph_generators.py, but one can never be too sure, so I asked if there were any other ones you found that escaped grep for some reason.
comment:31 followup: ↓ 35 Changed 3 years ago by
As I already said, I don't see the need for a pyx file if the code is essentially Python. Nonetheless, I will not fight against it.
You use type bool
, but you could use bint
instead (no need for import) as done in file src/sage/graphs/generic_graph_pyx.pyx
.
You also import string
but it is never used. You use type str
.
comment:32 Changed 3 years ago by
HammingGraph
needs tests for the use of X=
.
(e.g. what happens in X
is not equal to q
).
comment:33 Changed 3 years ago by
 Commit changed from 6666e1b4da69bdf6e4bb1be244827973b508c136 to 6c48d87ed35b0b3788a5aef8d3710295c5a59fa0
Branch pushed to git repo; I updated commit sha1. New commits:
6c48d87  Added doctest for HammingGraph's parameters

comment:34 Changed 3 years ago by
 Commit changed from 6c48d87ed35b0b3788a5aef8d3710295c5a59fa0 to 5e82a2a1a3d76808ce99d1e7e99d946129f493b8
Branch pushed to git repo; I updated commit sha1. New commits:
5e82a2a  Modified imports in families_pyx.pyx

comment:35 in reply to: ↑ 31 Changed 3 years ago by
Replying to dcoudert:
As I already said, I don't see the need for a pyx file if the code is essentially Python. Nonetheless, I will not fight against it.
You use type
bool
, but you could usebint
instead (no need for import) as done in filesrc/sage/graphs/generic_graph_pyx.pyx
. You also importstring
but it is never used. You use typestr
.
Done
Replying to dimpase:
HammingGraph
needs tests for the use ofX=
. (e.g. what happens inX
is not equal toq
).
And done
comment:36 followup: ↓ 40 Changed 3 years ago by
Please format documentation in 80 columns mode.
In method FurerGadget
:
 add an examples block
 I assume that
k
must be positive. What ifk==0
? add a test.  what is the expected type of
prefix
? you could document that.  you use
zip(...)
. With Python3,zip
becomes an iterator. So ifVa = zip(...)
, you can iterate overVa
only once. More precisely, after doingG.add_vertices(Va)
, the operationVa[i]
raises an error (in Python3). The solution here is to doVa = list(zip(...))
. rep(prefix, len(V_a))
>rep(prefix, k)
, no ?for r in range(k+1) if r % 2 == 0
could be simplyfor r in range(0, k+1, 2)
In method CaiFurerImmermanGraph
:
 in the documentation, you can write
`G`
instead of``G``
to use latex. F(v)
>`F(v)`
 add an examples block and possibly some tests.
 What if
G
is the empty graph ? G.edges(labels=False)
>G.edge_iterator(labels=False)
 The block
temp = edge_ua
is currently not correct as it setsedge_ua
to it's initial value without touchingedge_ub
. I recommend to rewrite it in 1 line:edge_ua, edge_ub = edge_ub, edge_ua
.
In method EgawaGraph
:
 Returns > Return
 add tests on
p
ands
. Strictly positive ?
In HammingGraph
:
if None (or left unused)
>if ``None`` (or left unused)
. It's a general convention in documentation forNone
,True
andFalse
. add tests for the expected values of
n
andq
.
Sorry to bother you with all these "details", but the cleaner the code, the easier it is to maintain.
comment:37 Changed 3 years ago by
 Commit changed from 5e82a2a1a3d76808ce99d1e7e99d946129f493b8 to 1b34dfef45629563ded4dfc8dba87dc3b6c710c8
Branch pushed to git repo; I updated commit sha1. New commits:
1b34dfe  Fixed a bug in the generation of CaiFurerImmerman graphs

comment:38 Changed 3 years ago by
 Commit changed from 1b34dfef45629563ded4dfc8dba87dc3b6c710c8 to e42ad05845a7fda2a39e4dadaaeeba308afc92e4
Branch pushed to git repo; I updated commit sha1. New commits:
e42ad05  Fixed the documentation and added some tests

comment:39 Changed 3 years ago by
 Commit changed from e42ad05845a7fda2a39e4dadaaeeba308afc92e4 to d7385446a44aa9b34600d35a35e9e8a1bfb49f40
Branch pushed to git repo; I updated commit sha1. New commits:
d738544  Small fix

comment:40 in reply to: ↑ 36 Changed 3 years ago by
Replying to dcoudert:
Please format documentation in 80 columns mode.
In method
FurerGadget
:
 add an examples block
 I assume that
k
must be positive. What ifk==0
? add a test. what is the expected type of
prefix
? you could document that. you use
zip(...)
. With Python3,zip
becomes an iterator. So ifVa = zip(...)
, you can iterate overVa
only once. More precisely, after doingG.add_vertices(Va)
, the operationVa[i]
raises an error (in Python3). The solution here is to doVa = list(zip(...))
.rep(prefix, len(V_a))
>rep(prefix, k)
, no ?for r in range(k+1) if r % 2 == 0
could be simplyfor r in range(0, k+1, 2)
In method
CaiFurerImmermanGraph
:
 in the documentation, you can write
`G`
instead of``G``
to use latex.F(v)
>`F(v)`
 add an examples block and possibly some tests.
 What if
G
is the empty graph ?G.edges(labels=False)
>G.edge_iterator(labels=False)
 The block
temp = edge_ua
is currently not correct as it setsedge_ua
to it's initial value without touchingedge_ub
. I recommend to rewrite it in 1 line:edge_ua, edge_ub = edge_ub, edge_ua
.In method
EgawaGraph
:
 Returns > Return
 add tests on
p
ands
. Strictly positive ?In
HammingGraph
:
if None (or left unused)
>if ``None`` (or left unused)
. It's a general convention in documentation forNone
,True
andFalse
. add tests for the expected values of
n
andq
.Sorry to bother you with all these "details", but the cleaner the code, the easier it is to maintain.
Fixed everything, the graph G can be empty for a CaiFurerImmerman? graph, it will simply return an equally empty graph. Prefix can be anything, so it doesn't really matter. And anyway, don't worry about it, I appreciate the attention to details, you're telling me things I couldn't have known by myself, thanks.
New commits:
d738544  Small fix

comment:41 Changed 3 years ago by
Is it ready for review? If so, please set it ready for review...
comment:42 Changed 3 years ago by
 Status changed from new to needs_review
comment:43 followup: ↓ 44 Changed 3 years ago by
A choice must be done: either put the methods in families.py
or in a new file families_pyx.pyx
.
I don't see the advantage of the new .pyx
file here, as the speed up improvement is rather limited, but I will not fight against it.
comment:44 in reply to: ↑ 43 Changed 3 years ago by
Replying to dcoudert:
A choice must be done: either put the methods in
families.py
or in a new filefamilies_pyx.pyx
. I don't see the advantage of the new.pyx
file here, as the speed up improvement is rather limited, but I will not fight against it.
I have to say in this case I agree with you, there's not much use for it, as the bottleneck in basically any case is going to be the creation of the graph itself, but since I didn't want to choose by myself, I'll leave it for other reviewers to decide.
It's a 1 minute job to delete one of the two versions, anyway.
comment:45 Changed 3 years ago by
 Branch changed from u/Vaush/HammingGraphs_EgawaGraphs_CaiGraphs to public/graphs/families/HammingEgavaFurer
 Commit changed from d7385446a44aa9b34600d35a35e9e8a1bfb49f40 to 1e243e762a84a60cace49079c6fb13375e4d6f86
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
comment:46 Changed 3 years ago by
 Status changed from positive_review to needs_work
still needs removal of the cython version
comment:47 Changed 3 years ago by
 Commit changed from 1e243e762a84a60cace49079c6fb13375e4d6f86 to 1cdaa3f1fa4bd39ca846ec5560bd6b887dc78aaf
Branch pushed to git repo; I updated commit sha1. New commits:
1cdaa3f  removed cython version; one more dostring fix

comment:49 Changed 3 years ago by
 Branch changed from public/graphs/families/HammingEgavaFurer to 1cdaa3f1fa4bd39ca846ec5560bd6b887dc78aaf
 Resolution set to fixed
 Status changed from positive_review to closed
Why are you creating new files for these graphs ? can't you just add these generators in file
families.py
? In general, we try to avoid adding new files unless there is a real need for it (easier for maintaining the code).Also, this patch is build on top of #25802 (without indicating the dependency) but I have the feeling that this can be done independently.
Last 10 new commits:
Support structure in place
Created adjacency matrix class
Support structure is complete and superficially tested, left to do: writing the algorithm's main loop
Working version of kWL. TODO: support edge and vertex labels, make a few memory optimisations and format the output properly
Now the kWL implementation supports labels. TODO: memory optimisations and output formatting
Slightly optimized memory usage, better output formatting is still needed, but the possible use cases are so many that for the moment leaving the possibility of manipulating raw vertextuples coloring looks like the best choice
Relabel bug fix
Merge branch 't/25802/weisfeiler_lehman_first_implementation' into HammingGraphs_IGraphs_and_CaiGraphs
Fixed error with initial graph coloring
Added documentation. TODO: verify CaiFurerImmermanGraph implementation