View classes#

This module implements views for (di)graphs. A view is a read-only iterable container enabling operations like for e in E and e in E. It is updated as the graph is updated. Hence, the graph should not be updated while iterating through a view. Views can be iterated multiple times.

Todo

  • View of neighborhood to get open/close neighborhood of a vertex/set of vertices

Classes#

class sage.graphs.views.EdgesView[source]#

Bases: object

EdgesView class.

This class implements a read-only iterable container of edges enabling operations like for e in E and e in E. An EdgesView can be iterated multiple times, and checking membership is done in constant time. It avoids the construction of edge lists and so consumes little memory. It is updated as the graph is updated. Hence, the graph should not be updated while iterating through an EdgesView.

INPUT:

  • G – a (di)graph

  • vertices – list (default: None); an iterable container of vertices or None. When set, consider only edges incident to specified vertices.

  • vertices2 – list (default: None); an iterable container of vertices or None. When set, consider only edges incident to specified vertices. More precisely:

    • When both vertices and vertices2 are set, consider only edges (u, v, l) with u in vertices and v in vertices2.

    • When vertices is None and vertices2 is set, consider only edges (u, v, l) with v in vertices2.

  • labels – boolean (default: True); if False, each edge is simply a pair (u, v) of vertices

  • ignore_direction – boolean (default: False); only applies to directed graphs. If True, searches across edges in either direction.

  • sort – boolean (default: False); whether to sort edges according the ordering specified with parameter key. If False (default), edges are not sorted. This is the fastest and less memory consuming method for iterating over edges.

  • key – a function (default: None); a function that takes an edge (a pair or a triple, according to the labels keyword) as its one argument and returns a value that can be used for comparisons in the sorting algorithm. This parameter is ignored when sort = False.

  • sort_vertices – boolean (default: True); whether to sort the ends of the edges; not sorting the ends is faster; only applicable to undirected graphs when sort is False

Warning

Since any object may be a vertex, there is no guarantee that any two vertices will be comparable, and thus no guarantee how two edges may compare. With default objects for vertices (all integers), or when all the vertices are of the same simple type, then there should not be a problem with how the vertices will be sorted. However, if you need to guarantee a total order for the sorting of the edges, use the key argument, as illustrated in the examples below.

EXAMPLES:

sage: from sage.graphs.views import EdgesView
sage: G = Graph([(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')])
sage: E = EdgesView(G, sort=True); E
[(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')]
sage: (1, 2) in E
False
sage: (1, 2, 'B') in E
True
sage: E = EdgesView(G, labels=False, sort=True); E
[(0, 1), (0, 2), (1, 2)]
sage: (1, 2) in E
True
sage: (1, 2, 'B') in E
False
sage: [e for e in E]
[(0, 1), (0, 2), (1, 2)]

>>> from sage.all import *
>>> from sage.graphs.views import EdgesView
>>> G = Graph([(Integer(0), Integer(1), 'C'), (Integer(0), Integer(2), 'A'), (Integer(1), Integer(2), 'B')])
>>> E = EdgesView(G, sort=True); E
[(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')]
>>> (Integer(1), Integer(2)) in E
False
>>> (Integer(1), Integer(2), 'B') in E
True
>>> E = EdgesView(G, labels=False, sort=True); E
[(0, 1), (0, 2), (1, 2)]
>>> (Integer(1), Integer(2)) in E
True
>>> (Integer(1), Integer(2), 'B') in E
False
>>> [e for e in E]
[(0, 1), (0, 2), (1, 2)]

An EdgesView can be iterated multiple times:

sage: G = graphs.CycleGraph(3)
sage: print(E)
[(0, 1), (0, 2), (1, 2)]
sage: print(E)
[(0, 1), (0, 2), (1, 2)]
sage: for e in E:
....:     for ee in E:
....:         print((e, ee))
((0, 1), (0, 1))
((0, 1), (0, 2))
((0, 1), (1, 2))
((0, 2), (0, 1))
((0, 2), (0, 2))
((0, 2), (1, 2))
((1, 2), (0, 1))
((1, 2), (0, 2))
((1, 2), (1, 2))

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(3))
>>> print(E)
[(0, 1), (0, 2), (1, 2)]
>>> print(E)
[(0, 1), (0, 2), (1, 2)]
>>> for e in E:
...     for ee in E:
...         print((e, ee))
((0, 1), (0, 1))
((0, 1), (0, 2))
((0, 1), (1, 2))
((0, 2), (0, 1))
((0, 2), (0, 2))
((0, 2), (1, 2))
((1, 2), (0, 1))
((1, 2), (0, 2))
((1, 2), (1, 2))

We can check if a view is empty:

sage: E = EdgesView(graphs.CycleGraph(3), sort=False)
sage: if E:
....:     print('not empty')
not empty
sage: E = EdgesView(Graph(), sort=False)
sage: if not E:
....:     print('empty')
empty

>>> from sage.all import *
>>> E = EdgesView(graphs.CycleGraph(Integer(3)), sort=False)
>>> if E:
...     print('not empty')
not empty
>>> E = EdgesView(Graph(), sort=False)
>>> if not E:
...     print('empty')
empty

When sort is True, edges are sorted by default in the default fashion:

sage: G = Graph([(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')])
sage: E = EdgesView(G, sort=True); E
[(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')]

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), 'C'), (Integer(0), Integer(2), 'A'), (Integer(1), Integer(2), 'B')])
>>> E = EdgesView(G, sort=True); E
[(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')]

This can be overridden by specifying a key function. This first example just ignores the labels in the third component of the triple:

sage: G = Graph([(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')])
sage: E = EdgesView(G, sort=True, key=lambda x: (x[1], -x[0])); E
[(0, 1, 'C'), (1, 2, 'B'), (0, 2, 'A')]

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), 'C'), (Integer(0), Integer(2), 'A'), (Integer(1), Integer(2), 'B')])
>>> E = EdgesView(G, sort=True, key=lambda x: (x[Integer(1)], -x[Integer(0)])); E
[(0, 1, 'C'), (1, 2, 'B'), (0, 2, 'A')]

We can also sort according to the labels:

sage: G = Graph([(0, 1, 'C'), (0, 2, 'A'), (1, 2, 'B')])
sage: E = EdgesView(G, sort=True, key=lambda x: x[2]); E
[(0, 2, 'A'), (1, 2, 'B'), (0, 1, 'C')]

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), 'C'), (Integer(0), Integer(2), 'A'), (Integer(1), Integer(2), 'B')])
>>> E = EdgesView(G, sort=True, key=lambda x: x[Integer(2)]); E
[(0, 2, 'A'), (1, 2, 'B'), (0, 1, 'C')]

Not sorting the ends of the vertices:

sage: G = Graph()
sage: G.add_edges([[1,2], [2,3], [0,3]])
sage: E = EdgesView(G, sort=False, sort_vertices=False); E
[(3, 0, None), (2, 1, None), (3, 2, None)]

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edges([[Integer(1),Integer(2)], [Integer(2),Integer(3)], [Integer(0),Integer(3)]])
>>> E = EdgesView(G, sort=False, sort_vertices=False); E
[(3, 0, None), (2, 1, None), (3, 2, None)]

With a directed graph:

sage: G = digraphs.DeBruijn(2, 2)                                               # needs sage.combinat
sage: E = EdgesView(G, labels=False, sort=True); E                              # needs sage.combinat
[('00', '00'), ('00', '01'), ('01', '10'), ('01', '11'),
 ('10', '00'), ('10', '01'), ('11', '10'), ('11', '11')]
sage: E = EdgesView(G, labels=False, sort=True, key=lambda e:(e[1], e[0])); E   # needs sage.combinat
[('00', '00'), ('10', '00'), ('00', '01'), ('10', '01'),
 ('01', '10'), ('11', '10'), ('01', '11'), ('11', '11')]

>>> from sage.all import *
>>> G = digraphs.DeBruijn(Integer(2), Integer(2))                                               # needs sage.combinat
>>> E = EdgesView(G, labels=False, sort=True); E                              # needs sage.combinat
[('00', '00'), ('00', '01'), ('01', '10'), ('01', '11'),
 ('10', '00'), ('10', '01'), ('11', '10'), ('11', '11')]
>>> E = EdgesView(G, labels=False, sort=True, key=lambda e:(e[Integer(1)], e[Integer(0)])); E   # needs sage.combinat
[('00', '00'), ('10', '00'), ('00', '01'), ('10', '01'),
 ('01', '10'), ('11', '10'), ('01', '11'), ('11', '11')]

We can consider only edges incident to a specified set of vertices:

sage: G = graphs.CycleGraph(5)
sage: E = EdgesView(G, vertices=[0, 1], labels=False, sort=True); E
[(0, 1), (0, 4), (1, 2)]
sage: E = EdgesView(G, vertices=[0], labels=False, sort=True); E
[(0, 1), (0, 4)]
sage: E = EdgesView(G, vertices=None, labels=False, sort=True); E
[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]

sage: G = digraphs.Circuit(5)
sage: E = EdgesView(G, vertices=[0, 1], labels=False, sort=True); E
[(0, 1), (1, 2)]

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(5))
>>> E = EdgesView(G, vertices=[Integer(0), Integer(1)], labels=False, sort=True); E
[(0, 1), (0, 4), (1, 2)]
>>> E = EdgesView(G, vertices=[Integer(0)], labels=False, sort=True); E
[(0, 1), (0, 4)]
>>> E = EdgesView(G, vertices=None, labels=False, sort=True); E
[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]

>>> G = digraphs.Circuit(Integer(5))
>>> E = EdgesView(G, vertices=[Integer(0), Integer(1)], labels=False, sort=True); E
[(0, 1), (1, 2)]

We can ignore the direction of the edges of a directed graph, in which case we search across edges in either direction:

sage: G = digraphs.Circuit(5)
sage: E = EdgesView(G, vertices=[0, 1], labels=False, sort=True, ignore_direction=False); E
[(0, 1), (1, 2)]
sage: (1, 0) in E
False
sage: E = EdgesView(G, vertices=[0, 1], labels=False, sort=True, ignore_direction=True); E
[(0, 1), (0, 1), (1, 2), (4, 0)]
sage: (1, 0) in E
True
sage: G.has_edge(1, 0)
False

>>> from sage.all import *
>>> G = digraphs.Circuit(Integer(5))
>>> E = EdgesView(G, vertices=[Integer(0), Integer(1)], labels=False, sort=True, ignore_direction=False); E
[(0, 1), (1, 2)]
>>> (Integer(1), Integer(0)) in E
False
>>> E = EdgesView(G, vertices=[Integer(0), Integer(1)], labels=False, sort=True, ignore_direction=True); E
[(0, 1), (0, 1), (1, 2), (4, 0)]
>>> (Integer(1), Integer(0)) in E
True
>>> G.has_edge(Integer(1), Integer(0))
False

We can consider only the edges between two specifed sets of vertices:

sage: G = Graph([(0, 1), (1, 2)])
sage: E = EdgesView(G, vertices=[0], vertices2=[1], labels=False)
sage: (0, 1) in E and (1, 2) not in E
True
sage: E = EdgesView(G, vertices=[0], labels=False)
sage: (0, 1) in E and (1, 2) not in E
True
sage: E = EdgesView(G, vertices2=[1], labels=False)
sage: (0, 1) in E and (1, 2) in E
True
sage: D = DiGraph([(0, 1), (1, 2)])
sage: E = EdgesView(D, vertices=[0], vertices2=[1], labels=False)
sage: (0, 1) in E and (1, 2) not in E
True
sage: EdgesView(D, vertices=[1], vertices2=[0], labels=False)
[]
sage: E = EdgesView(D, vertices=[1], vertices2=[0], labels=False, ignore_direction=True)
sage: (0, 1) in E and (1, 2) not in E
True
sage: E = EdgesView(D, vertices=[0], labels=False)
sage: (0, 1) in E and (1, 2) not in E
True
sage: E = EdgesView(D, vertices2=[1], labels=False)
sage: (0, 1) in E and (1, 2) not in E
True
sage: E = EdgesView(D, vertices2=[1], labels=False, ignore_direction=True)
sage: (0, 1) in E and (1, 2) in E
True

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(1), Integer(2))])
>>> E = EdgesView(G, vertices=[Integer(0)], vertices2=[Integer(1)], labels=False)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) not in E
True
>>> E = EdgesView(G, vertices=[Integer(0)], labels=False)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) not in E
True
>>> E = EdgesView(G, vertices2=[Integer(1)], labels=False)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) in E
True
>>> D = DiGraph([(Integer(0), Integer(1)), (Integer(1), Integer(2))])
>>> E = EdgesView(D, vertices=[Integer(0)], vertices2=[Integer(1)], labels=False)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) not in E
True
>>> EdgesView(D, vertices=[Integer(1)], vertices2=[Integer(0)], labels=False)
[]
>>> E = EdgesView(D, vertices=[Integer(1)], vertices2=[Integer(0)], labels=False, ignore_direction=True)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) not in E
True
>>> E = EdgesView(D, vertices=[Integer(0)], labels=False)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) not in E
True
>>> E = EdgesView(D, vertices2=[Integer(1)], labels=False)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) not in E
True
>>> E = EdgesView(D, vertices2=[Integer(1)], labels=False, ignore_direction=True)
>>> (Integer(0), Integer(1)) in E and (Integer(1), Integer(2)) in E
True

A view is updated as the graph is updated:

sage: G = Graph()
sage: E = EdgesView(G, vertices=[0, 3], labels=False, sort=True); E
[]
sage: G.add_edges([(0, 1), (1, 2)])
sage: E
[(0, 1)]
sage: G.add_edge(2, 3)
sage: E
[(0, 1), (2, 3)]

>>> from sage.all import *
>>> G = Graph()
>>> E = EdgesView(G, vertices=[Integer(0), Integer(3)], labels=False, sort=True); E
[]
>>> G.add_edges([(Integer(0), Integer(1)), (Integer(1), Integer(2))])
>>> E
[(0, 1)]
>>> G.add_edge(Integer(2), Integer(3))
>>> E
[(0, 1), (2, 3)]

Hence, the graph should not be updated while iterating through a view:

sage: G = Graph([('a', 'b'), ('b', 'c')])
sage: E = EdgesView(G, labels=False, sort=False); E
[('a', 'b'), ('b', 'c')]
sage: for u, v in E:
....:     G.add_edge(u + u, v + v)
Traceback (most recent call last):
...
RuntimeError: dictionary changed size during iteration

>>> from sage.all import *
>>> G = Graph([('a', 'b'), ('b', 'c')])
>>> E = EdgesView(G, labels=False, sort=False); E
[('a', 'b'), ('b', 'c')]
>>> for u, v in E:
...     G.add_edge(u + u, v + v)
Traceback (most recent call last):
...
RuntimeError: dictionary changed size during iteration

Two EdgesView are considered equal if they report either both directed, or both undirected edges, they have the same settings for ignore_direction, they have the same settings for labels, and they report the same edges in the same order:

sage: G = graphs.HouseGraph()
sage: EG = EdgesView(G, sort=False)
sage: H = Graph(EG)
sage: EH = EdgesView(H, sort=False)
sage: EG == EH
True
sage: G.add_edge(0, 10)
sage: EG = EdgesView(G, sort=False)
sage: EG == EH
False
sage: H.add_edge(0, 10)
sage: EH = EdgesView(H, sort=False)
sage: EG == EH
True
sage: H = G.strong_orientation()
sage: EH = EdgesView(H, sort=False)
sage: EG == EH
False

>>> from sage.all import *
>>> G = graphs.HouseGraph()
>>> EG = EdgesView(G, sort=False)
>>> H = Graph(EG)
>>> EH = EdgesView(H, sort=False)
>>> EG == EH
True
>>> G.add_edge(Integer(0), Integer(10))
>>> EG = EdgesView(G, sort=False)
>>> EG == EH
False
>>> H.add_edge(Integer(0), Integer(10))
>>> EH = EdgesView(H, sort=False)
>>> EG == EH
True
>>> H = G.strong_orientation()
>>> EH = EdgesView(H, sort=False)
>>> EG == EH
False

The sum of two EdgesView is a list containing the edges in both EdgesView:

sage: E1 = EdgesView(Graph([(0, 1)]), labels=False, sort=False)
sage: E2 = EdgesView(Graph([(2, 3)]), labels=False, sort=False)
sage: E1 + E2
[(0, 1), (2, 3)]
sage: E2 + E1
[(2, 3), (0, 1)]

>>> from sage.all import *
>>> E1 = EdgesView(Graph([(Integer(0), Integer(1))]), labels=False, sort=False)
>>> E2 = EdgesView(Graph([(Integer(2), Integer(3))]), labels=False, sort=False)
>>> E1 + E2
[(0, 1), (2, 3)]
>>> E2 + E1
[(2, 3), (0, 1)]

Recall that a EdgesView is read-only and that this method returns a list:

sage: E1 += E2
sage: type(E1) is list
True

>>> from sage.all import *
>>> E1 += E2
>>> type(E1) is list
True

It is also possible to get the sum a EdgesView with itself \(n\) times:

sage: E = EdgesView(Graph([(0, 1), (2, 3)]), labels=False, sort=True)
sage: E * 3
[(0, 1), (2, 3), (0, 1), (2, 3), (0, 1), (2, 3)]
sage: 3 * E
[(0, 1), (2, 3), (0, 1), (2, 3), (0, 1), (2, 3)]

>>> from sage.all import *
>>> E = EdgesView(Graph([(Integer(0), Integer(1)), (Integer(2), Integer(3))]), labels=False, sort=True)
>>> E * Integer(3)
[(0, 1), (2, 3), (0, 1), (2, 3), (0, 1), (2, 3)]
>>> Integer(3) * E
[(0, 1), (2, 3), (0, 1), (2, 3), (0, 1), (2, 3)]

Recall that a EdgesView is read-only and that this method returns a list:

sage: E *= 2
sage: type(E) is list
True

>>> from sage.all import *
>>> E *= Integer(2)
>>> type(E) is list
True

We can ask for the \(i\)-th edge, or a slice of the edges as a list:

sage: E = EdgesView(graphs.HouseGraph(), labels=False, sort=True)
sage: E[0]
(0, 1)
sage: E[2]
(1, 3)
sage: E[-1]
(3, 4)
sage: E[1:-1]
[(0, 2), (1, 3), (2, 3), (2, 4)]
sage: E[::-1]
[(3, 4), (2, 4), (2, 3), (1, 3), (0, 2), (0, 1)]

>>> from sage.all import *
>>> E = EdgesView(graphs.HouseGraph(), labels=False, sort=True)
>>> E[Integer(0)]
(0, 1)
>>> E[Integer(2)]
(1, 3)
>>> E[-Integer(1)]
(3, 4)
>>> E[Integer(1):-Integer(1)]
[(0, 2), (1, 3), (2, 3), (2, 4)]
>>> E[::-Integer(1)]
[(3, 4), (2, 4), (2, 3), (1, 3), (0, 2), (0, 1)]