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:
objectEdgesView class.
This class implements a read-only iterable container of edges enabling operations like
for e in Eande in E. AnEdgesViewcan 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 anEdgesView.INPUT:
G– a (di)graphvertices– list (default:None); an iterable container of vertices orNone. When set, consider only edges incident to specified vertices.labels– boolean (default:True); ifFalse, each edge is simply a pair(u, v)of verticesignore_direction– boolean (default:False); only applies to directed graphs. IfTrue, searches across edges in either direction.sort– boolean (default:None); whether to sort edgesif
None, sort edges according to the default ordering and give a deprecation warning as sorting will be set toFalseby default in the futureif
True, edges are sorted according the ordering specified with parameterkeyif
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 thelabelskeyword) as its one argument and returns a value that can be used for comparisons in the sorting algorithm. This parameter is ignored whensort = 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 whensortisFalse
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
keyargument, 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
EdgesViewcan 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
sortisTrue, 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')]
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)]
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 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
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
EdgesVieware considered equal if they report either both directed, or both undirected edges, they have the same settings forignore_direction, they have the same settings forlabels, 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
EdgesViewis a list containing the edges in bothEdgesView: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
EdgesViewis 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
EdgesViewwith 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
EdgesViewis 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)]