Opened 4 years ago

Last modified 4 years ago

#19526 closed defect

Certain methods fail on immutable graphs — at Version 2

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:
Report Upstream: N/A Work issues:
Branch: u/jaanos/certain_methods_fail_on_immutable_graphs (Commits) Commit: 7c16057d182112aee455aade5ff586cff75f4a15
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 (2)

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
Note: See TracTickets for help on using tickets.