传递闭包是什么东西呢？就是形如一个集合，如果元素<x,y>、<y,z>在集合里，那么元素<x,z>也在集合里。放到图里就是说如果点x到y可到达，那么x和y就有一条边相连。放到矩阵里就是<x,y>是1。那么这个集合本身就是一个传递闭包。如果这个集合不满足这个性质呢？那么我们就要求他的传递闭包，让他变成一个“完整”的图。
rep(i,1,n)
	rep(j,1,n)
		rep(k,1,n)
		v[i][j]=v[i][k]|v[k][j]; 
 
 
 
上面的传递闭包算法类似矩阵乘法，先说一下矩阵乘法吧，两个矩阵相乘，就是第一个矩阵的第x行和第二个矩阵的第y列相乘得到的！那么矩阵相乘的时候就有意思了，我们就可以得到，最后如果得到的结果为1，即<x,y>为1。那么<x,y>就是可到达的，并且是从x到y。
鸣谢
 

https://blog.csdn.net/ruangongshi/article/details/49837257
 

一个n个顶点有向图的传递闭包，即为一个n阶布尔矩阵T={ t i j }：如果从 i 到 j 顶点间存在一条有向路径，那么矩阵第 i 行第 j 列置1 即T[i, j]=1；否则置0即T[i, j]=0。
 
传递闭包给出给定图各顶点之间是否存在任意长度的有向路径。
 
首先可以肯定的是，求一个图的传递闭包，可以用DFS和BFS来求，但是很明显，使用DFS和BFS的话，我们必须要循环|V|次，因此效率会非常低。而Warshall算法则是使用的动态规划的思想，能够有效地提高效率。
 
具体思想
 
Warshall 算法首先对有向图的顶点编号：1,2,…,k,…n
 
然后按顶点编号对闭包问题进行划分：
 
第k阶段的子问题为求只包含前k顶点的传递闭包R(k) ：只允许路径中包含编号为1到k的顶点作为中间顶点。
 
然后通过一系列计算得到最终的传递闭包矩阵R(n)：
 
 
其中，
 
 
每个后继矩阵 R(k) 对其前趋 R(k-1) 来说，在路径上允许增加一个顶点，因此有可能包含更多的1（增加前为1的在增加后依然为1）。
 
确定递推关系式
 
 
所以状态转移方程为：
 
 
 
如：求出下图的传递闭包
 
 
则Warshall算法的过程为：
 
 
对于R(0)，很显然为该图的邻接矩阵。
 
对于R(1)，在R(0)的基础上添加了第一行第一列，然后我们可以发现[d,a]=1，因此这就说明，存在一条由d到a的路径，那么只要a能够到达的节点，d也能够到达，此时我们又发现[a,b]=1，因此应该将[d,b]置为1。
 
对于R(2)，在R(1)的基础上添加了第二行第二列，由于列方向上[a,b]=1，[d,b]=1，而行方向上[b,d]=1，因此将[a,d]和[d,d]置为1。
 
对于R(3)，在R(2)的基础上添加了第三行第三列，由于列方向上[d,b]=1，而行方向上全为0（说明节点c无法到达其它任何节点），因此不用改变。
 
对于R(4)，在R(3)的基础上添加了第四行第四列，由于列方向上[a,d]=1，[b,d]=1，[d,d]=1，而行方向上全为1（说明节点d可以到达其它任何节点），因此第a、b、d行全部置为1，此时算法终止。
 
注意：由于看[ i , j ]是否可达，还要考虑[ i , k ]和[ k , j ]之间是否可达，因此我们看图的时候应该是先看列方向，再看行方向。
 
伪代码
 
由上述思想，我们可以得到如下伪代码：
 
algorithm Warshall(A[1..n, 1..n])
//使用Warshall计算传递闭包
//输入：邻接矩阵A[1..n, 1..n]
//输出：该有向图的传递闭包
R(0) <- A
for k <- 1 to n do
	for i <- 1 to n do
		for j <- 1 to n do
			R(k)[i,j] <- R(k-1)[i,j] OR (R(k-1)[i,k] AND R(k-1)[k,j])
return R(n)
 
注意：这里虽然对R加了一个上标，但是我们其实不会需要使用n个n * n的矩阵，只需要一个即可（加上标只是为了让我们自己清楚这之间的不同），因为每次迭代的过程中，第k行第k列都不会改变（从前面的例子中我们也可以发现），我们只是借助第k行第k列来修改原矩阵，因此矩阵中的值在每次迭代的过程中除了第k行第k列的值以外，其他的值要么被上次迭代的值覆盖（即不变），要么就被本次迭代产生的新值覆盖（即更新）。因此，我们只需要对一个n * n的矩阵进行n次迭代即可。
 
代码实现
 
这里我使用的是C++（以前面的例子为例）：
 
首先是邻接矩阵：
 
int A[4][4] = {
	{0, 1, 0, 0},
	{0, 0, 0, 1},
	{0, 0, 0, 0},
	{1, 0, 1, 0}
};
 
算法部分的实现：
 
void Warshall(int A[][4], int R[][4]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			R[i][j] = A[i][j];
		}
	}
	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
			}
		}
	}
}
 
这里注意：由于C/C++的特性，如果为真，则默认为1，为假则默认为0，因此可以直接将布尔表达式的值赋值给一个int类型的变量。
 
最后在main()函数中启动：
 
int main() {
	int R[4][4];

	Warshall(A, R);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cout << R[i][j] << " ";
		}cout << endl;
	}

	return 0;
}
 
运行结果如下：
 
 
可以看到，输出了我们想要的最终结果。
 
完整代码
 
#include<iostream>
using namespace std;

int A[4][4] = {
	{0, 1, 0, 0},
	{0, 0, 0, 1},
	{0, 0, 0, 0},
	{1, 0, 1, 0}
};

void Warshall(int A[][4], int R[][4]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			R[i][j] = A[i][j];
		}
	}
	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
			}
		}
	}
}

int main() {
	int R[4][4];

	Warshall(A, R);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cout << R[i][j] << " ";
		}cout << endl;
	}

	return 0;
}

 
文章目录
 
一、关系闭包
二、自反闭包
三、对称闭包
四、传递闭包

 

 

 

 

 
一、关系闭包
 
 

 
包含给定的元素 , 并且 具有指定性质 的 最小的 集合 , 称为关系的闭包 ; 这个指定的性质就是关系 $R$
 
自反闭包 r ( R ) : 包含 $R$ 关系 , 向 $R$ 关系中 , 添加有序对 , 变成 自反 的 最小的二元关系
 
对称闭包 s ( R ) : 包含 $R$ 关系 , 向 $R$ 关系中 , 添加有序对 , 变成 对称 的 最小的二元关系
 
传递闭包 t ( R ) : 包含 $R$ 关系 , 向 $R$ 关系中 , 添加有序对 , 变成传递 的 最小的二元关系
 

 
定义中有三个重要要素 :
 
包含给定元素
具有指定性质
最小的二元关系
 

 

 

 

 
二、自反闭包
 
 

 
自反闭包 r ( R ) : 包含 $R$ 关系 , 向 $R$ 关系中 , 添加有序对 , 变成 自反 的 最小的二元关系
 
$R\subseteq r(R)$
 
$r(R)$ 是自反的
 
$\forall S((R\subseteq S\wedge S自反)\to r(R)\subseteq S)$
 

 
关系 $R$ 的关系图 $G(R)$ :
 

 
 
$R$ 的自反闭包 $G(r(R))$ 关系图 : 在 $R$ 的基础上 , 添加有些有序对 , 使 $r(R)$ 变成 自反 的 最小的二元关系 , 自反的条件是所有的顶点都有环 , 这里为四个顶点都添加环 ;
 
 

 

 

 

 
三、对称闭包
 
 

 
自反闭包 r ( R ) : 包含 $R$ 关系 , 向 $R$ 关系中 , 添加有序对 , 变成 对称 的 最小的二元关系
 
$R\subseteq s(R)$
 
$s(R)$ 是对称的
 
$\forall S((R\subseteq S\wedge S对称)\to r(R)\subseteq S)$
 

 
关系 $R$ 的关系图 $G(R)$ :
 

 
 
$R$ 的对称闭包 $G(s(R))$ 关系图 : 在 $R$ 的基础上 , 添加有些有序对 , 使 $s(R)$ 变成 对称 的 最小的二元关系 , 对称的条件是 任意两个顶点之间有 $0/2$ 条有向边 , 有 $0$ 条边的不管 , 有 $1$ 条边的在添加一条反向有向边 ;
 
 

 

 

 

 
四、传递闭包
 
 

 
自反闭包 r ( R ) : 包含 $R$ 关系 , 向 $R$ 关系中 , 添加有序对 , 变成 传递 的 最小的二元关系
 
$R\subseteq t(R)$
 
$t(R)$ 是对称的
 
$\forall S((R\subseteq S\wedge S传递)\to r(R)\subseteq S)$
 

 
关系 $R$ 的关系图 $G(R)$ :
 

 
 
$R$ 的对称闭包 $G(t(R))$ 关系图 : 在 $R$ 的基础上 , 添加有些有序对 , 使 $t(R)$ 变成 传递 的 最小的二元关系 , 传递的条件是 ① 前提 $a\to b,b\to c$ 成立 , $a\to c$ 存在 , 或  ② 前提不成立 , 前提不成立的情况下不管默认就是传递的 , 如果前提成立 , 则必修添加对应的第三条边 ;
 

FuzzyPy-模糊聚类（传递闭包法）
 


 
文章目录
 
**FuzzyPy-模糊聚类（传递闭包法）**
**一、传递闭包法的操作步骤**
**二、关键技术分析与准备工作**
1、涉及的主要编程技术和模糊数学的计算方法
2、准备工作
      
**三、实现步骤**
1、导入相关库
2、生成相似矩阵
3、计算传递闭包
4、筛选传递闭包的所有元素并排序
5、算出所有截矩阵、分类、记录分类结果
6、输出聚类报告
      
**四、技术总结**
    
   
  
 

 
一、传递闭包法的操作步骤
 
 
第一步： 计算相似矩阵 $R$ 的传递闭包。即依次计算 $R^2$、$R^4$、…，当第一次出现 $R^{2^i}=R^{2^{i+1}}$ 时 $R^{2^i}$ 就相似矩阵对应的传递闭包；
 
 
第二步： 将传递闭包中的元素从大到小排列：${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_m>$；
 
 
第三步： 求出所有 ${\lambda }_k$ 对应的截矩阵 $R_{{\lambda }_1},R_{{\lambda }_2},\cdots ,R_{{\lambda }_m}$，根据截矩阵进行分类，并记录分类结果；
 
 
第四步： 写出动态聚类结果（输出动态聚类报告）；
 
 
第五步： 画出动态聚类图。
 
 
二、关键技术分析与准备工作
 
1、涉及的主要编程技术和模糊数学的计算方法
 
 
（1）传递闭包的计算：模糊矩阵的合成；矩阵相等的判断
 
 
（2）找出截集水平${\lambda }_k$：筛选传递闭包中的重复元素并排序
 
 
（3）动态分类：计算截矩阵；找出元素为1的元素对应下标，并放入同一集合；
 
 
（4）输出聚类结果：字符串操作
 
 
（5）动态聚类图*：相关绘图工具的使用（暂不开发）
 
 
2、准备工作
 
要实现以上技术内容需要安装以下包库：
 
 
Python
 
 
Numpy
 
 
scikit-fuzzymath(skfuzzy)
 
 
三、实现步骤
 
1、导入相关库
 
方便起见直接将skfuzzy中所有函数导入。
 
import numpy as np
from skfuzzy import *
 
2、生成相似矩阵
 
为方便起见
 
 
直接写成 n*n的随机矩阵，取n=5
 
 
相似矩阵的元素都只取2位小数
 
 
n = 5
R = np.random.rand(n,n)
R = R.dot(R.T)
R = R / np.max(R)
row, col = np.diag_indices_from(R)
R[row,col] = np.ones([n])
R = (R*100).astype(np.int)/100
print(R)
 
[[1.   0.53 0.5  0.36 0.57]
 [0.53 1.   0.42 0.45 0.65]
 [0.5  0.42 1.   0.44 0.48]
 [0.36 0.45 0.44 1.   0.71]
 [0.57 0.65 0.48 0.71 1.  ]]
 
3、计算传递闭包
 
注意: 由于传递闭包至多只需要做 [ln(n)]+1次，因此最简单的实现方法就是直接从0到 [ln(n)]+1。
 
t_R = R
for i in range(np.log2(n).astype(np.int)+1):     
    t_R2 = maxmin_composition(t_R,t_R)
    if np.sum(np.abs(t_R-t_R2))!=0:
        t_R = t_R2
    else:        
        break
print('传递闭包为R的 2^{0} 次方:\r\n'.format(i))
print(t_R)
 
传递闭包为R的 2^2 次方:

[[1.   0.57 0.5  0.57 0.57]
 [0.57 1.   0.5  0.65 0.65]
 [0.5  0.5  1.   0.5  0.5 ]
 [0.57 0.65 0.5  1.   0.71]
 [0.57 0.65 0.5  0.71 1.  ]]
 
4、筛选传递闭包的所有元素并排序
 
这个非常简单
 
 
去重：直接用numpy的unique方法即可
 
 
变成数组：直接用reshape(-1)就变成了一维数组
 
 
排序：直接用sort。由于默认是升序，因此排完后再用[::-1]倒序即可
 
 
lambdas = np.sort(np.unique(t_R).reshape(-1))[::-1]
print(lambdas)
 
[1.   0.71 0.65 0.57 0.5 ]
 
这里可以小秀一下：
 
lam_str = ''
for (i,lam) in zip(range(len(lambdas)),lambdas):
                   if i !=len(lambdas)-1:
                       lam_str += str(lam)+' > '
                   else:
                       lam_str += str(lam)
print('截集水平：'+lam_str)
 
截集水平：1.0 > 0.71 > 0.65 > 0.57 > 0.5
 
5、算出所有截矩阵、分类、记录分类结果
 
这里需要注意一个问题，我们计算截矩阵的根本目的是找出在该截集水平时有关系的元素的对应下标。在Python里面这个操作其实可以直接实现，可以不用算出截矩阵。
 
 
 
截矩阵的实现方法非常简单：(t_R >= lambda)*1
 
 
temp_pairs = np.argwhere(t_R>=lambdas[1])

print(temp_pairs)
 
[[0 0]
 [1 1]
 [2 2]
 [3 3]
 [3 4]
 [4 3]
 [4 4]]
 
但接下来的问题有点麻烦，我们需要将互相有关系的元素下标放在一起。
 
为了方便实现，我们用了一种最 笨 的办法，这里大致说一下思路。
 
 
从截矩阵返回的内容是所有有关系的元素的下标的list，先遍历所有下标，任意一组下标集中出现它时我们就把另一个下标放进来。这样对每个元素而言，只要和它有关系的元素就会全部放进这一个列表；
 
 
由于传递闭包是对称矩阵，因此每组 非对角线 上元素的下标都会成对出现，因此只需将元素遍历一次即可；
 
 
由于 对角线元素 的下标并没有被我们删除，因此所有元素都会和它有关系的元素放在同一列表；
 
 
每个元素遍历完成后，清除它对应的列表的重复值；最后再对总的列表清理一次重复值，这样就得到了一个只包含最终分类结果的列表。
 
 
为了方便起见，我们将这个方法封装起来：
 
def get_classes(temp_pairs):
    lists = []

    for item1 in temp_pairs:
        temp_list = []
        for item2 in temp_pairs:
            if item1[0]==item2[1]:
                temp_list.append(item2[0])        
        lists.append(list(set(temp_list)))

    return(list(np.unique(lists)))

print(get_classes(temp_pairs)) 
 
[[0], [1], [2], [3, 4]]
 
接下来遍历所有的 $\lambda$得出所有聚类结果：
 
classes = []

for lam in lambdas:
    if lam == lambdas[0]:
        classes.append([[x] for x in range(n)])
    else:
        pairs = np.argwhere(t_R >= lam)
        classes.append(get_classes(pairs))

for c in classes:
    print(c)
 
[[0], [1], [2], [3], [4]]
[[0], [1], [2], [3, 4]]
[[0], [1, 3, 4], [2]]
[[0, 1, 3, 4], [2]]
[0, 1, 2, 3, 4]
 
6、输出聚类报告
 
这一步就简单了，只需要进行简单的字符串操作即可：
 
report_str = []

for c in classes:
    temp_str = 'classes:$\{'
    for x in c:
        sub_class = ''
        if type(x) == list:
            sub_class = '\{'
            for i in x:
                sub_class += 'x_{' + str(i) + '},'
            sub_class = sub_class[:-1] + '\},'
        else:
            sub_class += 'x_{' + str(x) + '},'
        temp_str += sub_class
    temp_str = temp_str[:-1]
    temp_str += '\}$'
    report_str.append(temp_str)

for r in report_str:
    print(r,'\n')
        
    
 
classes:$\{\{x_{0}\},\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\}\}$ 

classes:$\{\{x_{0}\},\{x_{1}\},\{x_{2}\},\{x_{3},x_{4}\}\}$ 

classes:$\{\{x_{0}\},\{x_{1},x_{3},x_{4}\},\{x_{2}\}\}$ 

classes:$\{\{x_{0},x_{1},x_{3},x_{4}\},\{x_{2}\}\}$ 

classes:$\{x_{0},x_{1},x_{2},x_{3},x_{4}\}$ 
 
​
 
放到 markdown 里看看效果：
 
classes:
    
     
      
       
        {
       
       
        {
       
       
        
         x
        
        
         0
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         1
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         2
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         3
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         4
        
       
       
        }
       
       
        }
       
      
      
       \{\{x_{0}\},\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\}\}
      
     
    {{x0​},{x1​},{x2​},{x3​},{x4​}}
 
classes:
    
     
      
       
        {
       
       
        {
       
       
        
         x
        
        
         0
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         1
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         2
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         3
        
       
       
        ,
       
       
        
         x
        
        
         4
        
       
       
        }
       
       
        }
       
      
      
       \{\{x_{0}\},\{x_{1}\},\{x_{2}\},\{x_{3},x_{4}\}\}
      
     
    {{x0​},{x1​},{x2​},{x3​,x4​}}
 
classes:
    
     
      
       
        {
       
       
        {
       
       
        
         x
        
        
         0
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         x
        
        
         3
        
       
       
        ,
       
       
        
         x
        
        
         4
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         2
        
       
       
        }
       
       
        }
       
      
      
       \{\{x_{0}\},\{x_{1},x_{3},x_{4}\},\{x_{2}\}\}
      
     
    {{x0​},{x1​,x3​,x4​},{x2​}}
 
classes:
    
     
      
       
        {
       
       
        {
       
       
        
         x
        
        
         0
        
       
       
        ,
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         x
        
        
         3
        
       
       
        ,
       
       
        
         x
        
        
         4
        
       
       
        }
       
       
        ,
       
       
        {
       
       
        
         x
        
        
         2
        
       
       
        }
       
       
        }
       
      
      
       \{\{x_{0},x_{1},x_{3},x_{4}\},\{x_{2}\}\}
      
     
    {{x0​,x1​,x3​,x4​},{x2​}}
 
classes:
    
     
      
       
        {
       
       
        
         x
        
        
         0
        
       
       
        ,
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         x
        
        
         2
        
       
       
        ,
       
       
        
         x
        
        
         3
        
       
       
        ,
       
       
        
         x
        
        
         4
        
       
       
        }
       
      
      
       \{x_{0},x_{1},x_{2},x_{3},x_{4}\}
      
     
    {x0​,x1​,x2​,x3​,x4​}
 
四、技术总结
 
本文利用Python实现了基于传递闭包法的模糊聚类分析。整个过程可以看出其实实现方法都非常简单。但目前仍然还是有一些不足之处：
 
1、相似矩阵我们是直接随机生成的，因此要直接应用的话还得自己写出相似矩阵的构造方法。当然这个方法很简单，我们不多讲；
 
2、在给定的截矩阵的前提下求出对应的分类方法get_classes还有很大的改进空间。目前的复杂度是 $n\times n$，方法特别笨。另外该方法在处理单位矩阵时其实返回的是一个元素为数字的列表，这导致分类结果没有正确将每个元素各为一类的情况展示出来，这部分必须要改进！
 
3、动态聚类图还没画！当然这个问题还比较麻烦，暂时不弄了。
 
完成时间：
 
import datetime
print(datetime.datetime.now())
 
2020-11-06 01:46:27.822593