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, and also the vertex boundary

Classes

class sage.graphs.views.EdgesView

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.
  • 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: None); whether to sort edges
    • if None, sort edges according to the default ordering and give a deprecation warning as sorting will be set to False by default in the future
    • if True, edges are sorted according the ordering specified with parameter key
    • if False, edges are not sorted. This is the fastest and less memory consuming method for iterating over edges. This will become the default behavior in the future.
  • 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.

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)]

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))

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

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')]

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')]

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')]

With a directed graph:

sage: G = digraphs.DeBruijn(2, 2)
sage: E = EdgesView(G, labels=False, sort=True); E
[('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
[('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)]

We can ignore the direction of the edges of a directed graph, in which case we search accross 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

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)]

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

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

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)]

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

sage: E1 += E2
sage: 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)]

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

sage: E *= 2
sage: 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)]