Certain methods fail on immutable graphs

[jaanos]

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.

[ncohen]

Helloooooo Janos,

Here is a first-pass review.

• Modification to DiGraph.to_undirected -- adding a immutable flag as you do it in this function is problematic. What is the intended behavior of g.to_undirected(sparse=False,immutable=True) ? :-/

This kind of compatibilities should be handled by the constructor. So, to avoid to do its job again, the best is probably to give it all the arguments you get and hope that it does its job.

• Could you write this is_immutable function? Then this

  +        if getattr(self, '_immutable', False):
  +            G = copy(self)
  +        else:
  +            G = self
  

  Could become

  G = self.copy(immutable=False) if self.is_immutable() else self
  

• I don't think it is worth testing if we work on a copy here ^^;

  -        self.add_edge(u,v,label)
  +        if not getattr(self, '_immutable', False):
  +            G.add_edge(u,v,label)
  

• Graph.to_directed -- same remark as for DiGraph.to_undirected

• Same function -- the documentation of immutable is not indented right. You can build the doc to observe it with sage -b && sage -docbuild reference/graphs html

Thanks,

Nathann

[jaanos]

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š

[ncohen]

Yooooooooooo,

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).

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 removing immutable, 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 have immutable here?

Yepyep, that should be good.

Nathann

[git]

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

[jaanos]

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).

[ncohen]

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

[jaanos]

Hi!

No problem, I can do that.

Janoš

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c7185e9	Add parameter immutable to relabel
​c5ff510	Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs

[jaanos]

OK, here you go.

[ncohen]

WOoooooorks for me ! THanks :-)

Nathann

[jaanos]

Thank you guys! I'll be back with a new ticket soon:)