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. 

Return an ordering of the vertices according a maximum cardinality search. 

Return the ordering and the edges of the triangulation produced by MCSM. 
Methods#
 sage.graphs.traversals.is_valid_lex_M_order(G, alpha, F)[source]#
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.
INPUT:
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, algorithm='fast')[source]#
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 consideralgorithm
– string (default:"fast"
); algorithm to use among:"slow"
– 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. See for instance [CK2008] for more details. The time complexity of this algorithm as described in [CK2008] is in \(O(n + m)\), where \(n\) is the number of vertices and \(m\) is the number of edges, but our implementation is in \(O(n^2)\)."fast"
– This algorithm uses the notion of slices to refine the position of the vertices in the ordering. The time complexity of this algorithm is in \(O(n + m)\), and our implementation follows that complexity forSparseGraph
. ForDenseGraph
, the complexity is \(O(n^2)\). See [HMPV2000] and next section for more details.
ALGORITHM:
The
"fast"
algorithm is the \(O(n + m)\) time algorithm proposed in [HMPV2000], where \(n\) is the number of vertices and \(m\) is the number of edges. It uses the notion of slices, i.e., subsets of consecutive vertices in the ordering, and iteratively refines the slices by subdividing them into subslices to determine the exact position of the vertices in the ordering.Consider an ordering \(\sigma\) of the vertices. For a vertex \(v\), we define \(N_i(v) = \{u  u \in N(v) \text{ and } \sigma(u) < i\}\), that is the subset of neighbors of \(v\) appearing before the \(i\)th vertex in the ordering \(\sigma\). Now, a slice of an ordering \(\sigma\) is a set of consecutive vertices, \(S = \{u  i \leq \sigma(u) \leq j\}\), such that for any \(u \in S\), we have \(N_i(u) = N_i(\sigma^{1}(i))\) and for any \(v\) such that \(j < \sigma(v)\), \(N_i(v) \neq N_i(\sigma^{1}(i))\). The head of a slice is the first position of its vertices.
The algorithm starts with a single slice containing all vertices. Then, when the position of the \(i\)th vertex \(v\) is fixed, it explores the neighbors of \(v\) that have not yet been ordered. Consider a slice \(S\) such that \(N(x)\cap S \neq \emptyset\). The algorithm will rearrange the ordering of the vertices in \(S\) so that the first vertices are the neighbors of \(v\). The subslice containing the neighbors of \(v\) is assigned a new slice name, and the head of slice \(S\) is set to the position of the first vertex of \(S \setminus N(v)\) in the ordering \(\sigma\).
Observe that each arc of the graph can induce the subdivision of a slice. Hence, the algorithm can use up to \(m + 1\) different slices.
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
>>> from sage.all import * >>> g = graphs.CompleteGraph(Integer(6)) >>> len(g.lex_BFS()) == g.order() True
Lex BFS ordering of the 3sun 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]
>>> from sage.all import * >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> 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, algorithm="slow") [2, 3, 1] sage: G.lex_BFS(initial_vertex=2, algorithm="fast") [2, 3, 1]
>>> from sage.all import * >>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))]) >>> G.lex_BFS(initial_vertex=Integer(2), algorithm="slow") [2, 3, 1] >>> G.lex_BFS(initial_vertex=Integer(2), algorithm="fast") [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) [(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
>>> from sage.all import * >>> g = graphs.PathGraph(Integer(3)).lexicographic_product(graphs.CompleteGraph(Integer(2))) >>> g.lex_BFS(reverse=True) [(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
>>> from sage.all import * >>> g = graphs.ClawGraph().lexicographic_product(graphs.CompleteGraph(Integer(2))) >>> v = g.lex_BFS()[Integer(1)] >>> peo, tree = g.lex_BFS(initial_vertex = v, tree=True) >>> leaves = [v for v in tree if tree.in_degree(v) ==Integer(0)] >>> all(g.subgraph(g.neighbors(v)).is_clique() for v in leaves) True
Different orderings for different traversals:
sage: # needs sage.combinat sage: G = digraphs.DeBruijn(2,3) sage: G.lex_BFS(initial_vertex='000', algorithm="fast") ['000', '001', '100', '010', '011', '110', '101', '111'] sage: G.lex_BFS(initial_vertex='000', algorithm="slow") ['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']
>>> from sage.all import * >>> # needs sage.combinat >>> G = digraphs.DeBruijn(Integer(2),Integer(3)) >>> G.lex_BFS(initial_vertex='000', algorithm="fast") ['000', '001', '100', '010', '011', '110', '101', '111'] >>> G.lex_BFS(initial_vertex='000', algorithm="slow") ['000', '001', '100', '010', '011', '110', '101', '111'] >>> G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] >>> G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] >>> 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)[source]#
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)\) for
SparseGraph
and \(O(n^2)\) forDenseGraph
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
>>> from sage.all import * >>> g = graphs.CompleteGraph(Integer(6)) >>> len(g.lex_DFS()) == g.order() True
Lex DFS ordering of the 3sun 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]
>>> from sage.all import * >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> 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]
>>> from sage.all import * >>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))]) >>> G.lex_DFS(initial_vertex=Integer(2)) [2, 3, 1]
Different orderings for different traversals:
sage: # needs sage.combinat 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']
>>> from sage.all import * >>> # needs sage.combinat >>> G = digraphs.DeBruijn(Integer(2),Integer(3)) >>> G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] >>> G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] >>> G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] >>> 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)[source]#
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 \(ni\) is prepended to the codes of all neighbors of the selected vertex that are left in the graph.
Time complexity is \(O(n+m)\) for
SparseGraph
and \(O(n^2)\) forDenseGraph
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
>>> from sage.all import * >>> g = graphs.CompleteGraph(Integer(6)) >>> len(g.lex_DOWN()) == g.order() True
Lex DOWN ordering of the 3sun 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]
>>> from sage.all import * >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> 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]
>>> from sage.all import * >>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))]) >>> G.lex_DOWN(initial_vertex=Integer(2)) [2, 3, 1]
Different orderings for different traversals:
sage: # needs sage.combinat 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']
>>> from sage.all import * >>> # needs sage.combinat >>> G = digraphs.DeBruijn(Integer(2),Integer(3)) >>> G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] >>> G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] >>> G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] >>> 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)[source]#
Return an ordering of the vertices according the LexM graph traversal.
LexM is a lexicographic ordering scheme that is a special type of breadthfirstsearch. 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(sort=False)) True sage: ord = g.lex_M(algorithm='lex_M_slow') sage: len(ord) == g.order() True sage: set(ord) == set(g.vertices(sort=False)) True
>>> from sage.all import * >>> g = graphs.CompleteGraph(Integer(6)) >>> ord = g.lex_M(algorithm='lex_M_fast') >>> len(ord) == g.order() True >>> set(ord) == set(g.vertices(sort=False)) True >>> ord = g.lex_M(algorithm='lex_M_slow') >>> len(ord) == g.order() True >>> set(ord) == set(g.vertices(sort=False)) 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
>>> from sage.all import * >>> from sage.graphs.traversals import is_valid_lex_M_order >>> G = graphs.PetersenGraph() >>> ord, F = G.lex_M(triangulation=True, algorithm='lex_M_slow') >>> is_valid_lex_M_order(G, ord, F) True >>> ord, F = G.lex_M(triangulation=True, algorithm='lex_M_fast') >>> 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
>>> from sage.all import * >>> G = graphs.PetersenGraph() >>> _, F = G.lex_M(triangulation=True) >>> H = Graph(F, format='list_of_edges') >>> H.is_chordal() True
LexM ordering of the 3sun 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]
>>> from sage.all import * >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> g.lex_M() [6, 4, 5, 3, 2, 1]
 sage.graphs.traversals.lex_M_fast(G, triangulation=False, initial_vertex=None)[source]#
Return an ordering of the vertices according the LexM graph traversal.
LexM is a lexicographic ordering scheme that is a special type of breadthfirstsearch. 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
>>> from sage.all import * >>> from sage.graphs.traversals import lex_M_fast >>> g = graphs.CompleteGraph(Integer(6)) >>> len(lex_M_fast(g)) == g.order() True
LexM ordering of the 3sun 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]
>>> from sage.all import * >>> from sage.graphs.traversals import lex_M_fast >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> 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
>>> from sage.all import * >>> from sage.graphs.traversals import lex_M_fast >>> G = graphs.PetersenGraph() >>> _, F = lex_M_fast(G, triangulation=True) >>> H = G.copy() >>> H.add_edges(F) >>> H.is_chordal() True
 sage.graphs.traversals.lex_M_slow(G, triangulation=False, labels=False, initial_vertex=None)[source]#
Return an ordering of the vertices according the LexM graph traversal.
LexM is a lexicographic ordering scheme that is a special type of breadthfirstsearch. 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,j1\) 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
>>> from sage.all import * >>> from sage.graphs.traversals import lex_M_slow >>> g = graphs.CompleteGraph(Integer(6)) >>> len(lex_M_slow(g)) == g.order() True
LexM ordering and label assignments on the vertices of the 3sun 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]})
>>> from sage.all import * >>> from sage.graphs.traversals import lex_M_slow >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> 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
>>> from sage.all import * >>> from sage.graphs.traversals import lex_M_slow >>> G = graphs.PetersenGraph() >>> _, F = lex_M_slow(G, triangulation=True) >>> H = G.copy() >>> H.add_edges(F) >>> H.is_chordal() True
 sage.graphs.traversals.lex_UP(G, reverse=False, tree=False, initial_vertex=None)[source]#
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)\) for
SparseGraph
and \(O(n^2)\) forDenseGraph
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
>>> from sage.all import * >>> g = graphs.CompleteGraph(Integer(6)) >>> len(g.lex_UP()) == g.order() True
Lex UP ordering of the 3sun 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]
>>> from sage.all import * >>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))]) >>> 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]
>>> from sage.all import * >>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))]) >>> G.lex_UP(initial_vertex=Integer(2)) [2, 3, 1]
Different orderings for different traversals:
sage: # needs sage.combinat 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']
>>> from sage.all import * >>> # needs sage.combinat >>> G = digraphs.DeBruijn(Integer(2),Integer(3)) >>> G.lex_BFS(initial_vertex='000') ['000', '001', '100', '010', '011', '110', '101', '111'] >>> G.lex_DFS(initial_vertex='000') ['000', '001', '100', '010', '101', '110', '011', '111'] >>> G.lex_UP(initial_vertex='000') ['000', '001', '010', '101', '110', '111', '011', '100'] >>> G.lex_DOWN(initial_vertex='000') ['000', '001', '100', '011', '010', '110', '111', '101']
 sage.graphs.traversals.maximum_cardinality_search(G, reverse=False, tree=False, initial_vertex=None)[source]#
Return an ordering of the vertices according a maximum cardinality search.
Maximum cardinality search (MCS) is a graph traversal introduced in [TY1984]. It starts by assigning an arbitrary vertex (or the specified
initial_vertex
) of \(G\) the last position in the ordering \(\alpha\). Every vertex keeps a weight equal to the number of its already processed neighbors (i.e., already added to \(\alpha\)), and a vertex of largest such number is chosen at each step \(i\) to be placed in position \(n  i\) in \(\alpha\). This ordering can be computed in time \(O(n + m)\).Time complexity is \(O(n+m)\) for
SparseGraph
and \(O(n^2)\) forDenseGraph
where \(n\) is the number of vertices and \(m\) is the number of edges.When the graph is chordal, the ordering returned by MCS is a perfect elimination ordering, like
lex_BFS()
. So this ordering can be used to recognize chordal graphs. See [He2006] for more details.Note
The current implementation is for connected graphs only.
INPUT:
G
– a Sage graphreverse
– boolean (default:False
); whether to return the vertices in discovery order, or the reversetree
– boolean (default:False
); whether to also 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
OUTPUT:
By default, return the ordering \(\alpha\) as a list. When
tree
isTrue
, the method returns a tuple \((\alpha, T)\), where \(T\) is a directed tree with the same set of vertices as \(G\) and a directed edge from \(u\) to \(v\) if \(u\) was the first vertex to see \(v\).EXAMPLES:
When specified, the
initial_vertex
is placed at the end of the ordering, unless parameterreverse
isTrue
, in which case it is placed at the beginning:sage: G = graphs.PathGraph(4) sage: G.maximum_cardinality_search(initial_vertex=0) [3, 2, 1, 0] sage: G.maximum_cardinality_search(initial_vertex=1) [0, 3, 2, 1] sage: G.maximum_cardinality_search(initial_vertex=2) [0, 1, 3, 2] sage: G.maximum_cardinality_search(initial_vertex=3) [0, 1, 2, 3] sage: G.maximum_cardinality_search(initial_vertex=3, reverse=True) [3, 2, 1, 0]
>>> from sage.all import * >>> G = graphs.PathGraph(Integer(4)) >>> G.maximum_cardinality_search(initial_vertex=Integer(0)) [3, 2, 1, 0] >>> G.maximum_cardinality_search(initial_vertex=Integer(1)) [0, 3, 2, 1] >>> G.maximum_cardinality_search(initial_vertex=Integer(2)) [0, 1, 3, 2] >>> G.maximum_cardinality_search(initial_vertex=Integer(3)) [0, 1, 2, 3] >>> G.maximum_cardinality_search(initial_vertex=Integer(3), reverse=True) [3, 2, 1, 0]
Returning the discovery tree:
sage: G = graphs.PathGraph(4) sage: _, T = G.maximum_cardinality_search(tree=True, initial_vertex=0) sage: T.order(), T.size() (4, 3) sage: T.edges(labels=False, sort=True) [(1, 0), (2, 1), (3, 2)] sage: _, T = G.maximum_cardinality_search(tree=True, initial_vertex=3) sage: T.edges(labels=False, sort=True) [(0, 1), (1, 2), (2, 3)]
>>> from sage.all import * >>> G = graphs.PathGraph(Integer(4)) >>> _, T = G.maximum_cardinality_search(tree=True, initial_vertex=Integer(0)) >>> T.order(), T.size() (4, 3) >>> T.edges(labels=False, sort=True) [(1, 0), (2, 1), (3, 2)] >>> _, T = G.maximum_cardinality_search(tree=True, initial_vertex=Integer(3)) >>> T.edges(labels=False, sort=True) [(0, 1), (1, 2), (2, 3)]
 sage.graphs.traversals.maximum_cardinality_search_M(G, initial_vertex=None)[source]#
Return the ordering and the edges of the triangulation produced by MCSM.
Maximum cardinality search M (MCSM) is an extension of MCS (
maximum_cardinality_search()
) in the same way that LexM (lex_M()
) is an extension of LexBFS (lex_BFS()
). That is, in MCSM when \(u\) receives number \(i\) at step \(n  i + 1\), it increments the weight of all unnumbered vertices \(v\) for which there exists a path between \(u\) and \(v\) consisting only of unnumbered vertices with weight strictly less than \(w^(u)\) and \(w^(v)\), where \(w^\) is the number of times a vertex has been reached during previous iterations. See [BBHP2004] for the details of this \(O(nm)\) time algorithm.If \(G\) is not connected, the orderings of each of its connected components are added consecutively. Furthermore, if \(G\) has \(k\) connected components \(C_i\) for \(0 \leq i < k\), \(X\) contains at least one vertex of \(C_i\) for each \(i \geq 1\). Hence, \(X \geq k  1\). In particular, some isolated vertices (i.e., of degree 0) can appear in \(X\) as for such a vertex \(x\), we have that \(G \setminus N(x) = G\) is not connected.
INPUT:
G
– a Sage graphinitial_vertex
– (default:None
); the first vertex to consider
OUTPUT: a tuple \((\alpha, F, X)\), where
\(\alpha\) is the resulting ordering of the vertices. If an initial vertex is specified, it gets the last position in the ordering \(\alpha\).
\(F\) is the list of edges of a minimal triangulation of \(G\) according \(\alpha\)
\(X\) is a list of vertices such that for each \(x \in X\), the neighborhood of \(x\) in \(G\) is a separator (i.e., \(G \setminus N(x)\) is not connected). Note that we may have \(N(x) = \emptyset\) if \(G\) is not connected and \(x\) has degree 0.
EXAMPLES:
Chordal graphs have a perfect elimination ordering, and so the set \(F\) of edges of the triangulation is empty:
sage: G = graphs.RandomChordalGraph(20) sage: alpha, F, X = G.maximum_cardinality_search_M(); F []
>>> from sage.all import * >>> G = graphs.RandomChordalGraph(Integer(20)) >>> alpha, F, X = G.maximum_cardinality_search_M(); F []
The cycle of order 4 is not chordal and so the triangulation has one edge:
sage: G = graphs.CycleGraph(4) sage: alpha, F, X = G.maximum_cardinality_search_M(); len(F) 1
>>> from sage.all import * >>> G = graphs.CycleGraph(Integer(4)) >>> alpha, F, X = G.maximum_cardinality_search_M(); len(F) 1
The number of edges needed to triangulate of a cycle graph or order \(n\) is \(n  3\), independently of the initial vertex:
sage: n = randint(3, 20) sage: C = graphs.CycleGraph(n) sage: _, F, X = C.maximum_cardinality_search_M() sage: len(F) == n  3 True sage: _, F, X = C.maximum_cardinality_search_M(initial_vertex=C.random_vertex()) sage: len(F) == n  3 True
>>> from sage.all import * >>> n = randint(Integer(3), Integer(20)) >>> C = graphs.CycleGraph(n) >>> _, F, X = C.maximum_cardinality_search_M() >>> len(F) == n  Integer(3) True >>> _, F, X = C.maximum_cardinality_search_M(initial_vertex=C.random_vertex()) >>> len(F) == n  Integer(3) True
When an initial vertex is specified, it gets the last position in the ordering:
sage: G = graphs.PathGraph(4) sage: G.maximum_cardinality_search_M(initial_vertex=0) ([3, 2, 1, 0], [], [2, 3]) sage: G.maximum_cardinality_search_M(initial_vertex=1) ([3, 2, 0, 1], [], [2, 3]) sage: G.maximum_cardinality_search_M(initial_vertex=2) ([0, 1, 3, 2], [], [0, 1]) sage: G.maximum_cardinality_search_M(initial_vertex=3) ([0, 1, 2, 3], [], [0, 1])
>>> from sage.all import * >>> G = graphs.PathGraph(Integer(4)) >>> G.maximum_cardinality_search_M(initial_vertex=Integer(0)) ([3, 2, 1, 0], [], [2, 3]) >>> G.maximum_cardinality_search_M(initial_vertex=Integer(1)) ([3, 2, 0, 1], [], [2, 3]) >>> G.maximum_cardinality_search_M(initial_vertex=Integer(2)) ([0, 1, 3, 2], [], [0, 1]) >>> G.maximum_cardinality_search_M(initial_vertex=Integer(3)) ([0, 1, 2, 3], [], [0, 1])
When \(G\) is not connected, the orderings of each of its connected components are added consecutively, the vertices of the component containing the initial vertex occupying the last positions:
sage: G = graphs.CycleGraph(4) * 2 sage: G.maximum_cardinality_search_M()[0] [5, 4, 6, 7, 2, 3, 1, 0] sage: G.maximum_cardinality_search_M(initial_vertex=7)[0] [2, 1, 3, 0, 5, 6, 4, 7]
>>> from sage.all import * >>> G = graphs.CycleGraph(Integer(4)) * Integer(2) >>> G.maximum_cardinality_search_M()[Integer(0)] [5, 4, 6, 7, 2, 3, 1, 0] >>> G.maximum_cardinality_search_M(initial_vertex=Integer(7))[Integer(0)] [2, 1, 3, 0, 5, 6, 4, 7]
Furthermore, if \(G\) has \(k\) connected components, \(X\) contains at least one vertex per connected component, except for the first one, and so at least \(k  1\) vertices:
sage: for k in range(1, 5): ....: _, _, X = Graph(k).maximum_cardinality_search_M() ....: if len(X) < k  1: ....: raise ValueError("something goes wrong") sage: G = graphs.RandomGNP(10, .2) sage: cc = G.connected_components(sort=False) sage: _, _, X = G.maximum_cardinality_search_M() sage: len(X) >= len(cc)  1 True
>>> from sage.all import * >>> for k in range(Integer(1), Integer(5)): ... _, _, X = Graph(k).maximum_cardinality_search_M() ... if len(X) < k  Integer(1): ... raise ValueError("something goes wrong") >>> G = graphs.RandomGNP(Integer(10), RealNumber('.2')) >>> cc = G.connected_components(sort=False) >>> _, _, X = G.maximum_cardinality_search_M() >>> len(X) >= len(cc)  Integer(1) True
In the example of [BPS2010], the triangulation has 3 edges:
sage: G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'], ....: 'd': ['e', 'f', 'j', 'k'], 'e': ['g'], ....: 'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'], ....: 'i': ['k'], 'j': ['k']}) sage: _, F, _ = G.maximum_cardinality_search_M(initial_vertex='a') sage: len(F) 3
>>> from sage.all import * >>> G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'], ... 'd': ['e', 'f', 'j', 'k'], 'e': ['g'], ... 'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'], ... 'i': ['k'], 'j': ['k']}) >>> _, F, _ = G.maximum_cardinality_search_M(initial_vertex='a') >>> len(F) 3