// NewBfs execute the BFS search for a specified source on a graph
NewBfs execute the BFS search for a specified source on a graph
// NewBfs execute the BFS search for a specified source on a graph
func NewBfs(g graph.Graph, source graph.NodeID, control SearchControl) (*Bfs, error) {
	if g.NodeCount() < 2 {
		return nil, fmt.Errorf("Invalid Graph len %d, at least 2 nodes should in the graph", g.NodeCount())
	}
	if !g.IsNodeValid(source) {
		return nil, fmt.Errorf("Invalid Source %v not in the graph", source)
	}
	bfsContext := &Bfs{source, nodeAttrArray{}}
	g.IterateAllNodes(func(k graph.NodeID) {
		bfsContext.nodesAttr[k] = &nodeAttr{0, white, graph.InvalidNodeID} 
	})
	bfsContext.nodesAttr[source].depth = 0
	bfsContext.nodesAttr[source].nodeColor = gray
	bfsContext.nodesAttr[source].parent = graph.InvalidNodeID
	var queue []graph.NodeID 
	queue = append(queue, source)
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		if control != nil {
			if control(u) == Break {
				break 
			}
		}
		currDepth := bfsContext.nodesAttr[u].depth
		g.IterateAdjacencyNodes(u, func(v graph.NodeID) {
			if bfsContext.nodesAttr[v].nodeColor == white {
				bfsContext.nodesAttr[v].depth = currDepth + 1
				bfsContext.nodesAttr[v].parent = u
				bfsContext.nodesAttr[v].nodeColor = gray
				queue = append(queue, v)
			}
		})
		bfsContext.nodesAttr[u].nodeColor = black
	}
	return bfsContext, nil
}
func NewBfs ( g graph . Graph , source graph . NodeID , control SearchControl ) ( * Bfs , error ) { if g . NodeCount ( ) < 2 { return nil , fmt . Errorf ( " " , g . NodeCount ( ) ) } if ! g . IsNodeValid ( source ) { return nil , fmt . Errorf ( " " , source ) } bfsContext := & Bfs { source , nodeAttrArray { } } g . IterateAllNodes ( func ( k graph . NodeID ) { bfsContext . nodesAttr [ k ] = & nodeAttr { 0 , white , graph . InvalidNodeID } } ) bfsContext . nodesAttr [ source ] . depth = 0 bfsContext . nodesAttr [ source ] . nodeColor = gray bfsContext . nodesAttr [ source ] . parent = graph . InvalidNodeID var queue [ ] graph . NodeID queue = append ( queue , source ) for len ( queue ) > 0 { u := queue [ 0 ] queue = queue [ 1 : ] if control != nil { if control ( u ) == Break { break } } currDepth := bfsContext . nodesAttr [ u ] . depth g . IterateAdjacencyNodes ( u , func ( v graph . NodeID ) { if bfsContext . nodesAttr [ v ] . nodeColor == white { bfsContext . nodesAttr [ v ] . depth = currDepth + 1 bfsContext . nodesAttr [ v ] . parent = u bfsContext . nodesAttr [ v ] . nodeColor = gray queue = append ( queue , v ) } } ) bfsContext . nodesAttr [ u ] . nodeColor = black } return bfsContext , nil }
NewBfs execute the BFS search for a specified source on a graph
NewBfs execute the BFS search for a specified source on a graph
// Initialize // create node attr for each node // next search queue // pop the first element //fmt.Printf("break at node %v\n", u) // break the search in advance by the process control