Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Graph::topSort

Topological sorting of the vertices

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

Syntax

Graph::topSort(G)

Description

Graph::topSort(G) computes a topological sorting of the graph G, i.e., a numbering T of the vertices, such that Ti < Tj whenever there is an edge [i, j] in the graph. Single vertices are positioned at the beginning.

Graph::topSort returns a list containing two tables. The first table holds the ordering of the vertices. The second table shows the predecessors of each vertex. If several vertex ui precede a vertex v, the first vertex in the ordering of ui is the predecessor of v. If no predecessor exist, the value will be infinity.

    Note:   If G contains any cycle then a topological sorting does not exist and the call of Graph::topSort results in an error.

Examples

Example 1

A "butterfly" graph that is decomposed in three strongly connected components:

G1 := Graph([a, b, c, d, e, f],
            [[a, b], [a, c], [a, d], [c, e], [d, e]],
            Directed):
Graph::topSort(G1)

The first table shows the ordering of the vertices. The left side holds the order for each vertex, whereas the right side holds the name of the vertex. The second table shows the predecessors of each vertex. If no predecessor exist, the right side holds infinity. Otherwise the right side holds the vertex that is the direct predecessor of the vertex on the left side. To see how the graph looks a graphical plotting helps:

plot(Graph::plotGridGraph(G1, 
         VertexOrder = [None, b,    f,
                        a,    c,    None,
                        None, None, e,
                        None, d,    None], 
         VerticesPerLine=3))

Parameters

G

A graph

Return Values

List containing two tables.

Was this topic helpful?