Singly connected Graph?

Question

A singly connected graph is a directed graph which has at most 1 path from u to v ∀ u,v.

I have thought of the following solution:

1. Run DFS from any vertex.
2. Now run DFS again but this time starting from the vertices in order of decreasing finish time. Run this DFS only for vertices which are not visited in some previous DFS. If we find a cross edge in the same component or a forward edge, then it is not Singly connected.
3. If all vertices are finished and no such cross of forward edges, then singly connected.

O(V+E)

Is this right? Or is there a better solution.

Update : atmost 1 simple path.

Answer 1

A simple algorithm for solving this decision problem performs a depth-first search (DFS) starting from each vertex, terminating the DFS after it visits all vertices reachable from the start vertex.

If we encounter the same vertex along two different simple paths from the initial vertex, the graph is not singly-connected. Conversely, if we find no such case for any initial vertex, the graph is singly-connected.

    def DFS(self, node: int, visited: List[int]) -> None:
        """
        Performs DFS on the graph
        """
        visited[node] = 1
        for neighbour in self.nodes[node]:
            if self.SC_ORIENTED == 0:
                return
            if visited[neighbour] == 2:
                self.SC_ORIENTED = 0
                return
            if visited[neighbour] == 0:
                self.DFS(neighbour, visited)
        visited[node] = 2

    def is_SC_oriented(self) -> bool:
        """
        self.nodes: dict with nodes as keys and set of its neighbours as values
        """
        if len(self.get_undirected_edges()) != 0:
            raise Exception("Graph is not undirected!")
        self.SC_ORIENTED = -1
        visited = [0]*len(self.nodes)
        for node in self.nodes:
            if visited[node] == 0:
                self.DFS(node, visited)
                if self.SC_ORIENTED == 0:
                    return False
        return True

This algorithm runs in O(V*E) time. A more efficient algorithm which runs in O(V^2) time can be seen found in the following paper.

Adam L. Buchsbaum and Martin C. Carlisle. Determining uni-connectivity in directed graphs. Information Processing Letters, 48(1):9–12, 1993.

Answer 2

Is this right?

No, it's not right. Considering the following graph which is not singly connected. The first component comes from a dfs beginning with vertex b and the second component comes from a dfs beginning with vertex a.

---

The right one:

Do the DFS, the graph is singly connected if all of the three following conditions satisfies:

1. no foward edges
2. no cross edges in the same component
3. there is no more than 1 cross edges between any two of components

Answer 3

A graph is not singly connected if one of the two following conditions satisfies:

1. In the same component, when you do the DFS, you get a road from a vertex to another vertex that has already finished it's search (when it is marked BLACK)

2. When a node points to >=2 vertices from another component, if the 2 vertices have a connection then it is not singly connected. But this would require you to keep a depth-first forest.

Answer 4

A singly connected component is any directed graph belonging to the same entity. It may not necessarily be a DAG and can contain a mixture of cycles.

Every node has atleast some link(in-coming or out-going) with atleast one node for every node in the same component. All we need to do is to check whether such a link exists for the same component.

Singly Connected Component could be computed as follows:

• Convert the graph into its undirected equivalent
• Run DFS and set the common leader of each node

Run an iteration over all nodes. If all the nodes have the same common leader, the undirected version of the graph is singly connected.

Else, it contains of multiple singly connected subgraphs represented by their corresponding leaders.