Changes between Initial Version and Version 2 of Ticket #19526

11/04/15 17:51:44 (4 years ago)


  • Ticket #19526

    • Property Status changed from new to needs_review
    • Property Authors changed from to Janoš Vidali
    • Property Cc ncohen added
    • Property Component changed from PLEASE CHANGE to graph theory
    • Property Branch changed from to u/jaanos/certain_methods_fail_on_immutable_graphs
    • Property Keywords graphs immutable added
    • Property Commit changed from to 7c16057d182112aee455aade5ff586cff75f4a15
    • Property Type changed from PLEASE CHANGE to defect
  • Ticket #19526 – Description

    initial v2  
     1The following methods fail for immutable graphs:
     3 * `GenericGraph.disjoint_routed_paths`
     4 * `GenericGraph.genus`
     5 * `GenericGraph.is_circular_planar`
     6 * `GenericGraph.is_cut_edge`
     7 * `GenericGraph.is_interval`
     8 * `GenericGraph.layout_planar`
     9 * `GenericGraph.multicommodity_flow`
     10 * `GenericGraph.set_planar_positions`
     11 * `GenericGraph.steiner_tree`
     12 * `GenericGraph.to_simple`
     13 * `GenericGraph.vertex_disjoint_paths`
     14 * `Graph.gomory_hu_tree`
     15 * `Graph.is_long_antihole_free`
     16 * `Graph.is_long_hole_free`
     17 * `Graph.is_weakly_chordal`
     18 * `Graph.join`
     19 * `Graph.seidel_switching`
     20 * `Graph.topological_minor`
     21 * `Graph.tutte_polynomial`
     23I 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).
     25A 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.
     27The 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.