They form the finest partition of the set of vertices that is totally ordered in this way.
The weak components were defined in a 1972 paper by Ronald Graham, Donald Knuth, and (posthumously) Theodore Motzkin, by analogy to the strongly connected components of a directed graph, which form the finest possible partition of the graph's vertices into subsets that are partially ordered by reachability.
Instead, they defined the weak components to be the finest partition of the vertices into subsets that are totally ordered by reachability.
[1][2] In more detail, Knuth (2022) defines the weak components through a combination of four symmetric relations on the vertices of any directed graph, denoted here as
(because it can reach itself in both directions by paths of length zero), any two vertices that are related by
These equivalence classes are the weak components of the given graph.
[2] The original definition by Graham, Knuth, and Motzkin is equivalent but formulated somewhat differently.
as the complement graph of the transitive closure of
represent non-paths, pairs of vertices that are not connected by a path in
[1][3] As Graham, Knuth, and Motzkin show, this condition defines an equivalence relation,[1] the same one defined above as
It differs from other notions of weak connectivity in the literature, such as connectivity and components in the underlying undirected graph, for which Knuth suggests the alternative terminology undirected components.
are two weak components of a directed graph, then either all vertices in
However, there cannot exist reachability relations in both directions between these two components.
Therefore, we can define an ordering on the weak components, according to which
Therefore, it defines a total ordering on the weak components.
It is the finest possible partition of the vertices into a totally ordered set of vertices consistent with reachability.
[1] This ordering on the weak components can alternatively be interpreted as a weak ordering on the vertices themselves, with the property that when
in the weak ordering, there necessarily exists a path from
However, this is not a complete characterization of this weak ordering, because two vertices
could have this same reachability ordering while belonging to the same weak component as each other.
[2] If the strongly connected components of any given graph are contracted to single vertices, producing a directed acyclic graph (the condensation of the given graph), and then this condensation is topologically sorted, then each weak component necessarily appears as a consecutive subsequence of the topological order of the strong components.
[3] An algorithm for computing the weak components of a given directed graph in linear time was described by Pacault (1974), and subsequently simplified by Tarjan (1974) and Knuth (2022).
[2][3][5] As Tarjan observes, Tarjan's strongly connected components algorithm based on depth-first search will output the strongly connected components in (the reverse of) a topologically sorted order.
[2][3] It is convenient to maintain the current partition into weak components in a stack, with each weak component maintaining additionally a list of its sources, strongly connected components that have no incoming edges from other strongly connected components in the same weak component, with the most recently generated source first.
Each newly generated strongly connected component may form a new weak component on its own, or may end up merged with some of the previously constructed weak components near the top of the stack, the ones for which it cannot reach all sources.
[2][3] Thus, the algorithm performs the following steps:[2][3] Each test for whether any edges from
hit a weak component can be performed in constant time once we find an edge from