Graph Utilities

/**
 * Build adjacency list from workflow connections
 * @param connections - Workflow connections object
 * @returns Adjacency list for graph traversal
 */
function buildAdjacencyList(connections: IConnections): AdjacencyList;

/**
 * Adjacency list type for representing graph connections
 */
type AdjacencyList = Record<string, Array<{
  node: string;
  type: NodeConnectionType;
  index: number;
}>>;

type NodeConnectionType = 'main' | 'ai_tool' | 'ai_agent' | 'ai_chain' | 'ai_document';

/**
 * Parse extractable subgraph selection
 * @param selection - Subgraph selection criteria
 * @returns Parsed subgraph data structure
 */
function parseExtractableSubgraphSelection(
  selection: string | ISubgraphSelection
): ExtractableSubgraphData | ExtractableErrorResult;

/**
 * Subgraph data structure containing nodes and connections
 */
interface ExtractableSubgraphData {
  nodes: string[];
  connections: IConnection[];
  entryNodes: string[];
  exitNodes: string[];
  metadata?: ISubgraphMetadata;
}

/**
 * Error result for failed subgraph extraction
 */
interface ExtractableErrorResult {
  error: string;
  code: 'INVALID_SELECTION' | 'MISSING_NODES' | 'CIRCULAR_DEPENDENCY' | 'DISCONNECTED_GRAPH';
  details?: IDataObject;
}

interface ISubgraphSelection {
  nodeNames?: string[];
  nodeTypes?: string[];
  startNode?: string;
  endNode?: string;
  maxDepth?: number;
  includeDisabled?: boolean;
}

interface ISubgraphMetadata {
  nodeCount: number;
  connectionCount: number;
  depth: number;
  hasCircularDependencies: boolean;
}

/**
 * Get all parent nodes of a specific node
 * @param workflow - Workflow instance
 * @param nodeName - Target node name
 * @returns Array of parent node names
 */
function getParentNodes(workflow: Workflow, nodeName: string): string[];

/**
 * Get all child nodes of a specific node
 * @param workflow - Workflow instance
 * @param nodeName - Target node name
 * @returns Array of child node names
 */
function getChildNodes(workflow: Workflow, nodeName: string): string[];

/**
 * Get all connected nodes (parents and children)
 * @param workflow - Workflow instance
 * @param nodeName - Target node name
 * @returns Array of connected node names
 */
function getConnectedNodes(workflow: Workflow, nodeName: string): string[];

/**
 * Find node by name in workflow
 * @param workflow - Workflow instance
 * @param nodeName - Node name to find
 * @returns Node object or null if not found
 */
function getNodeByName(workflow: Workflow, nodeName: string): INode | null;

/**
 * Map connections by their destination nodes
 * @param connections - Workflow connections
 * @returns Map of destination nodes to their input connections
 */
function mapConnectionsByDestination(
  connections: IConnections
): IConnectionMap;

interface IConnectionMap {
  [destinationNode: string]: Array<{
    sourceNode: string;
    sourceType: NodeConnectionType;
    sourceIndex: number;
    destinationType: NodeConnectionType;
    destinationIndex: number;
  }>;
}

/**
 * Get connection path between two nodes
 * @param workflow - Workflow instance
 * @param startNode - Starting node name
 * @param endNode - Target node name
 * @returns Connection path or null if no path exists
 */
function getConnectionPath(
  workflow: Workflow,
  startNode: string,
  endNode: string
): IConnectionPath | null;

interface IConnectionPath {
  nodes: string[];
  connections: IConnection[];
  length: number;
  isDirectConnection: boolean;
}

/**
 * Detect circular dependencies in workflow
 * @param workflow - Workflow instance
 * @returns Array of circular dependency chains
 */
function detectCircularDependencies(workflow: Workflow): string[][];

/**
 * Find disconnected nodes in workflow
 * @param workflow - Workflow instance
 * @returns Array of disconnected node names
 */
function findDisconnectedNodes(workflow: Workflow): string[];

/**
 * Calculate workflow execution order
 * @param workflow - Workflow instance
 * @param startNodes - Optional starting nodes
 * @returns Topologically sorted execution order
 */
function calculateExecutionOrder(
  workflow: Workflow,
  startNodes?: string[]
): string[];

/**
 * Analyze workflow complexity metrics
 * @param workflow - Workflow instance
 * @returns Complexity analysis results
 */
function analyzeWorkflowComplexity(workflow: Workflow): IComplexityAnalysis;

interface IComplexityAnalysis {
  nodeCount: number;
  connectionCount: number;
  maxDepth: number;
  branchingFactor: number;
  cyclomaticComplexity: number;
  hasCycles: boolean;
  disconnectedComponents: number;
}

/**
 * Depth-first search traversal
 * @param workflow - Workflow instance
 * @param startNode - Starting node name
 * @param visitFn - Function called for each visited node
 * @param options - Traversal options
 */
function depthFirstSearch(
  workflow: Workflow,
  startNode: string,
  visitFn: (node: INode, depth: number) => boolean | void,
  options?: ITraversalOptions
): void;

/**
 * Breadth-first search traversal
 * @param workflow - Workflow instance
 * @param startNode - Starting node name
 * @param visitFn - Function called for each visited node
 * @param options - Traversal options
 */
function breadthFirstSearch(
  workflow: Workflow,
  startNode: string,
  visitFn: (node: INode, level: number) => boolean | void,
  options?: ITraversalOptions
): void;

interface ITraversalOptions {
  maxDepth?: number;
  includeDisabled?: boolean;
  skipVisited?: boolean;
  connectionTypes?: NodeConnectionType[];
}

/**
 * Find shortest path between nodes
 * @param workflow - Workflow instance
 * @param startNode - Starting node name
 * @param endNode - Target node name
 * @returns Shortest path or null if no path exists
 */
function findShortestPath(
  workflow: Workflow,
  startNode: string,
  endNode: string
): string[] | null;

/**
 * Validate workflow graph structure
 * @param workflow - Workflow instance
 * @returns Validation results with errors and warnings
 */
function validateWorkflowGraph(workflow: Workflow): IGraphValidationResult;

interface IGraphValidationResult {
  isValid: boolean;
  errors: IGraphValidationError[];
  warnings: IGraphValidationWarning[];
}

interface IGraphValidationError {
  type: 'MISSING_NODE' | 'INVALID_CONNECTION' | 'CIRCULAR_DEPENDENCY' | 'DISCONNECTED_NODE';
  message: string;
  affectedNodes: string[];
  severity: 'high' | 'medium' | 'low';
}

interface IGraphValidationWarning {
  type: 'UNUSED_NODE' | 'COMPLEX_PATH' | 'PERFORMANCE_CONCERN';
  message: string;
  affectedNodes: string[];
  suggestion?: string;
}

/**
 * Check if workflow has valid execution paths
 * @param workflow - Workflow instance
 * @returns Boolean indicating if workflow has valid paths
 */
function hasValidExecutionPaths(workflow: Workflow): boolean;

/**
 * Validate node connections
 * @param workflow - Workflow instance
 * @param nodeName - Node to validate connections for
 * @returns Connection validation result
 */
function validateNodeConnections(
  workflow: Workflow,
  nodeName: string
): IConnectionValidationResult;

interface IConnectionValidationResult {
  isValid: boolean;
  invalidConnections: string[];
  missingRequiredInputs: string[];
  extraneousOutputs: string[];
}

import { 
  buildAdjacencyList,
  parseExtractableSubgraphSelection,
  getParentNodes,
  getChildNodes,
  mapConnectionsByDestination,
  detectCircularDependencies,
  calculateExecutionOrder,
  depthFirstSearch,
  validateWorkflowGraph
} from "n8n-workflow";

// Build adjacency list for graph analysis
const adjacencyList = buildAdjacencyList(workflow.getConnections());
console.log('Adjacency list:', adjacencyList);

// Extract subgraph
const subgraphResult = parseExtractableSubgraphSelection({
  nodeNames: ['Start', 'HTTP Request', 'Data Transform'],
  includeDisabled: false
});

if ('error' in subgraphResult) {
  console.log('Subgraph extraction failed:', subgraphResult.error);
} else {
  console.log('Extracted subgraph nodes:', subgraphResult.nodes);
  console.log('Entry nodes:', subgraphResult.entryNodes);
  console.log('Exit nodes:', subgraphResult.exitNodes);
}

// Analyze node relationships
const parents = getParentNodes(workflow, 'Data Transform');
const children = getChildNodes(workflow, 'HTTP Request');
const connected = getConnectedNodes(workflow, 'Start');

console.log('Parent nodes of Data Transform:', parents);
console.log('Child nodes of HTTP Request:', children);
console.log('All connected nodes to Start:', connected);

// Map connections by destination
const connectionMap = mapConnectionsByDestination(workflow.getConnections());
Object.entries(connectionMap).forEach(([destNode, connections]) => {
  console.log(`${destNode} receives input from:`, connections);
});

// Detect circular dependencies
const cycles = detectCircularDependencies(workflow);
if (cycles.length > 0) {
  console.log('Circular dependencies detected:');
  cycles.forEach((cycle, index) => {
    console.log(`Cycle ${index + 1}: ${cycle.join(' -> ')}`);
  });
}

// Calculate execution order
const executionOrder = calculateExecutionOrder(workflow);
console.log('Execution order:', executionOrder);

// Traverse workflow graph
depthFirstSearch(
  workflow,
  'Start',
  (node, depth) => {
    console.log(`${'  '.repeat(depth)}Visiting: ${node.name} (${node.type})`);
    
    // Return true to stop traversal, false/void to continue
    if (depth > 5) {
      console.log('Max depth reached, stopping traversal');
      return true;
    }
  },
  {
    maxDepth: 10,
    includeDisabled: false
  }
);

// Validate workflow graph
const validation = validateWorkflowGraph(workflow);
if (!validation.isValid) {
  console.log('Workflow validation errors:');
  validation.errors.forEach(error => {
    console.log(`- ${error.type}: ${error.message}`);
    console.log(`  Affected nodes: ${error.affectedNodes.join(', ')}`);
  });
}

if (validation.warnings.length > 0) {
  console.log('Workflow validation warnings:');
  validation.warnings.forEach(warning => {
    console.log(`- ${warning.type}: ${warning.message}`);
    if (warning.suggestion) {
      console.log(`  Suggestion: ${warning.suggestion}`);
    }
  });
}

// Complex workflow analysis
const complexity = analyzeWorkflowComplexity(workflow);
console.log('Workflow complexity analysis:');
console.log(`- Nodes: ${complexity.nodeCount}`);
console.log(`- Connections: ${complexity.connectionCount}`);
console.log(`- Max depth: ${complexity.maxDepth}`);
console.log(`- Branching factor: ${complexity.branchingFactor}`);
console.log(`- Cyclomatic complexity: ${complexity.cyclomaticComplexity}`);
console.log(`- Has cycles: ${complexity.hasCycles}`);
console.log(`- Disconnected components: ${complexity.disconnectedComponents}`);

// Find shortest path between nodes
const shortestPath = findShortestPath(workflow, 'Start', 'End');
if (shortestPath) {
  console.log('Shortest path from Start to End:', shortestPath.join(' -> '));
} else {
  console.log('No path found from Start to End');
}

// Breadth-first traversal to find all nodes at each level
const nodesByLevel: { [level: number]: string[] } = {};
breadthFirstSearch(
  workflow,
  'Start',
  (node, level) => {
    if (!nodesByLevel[level]) {
      nodesByLevel[level] = [];
    }
    nodesByLevel[level].push(node.name);
  }
);

console.log('Nodes by execution level:');
Object.entries(nodesByLevel).forEach(([level, nodes]) => {
  console.log(`Level ${level}: ${nodes.join(', ')}`);
});