var traverse = require("json-schema-traverse");
var schema = {
"type": "object",
"definitions": {
"red": {
"type": "object",
"properties": {
"valueRed": {
"type": "string"
},
"green": {
"$ref": "#/definitions/green"
},
"yellow": {
"$ref": "#/definitions/yellow"
}
}
},
"yellow": {
"type": "object",
"properties": {
"value": {
"type": "string"
},
"green": {
"$ref": "#/definitions/green"
},
"red": {
"$ref": "#/definitions/red"
}
}
},
"green": {
"type": "object",
"properties": {
"value": {
"type": "string"
},
"red": {
"$ref": "#/definitions/red"
},
"yellow": {
"$ref": "#/definitions/yellow"
}
}
}
},
"properties": {
"name": {
"type": "string"
},
"children": {
"$ref": "#/definitions/yellow"
}
}
};
const removeHashPrefix = str => str.startsWith('#/') ? str.slice(1) : str;
function buildGraph(schema) {
const graph = new Map();
function pre(schema, jsonPointer, rootSchema, parentJSON, parentKeyword, parentSchema, indexOrProperty) {
if (schema && schema.$ref) {
const ref = schema.$ref;
const parentPointer = jsonPointer.split('/').slice(0, -2).join('/') || '#';
if (!graph.has(parentPointer)) {
graph.set(parentPointer, []);
}
graph.get(parentPointer).push(removeHashPrefix(ref));
}
}
traverse(schema, { cb: { pre } });
return graph;
}
const graph = buildGraph(schema);
function findAllCycles(graphMap) {
const visited = new Set();
const stack = [];
const stackSet = new Set(); // Zbiór śledzący elementy w stosie
const cycles = [];
function dfs(current) {
visited.add(current);
stack.push(current);
stackSet.add(current);
for (const neighbor of graphMap.get(current) || []) {
if (!visited.has(neighbor)) {
dfs(neighbor);
} else if (stackSet.has(neighbor)) {
// Znaleziono cykl, wyodrębnij ścieżkę cyklu
const cycleStartIndex = stack.indexOf(neighbor);
const cycle = stack.slice(cycleStartIndex);
cycles.push(cycle);
}
}
stack.pop();
stackSet.delete(current);
}
for (const vertex of graphMap.keys()) {
if (!visited.has(vertex)) {
dfs(vertex);
}
}
return cycles;
}
const cycles = findAllCycles(graph);
result = {graph: Array.from(graph.entries()), cycles}