Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#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) Commit:
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (14)

comment:1 Changed 4 years ago by jaanos

  • Branch set to u/jaanos/certain_methods_fail_on_immutable_graphs

comment:2 Changed 4 years ago by jaanos

  • Authors set to Janoš Vidali
  • 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 4 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to needs_work

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

comment:4 follow-up: Changed 4 years ago by 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š

comment:5 in reply to: ↑ 4 Changed 4 years ago by 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

comment:6 Changed 4 years ago by git

  • Commit changed from 7c16057d182112aee455aade5ff586cff75f4a15 to ee7eb7cd6801bad4abd8086ec5f69d8743423a63

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

ea67b00Replace self.to_undirected(immutable=False) with Graph(self)
cca899dAdd is_immutable()
b90f134Import sage.graphs.Graph where needed
63d9a27Use is_immutable() in weakly_chordal.pyx
1e29090Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs
30752faUse is_immutable in tutte_polynomial.py
d2fbff3Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs
fa6b8f6Use imperative in documentation index
9c03d89Fix indents in documentation
ee7eb7cMerge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs

comment:7 Changed 4 years ago by jaanos

  • 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 4 years ago by ncohen

  • 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 4 years ago by jaanos

Hi!

No problem, I can do that.

Janoš

comment:10 Changed 4 years ago by git

  • Commit changed from ee7eb7cd6801bad4abd8086ec5f69d8743423a63 to c5ff5104ee2671ff61fd7de36cc696265e4c4c4c

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

c7185e9Add parameter immutable to relabel
c5ff510Merge branch 'immutable_graph_copy' into t/19526/certain_methods_fail_on_immutable_graphs

comment:11 Changed 4 years ago by jaanos

  • Status changed from needs_info to needs_review

OK, here you go.

comment:12 Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

WOoooooorks for me ! THanks :-)

Nathann

comment:13 Changed 4 years ago by vbraun

  • 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 4 years ago by jaanos

  • Commit c5ff5104ee2671ff61fd7de36cc696265e4c4c4c deleted

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

Note: See TracTickets for help on using tickets.