#18972: twographs and Seidel switching
-------------------------------------+-------------------------------------
Reporter: dimpase | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers: Nathann Cohen
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/dimpase/seidelsw | 1b7f6b99019699fdccb4bb9afa86315defc87994
Dependencies: #18960, #18948, | Stopgaps:
#18988, #18991 |
-------------------------------------+-------------------------------------
Comment (by dimpase):
Replying to [comment:54 ncohen]:
>
> > > - `Graph([V, lambda i, j: frozenset((i,j)) in edges])` THINK ABOUT
WHAT IT
> > > DOES. This is insulting.
> >
> > Indeed, I wish I could write `Graph(V,edges)` or `Graph([V,edges])` or
even `Graph(edges)` instead. Why can't I?
>
> There is no God above forbidding this syntax. If the constructor does
not do what you want, then improve it.
>
> In this situation, `Graph(edges)` simply works.
Really? This is not documented! No wonder I didn't try this.
>
> > Why must I instead do something like
> > `blah=Graph(V); blah.add_edges(edges); return blah`? Cause the GC is
hungry and must be fed `blah` on each return?
>
> What your code does is this:
>
> "For every pair of points among V, build a frozen set {i,j} then test if
this set is contained in a LIST (linear time) of sets". That's ridiculous.
I just wanted one function call, you know...
>
> > > - Use `g.copy()` (which should be called by `copy(g)`), not
deepcopy.
> >
> > the docs to `g.copy()` say something like "use only if you change the
backend..."
> > {{{
> > Warning: Please use this method only if you need to copy but
> > change the underlying implementation or weightedness. Otherwise
> > simply do "copy(g)" instead of "g.copy()".
> > }}}
> > Should I ignore this? Should the docs be improved?
>
> All that it says is that "g.copy()" is equivalent to "copy(g)", and that
the latter should be preferred. The advantage of `g.copy()` is that you
can give it additional arguments, e.g. change the backend.
If `g.copy()==copy(g)` then it would not work. I tried using `copy(g)` in
place of `deepcopy(g)` and it produced crap. A bug in `Graph`? I don't
know...
> I am not saying that it is slow to use lambda function, I say that you
have no idea of what you are doing.
>
> > > {{{
> > > + return Graph([Nv+NonNv, lambda i, j:
> > > + (i in NonNv and j in NonNv and i in
self.neighbors(j)) or
> > > + (i in Nv and j in Nv and i in
self.neighbors(j)) or
> > > + (i in Nv and j in NonNv and not i in
self.neighbors(j)) or
> > > + (j in Nv and i in NonNv and not i in
self.neighbors(j))])
> > > }}}
> > > Build this graph by adding edges to it. It will be incomparably
> > > faster. Writing code like this should not be allowed.
> >
> > in my book using temporary variables is slow; perhaps Python
implementations will get fuller use of this fact as its devs and users get
wiser...
>
> This code call `.neighbors()` for around `Theta(n^2)` times. Each time
it builds a list in memory, and does a linear search in a list of things
which may not even be integers. That's madness. THIS IS NOT SYMBOLICS.
THIS IS ACTUAL CODE. For every pair of i,j this function is run, and every
time all these lists are creates for nothing.
I don't get it. Somewhere deep inside `Graph` there must be a fast way to
check if two vertices are adjacent... I took it as `self.neighbour(j)` is
actually something that takes constant time to invoke. If not, pray tell
me how to check that two vertices are adjacent in a reasonably fast way.
> > > - `is_even`.
> >
> > I like it better than `%`, more readable: one does not need to swap
out some other language in the head to recall the meaning. But if you
insist...
> e
> Are you telling me that you are having a hard time remembering the
meaning of `%` ? Is that a joke?
No, not at all. I have been programming for over 35 years, you know...
Yes, I do need nonzero time to recall the meaning of `%`, of `//`, etc
etc, if I don't touch them for a week...
--
Ticket URL: <http://trac.sagemath.org/ticket/18972#comment:55>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
