Revision history [back]

You could make one mutable copy and modify it in place:

def edges_to_add_to_attain_property(graph, prop):
    G = graph.copy(immutable=False)
    prev_edge = None
    for edge in G.complement().edges(labels=False, sort=False):
        if prev_edge is not None:
            G.delete_edge(prev_edge)
        G.add_edge(edge)
        if prop(G):
            yield edge
        prev_edge = edge

Example:

sage: G = Graph('J~f[MN@PQg?', sparse=True)
sage: len(G.edges())
27
sage: list(edges_to_add_to_attain_property(G, lambda H: not H.is_hamiltonian()))
[(0, 9),
 (0, 10),
 (1, 4),
 (1, 6),
 (2, 5),
 (2, 7),
 (3, 6),
 (3, 7),
 (3, 8),
 (3, 9),
 (4, 7),
 (5, 8),
 (7, 10)]
sage: len(G.edges())
27

Note g.complement() internally also makes a copy, but it's probably worth it as the backend (C code) probably calculates the complement efficiently.

You could make one mutable copy and modify it in place:

def edges_to_add_to_attain_property(graph, prop):
    G = graph.copy(immutable=False)
    prev_edge = None
    for edge in G.complement().edges(labels=False, sort=False):
        if prev_edge is not None:
            G.delete_edge(prev_edge)
        G.add_edge(edge)
        if prop(G):
            yield edge
        prev_edge = edge

Example:

sage: G = Graph('J~f[MN@PQg?', sparse=True)
sage: len(G.edges())
27
G.graph6_string()
'J~f[MN@PQg?'
sage: list(edges_to_add_to_attain_property(G, lambda H: not H.is_hamiltonian()))
[(0, 9),
 (0, 10),
 (1, 4),
 (1, 6),
 (2, 5),
 (2, 7),
 (3, 6),
 (3, 7),
 (3, 8),
 (3, 9),
 (4, 7),
 (5, 8),
 (7, 10)]
sage: len(G.edges())
27
G.graph6_string() # not modified
'J~f[MN@PQg?'

Note g.complement() internally also makes a copy, but it's probably worth it as the backend (C code) probably calculates the complement efficiently.

You could make one mutable copy and modify it in place:

def edges_to_add_to_attain_property(graph, prop):
    G = graph.copy(immutable=False)
    prev_edge = None
    for edge in G.complement().edges(labels=False, sort=False):
        if prev_edge is not None:
            G.delete_edge(prev_edge)
        G.add_edge(edge)
        if prop(G):
            yield edge
        prev_edge = edge

Example:

sage: G = Graph('J~f[MN@PQg?', sparse=True)
sage: G.graph6_string()
'J~f[MN@PQg?'
sage: list(edges_to_add_to_attain_property(G, lambda H: not H.is_hamiltonian()))
[(0, 9),
 (0, 10),
 (1, 4),
 (1, 6),
 (2, 5),
 (2, 7),
 (3, 6),
 (3, 7),
 (3, 8),
 (3, 9),
 (4, 7),
 (5, 8),
 (7, 10)]
sage: G.graph6_string() # G is not modified
'J~f[MN@PQg?'

Note g.complement()G.complement() internally also makes a copy, but it's probably worth it as the backend (C code) probably calculates the complement efficiently.