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 | 16x 3x 3x 7x 7x 2x 1x 16x 6x 6x 9x 9x 4x 2x 16x 12x 39x 12x 16x 8x 24x 8x 16x 5x 16x 9x 9x 16x 5x 5x 16x 2x 16x 2x | /**
* @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)
);
};
|