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#
Bases:
object
EdgesView class.
This class implements a read-only iterable container of edges enabling operations like
for e in E
ande in E
. AnEdgesView
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 anEdgesView
.INPUT:
G
– a (di)graphvertices
– list (default:None
); an iterable container of vertices orNone
. When set, consider only edges incident to specified vertices.vertices2
– list (default:None
); an iterable container of vertices orNone
. When set, consider only edges incident to specified vertices. More precisely:When both
vertices
andvertices2
are set, consider only edges(u, v, l)
withu
invertices
andv
invertices2
.When
vertices
isNone
andvertices2
is set, consider only edges(u, v, l)
withv
invertices2
.
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:False
); whether to sort edges according the ordering specified with parameterkey
. IfFalse
(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 thelabels
keyword) 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 whensort
isFalse
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
isTrue
, 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) # 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')]
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
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
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 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
EdgesView
is 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
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)]