Skip to main content
Computer Science

Return to Answer

added 157 characters in body
Source Link
Russel
Russel
  • 2.8k
  • 1
  • 8
  • 16

In my discussion, I will assume that the $|V|$ vertices of the DAG are represented as integers $0,1,..., |V|-1$ so they can be used as indices of an array. In case, different "labeling" is used, all arrays used in the solution can be replaced by any dictionary structure. Also, it is assumed that the DAG is represented as an adjacency list.

Idea

The idea behind the algorithm below is based on the observation that if vertex $v$ is the only source (a vertex with no incoming edge) in the DAG then $v$'s position must be fixed in the topological sort. Now, removing $v$ and all its out-going edges from the DAG might create 0 or more sources. If in case only one new source is created, then this new source has fixed position too. If multiple sources are created, then all these new sources cannot have fixed position, since their order with respect to each other can be arbitrary. You just have to repeat this process until all vertices are classified and removed. However, if in case a newly created source $v'$ is also a sink (a vertex with no outgoing edge), then any remaining vertex $u$ in the graph cannot have a fixed position since $v'$ can appear before or after $u$ in the topological order.

Algorithm

The algorithm can be viewed as BFS-based topological sorting algorithm. Let $I$ be an array containing the number of incoming edges of each vertex $v$. Let $Q$ be the queue. Then, let $F$ be a Boolean array, initially filled with false values, that will be used to set the mark of a vertex whether it has fixed position or not, e.g. $F[v]$ is true if vertex $v$ has fixed position. Finally, let $sinked$ be a Boolean variable, initially false, that will indicate if a source that is also a sink has been found. The algorithm is as follows:

  1. Fill $I$ with values by scanning the adjacency list of the DAG.
  2. Scan $I$ to find the sources, e.g. vertices whose value in $I$ is 0. When a source is found, insert it to $Q$.
  3. Let $s$ be the number of vertices in $Q$. Repeat the following $s$ times:
    1. Remove a vertex $v$ from $Q$.
    2. If $s > 1$ or $sinked$ is true, set $F[v]$ to false.
    3. If $v$ is a sink, set $sinked$ to true.
    4. For each neighbor $u$ of $v$ in the DAG, decrement $I[u]$ by 1. If after this, $I[u]$ becomes 0, insert $u$ to $Q$.
  4. If $Q$ is not empty, repeat step 3, otherwise scan $F$ to find all vertices marked as fixed (set to true).

Analysis

Step 1 of the algorithm can be performed in $O(|V|+|E|)$ time. Step two takes $O(|V|)$ time. While the remaining part is just BFS, with the modification that a vertex will only be added to $Q$ if it's a source. This is equivalent to adding a vertex, the last time it was found during BFS, which unlike the usual case where the vertex is added the first time it was found. Since BFS takes $O(|V|+|E|)$ time, the entire algorithm takes $O(|V|+|E|)$ time, which is linear.

Note

This algorithm is a modification of Kahn's Topological sorting algorithm.

In my discussion, I will assume that the $|V|$ vertices of the DAG are represented as integers $0,1,..., |V|-1$ so they can be used as indices of an array. In case, different "labeling" is used, all arrays used in the solution can be replaced by any dictionary structure. Also, it is assumed that the DAG is represented as an adjacency list.

Idea

The idea behind the algorithm below is based on the observation that if vertex $v$ is the only source (a vertex with no incoming edge) in the DAG then $v$'s position must be fixed in the topological sort. Now, removing $v$ and all its out-going edges from the DAG might create 0 or more sources. If in case only one new source is created, then this new source has fixed position too. If multiple sources are created, then all these new sources cannot have fixed position, since their order with respect to each other can be arbitrary. You just have to repeat this process until all vertices are classified and removed. However, if in case a newly created source $v'$ is also a sink (a vertex with no outgoing edge), then any remaining vertex $u$ in the graph cannot have a fixed position since $v'$ can appear before or after $u$ in the topological order.

Algorithm

The algorithm can be viewed as BFS-based topological sorting algorithm. Let $I$ be an array containing the number of incoming edges of each vertex $v$. Let $Q$ be the queue. Then, let $F$ be a Boolean array, initially filled with false values, that will be used to set the mark of a vertex whether it has fixed position or not, e.g. $F[v]$ is true if vertex $v$ has fixed position. Finally, let $sinked$ be a Boolean variable, initially false, that will indicate if a source that is also a sink has been found. The algorithm is as follows:

  1. Fill $I$ with values by scanning the adjacency list of the DAG.
  2. Scan $I$ to find the sources, e.g. vertices whose value in $I$ is 0. When a source is found, insert it to $Q$.
  3. Let $s$ be the number of vertices in $Q$. Repeat the following $s$ times:
    1. Remove a vertex $v$ from $Q$.
    2. If $s > 1$ or $sinked$ is true, set $F[v]$ to false.
    3. If $v$ is a sink, set $sinked$ to true.
    4. For each neighbor $u$ of $v$ in the DAG, decrement $I[u]$ by 1. If after this, $I[u]$ becomes 0, insert $u$ to $Q$.
  4. If $Q$ is not empty, repeat step 3, otherwise scan $F$ to find all vertices marked as fixed (set to true).

Analysis

Step 1 of the algorithm can be performed in $O(|V|+|E|)$ time. Step two takes $O(|V|)$ time. While the remaining part is just BFS, with the modification that a vertex will only be added to $Q$ if it's a source. This is equivalent to adding a vertex, the last time it was found during BFS, which unlike the usual case where the vertex is added the first time it was found. Since BFS takes $O(|V|+|E|)$ time, the entire algorithm takes $O(|V|+|E|)$ time, which is linear.

In my discussion, I will assume that the $|V|$ vertices of the DAG are represented as integers $0,1,..., |V|-1$ so they can be used as indices of an array. In case, different "labeling" is used, all arrays used in the solution can be replaced by any dictionary structure. Also, it is assumed that the DAG is represented as an adjacency list.

Idea

The idea behind the algorithm below is based on the observation that if vertex $v$ is the only source (a vertex with no incoming edge) in the DAG then $v$'s position must be fixed in the topological sort. Now, removing $v$ and all its out-going edges from the DAG might create 0 or more sources. If in case only one new source is created, then this new source has fixed position too. If multiple sources are created, then all these new sources cannot have fixed position, since their order with respect to each other can be arbitrary. You just have to repeat this process until all vertices are classified and removed. However, if in case a newly created source $v'$ is also a sink (a vertex with no outgoing edge), then any remaining vertex $u$ in the graph cannot have a fixed position since $v'$ can appear before or after $u$ in the topological order.

Algorithm

The algorithm can be viewed as BFS-based topological sorting algorithm. Let $I$ be an array containing the number of incoming edges of each vertex $v$. Let $Q$ be the queue. Then, let $F$ be a Boolean array, initially filled with false values, that will be used to set the mark of a vertex whether it has fixed position or not, e.g. $F[v]$ is true if vertex $v$ has fixed position. Finally, let $sinked$ be a Boolean variable, initially false, that will indicate if a source that is also a sink has been found. The algorithm is as follows:

  1. Fill $I$ with values by scanning the adjacency list of the DAG.
  2. Scan $I$ to find the sources, e.g. vertices whose value in $I$ is 0. When a source is found, insert it to $Q$.
  3. Let $s$ be the number of vertices in $Q$. Repeat the following $s$ times:
    1. Remove a vertex $v$ from $Q$.
    2. If $s > 1$ or $sinked$ is true, set $F[v]$ to false.
    3. If $v$ is a sink, set $sinked$ to true.
    4. For each neighbor $u$ of $v$ in the DAG, decrement $I[u]$ by 1. If after this, $I[u]$ becomes 0, insert $u$ to $Q$.
  4. If $Q$ is not empty, repeat step 3, otherwise scan $F$ to find all vertices marked as fixed (set to true).

Analysis

Step 1 of the algorithm can be performed in $O(|V|+|E|)$ time. Step two takes $O(|V|)$ time. While the remaining part is just BFS, with the modification that a vertex will only be added to $Q$ if it's a source. This is equivalent to adding a vertex, the last time it was found during BFS, which unlike the usual case where the vertex is added the first time it was found. Since BFS takes $O(|V|+|E|)$ time, the entire algorithm takes $O(|V|+|E|)$ time, which is linear.

Note

This algorithm is a modification of Kahn's Topological sorting algorithm.

Source Link
Russel
Russel
  • 2.8k
  • 1
  • 8
  • 16

In my discussion, I will assume that the $|V|$ vertices of the DAG are represented as integers $0,1,..., |V|-1$ so they can be used as indices of an array. In case, different "labeling" is used, all arrays used in the solution can be replaced by any dictionary structure. Also, it is assumed that the DAG is represented as an adjacency list.

Idea

The idea behind the algorithm below is based on the observation that if vertex $v$ is the only source (a vertex with no incoming edge) in the DAG then $v$'s position must be fixed in the topological sort. Now, removing $v$ and all its out-going edges from the DAG might create 0 or more sources. If in case only one new source is created, then this new source has fixed position too. If multiple sources are created, then all these new sources cannot have fixed position, since their order with respect to each other can be arbitrary. You just have to repeat this process until all vertices are classified and removed. However, if in case a newly created source $v'$ is also a sink (a vertex with no outgoing edge), then any remaining vertex $u$ in the graph cannot have a fixed position since $v'$ can appear before or after $u$ in the topological order.

Algorithm

The algorithm can be viewed as BFS-based topological sorting algorithm. Let $I$ be an array containing the number of incoming edges of each vertex $v$. Let $Q$ be the queue. Then, let $F$ be a Boolean array, initially filled with false values, that will be used to set the mark of a vertex whether it has fixed position or not, e.g. $F[v]$ is true if vertex $v$ has fixed position. Finally, let $sinked$ be a Boolean variable, initially false, that will indicate if a source that is also a sink has been found. The algorithm is as follows:

  1. Fill $I$ with values by scanning the adjacency list of the DAG.
  2. Scan $I$ to find the sources, e.g. vertices whose value in $I$ is 0. When a source is found, insert it to $Q$.
  3. Let $s$ be the number of vertices in $Q$. Repeat the following $s$ times:
    1. Remove a vertex $v$ from $Q$.
    2. If $s > 1$ or $sinked$ is true, set $F[v]$ to false.
    3. If $v$ is a sink, set $sinked$ to true.
    4. For each neighbor $u$ of $v$ in the DAG, decrement $I[u]$ by 1. If after this, $I[u]$ becomes 0, insert $u$ to $Q$.
  4. If $Q$ is not empty, repeat step 3, otherwise scan $F$ to find all vertices marked as fixed (set to true).

Analysis

Step 1 of the algorithm can be performed in $O(|V|+|E|)$ time. Step two takes $O(|V|)$ time. While the remaining part is just BFS, with the modification that a vertex will only be added to $Q$ if it's a source. This is equivalent to adding a vertex, the last time it was found during BFS, which unlike the usual case where the vertex is added the first time it was found. Since BFS takes $O(|V|+|E|)$ time, the entire algorithm takes $O(|V|+|E|)$ time, which is linear.