3
\$\begingroup\$

I wrote a program that can tell if a graph has_cycle or not.

Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to represent a graph with vertices and edges?)

def has_cycle(g, directed=False):
    def dfs(x, entered, exited, tree_edges, back_edges):
        if x not in entered:
            entered.add(x)
            for y in g[x]:
                if y not in entered:
                    tree_edges[y] = x
                elif (not directed and tree_edges.get(x, None) != y
                      or directed and y not in exited):
                          back_edges.setdefault(y, set()).add(x)
                dfs(y, entered, exited, tree_edges, back_edges)
            exited.add(x)
        return (tree_edges, back_edges)
    for x in range(len(g)):
        if dfs(x, entered=set(), exited=set(), tree_edges={}, back_edges={})[1]:
            return True
    else:
        return False

Test Cases - Directed Graphs

'''    A0 →  C2 → E4
graph: ↓  ↗  ↓   ↗
       B1    D3     '''
a, b, c, d, e = range(5)
g = [
    {b, c}, # a
    {c},    # b
    {d, e}, # c
    {e},    # d
    set()   # e
]

assert not has_cycle(g, True)

g[a] = {b}
g[c] = {a, d, e}
assert has_cycle(g, True)

Test Cases - Directed Graphs

# undirected graph: A0 - B1 - C2
a, b, c = range(3)
g2 = [
    {b},    # a
    {a, c}, # b
    {b}     # c
]
assert not has_cycle(g2, False)

# undirected graph: A0 - B1 - C2 - A0
g2[a].add(c)
g2[c].add(a)
assert has_cycle(g2, False)
\$\endgroup\$
1
\$\begingroup\$

Comments regarding graphs:

The typical way to describe a graph G is G = {V, E} where V is the set of vertices and E is a bag of edges. The number of vertices is denoted n. The number of edges e [1]. Convention is to re-label the vertices by number either from 1 to n or from 0 to n-1 for the sake of programming conventions.

E is a bag because redundant edges matter in several important graph algorithms (e.g. minimum cut). If u and v are vertices then a non-directed edge is annotated u--v and a directed edge from u to v as u-->v.

For sparse graphs, the bag of edges is typically represented as a sequence [e.g. array or list] of tuples (u,v). For dense graphs an adjacency matrix of n rows and n columns is more typical ("sparse" and "dense" are terms of art, profiling to determine the data structure is appropriate).

Using mathematical language for variables and constants will make for more readable code, as will following conventions for vertex labeling and the data structures for edges.

[1] Art of Computer Programming: Volume 4A, Knuth.

\$\endgroup\$
1
\$\begingroup\$
  • It is not necessary to run the full DFS from every node. A cycle can be detected starting from any node that is in the cycle. Each search only needs to explore nodes that were not visited by previous searches. You can accomplish this by retaining entered and exited between dfs calls.
  • You collect more data than necessary. dfs could simply return True when it detects a cycle, instead of filling up back_edges. tree_edges seems to exist only to prevent recursing back to the parent node in the undirected case. It would be simpler to pass a parent argument in the recursive call.
\$\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.