#19526 closed defect (fixed)
Certain methods fail on immutable graphs
Reported by: | jaanos | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.10 |
Component: | graph theory | Keywords: | graphs, immutable |
Cc: | ncohen | Merged in: | |
Authors: | Janoš Vidali | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | c5ff510 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description (last modified by )
The following methods fail for immutable graphs:
GenericGraph.disjoint_routed_paths
GenericGraph.genus
GenericGraph.is_circular_planar
GenericGraph.is_cut_edge
GenericGraph.is_interval
GenericGraph.layout_planar
GenericGraph.multicommodity_flow
GenericGraph.set_planar_positions
GenericGraph.steiner_tree
GenericGraph.to_simple
GenericGraph.vertex_disjoint_paths
Graph.gomory_hu_tree
Graph.is_long_antihole_free
Graph.is_long_hole_free
Graph.is_weakly_chordal
Graph.join
Graph.seidel_switching
Graph.topological_minor
Graph.tutte_polynomial
I have changed these methods (or ones they depend on) to make a copy of the appropriate (sub)graph if one is needed. To prevent making unneeded copies of (potentially large) graphs, the methods to_directed
, to_undirected
, to_simple
, subgraph
, disjoint_union
, union
and join
now take an additional parameter immutable
specifying whether the returned graph should be mutable or not (with the default None
specifying the old behaviour, i.e. keeping the mutability of the input).
A minor exception is the subgraph
method, which would always return a mutable graph when the "add" algorithm was being used, but this is now made consistent with the "delete" algorithm and other methods.
The reason I need these methods to work on immutable graphs is that I am part of a team building a database of graphs with precomputed attributes (so the graphs being mutable would make no sense) which will be accessible through Sage - of course we still want to do stuff with the graphs that won't change them.
Change History (14)
comment:1 Changed 7 years ago by
- Branch set to u/jaanos/certain_methods_fail_on_immutable_graphs
comment:2 Changed 7 years ago by
- Cc ncohen added
- Commit set to 7c16057d182112aee455aade5ff586cff75f4a15
- Component changed from PLEASE CHANGE to graph theory
- Description modified (diff)
- Keywords graphs immutable added
- Status changed from new to needs_review
- Type changed from PLEASE CHANGE to defect
comment:3 Changed 7 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to needs_work
comment:4 follow-up: ↓ 5 Changed 7 years ago by
Hi!
Thanks for the review. I'll implement the suggestions shortly.
I guess the right thing to do here is to remove the immutable
flag from to_(un)directed
in both Graph
and DiGraph
, and use Graph(G)
instead of G.to_undirected(immutable=False)
, and DiGraph(G)
instead of G.to_directed(immutable=False)
.
As for g.to_undirected(sparse=False,immutable=True)
, there should've been a check to yield an error if this is called (instead of just returning a sparse immutable graph), but since I'm removing immutable
, this is now a non-issue.
What about GenericGraph.to_simple
? Since there is no corresponding constructor, it would probably be OK to have immutable
here?
Janoš
comment:5 in reply to: ↑ 4 Changed 7 years ago by
Yooooooooooo,
I guess the right thing to do here is to remove the
immutable
flag fromto_(un)directed
in bothGraph
andDiGraph
, and useGraph(G)
instead ofG.to_undirected(immutable=False)
, andDiGraph(G)
instead ofG.to_directed(immutable=False)
.
Yep. And it convinces me even more that we should remove those functions totally. In another ticket, if you don't feel like doing it.
As for
g.to_undirected(sparse=False,immutable=True)
, there should've been a check to yield an error if this is called (instead of just returning a sparse immutable graph), but since I'm removingimmutable
, this is now a non-issue.
What I meant is that this prameter-checking is/should be done in the constructor anyway. So let us not double this administrative code.
What about
GenericGraph.to_simple
? Since there is no corresponding constructor, it would probably be OK to haveimmutable
here?
Yepyep, that should be good.
Nathann
comment:6 Changed 7 years ago by
- Commit changed from 7c16057d182112aee455aade5ff586cff75f4a15 to ee7eb7cd6801bad4abd8086ec5f69d8743423a63
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
ea67b00 | Replace self.to_undirected(immutable=False) with Graph(self)
|
cca899d | Add is_immutable()
|
b90f134 | Import sage.graphs.Graph where needed
|
63d9a27 | Use is_immutable() in weakly_chordal.pyx
|
1e29090 | Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs
|
30752fa | Use is_immutable in tutte_polynomial.py
|
d2fbff3 | Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs
|
fa6b8f6 | Use imperative in documentation index
|
9c03d89 | Fix indents in documentation
|
ee7eb7c | Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs
|
comment:7 Changed 7 years ago by
- Status changed from needs_work to needs_review
OK, I fixed the issues. I haven't removed to_(un)directed
, since these functions are used all over the place and I don't feel I'm in position to remove them :) (plus, I see the benefit of not creating a copy of an immutable graph when one isn't needed).
comment:8 Changed 7 years ago by
- Status changed from needs_review to needs_info
Hellooooooooooooooo,
It all looks good, but I have one question left about this modification:
- G = G.relabel(inplace=False) # making sure the vertices are integers + if G.is_immutable(): + G = G.copy(immutable=False) + G.relabel(inplace=True) + else: + G = G.relabel(inplace=False) # making sure the vertices are integers
Why wouldn't you add the same argument 'immutable' to 'relabel' instead? It seems that you only want something like G.relabel(inplace=False,immutable=False)
?..
Nathann
comment:9 Changed 7 years ago by
Hi!
No problem, I can do that.
Janoš
comment:10 Changed 7 years ago by
- Commit changed from ee7eb7cd6801bad4abd8086ec5f69d8743423a63 to c5ff5104ee2671ff61fd7de36cc696265e4c4c4c
comment:12 Changed 7 years ago by
- Status changed from needs_review to positive_review
WOoooooorks for me ! THanks :-)
Nathann
comment:13 Changed 7 years ago by
- Branch changed from u/jaanos/certain_methods_fail_on_immutable_graphs to c5ff5104ee2671ff61fd7de36cc696265e4c4c4c
- Resolution set to fixed
- Status changed from positive_review to closed
comment:14 Changed 7 years ago by
- Commit c5ff5104ee2671ff61fd7de36cc696265e4c4c4c deleted
Thank you guys! I'll be back with a new ticket soon:)
Helloooooo Janos,
Here is a first-pass review.
DiGraph.to_undirected
-- adding aimmutable
flag as you do it in this function is problematic. What is the intended behavior ofg.to_undirected(sparse=False,immutable=True)
?:-/
is_immutable
function? Then this Could become^^;
Graph.to_directed
-- same remark as forDiGraph.to_undirected
immutable
is not indented right. You can build the doc to observe it withsage -b && sage -docbuild reference/graphs html
Thanks,
Nathann