https://stackoverflow.com/questions/20694742
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianI am not entirely sure whether this is correct, but I think that it should suffice to check if the digraph is "connected" (see description of the algorithm below to find out what I mean by connected). If there are multiple connected components in the digraph, then it is not unilateral.
Proof attempt:
Suppose that the digraph has multiple connected components. For simplicity's sake, let the number of connected components be 2, and let's call the components C1 and C2. Select any vertex v from C1 and any vertex w from C2. Since they are in different connected components, there is no path from v to w or w to v, otherwise C1 and C2 will be in the same component.
For the other case, suppose that a digraph is connected. Then for any 2 distinct vertices x and y in the digraph, there is either a path from x to y or from y to x, otherwise they will not be in the same component. I know it's a bit hand wavy here, but I'm not exactly good at proofs.
EDIT: A simpler algorithm:
I do think a modified Depth First Search / Breadth First Search should be able to do it. Essentially, we can start the search from any vertex. We mark all vertices reachable from that first vertex as visited. Then loop through all vertices. For any unvisited vertex, we conduct a BFS / DFS, and we use a list to keep track of all unvisited vertices that we have traversed. If during the BFS / DFS, we do not visit any previously visited vertex from a prior BFS / DFS, then we can conclude immediately that the digraph has multiple connected components and is not unilateral. Otherwise, we mark all vertices in the list we obtained during the search as visited, and we continue.
Once we have gone through all vertices in the graph all the BFS / DFS hit some previously visited vertex, we can conclude that the graph is unilateral.
Some pseudocode to illustrate this. I shall make use of Depth First Search:
// a boolean array to keep track if a given vertex is visited
// initially this is set to false
boolean[] visited
// boolean array to keep track of visited vertices for 2nd dfs onwards
boolean[] visited_two
// used for first dfs
dfs(vertex) {
visited[vertex] <- true
for each edge leading out of vertex {
dfs(next vertex)
}
}
// used for subsequent dfs
dfs_two(vertex, list_for_storing_vertices) {
// we use the visited_two array here, because the
// visited array is used to store previously visited
// vertices
visited_two[vertex] <- true
list_for_storing_vertices.append(vertex)
// return value. we return true if we encounter
// a previously visited vertex. otherwise, return false
return_value <- false
for each edge leading out of vertex {
if visited[next vertex]
return_value <- true
else if !visited_two[next_vertex]
r = dfs_two(next vertex, list_for_storing_vertices)
return_value = return_value || r
}
return return_value
}
// overall algorithm
// Returns true if the graph is unilateral. false otherwise
bool digraph_unilateral(graph) {
// Just pick any vertex. we will pick vertex 0
set all entries in `visited` array to false
dfs(0)
// then loop through all vertices. if they haven't been visited,
// we perform a dfs
for each vertex in the digraph {
if !visited[vertex] {
// reset visited_two array
set all entries in `visited_two` array to false
visited_list <- []
encountered_previously_visited <- dfs_two(vertex, visited_list)
if encountered_previously_visited {
// mark the vertices we encountered as visited
for each v in visited_list {
visited[v] <- true
}
} else {
// we did not encounter any previously visited vertex
// so all vertices we encounter on this search are in
// a distinct connected component
return false
}
}
}
return true
}
Original, more difficult algorithm:
How do we then compute if a digraph is unilateral? You can first run Tarjan's Strongly Connected Components algorithm and determine the strongly connected components of the digraph. You will need to modify the algorithm slightly to compress the strongly connected components into supervertices. This is not difficult to do, just assign each vertex in the same strongly connected component an integer label. In other words, all the vertices in the same strongly connected component will be replaced by 1 supervertex. Tarjan's SCC (Strongly Connected Components) algorithm runs in O(V+E) time.
After the step above, the digraph is now acyclic (no cycles). This allows us to move on to the next step.
After that, perform a topological sort on the resulting graph from above. This should give us a topological ordering of the directed acyclic graph. This step also runs in O(V+E) time using a depth first search implementation.
Now that we have the topological ordering, perform either Breadth First Search or Depth First Search according to the topological ordering on the directed acyclic graph obtained after the Tarjan's SCC step. If the number of connected components is 1, then the original graph is unilateral (it is also unilateral if the number of connected components is 0, but that is an empty graph and so is trivial). Otherwise, there are multiple components, and the original graph is not unilateral. This step also runs in O(V+E) time.
Therefore, the overall algorithm runs in O(V+E) time.
Conclusion
I think this should be correct, but you might want to verify this approach with someone else. If you have any difficulty in understanding my approach or implementing the algorithms, do leave a comment.
Hope that helps!
