import copy


def randomWalkBFS2(G, initialVoxels, boundaryVoxels):
    """
    Similar to `randomWalkBFS` except that this function does not modify the graph `G`. `G` should have `depthVoxel` 
    attribute for each voxel.

    Parameters
    ----------
    G : NetworkX graph
        The graph to be traversed.
    initialVoxels : list
        A list of voxels to start with.
    boundaryVoxels : list
        A list of voxels that mark the boundary.
    
    Returns
    -------
    G : NetworkX graph
        The graph with traversal information added.
    voxelsVisitedList : list
        A list of voxels that have been traversed.
    segmentIndexVisitedList : list
        A list of segment indices that have been traversed.
    """
    initialVoxelsTuple = initialVoxels
    boundaryVoxelsTuple = boundaryVoxels
    initialVoxelsTuple = list(map(tuple, initialVoxels))
    boundaryVoxelsTuple = list(map(tuple, boundaryVoxels))
    numOfVoxelsVisited = len(initialVoxelsTuple)
    voxelsVisitedList = copy.deepcopy(initialVoxelsTuple) # make deep copy
    pool = copy.deepcopy(initialVoxelsTuple) # make deep copy
    segmentIndexVisitedList = [] # record the index of segments traversed
    while len(pool) != 0:
        poolTemp = []
        for currentVoxel in pool:
            depthVoxel = G.node[currentVoxel]['depthVoxel']
            newVoxels = [voxel for voxel in G.neighbors(currentVoxel) if voxel not in boundaryVoxelsTuple and 'depthVoxel' in G.node[voxel] and G.node[voxel]['depthVoxel'] > depthVoxel]
            for newVoxel in newVoxels:
                if G.degree(newVoxel) >= 3: # add the current segment after passing a bifurcation point
                    newSegmentIndex = G[currentVoxel][newVoxel]['segmentIndex']
                    segmentIndexVisitedList.append(newSegmentIndex)
                elif G.degree(newVoxel) == 1: # add the current segment when reaching the end of a segment
                    newSegmentIndex = G[currentVoxel][newVoxel]['segmentIndex']
                    segmentIndexVisitedList.append(newSegmentIndex)

            poolTemp += newVoxels
            numOfVoxelsVisited += len(newVoxels)
            voxelsVisitedList += newVoxels
        
        pool = poolTemp
    
    print('{} nodes visited'.format(numOfVoxelsVisited))
    return G, voxelsVisitedList, segmentIndexVisitedList