Determine if a vertex is a part of a cycle (undirected graph)

Usage
1

The one method that was suggested was to calculated the connected components and for each component containing 3 or more vertex indices delete one edge. If after this the total number of connected components does not change there is a cycle which can be calculated by using any shortest_path alg.

Another method, if you updated to version 0.8.0 is to use get_all_simple_paths function (the output is a list of lists containing vertex indexes). If the output has 2 or more elements than there is at least one cycle (len(output)- 1 cycles, because one element will just be the actual edge between the selected vertices).

Any ideas for a better algorithm ?

2

Assuming your graphs is simple, you can try this solution in igraph:

Compute the biconnected components. Any vertex that is part of a cycle is in a biconnected component of size > 2. The rest have no cycles.

I will use the Mathematica interface for visualization purposes only. You can implement the same in Python (which I can’t do so quickly now).

g = IGShorthand["1-2-3-4-1, 1-5-6, 6-7-8-9-6, 9-10-11, 10-12"]

image

These are the (overlapping!) biconnected components:

biConnComps = IGBiconnectedComponents[g]
(* {{4, 3, 2, 1}, {11, 10}, {12, 10}, {10, 9}, {9, 8, 7, 6}, {6, 5}, {5, 1}} *)

CommunityGraphPlot[g, biConnComps, EdgeShapeFunction -> "Line"]

image

These are the vertices that are not in any biconnected component of size at least 3. They have no cycles.

nonCyclevertices = Complement[VertexList[g], Join @@ Select[biConnComps, Length[#] > 2 &]]
(* {5, 10, 11, 12} *)

image

What you’d really want is not bi-vertex-connected components, but bi-edge-connected components. Anything not part of such a component has no cycle. However, igraph does not currently have this functionality. It can determine if the graph is bi-edge-connected, but it cannot decompose it into such components.

3

This works great if there aren’t cycles inside cycles. The fastest way I was able to solve is by doing it recursively using 2 functions and each vertex needs 3 attrib: parent(int), passed(int), cycles(list).
I think this might be a useful tool to have it integrated.

def find_cycles(g):
    #for each component
    for comp in g.components():
        if len(comp) >= 3:
            for ind in comp:
                edge = g.es.find(_source_in = [ind])
                target_vertex_id = edge.target
                child_vertex_id = edge.source
                has_cycle(child_vertex_id,parent_vertex_id, g) 

def has_cycle(c,p,g):
    global cyclenumber
    if g.vs[c]['passed'] == 2:
        return
    if g.vs[c]['passed'] == 1:
        cur = p
        cyclenumber += 1
        g.vs[cur]['cycles'].append(cyclenumber)
        while cur != c :
            cur = g.vs[cur]['parent']
            g.vs[cur]['cycles'].append(cyclenumber)
        return
    g.vs[c]['parent'] = p
    g.vs[c]['passed'] = 1
    for edge_check in g.es.select(_source_in = [c]):
        target_vertex_id = edge_check.target
        parent_vertex_id = edge_check.source
        if c != parent_vertex_id:
            interm = parent_vertex_id
            parent_vertex_id = target_vertex_id
            target_vertex_id = interm
        if target_vertex_id == g.vs[c]['parent']:
            continue
        has_cycle(target_vertex_id, c, g)
    
   g.vs[c]['passed'] = 2
4

I believe the solution is much simpler. Simply detect a spanning tree. Any edge that does not belong to a spanning tree induces a (fundamental) cycle, which leads to a so-called cycle basis. If you then delete all edges that are in the spanning tree from the original graph, all the nodes with a degree >= 1 are included in a cycle.

6

Sorry, my answer is (partly) incorrect. Of course, any node within a spanning tree can still be part of a cycle, even if it doesn’t have any neighbours outside of the tree (take for example a simply graph consisting of one cycle).

We should therefore take a slightly different approach. We get a spanning tree, and each edge not in the spanning tree induces a fundamental cycle. For each edge not in the spanning tree, we then get the shortest path in the spanning tree. All nodes on that shortest path in the spanning tree are part of at least one fundamental cycle. We thus simply have to go through all edges not in the spanning tree and mark the nodes on the shortest path as being part of a cycle. Since this is a tree, the shortest path can be determined fairly efficiently. Below is an implementation of this idea in Python. There are quite some redundancies in this code, so it could be made to run substantially faster when implemented in the C core of igraph.

# Get tree structure and distance
_, _, parents = G.bfs(0)
dist = G.shortest_paths(0, target=G.vs)[0]

# Check which edges are part of the tree
edges_in_tree = []
for node, parent in enumerate(parents):
  if node != parent:
    edges_in_tree.append(G.get_eid(node, parent))

# Get edges not in spanning tree
H = G.copy()
H.delete_edges(edges_in_tree)

# Determine for each each edge in H the shortest path in the tree
node_in_cycle = [False]*G.vcount()
n_nodes_in_cycle = 0
for edge in H.es:
  
  # Find common ancestor
  ancestor_i = edge.source
  ancestor_j = edge.target
      
  # Mark both as part of cycle
  if not node_in_cycle[ancestor_j]:
    node_in_cycle[ancestor_j] = True
    n_nodes_in_cycle += 1
  if not node_in_cycle[ancestor_i]:
    node_in_cycle[ancestor_i] = True
    n_nodes_in_cycle += 1
    
  dist_ancestor_i = dist[ancestor_i]
  dist_ancestor_j = dist[ancestor_j]
  while ancestor_i != ancestor_j:
    if dist_ancestor_i < dist_ancestor_j:
      # Ancestor j is further removed, so move j one up
      ancestor_j = parents[ancestor_j]
      dist_ancestor_j = dist[ancestor_j]
      
      # Mark j as part of cycle
      if not node_in_cycle[ancestor_j]:
        node_in_cycle[ancestor_j] = True
        n_nodes_in_cycle += 1
    elif dist_ancestor_i > dist_ancestor_j:
      # Ancestor i is further removed, so move i one up
      ancestor_i = parents[ancestor_i]
      dist_ancestor_i = dist[ancestor_i]
      
      # Mark i as part of cycle
      if not node_in_cycle[ancestor_i]:
        node_in_cycle[ancestor_i] = True
        n_nodes_in_cycle += 1
    else:
      # Equal distance, we can move both up

      # Move j up
      ancestor_j = parents[ancestor_i]
      dist_ancestor_j = dist[ancestor_i]
      # Mark j as part of cycle
      if not node_in_cycle[ancestor_i]:
        node_in_cycle[ancestor_i] = True
        n_nodes_in_cycle += 1      

      # Move i up
      ancestor_i = parents[ancestor_i]
      dist_ancestor_i = dist[ancestor_i]
      # Mark i as part of cycle
      if not node_in_cycle[ancestor_i]:
        node_in_cycle[ancestor_i] = True
        n_nodes_in_cycle += 1        

  if n_nodes_in_cycle == G.vcount():
    break
7

@LivC182 Do you have any concerns about the simple solution based on biconnected components?