#19526 closed defect (fixed)
Certain methods fail on immutable graphs
Reported by:  jaanos  Owned by:  

Priority:  major  Milestone:  sage6.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)  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 5 years ago by
 Branch set to u/jaanos/certain_methods_fail_on_immutable_graphs
comment:2 Changed 5 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 5 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to needs_work
comment:4 followup: ↓ 5 Changed 5 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 nonissue.
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 5 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 nonissue.
What I meant is that this prameterchecking 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 5 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 5 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 5 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 5 years ago by
Hi!
No problem, I can do that.
Janoš
comment:10 Changed 5 years ago by
 Commit changed from ee7eb7cd6801bad4abd8086ec5f69d8743423a63 to c5ff5104ee2671ff61fd7de36cc696265e4c4c4c
comment:12 Changed 5 years ago by
 Status changed from needs_review to positive_review
WOoooooorks for me ! THanks :)
Nathann
comment:13 Changed 5 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 5 years ago by
 Commit c5ff5104ee2671ff61fd7de36cc696265e4c4c4c deleted
Thank you guys! I'll be back with a new ticket soon:)
Helloooooo Janos,
Here is a firstpass 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