#13820: This patch implements the construction of the Johnson graph.
---------------------------------+------------------------------------------
Reporter: slani | Owner: slani
Type: task | Status: needs_work
Priority: major | Milestone: sage-5.6
Component: graph theory | Resolution:
Keywords: Johnson graph | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Uros Slana | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Comment (by ncohen):
Helloooooooo Uros !
About the last two points :
* Oh. By embedding, I was talking about the different between those two
commands :
{{{
sage: graphs.PetersenGraph().show(layout="spring")
sage: graphs.PetersenGraph().show()
}}}
Most graph generators include the definition of an embedding (err.
layout) in the graph they return, just in case that there would be a
"nice" way to display the graph. Actually, it looks like there is no
default layout for Kneser Graph (and I would have a hard time finding a
general one). So except if you know a good way to display Johnson graphs,
I guess you can skip it.
* If you write the algorithm this way "for any pair of vertices, test
whether the intersection has size exactly k" the amount of operations you
do is `(\binom n k)^2`. And that's usually a LOT `:-P`. If, instead, you
write "for any sets S of size k-1, and for any two distincts elements i,j
not included in S, add the edge (S+i,S+j)", then the amount of operations
you do is exactly the number of edges you need to add. And I guess it may
be faster, even for small cases `:-)`
You can evaluate the time it takes to run a command this way :
{{{
sage: %timeit graphs.JohnsonGraph(6,4)
25 loops, best of 3: 10.7 ms per loop
sage: %timeit graphs.JohnsonGraph(7,4)
5 loops, best of 3: 55.2 ms per loop
sage: %timeit graphs.JohnsonGraph(8,4)
5 loops, best of 3: 217 ms per loop
}}}
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13820#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
