计算有向图中环的数量

首先，我们先删除图中的孤立点(对应于邻接矩阵，即，第i行和第j列均为0的点)。其次，我们对于有向图进行深度优先搜索(具体思路与利用DFS判断有向图是否为DAG相同，https://www.jianshu.com/p/acc0eb465cd8) ，每搜索出一个环之后，计数+1.

import numpy as np

"""
color[i] = 0, 没有被访问过
color[i]  = -1, 后裔节点均被访问过
color[i]  = 1, 之前被访问过，后裔节点中正在被访问
"""

class Graph(object):
            
    def __init__(self,G):
        self.color = [0] * len(G)
        self.G = np.array(G)
        self.isDAG = True
        self.circlecount = 0
    
  #对于graph进行预处理，删除孤立点
    def graph_preprocessing(self):
        index = []
        for i in range(len(self.G)):
            if np.sum(self.G[:,i]) == 0 and np.sum(self.G[i,:]) == 0:
                index.append(i)
        #delete columns
        self.G = np.delete(self.G,index, axis=1)
        #delte rows
        self.G = np.delete(self.G,index, axis=0)   
        self.color = [0] * len(self.G)
                
    def DFS(self,i):
        self.color[i] = 1
        for j in range(len(self.G)):
            if self.G[i][j] != 0:
               # print(str(i) + 'can go to '+ str(j))
                if self.color[j] == 1:
                    self.circlecount = self.circlecount + 1
                    self.isDAG = False
                elif self.color[j] == -1:
                    continue
                else:
                    #print('We are visiting node' + str(j))
                    self.DFS(j)
        self.color[i] = -1
        #print(str(i) + " has been examined")
        
    def DAG(self):
        for i in range(len(self.G)):
            if self.color[i] == 0:
                print(i)
                self.DFS(i)

对于上述程序，进行了三次测试

test1.png

##test1 circle = 2              
G = [[0,0,1,0,0,0,0],
     [0,0,1,0,0,0,0],
     [0,0,0,1,0,0,0],
     [0,0,0,0,1,1,0],
     [0,0,0,0,0,0,0],
     [0,0,0,0,0,0,1],
     [0,1,0,1,0,0,0]]
G1 = Graph(G)
G1.DAG()

test2.png

###test2 circle = 3
G = [[0,0,1,0,0,0,0],
     [0,0,1,0,0,0,0],
     [0,0,0,1,0,0,0],
     [0,0,0,0,1,1,0],
     [1,0,0,0,0,0,0],
     [0,0,0,0,0,0,1],
     [0,1,0,1,0,0,0]]
G1 = Graph(G)
G1.DAG()

test3.png

###test3 circle = 4
G = [[0,0,1,0,0,0,0,0,0,0],
     [0,0,1,0,0,0,0,0,0,0],
     [0,0,0,1,0,0,0,0,0,0],
     [0,0,0,0,1,1,0,0,0,0],
     [1,0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,1,0,0,0],
     [0,1,0,1,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,1,0],
     [0,0,0,0,0,0,0,0,0,1],
     [0,0,0,0,0,0,0,1,0,0]]

G1 = Graph(G)
G1.DAG()