Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 | 15x 3x 3x 7x 7x 2x 1x 15x 5x 5x 8x 8x 3x 2x 15x 10x 34x 10x 15x 8x 24x 8x 15x 5x 15x 7x 7x 15x 5x 5x 15x 2x 15x 2x 15x 2x 2x 2x 1x 1x 1x 15x | /**
* @file Functions that used to find similar element between two graph
* @file.zh-CN 在两个图中查找相似元素的函数
*/
import { isSimpleGraph } from './essence';
import Graph from './Graph';
/**
* @description Check if two graphs are contains the same nodes.
* @description.zh-CN 检查两个图是否包含相同的节点。
*/
export const containSameNodes = <NodeIDType = any>(
aGraph: Graph<NodeIDType>,
bGraph: Graph<NodeIDType>,
) => {
const aNodes = aGraph.nodes();
for (let i = 0; i < aNodes.length; i++) {
const aNode = aNodes[i];
if (bGraph.hasNode(aNode)) {
return true;
}
}
return false;
};
/**
* @description Check if two graphs are contains the same edges.
* @description.zh-CN 检查两个图是否包含相同的边。
*/
export const containSameEdges = <NodeIDType = any>(
aGraph: Graph<NodeIDType, any, any>,
bGraph: Graph<NodeIDType, any, any>,
) => {
const aEdges = aGraph.edges();
for (let i = 0; i < aEdges.length; i++) {
const aEdge = aEdges[i];
if (bGraph.hasEdge(aEdge.v, aEdge.w, aEdge.name)) {
return true;
}
}
return false;
};
/**
* @description get same nodes in two graphs.
* @description.zh-CN 获取两个图中相同的节点。
*/
export const getSameNodes = <NodeIDType = any>(
aGraph: Graph<NodeIDType>,
bGraph: Graph<NodeIDType>,
) => {
const aNodes = aGraph.nodes();
const sameNodes = aNodes.filter((aNode) => bGraph.hasNode(aNode));
return sameNodes;
};
/**
* @description get same edges in two graphs.
* @description.zh-CN 获取两个图中相同的边。
*/
export const getSameEdges = <NodeIDType = any, EdgeType = any>(
aGraph: Graph<NodeIDType, any, EdgeType, any>,
bGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
const aEdges = aGraph.edges();
const sameEdges = aEdges.filter((aEdge) => bGraph.hasEdge(aEdge.v, aEdge.w, aEdge.name));
return sameEdges;
};
/**
* @description Check if two graphs'option are the same.
* @description.zh-CN 检查两个图的选项是否相同。
*/
export const isGraphOptionSame = <NodeIDType = any, EdgeType = any>(
aGraph: Graph<NodeIDType, any, EdgeType, any>,
bGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
return (
aGraph.isCompound() === bGraph.isCompound() &&
aGraph.isDirected() === bGraph.isDirected() &&
aGraph.isMultigraph() === bGraph.isMultigraph()
);
};
/**
* @description Check if a graph contains all nodes in another graph.
* @description.zh-CN 检查一个图是否包含另一个图的所有节点。
*/
export const containAllSameNodes = <NodeIDType = any>(
aGraph: Graph<NodeIDType, any, any, any>,
bGraph: Graph<NodeIDType, any, any, any>,
) => {
const sameNodes = getSameNodes(aGraph, bGraph);
return sameNodes.length === aGraph.nodes().length;
};
/**
* @description Check if a graph contains all edges in another graph.
* @description.zh-CN 检查一个图是否包含另一个图的所有边。
*/
export const containAllSameEdges = <NodeIDType = any, EdgeType = any>(
aGraph: Graph<NodeIDType, any, EdgeType, any>,
bGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
const sameEdges = getSameEdges(aGraph, bGraph);
return sameEdges.length === aGraph.edges().length;
};
/**
* @description Check if two graphs are the same.
* @description.zh-CN 检查两个图是否相同。
*/
export const isGraphSame = <NodeIDType = any, EdgeType = any>(
aGraph: Graph<NodeIDType, any, EdgeType, any>,
bGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
return (
isGraphOptionSame(aGraph, bGraph) &&
aGraph.nodeCount() === bGraph.nodeCount() &&
containAllSameNodes<NodeIDType>(aGraph, bGraph) &&
aGraph.edgeCount() === bGraph.edgeCount() &&
containAllSameEdges(aGraph, bGraph)
);
};
/**
* @description Check if one graph is the subgraph of another graph.
* @description.zh-CN 检查一个图是否是另一个图的子图。
*/
export const isGraphContainsAnother = <NodeIDType = any, EdgeType = any>(
originGraph: Graph<NodeIDType, any, EdgeType, any>,
targetGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
return (
containAllSameNodes<NodeIDType>(originGraph, targetGraph) &&
containAllSameEdges(originGraph, targetGraph)
);
};
/**
* @description Check if one graph is the complement of another graph.
* @description.zh-CN 检查一个图是否是另一个图的补图。
*/
export const isGraphComplement = <NodeIDType = any, EdgeType = any>(
originGraph: Graph<NodeIDType, any, EdgeType, any>,
targetGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
Iif (!isSimpleGraph(originGraph) || !isSimpleGraph(targetGraph)) {
return false;
}
Iif (!containAllSameNodes(originGraph, targetGraph)) {
return false;
}
if (containSameEdges(originGraph, targetGraph)) {
return false;
}
const nodeCount = originGraph.nodeCount();
return (originGraph.edgeCount() + targetGraph.edgeCount()) === nodeCount * (nodeCount - 1) / 2;
}
/**
* @description Get the graph's complement
* @description.zh-CN 获取图的补图
*/
export const getGraphComplement = <NodeIDType = any, EdgeType = any>(
originGraph: Graph<NodeIDType, any, EdgeType, any>,
) => {
if (!isSimpleGraph(originGraph)) {
return null;
}
const nodeCount = originGraph.nodeCount();
const complementGraph = new Graph<NodeIDType, any, EdgeType, any>({
compound: originGraph.isCompound(),
directed: originGraph.isDirected(),
multigraph: originGraph.isMultigraph(),
});
const nodes = originGraph.nodes();
for (let i = 0; i < nodeCount; i++) {
const nodei = nodes[i];
complementGraph.setNode(nodei, originGraph.node(nodei));
for (let j = i + 1; j < nodeCount; j++) {
const nodej = nodes[j];
complementGraph.setEdge(nodei, nodej);
}
}
return complementGraph;
}
|