Find shortest path from one table to another table

TableRelation.java

import java.util.*;
import java.util.stream.Collectors;

public class TableRelation {

    public static void main(String[] args) {

        ArrayList<Table> tablesList = new ArrayList<Table>();

//		tableColumnDetails

        Table employeTable = new Table("Employee");
        employeTable.addColumn(new Column("EmployeeName", false, null));
        employeTable.addColumn(new Column("EmployeeAge", false, null));
        employeTable.addColumn(new Column("EmployeeLocation", true, new ForeignKeyRelation("Location", "LocationName")));
        employeTable.addColumn(new Column("AssiagnedVehicle", true, new ForeignKeyRelation("Vechicles", "VehicleName")));
        employeTable.addColumn(new Column("EmployeeDepartment", true, new ForeignKeyRelation("Department", "DepartmentName")));

        Table locationTable = new Table("Location");
        locationTable.addColumn(new Column("LocationName", false, null));
        locationTable.addColumn(new Column("LocationPincode", false, null));
        locationTable.addColumn(new Column("LocationAdmin", true, new ForeignKeyRelation("Employee", "EmployeeName")));


        Table departmentTable = new Table("Department");
        departmentTable.addColumn(new Column("DepartmentName", false, null));
        departmentTable.addColumn(new Column("DepartmentRevenue", false, null));
        departmentTable.addColumn(new Column("DepartmentHead", true, new ForeignKeyRelation("Employee", "EmployeeName")));

        Table productTable = new Table("Product");
        productTable.addColumn(new Column("ProductName", false, null));
        productTable.addColumn(new Column("ProductUnitPrice", false, null));
        productTable.addColumn(new Column("ProductStock", false, null));

        Table ordersTable = new Table("Orders");
        ordersTable.addColumn(new Column("OrderProduct", true, new ForeignKeyRelation("Product", "ProductName")));
        ordersTable.addColumn(new Column("OrderQuantity", false, null));
        ordersTable.addColumn(new Column("OrderBy", true, new ForeignKeyRelation("Employee", "EmployeeName")));

        Table vechiclesTable = new Table("Vechicles");
        vechiclesTable.addColumn(new Column("VehicleName", false, null));
        vechiclesTable.addColumn(new Column("VehicleTopSpeed", false, null));

//		below is the relations

        tablesList.add(employeTable);
        tablesList.add(locationTable);
        tablesList.add(departmentTable);
        tablesList.add(productTable);
        tablesList.add(ordersTable);
        tablesList.add(vechiclesTable);

//		Input for the program

        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter Table1:");
        String table1 = scanner.next();

        System.out.println("Enter Table2:");
        String table2 = scanner.next();

        System.out.println("input : " + table1 + " to " + table2);

/*

		develop logic to detect relation between tables
		Refer the image for better understanding of the relationship

		Output Format:
		Table --> Table(PrevTableCol,CurrentTableCol) --> Table(PrevTableCol,CurrentTableCol) --> .....
		PrevTableCol,CurrentTableCol are directly related or indirectly if both tables has same foreign key
 --------------------------------------------------------------------------------------------------------------
		example:
 --------------------------------------------------------------------------------------------------------------
		Input: Vechicles to Employee
      Ouput:
		Shortest path:
		Output --> Vechicles --> Employee(VehicleName,AssiagnedVehicle)

		All possible path
		... <Print all possible paths, refer Usecase1.JPG> .............

 --------------------------------------------------------------------------------------------------------------
		Input: Department to Orders
      Ouput:
		Shortest path:
		Output --> Department --> Orders(DepartmentHead,OrderBy)

		All possible path
		... <Print all possible paths, refer Usecase2.JPG> .............

 --------------------------------------------------------------------------------------------------------------
		Input: Product to Vehicles
      Ouput:
		Shortest path:
		Output --> Product --> Orders(ProductName,OrderProduct) --> Employee(OrderBy,EmployeeName) --> Vehicles(AssiagnedVehicle,VehicleName)

		All possible path
		... <Print all possible paths, refer Usecase3.JPG> .............

 --------------------------------------------------------------------------------------------------------------
		Note:
		1. We need to execute this logic for N(say 100) tables and finding the relationship path should be in shortest time
		2. We need both outputs
			A. Shortest path
			B. All possible paths
		3. Two table are inter-related if they have same foreign key (for example: LocationAdmin, DeptHead and OrderBy are related)
		4. Please refer the image for better understanding
*/

        GraphTraversal gt = new GraphTraversal(tablesList);

        // Construct Graph
        tablesList.forEach(
                table -> {
                    table.tableColumns.stream()
                            // filter only foreign keys
                            .filter(column -> column.isForeignKey)
                            .forEach(column -> {
                                        gt.addRelation(table.tableName, column.ForeignKeyRelation.foreignTable,
                                                column.columnName, column.ForeignKeyRelation.foreignTableColumn);

                                        tablesList.forEach(table3 -> {
                                            table3.tableColumns.stream()
                                                    // filter only foreign keys
                                                    .filter(column1 -> column1.isForeignKey)
                                                    .forEach(column1 -> {
                                                        if (!table.tableName.equals(table3.tableName)
                                                                && column1.ForeignKeyRelation.foreignTableColumn.equals(column.ForeignKeyRelation.foreignTableColumn)) {
                                                            gt.addRelation(table3.tableName, table.tableName,
                                                                    column1.columnName, column.columnName);
                                                        }
                                                    });
                                        });
                                    }
                            );
                }
        );

        // generate All Paths
        gt.generateAllPaths(table1, table2);

        // print All possible paths
        List<String> allPossiblePaths = gt.getAllPossiblePaths();

        String shortestPath = allPossiblePaths.get(0);
        for (String str : allPossiblePaths) {
            if (str.length() < shortestPath.length()) {
                shortestPath = str;
            }
        }

        System.out.println("Shortest path:");
        System.out.println("Output --> " + shortestPath);
        System.out.println("All possible path:");
        allPossiblePaths.stream().forEach(path -> System.out.println("Output --> " + path));

    }

    static class ForeignKeyRelation {
        String foreignTable;
        String foreignTableColumn;

        public ForeignKeyRelation() {
            // TODO Auto-generated constructor stub
        }

        public ForeignKeyRelation(String foreignTable, String foreignTableColumn) {
            this.foreignTable = foreignTable;
            this.foreignTableColumn = foreignTableColumn;
        }
    }

    static class Column {
        String columnName;
        boolean isForeignKey;
        ForeignKeyRelation ForeignKeyRelation;

        public Column() {
            // TODO Auto-generated constructor stub
        }

        public Column(String columnName, boolean isForeignKey, ForeignKeyRelation ForeignKeyRelation) {
            this.columnName = columnName;
            this.isForeignKey = isForeignKey;
            this.ForeignKeyRelation = ForeignKeyRelation;
        }
    }

    static class Table {
        String tableName;
        ArrayList<Column> tableColumns = new ArrayList<Column>();

        public Table() {

        }

        public Table(String tableName) {
            this.tableName = tableName;
        }

        public Table addColumn(Column column) {
            tableColumns.add(column);
            return this;
        }
    }

}

class GraphTraversal {

    // No of tables
    private final List<TableRelation.Table> tablesList;

    // List of related Classes
    private Map<String, ArrayList<String>> relationMap = new HashMap<>();

    private List<String> allPossiblePaths = new ArrayList<>();

    public List<String> getAllPossiblePaths() {
        return allPossiblePaths;
    }

    // Constructor
    public GraphTraversal(List<TableRelation.Table> tablesList) {
        this.tablesList = tablesList;
        initRelationList();
    }

    private void initRelationList() {
        tablesList.forEach(table -> relationMap.put(table.tableName, new ArrayList<>()));
    }

    /**
     * Add relation between source to destination
     *
     * @param source: source table name
     * @param dest:   destination table name
     * @param s1:     source relationship column
     * @param d1:     destination relationship column
     */
    public void addRelation(String source, String dest, String s1, String d1) {
        // format is "destination(s1,d1)"
        String sourceRelation = dest + "(" + s1 + "," + d1 + ")";
        String destRelation = source + "(" + d1 + "," + s1 + ")";

        // add relation to source
        if (!relationMap.get(source).contains(sourceRelation)) {
            relationMap.get(source).add(sourceRelation);
        }

        // add relation to destination
        if (!relationMap.get(dest).contains(destRelation)) {
            relationMap.get(dest).add(destRelation);
        }
    }

    /**
     * Print all paths from source to destination
     *
     * @param source
     * @param destination
     */
    public void generateAllPaths(String source, String destination) {
        List<String> isVisited = new ArrayList<>();
        List<String> pathList = new ArrayList<>();

        // add source to path
        pathList.add(source);
        // all paths from source to destination

        pathsUtil(source, destination, isVisited, pathList);

        pathList.remove(source);
        pathList.add(destination);
        // all paths from destination to source
        pathsUtil(destination, source, isVisited, pathList);
    }

    /**
     * Recursive print path helper
     *
     * @param currentNode
     * @param destination
     * @param isVisited
     * @param localPathList
     */
    private void pathsUtil(String currentNode,
                           String destination,
                           List<String> isVisited,
                           List<String> localPathList) {
        if (destination.equals(currentNode)) {
//            System.out.println(String.join(" --> ", localPathList));
            this.allPossiblePaths.add(String.join(" --> ", localPathList));
            return;
        }

        isVisited.add(currentNode);

        this.relationMap.forEach((nodeName, value) -> {
            List<String> currentNodePaths = this.relationMap.get(currentNode);

            if (!isVisited.contains(nodeName)) {
                List<String> validPaths = currentNodePaths.stream()
                        .filter(path -> path.contains(nodeName + "("))
                        .collect(Collectors.toList());

                validPaths.forEach(
                        path -> {
                            localPathList.add(path);
                            pathsUtil(nodeName, destination, isVisited, localPathList);
                            localPathList.remove(path);
                        }
                );
            }
        });

        isVisited.remove(currentNode);
    }
}