#15278: Hash and equality for graphs
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.13
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/SimonKing/ticket/15278 | c774057bf07b2da8539f2395555b2062428874f4
Dependencies: #12601 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
* About not requiring `allows_multiple_edges` and `allows_loops` to be
equal :
there is actually a technical problem there I just noticed : the
`get_edge_label` function behaves differently according to the value of
`allow_multiple_edges()`. It returns either a label, or a list of
labels. And
that complicates things.
{{{
sage: g = graphs.PetersenGraph()
sage: print g.edge_label(0,1)
None
sage: g.allow_multiple_edges(True)
sage: print g.edge_label(0,1)
[None]
}}}
(I hate labels and multiple edges)
Besides, testing whether the graph containts multiple edges is currently
a bit
costly. I think we actually go over all edges, and test it.
* About `.weighted()` : looks like the meaning of "weighted" is only used
in
`spanning_tree.pyx`. And I'd say that this can easily be replaced by an
additional argument to the methods (as it is already the case in many
others,
like `flow` of `traveling_salesman_problem`)
* I believe (note sure, never used it) that `.weighted()` only indicates
whether
the labels on the edges are to be understood as weights. That's all.
Multiple
edges are handled by the backend, and each edge can have a different
label,
it's unrelated.
* I don't see any problem with using #12601. Do you see one ?
* `copy(gi)` takes a lot of time : indeed, returning `self` makes sense.
If one
actually wants to copy the immutable copy of the graph, i.e. the
underlying C
data and arrays, this can be made MUCH faster than the current
implementation. Two calls to `memcpy` and it's settled `:-P`
* Why didn't you use the decorators from your first immutable graph patch
to
deal with immutability in `.weighted()` ?
* If you want to check that current functions act well on immutable
graphs, you
may be interested by the decorator named `_run_it_on_static_instead` in
`sage.graphs.backends.static_sparse_backend`. It makes the function take
the
graph as input, create an immutable copy of it, and run the code and the
immutable copy instead. It's still a lot of manual work to do, but it's
easier
than trying the functions hand by hand. Just add the decorator to the
graph
functions you want to test, and run the doctests `;-)`
Sorry for the delay. I moved a lot through Paris with my backpack during
the
last days `:-P`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15278#comment:11>
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/groups/opt_out.
