MySQL table dependency resolution

main.rs

use std::collections::{HashMap, VecDeque};
use std::io;


#[tokio::main]
async fn main() -> io::Result<()> {
    // Initialize a HashMap to represent the tables and their dependencies
    let mut tables = HashMap::new();
    tables.insert("users".to_string(), vec![]);
    tables.insert("roles".to_string(), vec![]);
    tables.insert("role_users".to_string(), vec!["users".to_string(), "roles".to_string()]);
    tables.insert("blogs".to_string(), vec!["users".to_string()]);
    tables.insert("comments".to_string(), vec!["users".to_string(), "blogs".to_string(), "comments".to_string()]);
    tables.insert("medias".to_string(), vec!["users".to_string()]);
    tables.insert("user_settings".to_string(), vec!["users".to_string()]);
    tables.insert("settings".to_string(), vec![]);

    // Resolve the order in which tables should be imported
    let import_order = resolve_tables(tables);
    println!("Import order: {:?}", import_order);
    Ok(())
}

// Function to resolve the order of table imports based on dependencies
// This function determines the order in which tables should be imported to respect their dependencies.
// It calculates the in-degree for each table, collects tables with zero in-degree, processes the queue to resolve the order,
// and adds self-referencing tables at the end. Finally, it reverses the resolved list to get the correct import order.
fn resolve_tables(tables: HashMap<String, Vec<String>>) -> Vec<String> {
    // Calculate the in-degree (number of incoming edges) for each table
    let in_degree = calculate_in_degree(&tables);
    let mut resolved = Vec::new();
    // Collect tables with zero in-degree (no dependencies)
    let mut queue = collect_zero_in_degree_nodes(&in_degree);

    // Process the queue to resolve the order
    process_queue(&tables, &mut resolved, &mut queue, in_degree);
    // Add self-referencing tables at the end
    add_self_referencing_tables(&tables, &mut resolved);
    
    // Reverse the resolved vector before returning it
    resolved.reverse();
    
    resolved
}

// Function to calculate the in-degree for each table
// This function is used to determine the number of dependencies (incoming edges) for each table in the database schema.
// The in-degree of a table represents how many other tables depend on it.
// This information is crucial for determining the order in which tables should be imported to respect their dependencies.
fn calculate_in_degree(tables: &HashMap<String, Vec<String>>) -> HashMap<String, usize> {
    let mut in_degree = HashMap::new();

    for (table, parent_tables) in tables {
        // Initialize in-degree for the current table if it doesn't exist
        if !in_degree.contains_key(table) {
            in_degree.insert(table.clone(), 0);
        }
        for parent_table in parent_tables {
            if table != parent_table {
                // Initialize in-degree for the parent table if it doesn't exist
                if !in_degree.contains_key(parent_table) {
                    in_degree.insert(parent_table.clone(), 0);
                }
                // Increment the in-degree for the parent table
                *in_degree.get_mut(parent_table).unwrap() += 1;
            }
        }
    }

    in_degree
}

// Function to collect tables with zero in-degree
// This function identifies all tables that have no dependencies (zero in-degree).
// Tables with zero in-degree can be imported first because they do not depend on any other tables.
// The function returns a queue (VecDeque) containing these tables, which will be processed first in the import order.
fn collect_zero_in_degree_nodes(in_degree: &HashMap<String, usize>) -> VecDeque<String> {
    let mut queue = VecDeque::new();

    for (node, &degree) in in_degree {
        if degree == 0 {
            // Add tables with zero in-degree to the queue
            queue.push_back(node.clone());
        }
    }

    queue
}

// Function to process the queue and resolve the order of tables
// This function processes the queue of tables with zero in-degree and determines the order in which tables should be imported.
// It iteratively removes tables from the queue, adds them to the resolved list, and updates the in-degree of their dependent tables.
// If a dependent table's in-degree becomes zero, it is added to the queue to be processed next.
// This ensures that tables are imported in an order that respects their dependencies.
fn process_queue(
    tables: &HashMap<String, Vec<String>>,
    resolved: &mut Vec<String>,
    queue: &mut VecDeque<String>,
    mut in_degree: HashMap<String, usize>,
) {
    while let Some(node) = queue.pop_front() {
        // Add the current table to the resolved list
        resolved.push(node.clone());
        if let Some(edges) = tables.get(&node) {
            for edge in edges {
                if node != *edge {
                    // Decrement in-degree for each dependency
                    let degree = in_degree.get_mut(edge).unwrap();
                    *degree -= 1;
                    if *degree == 0 {
                        // Add tables with zero in-degree to the queue
                        let table = edge.clone();
                        // queue.push_back(table);
                        queue.push_front(table);
                    }
                }
            }
        }
    }
}

// Function to add self-referencing tables to the resolved list
// This function identifies tables that reference themselves (self-referencing tables).
// Self-referencing tables are those that have a dependency on themselves.
// These tables are added to the resolved list if they haven't been added already.
// This ensures that all tables, including self-referencing ones, are included in the import order.
fn add_self_referencing_tables(tables: &HashMap<String, Vec<String>>, resolved: &mut Vec<String>) {
    for (node, edges) in tables {
        if edges.contains(node) && !resolved.contains(node) {
            // Add self-referencing table to the resolved list
            resolved.push(node.clone());
        }
    }
}