// SplitToStronglyConnectedComponents to split the input directed graph
// to several strongly connected components
SplitToStronglyConnectedComponents to split the input directed graph
to several strongly connected components
// SplitToStronglyConnectedComponents to split the input directed graph // to several strongly connected components
func SplitToStronglyConnectedComponents(g graph.Graph) ([]StronglyConnectedComponent, error) {
	if !g.Directed() {
		return nil, fmt.Errorf("It's not a directed graph")
	}
	firstDfs, err := NewDfsForest(g, StackBased)
	if err != nil {
		return nil, err
	}
	sortedNodes, err := sortNodesByTimestampF(firstDfs.nodesAttr)
	if err != nil {
		return nil, err
	}
	transposedG, err := graph.Transpose(g, graph.NewAdjacencyListGraph) 
	if err != nil {
		return nil, err
	}
	secondDfs := &Dfs{0, []dfsTree{}, nodeAttrArray{}, edgeAttrArray{}}
	secondDfs.initialize(transposedG)
	secondRootIndicators := make([]bool, transposedG.NodeCount(), transposedG.NodeCount())
	for i := len(sortedNodes) - 1; i >= 0; i-- { 
		currNode := sortedNodes[i]
		if secondDfs.nodesAttr[currNode].nodeColor == white {
			secondDfs.forest = append(secondDfs.forest, dfsTree{currNode})
			secondRootIndicators[currNode] = true
			secondDfs.dfsStackBasedVisit(transposedG, currNode, nil)
		}
	}
	secondSortedNodes, err := sortNodesByTimestampF(secondDfs.nodesAttr)
	if err != nil {
		return nil, err
	}
	components := []StronglyConnectedComponent{}
	scc := StronglyConnectedComponent{}
	for _, v := range secondSortedNodes {
		scc = append(scc, v)
		if secondRootIndicators[v] {
			components = append(components, scc)
			scc = StronglyConnectedComponent{} 
		}
	}
	return components, nil
}
func SplitToStronglyConnectedComponents ( g graph . Graph ) ( [ ] StronglyConnectedComponent , error ) { if ! g . Directed ( ) { return nil , fmt . Errorf ( " " ) } firstDfs , err := NewDfsForest ( g , StackBased ) if err != nil { return nil , err } sortedNodes , err := sortNodesByTimestampF ( firstDfs . nodesAttr ) if err != nil { return nil , err } transposedG , err := graph . Transpose ( g , graph . NewAdjacencyListGraph ) if err != nil { return nil , err } secondDfs := & Dfs { 0 , [ ] dfsTree { } , nodeAttrArray { } , edgeAttrArray { } } secondDfs . initialize ( transposedG ) secondRootIndicators := make ( [ ] bool , transposedG . NodeCount ( ) , transposedG . NodeCount ( ) ) for i := len ( sortedNodes ) - 1 ; i >= 0 ; i -- { currNode := sortedNodes [ i ] if secondDfs . nodesAttr [ currNode ] . nodeColor == white { secondDfs . forest = append ( secondDfs . forest , dfsTree { currNode } ) secondRootIndicators [ currNode ] = true secondDfs . dfsStackBasedVisit ( transposedG , currNode , nil ) } } secondSortedNodes , err := sortNodesByTimestampF ( secondDfs . nodesAttr ) if err != nil { return nil , err } components := [ ] StronglyConnectedComponent { } scc := StronglyConnectedComponent { } for _ , v := range secondSortedNodes { scc = append ( scc , v ) if secondRootIndicators [ v ] { components = append ( components , scc ) scc = StronglyConnectedComponent { } } } return components , nil }
SplitToStronglyConnectedComponents to split the input directed graph
to several strongly connected components
SplitToStronglyConnectedComponents to split the input directed graph to several strongly connected components
// sort nodes by increasing timestampF // calculate transposed graph of original graph // initialize for second DFS on transposed graph //second iteration by reverse order of topoSort // retrieve components split by root of forest // root will always have biggeest timestampF // so the last node MUST be root, and will be append into components //clear