Spaces:
Paused
Paused
File size: 7,328 Bytes
529090e | 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 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 | import { neo4jService } from '../../database/Neo4jService';
/**
* Advanced Graph Traversal Optimizer
* Optimizes multi-hop graph queries for better performance
*/
export class GraphTraversalOptimizer {
/**
* Optimized breadth-first search with pruning
*/
async optimizedBFS(
startNodeId: string,
targetCondition: (node: any) => boolean,
maxDepth: number = 3,
maxNodes: number = 100
): Promise<{ path: any[]; nodesVisited: number }> {
await neo4jService.connect();
try {
// Use Cypher's built-in path finding with limits
const result = await neo4jService.runQuery(
`MATCH path = (start)-[*1..${maxDepth}]-(end)
WHERE id(start) = $startId
WITH path, nodes(path) as pathNodes
LIMIT $maxNodes
RETURN path, pathNodes`,
{ startId: parseInt(startNodeId), maxNodes }
);
await neo4jService.disconnect();
if (result.length === 0) {
return { path: [], nodesVisited: 0 };
}
// Find best path based on condition
const bestPath = result.find(r => {
const nodes = r.pathNodes;
return nodes.some((node: any) => targetCondition(node));
});
return {
path: bestPath?.pathNodes || [],
nodesVisited: result.length,
};
} catch (error) {
await neo4jService.disconnect();
throw error;
}
}
/**
* Find shortest path with relationship type filtering
*/
async findShortestPath(
startNodeId: string,
endNodeId: string,
relationshipTypes?: string[],
maxDepth: number = 5
): Promise<{ path: any[]; length: number } | null> {
await neo4jService.connect();
try {
const relFilter = relationshipTypes
? `:${relationshipTypes.join('|')}`
: '';
const result = await neo4jService.runQuery(
`MATCH path = shortestPath((start)-[${relFilter}*1..${maxDepth}]-(end))
WHERE id(start) = $startId AND id(end) = $endId
RETURN path, length(path) as pathLength`,
{ startId: parseInt(startNodeId), endId: parseInt(endNodeId) }
);
await neo4jService.disconnect();
if (result.length === 0) return null;
return {
path: result[0].path,
length: result[0].pathLength,
};
} catch (error) {
await neo4jService.disconnect();
throw error;
}
}
/**
* Find all paths with cost optimization
*/
async findAllPathsWithCost(
startNodeId: string,
endNodeId: string,
maxDepth: number = 4,
costProperty: string = 'weight'
): Promise<Array<{ path: any[]; cost: number }>> {
await neo4jService.connect();
try {
const result = await neo4jService.runQuery(
`MATCH path = (start)-[*1..${maxDepth}]-(end)
WHERE id(start) = $startId AND id(end) = $endId
WITH path, relationships(path) as rels
RETURN path,
reduce(cost = 0, r in rels | cost + coalesce(r.${costProperty}, 1)) as totalCost
ORDER BY totalCost ASC
LIMIT 10`,
{ startId: parseInt(startNodeId), endId: parseInt(endNodeId) }
);
await neo4jService.disconnect();
return result.map(r => ({
path: r.path,
cost: r.totalCost,
}));
} catch (error) {
await neo4jService.disconnect();
throw error;
}
}
/**
* Community detection using label propagation
*/
async detectCommunities(minCommunitySize: number = 3): Promise<Map<string, string[]>> {
await neo4jService.connect();
try {
// Simple community detection based on connected components
const result = await neo4jService.runQuery(
`CALL gds.wcc.stream('myGraph')
YIELD nodeId, componentId
WITH componentId, collect(nodeId) as members
WHERE size(members) >= $minSize
RETURN componentId, members`,
{ minSize: minCommunitySize }
);
await neo4jService.disconnect();
const communities = new Map<string, string[]>();
result.forEach(r => {
communities.set(r.componentId.toString(), r.members.map((id: any) => id.toString()));
});
return communities;
} catch (error) {
await neo4jService.disconnect();
// Fallback to simple connected components
return this.simpleConnectedComponents(minCommunitySize);
}
}
/**
* Fallback: Simple connected components without GDS
*/
private async simpleConnectedComponents(minSize: number): Promise<Map<string, string[]>> {
const result = await neo4jService.runQuery(
`MATCH (n)
OPTIONAL MATCH path = (n)-[*]-(m)
WITH n, collect(DISTINCT m) as connected
WHERE size(connected) >= $minSize
RETURN id(n) as nodeId, [x in connected | id(x)] as members
LIMIT 100`,
{ minSize }
);
const communities = new Map<string, string[]>();
result.forEach((r, idx) => {
communities.set(`community_${idx}`, r.members.map((id: any) => id.toString()));
});
return communities;
}
/**
* PageRank-style importance scoring
*/
async computeNodeImportance(dampingFactor: number = 0.85, iterations: number = 20): Promise<Map<string, number>> {
await neo4jService.connect();
try {
// Try using GDS PageRank
const result = await neo4jService.runQuery(
`CALL gds.pageRank.stream('myGraph', {
maxIterations: $iterations,
dampingFactor: $dampingFactor
})
YIELD nodeId, score
RETURN nodeId, score
ORDER BY score DESC
LIMIT 100`,
{ iterations, dampingFactor }
);
await neo4jService.disconnect();
const scores = new Map<string, number>();
result.forEach(r => {
scores.set(r.nodeId.toString(), r.score);
});
return scores;
} catch (error) {
await neo4jService.disconnect();
// Fallback to simple degree centrality
return this.simpleDegreeCentrality();
}
}
/**
* Fallback: Simple degree centrality without GDS
*/
private async simpleDegreeCentrality(): Promise<Map<string, number>> {
const result = await neo4jService.runQuery(
`MATCH (n)-[r]-(m)
WITH n, count(r) as degree
RETURN id(n) as nodeId, degree
ORDER BY degree DESC
LIMIT 100`
);
const scores = new Map<string, number>();
result.forEach(r => {
scores.set(r.nodeId.toString(), r.degree);
});
return scores;
}
}
export const graphTraversalOptimizer = new GraphTraversalOptimizer();
|