Graph traversals.¶
This module implements the following graph traversals
Perform a lexicographic breadth first search (LexBFS) on the graph. |
|
Perform a lexicographic depth first search (LexDFS) on the graph. |
|
Perform a lexicographic UP search (LexUP) on the graph. |
|
Perform a lexicographic DOWN search (LexDOWN) on the graph. |
|
Return an ordering of the vertices according the LexM graph traversal. |
|
Return an ordering of the vertices according the LexM graph traversal. |
|
Return an ordering of the vertices according the LexM graph traversal. |
Methods¶
-
sage.graphs.traversals.
is_valid_lex_M_order
(G, alpha, F)¶ Check whether the ordering alpha and the triangulation F are valid for G.
Given the graph \(G = (V, E)\) with vertex set \(V\) and edge set \(E\), and the set \(F\) of edges of a triangulation of \(G\), let \(H = (V, E\cup F)\). By induction one can see that for every \(i \in \{1, ..., n - 1\}\) the neighbors of \(\alpha(i)\) in \(H[\{\alpha(i), ..., \alpha(n)\}]\) induce a clique. The ordering \(\alpha\) is a perfect elimination ordering of \(H\), so \(H\) is chordal. See [RTL76] for more details.
INPUTS:
G
– a Graphalpha
– list; an ordering of the vertices of \(G\)F
– an iterable of edges given either as(u, v)
or(u, v, label)
, the edges of the triangulation of \(G\)
-
sage.graphs.traversals.
lex_BFS
(G, reverse=False, tree=False, initial_vertex=None)¶ Perform a lexicographic breadth first search (LexBFS) on the graph.
INPUT:
G
– a sage graphreverse
– boolean (default:False
); whether to return the vertices in discovery order, or the reversetree
– boolean (default:False
); whether to return the discovery directed tree (each vertex being linked to the one that saw it for the first time)initial_vertex
– (default:None
); the first vertex to consider
ALGORITHM:
This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated.
Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.
See [CK2008] for more details on the algorithm.
See also
lex_DFS()
– perform a lexicographic depth first search (LexDFS) on the graphlex_UP()
– perform a lexicographic UP search (LexUP) on the graphlex_DOWN()
– perform a lexicographic DOWN search (LexDOWN) on the graph
EXAMPLES:
A Lex BFS is obviously an ordering of the vertices:
sage: g = graphs.CompleteGraph(6) sage: len(g.lex_BFS()) == g.order() True
Lex BFS ordering of the 3-sun graph:
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: g.lex_BFS() [1, 2, 3, 5, 4, 6]
The method also works for directed graphs:
sage: G = DiGraph([(1, 2), (2, 3), (1, 3)]) sage: G.lex_BFS(initial_vertex=2) [2, 3, 1]
For a Chordal Graph, a reversed Lex BFS is a Perfect Elimination Order:
sage: g = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2)) sage: g.lex_BFS(reverse=True) # py2 [(2, 0), (2, 1), (1, 1), (1, 0), (0, 0), (0, 1)] sage: g.lex_BFS(reverse=True) # py3 [(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
And the vertices at the end of the tree of discovery are, for chordal graphs, simplicial vertices (their neighborhood is a complete graph):
sage: g = graphs.ClawGraph().lexicographic_product(graphs.CompleteGraph(2)) sage: v = g.lex_BFS()[-1] sage: peo, tree = g.lex_BFS(initial_vertex = v, tree=True) sage: leaves = [v for v in tree if tree.in_degree(v) ==0] sage: all(g.subgraph(g.neighbors(v)).is_clique() for v in leaves) True
Different orderings for different traversals:
sage: G = digraphs.DeBruijn(2,3) sage: G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] sage: G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] sage: G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] sage: G.lex_DOWN(initial_vertex='000') ['000', '001', '100', '011', '010', '110', '111', '101']
-
sage.graphs.traversals.
lex_DFS
(G, reverse=False, tree=False, initial_vertex=None)¶ Perform a lexicographic depth first search (LexDFS) on the graph.
INPUT:
G
– a sage graphreverse
– boolean (default:False
); whether to return the vertices in discovery order, or the reversetree
– boolean (default:False
); whether to return the discovery directed tree (each vertex being linked to the one that saw it for the first time)initial_vertex
– (default:None
); the first vertex to consider
ALGORITHM:
This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. Lex DFS differs from Lex BFS only in the way codes are updated after each iteration.
Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.
See [CK2008] for more details on the algorithm.
See also
lex_BFS()
– perform a lexicographic breadth first search (LexBFS) on the graphlex_UP()
– perform a lexicographic UP search (LexUP) on the graphlex_DOWN()
– perform a lexicographic DOWN search (LexDOWN) on the graph
EXAMPLES:
A Lex DFS is obviously an ordering of the vertices:
sage: g = graphs.CompleteGraph(6) sage: len(g.lex_DFS()) == g.order() True
Lex DFS ordering of the 3-sun graph:
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: g.lex_DFS() [1, 2, 3, 5, 6, 4]
The method also works for directed graphs:
sage: G = DiGraph([(1, 2), (2, 3), (1, 3)]) sage: G.lex_DFS(initial_vertex=2) [2, 3, 1]
Different orderings for different traversals:
sage: G = digraphs.DeBruijn(2,3) sage: G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] sage: G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] sage: G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] sage: G.lex_DOWN(initial_vertex='000') ['000', '001', '100', '011', '010', '110', '111', '101']
-
sage.graphs.traversals.
lex_DOWN
(G, reverse=False, tree=False, initial_vertex=None)¶ Perform a lexicographic DOWN search (LexDOWN) on the graph.
INPUT:
G
– a sage graphreverse
– boolean (default:False
); whether to return the vertices in discovery order, or the reversetree
– boolean (default:False
); whether to return the discovery directed tree (each vertex being linked to the one that saw it for the first time)initial_vertex
– (default:None
); the first vertex to consider
ALGORITHM:
This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. During the \(i\)-th iteration of the algorithm \(n-i\) is prepended to the codes of all neighbors of the selected vertex that are left in the graph.
Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.
See [Mil2017] for more details on the algorithm.
See also
EXAMPLES:
A Lex DOWN is obviously an ordering of the vertices:
sage: g = graphs.CompleteGraph(6) sage: len(g.lex_DOWN()) == g.order() True
Lex DOWN ordering of the 3-sun graph:
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: g.lex_DOWN() [1, 2, 3, 4, 6, 5]
The method also works for directed graphs:
sage: G = DiGraph([(1, 2), (2, 3), (1, 3)]) sage: G.lex_DOWN(initial_vertex=2) [2, 3, 1]
Different orderings for different traversals:
sage: G = digraphs.DeBruijn(2,3) sage: G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] sage: G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] sage: G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] sage: G.lex_DOWN(initial_vertex='000') ['000', '001', '100', '011', '010', '110', '111', '101']
-
sage.graphs.traversals.
lex_M
(self, triangulation=False, labels=False, initial_vertex=None, algorithm=None)¶ Return an ordering of the vertices according the LexM graph traversal.
LexM is a lexicographic ordering scheme that is a special type of breadth-first-search. LexM can also produce a triangulation of the given graph. This functionality is implemented in this method. For more details on the algorithms used see Sections 4 (
'lex_M_slow'
) and 5.3 ('lex_M_fast'
) of [RTL76].Note
This method works only for undirected graphs.
INPUT:
triangulation
– boolean (default:False
); whether to return a list of edges that need to be added in order to triangulate the graphlabels
– boolean (default:False
); whether to return the labels assigned to each vertexinitial_vertex
– (default:None
); the first vertex to consideralgorithm
– string (default:None
); one of the following algorithms:'lex_M_slow'
: slower implementation of LexM traversal'lex_M_fast'
: faster implementation of LexM traversal (works only whenlabels
is set toFalse
)None
: Sage chooses the best algorithm:'lex_M_slow'
iflabels
is set toTrue
,'lex_M_fast'
otherwise.
OUTPUT:
Depending on the values of the parameters
triangulation
andlabels
the method will return one or more of the following (in that order):an ordering of vertices of the graph according to LexM ordering scheme
the labels assigned to each vertex
a list of edges that when added to the graph will triangulate it
EXAMPLES:
LexM produces an ordering of the vertices:
sage: g = graphs.CompleteGraph(6) sage: ord = g.lex_M(algorithm='lex_M_fast') sage: len(ord) == g.order() True sage: set(ord) == set(g.vertices()) True sage: ord = g.lex_M(algorithm='lex_M_slow') sage: len(ord) == g.order() True sage: set(ord) == set(g.vertices()) True
Both algorithms produce a valid LexM ordering \(\alpha\) (i.e the neighbors of \(\alpha(i)\) in \(G[\{\alpha(i), ..., \alpha(n)\}]\) induce a clique):
sage: from sage.graphs.traversals import is_valid_lex_M_order sage: G = graphs.PetersenGraph() sage: ord, F = G.lex_M(triangulation=True, algorithm='lex_M_slow') sage: is_valid_lex_M_order(G, ord, F) True sage: ord, F = G.lex_M(triangulation=True, algorithm='lex_M_fast') sage: is_valid_lex_M_order(G, ord, F) True
LexM produces a triangulation of given graph:
sage: G = graphs.PetersenGraph() sage: _, F = G.lex_M(triangulation=True) sage: H = Graph(F, format='list_of_edges') sage: H.is_chordal() True
LexM ordering of the 3-sun graph:
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: g.lex_M() [6, 4, 5, 3, 2, 1]
-
sage.graphs.traversals.
lex_M_fast
(G, triangulation=False, initial_vertex=None)¶ Return an ordering of the vertices according the LexM graph traversal.
LexM is a lexicographic ordering scheme that is a special type of breadth-first-search. This function implements the algorithm described in Section 5.3 of [RTL76].
Note that instead of using labels \(1, 2, \ldots, k\) and adding \(1/2\), we use labels \(2, 4, \ldots, k\) and add \(1\), thus avoiding to use floats or rationals.
Note
This method works only for undirected graphs.
INPUT:
G
– a sage graphtriangulation
– boolean (default:False
); whether to return the triangulation of given graph produced by the methodinitial_vertex
– (default:None
); the first vertex to consider
OUTPUT:
This method will return an ordering of the vertices of
G
according to the LexM ordering scheme. Furthermore, iftriangulation
is set toTrue
the method also returns a list of edgesF
such that when added toG
the resulting graph is a triangulation ofG
.EXAMPLES:
A LexM ordering is obviously an ordering of the vertices:
sage: from sage.graphs.traversals import lex_M_fast sage: g = graphs.CompleteGraph(6) sage: len(lex_M_fast(g)) == g.order() True
LexM ordering of the 3-sun graph:
sage: from sage.graphs.traversals import lex_M_fast sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: lex_M_fast(g) [6, 4, 5, 3, 2, 1]
LexM produces a triangulation of given graph:
sage: from sage.graphs.traversals import lex_M_fast sage: G = graphs.PetersenGraph() sage: _, F = lex_M_fast(G, triangulation=True) sage: H = G.copy() sage: H.add_edges(F) sage: H.is_chordal() True
-
sage.graphs.traversals.
lex_M_slow
(G, triangulation=False, labels=False, initial_vertex=None)¶ Return an ordering of the vertices according the LexM graph traversal.
LexM is a lexicographic ordering scheme that is a special type of breadth-first-search. This function implements the algorithm described in Section 4 of [RTL76].
During the search, the vertices are numbered from \(n\) to \(1\). Let \(\alpha(i)\) denote the vertex numbered \(i\) and let \(\alpha^{-1}(u)\) denote the number assigned to \(u\). Each vertex \(u\) has also a label, denoted by \(label(u)\), consisting of a list of numbers selected from \([1,n]\) and ordered in decreasing order. Given two labels \(L_1=[p_1, p_2,\ldots, p_k]\) and \(L_1=[q_1, q_2,\ldots, q_l]\), we define \(L_1<L_2\) if, for some \(j\), \(p_i==q_i\) for \(i=1,\ldots,j-1\) and \(p_j<q_j\), or if \(p_i==q_i\) for \(i=1,\ldots,k\) and \(k<l\). Observe that this is exactly how Python compares two lists.
Note
This method works only for undirected graphs.
INPUT:
G
– a sage graphtriangulation
– boolean (default:False
); whether to return the triangulation of the graph produced by the methodlabels
– boolean (default:False
); whether to return the labels assigned to each vertexinitial_vertex
– (default:None
); the first vertex to consider. If not specified, an arbitrary vertex is chosen.
OUTPUT:
Depending on the values of the parameters
triangulation
andlabels
the method will return one or more of the following (in that order):the ordering of vertices of \(G\)
the labels assigned to each vertex
a list of edges that when added to \(G\) will produce a triangulation of \(G\)
EXAMPLES:
A LexM ordering is obviously an ordering of the vertices:
sage: from sage.graphs.traversals import lex_M_slow sage: g = graphs.CompleteGraph(6) sage: len(lex_M_slow(g)) == g.order() True
LexM ordering and label assignments on the vertices of the 3-sun graph:
sage: from sage.graphs.traversals import lex_M_slow sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: lex_M_slow(g, labels=True) ([6, 4, 5, 3, 2, 1], {1: [], 2: [5], 3: [5, 4], 4: [4, 2], 5: [4, 3], 6: [3, 2]})
LexM produces a triangulation of given graph:
sage: from sage.graphs.traversals import lex_M_slow sage: G = graphs.PetersenGraph() sage: _, F = lex_M_slow(G, triangulation=True) sage: H = G.copy() sage: H.add_edges(F) sage: H.is_chordal() True
-
sage.graphs.traversals.
lex_UP
(G, reverse=False, tree=False, initial_vertex=None)¶ Perform a lexicographic UP search (LexUP) on the graph.
INPUT:
G
– a sage graphreverse
– boolean (default:False
); whether to return the vertices in discovery order, or the reversetree
– boolean (default:False
); whether to return the discovery directed tree (each vertex being linked to the one that saw it for the first time)initial_vertex
– (default:None
); the first vertex to consider
ALGORITHM:
This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. During the \(i\)-th iteration of the algorithm \(i\) is appended to the codes of all neighbors of the selected vertex that are left in the graph.
Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.
See [Mil2017] for more details on the algorithm.
See also
lex_BFS()
– perform a lexicographic breadth first search (LexBFS) on the graphlex_DFS()
– perform a lexicographic depth first search (LexDFS) on the graphlex_DOWN()
– perform a lexicographic DOWN search (LexDOWN) on the graph
EXAMPLES:
A Lex UP is obviously an ordering of the vertices:
sage: g = graphs.CompleteGraph(6) sage: len(g.lex_UP()) == g.order() True
Lex UP ordering of the 3-sun graph:
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)]) sage: g.lex_UP() [1, 2, 4, 5, 6, 3]
The method also works for directed graphs:
sage: G = DiGraph([(1, 2), (2, 3), (1, 3)]) sage: G.lex_UP(initial_vertex=2) [2, 3, 1]
Different orderings for different traversals:
sage: G = digraphs.DeBruijn(2,3) sage: G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] sage: G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] sage: G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] sage: G.lex_DOWN(initial_vertex='000') ['000', '001', '100', '011', '010', '110', '111', '101']