// Subgraph returns the directed subgraph with only the nodes and edges that match the
// provided functions.
345455
func (g Graph) Subgraph(nodeFn NodeFunc, edgeFn EdgeFunc) Graph {
	out := New()
	for _, node := range g.Nodes() {
		if nodeFn(out, node) {
			out.internal.AddNode(node)
		}
	}
	out.addEdges(g.internal.Edges(), edgeFn)
	return out
}
1216824
func (g *Virtual) Subgraph(s VertexSet) *Virtual {
	n := g.Order()
	s = s.And(Range(0, n))
	m := s.size()
	switch {
	case m == 0:
		return null
	case m == 1:
		return singleton()
	case m == n:
		return g
	}

	cost := func(v, w int) int64 {
		return g.cost(s.get(v), s.get(w))
	}
	res := generic(m, cost, func(v, w int) bool {
		return g.edge(s.get(v), s.get(w))
	})
	res.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
		if a >= m {
			return
		}
		v0 := s.get(v)
		s0 := s.And(Range(s.get(a), n))
		for _, in := range s0.set {
			if more := false; g.visit(v0, in.a, func(w0 int, c int64) (skip bool) {
				switch {
				case w0 >= in.b:
					more, skip = true, true
					return
				case do(s.rank(w0), c):
					return true
				default:
					return
				}
			}) && !more {
				return true
			}
		}
		return
	}
	return res
}
1041474
func (c *ChannelGraph) pruneGraphNodes(nodes *bbolt.Bucket,
	edgeIndex *bbolt.Bucket) error {

	log.Trace("Pruning nodes from graph with no open channels")

	// We'll retrieve the graph's source node to ensure we don't remove it
	// even if it no longer has any open channels.
	sourceNode, err := c.sourceNode(nodes)
	if err != nil {
		return err
	}

	// We'll use this map to keep count the number of references to a node
	// in the graph. A node should only be removed once it has no more
	// references in the graph.
	nodeRefCounts := make(map[[33]byte]int)
	err = nodes.ForEach(func(pubKey, nodeBytes []byte) error {
		// If this is the source key, then we skip this
		// iteration as the value for this key is a pubKey
		// rather than raw node information.
		if bytes.Equal(pubKey, sourceKey) || len(pubKey) != 33 {
			return nil
		}

		var nodePub [33]byte
		copy(nodePub[:], pubKey)
		nodeRefCounts[nodePub] = 0

		return nil
	})
	if err != nil {
		return err
	}

	// To ensure we never delete the source node, we'll start off by
	// bumping its ref count to 1.
	nodeRefCounts[sourceNode.PubKeyBytes] = 1

	// Next, we'll run through the edgeIndex which maps a channel ID to the
	// edge info. We'll use this scan to populate our reference count map
	// above.
	err = edgeIndex.ForEach(func(chanID, edgeInfoBytes []byte) error {
		// The first 66 bytes of the edge info contain the pubkeys of
		// the nodes that this edge attaches. We'll extract them, and
		// add them to the ref count map.
		var node1, node2 [33]byte
		copy(node1[:], edgeInfoBytes[:33])
		copy(node2[:], edgeInfoBytes[33:])

		// With the nodes extracted, we'll increase the ref count of
		// each of the nodes.
		nodeRefCounts[node1]++
		nodeRefCounts[node2]++

		return nil
	})
	if err != nil {
		return err
	}

	// Finally, we'll make a second pass over the set of nodes, and delete
	// any nodes that have a ref count of zero.
	var numNodesPruned int
	for nodePubKey, refCount := range nodeRefCounts {
		// If the ref count of the node isn't zero, then we can safely
		// skip it as it still has edges to or from it within the
		// graph.
		if refCount != 0 {
			continue
		}

		// If we reach this point, then there are no longer any edges
		// that connect this node, so we can delete it.
		if err := c.deleteLightningNode(nodes, nodePubKey[:]); err != nil {
			log.Warnf("Unable to prune node %x from the "+
				"graph: %v", nodePubKey, err)
			continue
		}

		log.Infof("Pruned unconnected node %x from channel graph",
			nodePubKey[:])

		numNodesPruned++
	}

	if numNodesPruned > 0 {
		log.Infof("Pruned %v unconnected nodes from the channel graph",
			numNodesPruned)
	}

	return nil
}
440932
func (it *Not) SubIterators() []graph.Iterator {
	return []graph.Iterator{it.primaryIt, it.allIt}
}
137075
func (s *joinReorderDPSolver) dpGraph(visitID2NodeID, nodeID2VisitID []int, joinGroup []LogicalPlan,
	totalEqEdges []joinGroupEqEdge, totalNonEqEdges []joinGroupNonEqEdge) (LogicalPlan, error) {
	nodeCnt := uint(len(visitID2NodeID))
	bestPlan := make([]*jrNode, 1<<nodeCnt)
	// bestPlan[s] is nil can be treated as bestCost[s] = +inf.
	for i := uint(0); i < nodeCnt; i++ {
		bestPlan[1<<i] = s.curJoinGroup[visitID2NodeID[i]]
	}
	// Enumerate the nodeBitmap from small to big, make sure that S1 must be enumerated before S2 if S1 belongs to S2.
	for nodeBitmap := uint(1); nodeBitmap < (1 << nodeCnt); nodeBitmap++ {
		if bits.OnesCount(nodeBitmap) == 1 {
			continue
		}
		// This loop can iterate all its subset.
		for sub := (nodeBitmap - 1) & nodeBitmap; sub > 0; sub = (sub - 1) & nodeBitmap {
			remain := nodeBitmap ^ sub
			if sub > remain {
				continue
			}
			// If this subset is not connected skip it.
			if bestPlan[sub] == nil || bestPlan[remain] == nil {
				continue
			}
			// Get the edge connecting the two parts.
			usedEdges, otherConds := s.nodesAreConnected(sub, remain, nodeID2VisitID, totalEqEdges, totalNonEqEdges)
			// Here we only check equal condition currently.
			if len(usedEdges) == 0 {
				continue
			}
			join, err := s.newJoinWithEdge(bestPlan[sub].p, bestPlan[remain].p, usedEdges, otherConds)
			if err != nil {
				return nil, err
			}
			curCost := s.calcJoinCumCost(join, bestPlan[sub], bestPlan[remain])
			if bestPlan[nodeBitmap] == nil {
				bestPlan[nodeBitmap] = &jrNode{
					p:       join,
					cumCost: curCost,
				}
			} else if bestPlan[nodeBitmap].cumCost > curCost {
				bestPlan[nodeBitmap].p = join
				bestPlan[nodeBitmap].cumCost = curCost
			}
		}
	}
	return bestPlan[(1<<nodeCnt)-1].p, nil
}
766528
func (g Graph) OutboundEdges(node graph.Node, edgeKinds ...string) []graph.Edge {
	ret := []graph.Edge{}

	for _, n := range g.From(node) {
		edge := g.Edge(node, n)
		if edge == nil {
			continue
		}

		if len(edgeKinds) == 0 || g.EdgeKinds(edge).HasAny(edgeKinds...) {
			ret = append(ret, edge)
		}
	}

	return ret
}
1328058
func getChildrenNodes(nodes []*html.Node, st siblingType) []*html.Node {
	return mapNodes(nodes, func(i int, n *html.Node) []*html.Node {
		return getChildrenWithSiblingType(n, st, nil, nil)
	})
}
519494
func substringFunc(arg1, arg2, arg3 query) func(query, iterator) interface{} {
	return func(q query, t iterator) interface{} {
		var m string
		switch typ := arg1.Evaluate(t).(type) {
		case string:
			m = typ
		case query:
			node := typ.Select(t)
			if node == nil {
				return ""
			}
			m = node.Value()
		}

		var start, length float64
		var ok bool

		if start, ok = arg2.Evaluate(t).(float64); !ok {
			panic(errors.New("substring() function first argument type must be int"))
		} else if start < 1 {
			panic(errors.New("substring() function first argument type must be >= 1"))
		}
		start--
		if arg3 != nil {
			if length, ok = arg3.Evaluate(t).(float64); !ok {
				panic(errors.New("substring() function second argument type must be int"))
			}
		}
		if (len(m) - int(start)) < int(length) {
			panic(errors.New("substring() function start and length argument out of range"))
		}
		if length > 0 {
			return m[int(start):int(length+start)]
		}
		return m[int(start):]
	}
}
378413
func Sub(a, b *T) T {
	if a[3] == b[3] {
		return T{a[0] - b[0], a[1] - b[1], a[2] - b[2], 1}
	} else {
		a3 := a.Vec3DividedByW()
		b3 := b.Vec3DividedByW()
		return T{a3[0] - b3[0], a3[1] - b3[1], a3[2] - b3[2], 1}
	}
}
189057
func (c *Context) Graph(typ GraphType, opts *ContextGraphOpts) (*Graph, tfdiags.Diagnostics) {
	if opts == nil {
		opts = &ContextGraphOpts{Validate: true}
	}

	log.Printf("[INFO] terraform: building graph: %s", typ)
	switch typ {
	case GraphTypeApply:
		return (&ApplyGraphBuilder{
			Config:     c.config,
			Changes:    c.changes,
			State:      c.state,
			Components: c.components,
			Schemas:    c.schemas,
			Targets:    c.targets,
			Destroy:    c.destroy,
			Validate:   opts.Validate,
		}).Build(addrs.RootModuleInstance)

	case GraphTypeValidate:
		// The validate graph is just a slightly modified plan graph
		fallthrough
	case GraphTypePlan:
		// Create the plan graph builder
		p := &PlanGraphBuilder{
			Config:     c.config,
			State:      c.state,
			Components: c.components,
			Schemas:    c.schemas,
			Targets:    c.targets,
			Validate:   opts.Validate,
		}

		// Some special cases for other graph types shared with plan currently
		var b GraphBuilder = p
		switch typ {
		case GraphTypeValidate:
			b = ValidateGraphBuilder(p)
		}

		return b.Build(addrs.RootModuleInstance)

	case GraphTypePlanDestroy:
		return (&DestroyPlanGraphBuilder{
			Config:     c.config,
			State:      c.state,
			Components: c.components,
			Schemas:    c.schemas,
			Targets:    c.targets,
			Validate:   opts.Validate,
		}).Build(addrs.RootModuleInstance)

	case GraphTypeRefresh:
		return (&RefreshGraphBuilder{
			Config:     c.config,
			State:      c.state,
			Components: c.components,
			Schemas:    c.schemas,
			Targets:    c.targets,
			Validate:   opts.Validate,
		}).Build(addrs.RootModuleInstance)

	case GraphTypeEval:
		return (&EvalGraphBuilder{
			Config:     c.config,
			State:      c.state,
			Components: c.components,
			Schemas:    c.schemas,
		}).Build(addrs.RootModuleInstance)

	default:
		// Should never happen, because the above is exhaustive for all graph types.
		panic(fmt.Errorf("unsupported graph type %s", typ))
	}
}
943856
func (g Graph) SuccessorNodesByEdgeKind(node graph.Node, edgeKinds ...string) []graph.Node {
	ret := []graph.Node{}

	for _, outboundEdge := range g.OutboundEdges(node, edgeKinds...) {
		ret = append(ret, outboundEdge.To())
	}

	return ret
}
1091220
func Sub(a, b *T) T {
	return T{a[0] - b[0], a[1] - b[1], a[2] - b[2]}
}
566206
func (g *UndirectedGraph) Edge(u, v graph.Node) graph.Edge {
	return g.EdgeBetween(u, v)
}
402043
func Intersect(subExprs interface{}, src *Col, result *map[int]struct{}) (err error) {
	myResult := make(map[int]struct{})
	if subExprVecs, ok := subExprs.([]interface{}); ok {
		first := true
		for _, subExpr := range subExprVecs {
			subResult := make(map[int]struct{})
			intersection := make(map[int]struct{})
			if err = evalQuery(subExpr, src, &subResult, false); err != nil {
				return
			}
			if first {
				myResult = subResult
				first = false
			} else {
				for k := range subResult {
					if _, inBoth := myResult[k]; inBoth {
						intersection[k] = struct{}{}
					}
				}
				myResult = intersection
			}
		}
		for docID := range myResult {
			(*result)[docID] = struct{}{}
		}
	} else {
		return dberr.New(dberr.ErrorExpectingSubQuery, subExprs)
	}
	return
}
1084372
func NewGraph(defs ...Definition) Graph {
	defMap := make(map[interface{}]Definition, len(defs))
	for _, def := range defs {
		defMap[def.Ptr()] = def
	}
	return &graph{
		definitions: defMap,
	}
}
998344
func (it *And) SubIterators() []graph.Iterator {
	iters := make([]graph.Iterator, 0, len(it.internalIterators)+1)
	if it.primaryIt != nil {
		iters = append(iters, it.primaryIt)
	}
	iters = append(iters, it.internalIterators...)
	return iters
}
767343
func marshalSubgrapher(v Vertex) (*Graph, bool) {
	sg, ok := v.(Subgrapher)
	if !ok {
		return nil, false
	}

	switch g := sg.Subgraph().DirectedGraph().(type) {
	case *Graph:
		return g, true
	case *AcyclicGraph:
		return &g.Graph, true
	}

	return nil, false
}