一般性骨架矩阵:指的是系统里存在环路,在不进行缩点处理的情况下,把其它向前边全部删除。回路元素用一个回环表示!
骨架矩阵求解基本上都是利用代数方法,该方法好理解但是操作起来的计算量要更大,主要是处理缩点的时候:
对于有向无环图(DAG),其骨架矩阵可以用简单的代数方法求解,就是R-(R-I)^2-I;对DAG来说。所减掉的边,都为向前边。
对于有环图的缩减,主要是在环路边的缩减替换上。其中环路内部的边都用一条方向代替。环路的出边,与入边可以多种方式处理。一种是指定出边或者入边的节点。一种是不指定。也可以单独指定出边的结点。
此处使用的骨架矩阵算法利用最小并集进行计算:
第一:求出强连通子集,返回一个有序的结点集合,边都朝上。
第二:判断当前层的要素数量,如果大于2个要素表示有环路。计算每个要素的可达集合,其并集减去本层要素的结点,就是环路所有的出边。也就是环路所有的出边。
第三:判断当前所有的出边,访问到的每个层级只记录第一次的访问,获得第一次缩边,因为当前层(环路),可能有两次出边指向同一个节点,或者同一个环路。
第四:经过第一次缩边后,判断当前出边Now数目是否大于2条,大于2的话,计算每条向上边,该向上边到达的结点的可达集合R+,如果R+与包含本层级的向上的边也就是Now有交集,这个交集就是有公共祖先的边,也就是该条边为向前边,在Now中删除所有公共祖先的边。
第五:最后得到的Now是最少出边,这个时候,如果当前层是个大于二的环路。要给环路每个要素构建最小出边集。方式有2种。
A、第一种方法 指定一个环路一个结点的出边为所有的Now+指向环路下一个结点,环路最后一个结点指向环路第一个结点。
B、第二种方法,根据原始矩阵中要素的出边与当前向上边Now里面的交集,然后删除Now里面已有的交集,加上指向环内下个结点的边,就为当前要素所有的出边。
C、第三种方法,保留环内的边,计算自身与总出边的并集,再并自己在环内的边。
具有环路的有向图其最小骨架矩阵不唯一,这图都有相似性。最核心的特征有三。
A:边的数目最小
B:不改变系统的可达关系,本矩阵与原始矩阵互为等可达关系。
C:不缩点的骨架矩阵不具有唯一性,大部分变化与环有关系。
子 | 丑 | 寅 | 卯 | 辰 | 巳 | 午 | 未 | 申 | 酉 | 戌 | 亥 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
子 | 1 | |||||||||||
丑 | 1 | 1 | ||||||||||
寅 | 1 | 1 | ||||||||||
卯 | 1 | |||||||||||
辰 | 1 | |||||||||||
巳 | 1 | |||||||||||
午 | 1 | 1 | ||||||||||
未 | ||||||||||||
申 | 1 | |||||||||||
酉 | 1 | 1 | 1 | |||||||||
戌 | 1 | 1 | 1 | 1 | 1 | |||||||
亥 |