4
\$\begingroup\$

I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding and removing of components from the components list.

g = {1: [3, 4], 2: [5], 3:[7], 4:[], 5:[], 6:[1], 7:[]}

vertices = set(g)
components = []
while vertices:
  stack = list((vertices.pop(),))
  comp = set()
  while stack:
    vert = stack.pop()
    comp.add(vert)
    if vert in vertices:
       vertices.remove(vert)
    for e in g[vert]:
        if e in vertices:
            stack.append(e)
        else:
            for component in components:
               if e in component:
                  component.update(comp)
                  comp = component
                  components.remove(comp)
    components.append(comp)

print([c for c in components])

>>> [{2, 5}, {1, 3, 4, 6, 7}]

\$\endgroup\$
1
\$\begingroup\$

It would seem to me that one way to solve this is to change all the directed arcs in the dag to undirected edges. The rest is to recognize the disjoint subgraphs using breadth-first search:

def convert_directed_graph_to_undirected_graph(graph):
    """Converts each directed arc into an undirected edge."""
    undirected_graph = {}
    for node, child_node_list in graph.items():
        if node not in undirected_graph.keys():
            undirected_graph[node] = []
        undirected_graph[node].extend(child_node_list)
        for child_node in child_node_list:
            if child_node not in undirected_graph.keys():
                undirected_graph[child_node] = []
            undirected_graph[child_node].append(node)
    return undirected_graph


def crawl_subgraph(source_node, undirected_graph, visited):
    """Implements breadth-first search in order to find the entire subgraph including the source noe."""
    if source_node in visited:
        return None
    visited.add(source_node)
    queue = deque([source_node])
    subgraph = [source_node]
    while queue:
        current_node = queue.popleft()
        for neighbor_node in undirected_graph[current_node]:
            if neighbor_node not in visited:
                visited.add(neighbor_node)
                subgraph.append(neighbor_node)
                queue.append(neighbor_node)
    return subgraph


def find_disjoint_dags(graph):
    """Finds all disjoint subdags in the input dag."""
    undirected_graph = convert_directed_graph_to_undirected_graph(graph)
    visited = set()
    disjoint_subgraphs = []
    vertices = set(undirected_graph)
    for vertex in vertices:
        subgraph = crawl_subgraph(vertex, undirected_graph, visited)
        if subgraph:
            disjoint_subgraphs.append(subgraph)
    return disjoint_subgraphs

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I know this approach as Tarjan's algorithm. However, I am trying to avoid the conversion to an undirected graph. I feel like I was able to circumvent that with keeping sets of components. I was looking for comments on that approach. \$\endgroup\$ – shane Feb 7 '17 at 14:34
  • \$\begingroup\$ @shane Fair enough. However, note that this is not Tarjan's algorithm, since Tarjan's algorithm is about computing strongly connected components of a directed graph, which is different from your problem setting. \$\endgroup\$ – coderodde Feb 7 '17 at 14:43
  • \$\begingroup\$ Ahh, yep you are correct \$\endgroup\$ – shane Feb 7 '17 at 14:45
0
\$\begingroup\$

You could use Union-Find. Every edge in your graph represents elements from two subsets that you want to merge. Once you have completed the merges constructing the sets is trivial. When implemented with union by rank and path compression the algorithm runs in O(n) time:

from collections import defaultdict

# Find ancestor and compress the path along the way
def find_ancestor(parent, vertex):
    if parent[vertex] != vertex:
        parent[vertex] = find_ancestor(parent, parent[vertex])

    return parent[vertex]

# Merge sets in case given vertices are not in same set already
def merge(parent, rank, v1, v2):
    v1 = find_ancestor(parent, v1)
    v2 = find_ancestor(parent, v2)

    if v1 != v2:
        if rank[v2] > rank[v1]:
            v1, v2 = v2, v1

        parent[v2] = v1
        rank[v1] += rank[v2]

def disjoint_sets(graph):
    parent = {k: k for k in graph}
    rank = {k: 1 for k in graph}

    # Iterate over edges, for every edge merge vertices
    for vertex, neighbors in graph.items():
        for n in neighbors:
            merge(parent, rank, vertex, n)

    # Group vertices based on the component
    components = defaultdict(list)
    for vertex in graph:
        components[find_ancestor(parent, vertex)].append(vertex)

    return components.values()

g = {1: [3, 4], 2: [5], 3:[7], 4:[], 5:[], 6:[1], 7:[]}
print(disjoint_sets(g))

Output:

[[1, 3, 4, 6, 7], [2, 5]]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.