SpreadSheet/cycle.js at main · dixi225/SpreadSheet · GitHub

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
let collectedGraphComponent= [];
let graphComponentMatrix=[];
// for( let i=0;i< rows;i++)
// {
//     let row=[];
//     for( let j=0;j<col;j++)
//     {

//         row.push([]);
//     }
//     graphComponentMatrix.push(row);
// }
function isCyclic(graphComponentMatrix)
{
    let visited=[];
    let dfsVisited=[];
    for(let i=0;i<rows;i++)
    {
        let visitedRow=[];
        let dfsVisitedRow=[];
        for(let j=0;j<col;j++)
        {
            visitedRow.push(false);
            dfsVisitedRow.push(false);
        }
        visited.push(visitedRow);
        dfsVisited.push(dfsVisitedRow);
    }
    for(let i=0;i<rows;i++)
    {
        for(let j=0;j<col;j++)
        {
            if(visited[i][j]===true) continue;
            else
            {
                let response=dfsCycleDetection(graphComponentMatrix , i ,j ,visited , dfsVisited);
                if(response===true) return [i , j];
            }
        }
    }
    return null;
}
function dfsCycleDetection(graphComponentMatrix , i ,j ,visited , dfsVisited)
{
    visited[i][j]=true;
    dfsVisited[i][j]=true;
    for(let child=0;child<graphComponentMatrix[i][j].length;child++)
    {
        let[crid, ccid]=graphComponentMatrix[i][j][child];
        if(visited[crid][ccid]===false)
        {
            let response=dfsCycleDetection(graphComponentMatrix,crid,ccid,visited,dfsVisited);
            if(response===true) return true;
        }
        else
        {
            if(visited[crid][ccid]===true&&dfsVisited[i][j]===true) return true;
        }
    }
    dfsVisited[i][j]=false;
    return false;
}