func isRedundantEdge(e *Edge) bool {
	src, n := e.Src, e.Dest
	seen := map[*Node]bool{n: true}
	queue := Nodes{n}
	for len(queue) > 0 {
		n := queue[0]
		queue = queue[1:]
		for _, ie := range n.In {
			if e == ie || seen[ie.Src] {
				continue
			}
			if ie.Src == src {
				return true
			}
			seen[ie.Src] = true
			queue = append(queue, ie.Src)
		}
	}
	return false
}
isRedundantEdge determines if there is a path that allows e.Src
to reach e.Dest after removing e.
package graph
import (
	"fmt"
	"math"
	"path/filepath"
	"regexp"
	"sort"
	"strconv"
	"strings"
	"github.com/google/pprof/profile"
)
var (
	javaRegExp = regexp.MustCompile(`^(?:[a-z]\w*\.)*([A-Z][\w\$]*\.(?:<init>|[a-z][\w\$]*(?:\$\d+)?))(?:(?:\()|$)`)
	goRegExp = regexp.MustCompile(`^(?:[\w\-\.]+\/)+(.+)`)
	goVerRegExp = regexp.MustCompile(`^(.*?)/v(?:[2-9]|[1-9][0-9]+)([./].*)$`)
	cppRegExp                = regexp.MustCompile(`^(?:[_a-zA-Z]\w*::)+(_*[A-Z]\w*::~?[_a-zA-Z]\w*(?:<.*>)?)`)
	cppAnonymousPrefixRegExp = regexp.MustCompile(`^\(anonymous namespace\)::`)
)
type Graph struct {
	Nodes Nodes
}
type Options struct {
	SampleValue       func(s []int64) int64       
	SampleMeanDivisor func(s []int64) int64       
	FormatTag         func(int64, string) string  
	ObjNames          bool                        
	OrigFnNames       bool                        
	CallTree     bool  
	DropNegative bool  
	KeptNodes NodeSet  
}
type Nodes []*Node
type Node struct {
	Info NodeInfo
	Function *Node
	Flat, FlatDiv, Cum, CumDiv int64
	In, Out EdgeMap
	LabelTags TagMap
	NumericTags map[string]TagMap
}
func (n *Node) FlatValue() int64 {
	if n.FlatDiv == 0 {
		return n.Flat
	}
	return n.Flat / n.FlatDiv
}
func (n *Node) CumValue() int64 {
	if n.CumDiv == 0 {
		return n.Cum
	}
	return n.Cum / n.CumDiv
}
func (n *Node) AddToEdge(to *Node, v int64, residual, inline bool) {
	n.AddToEdgeDiv(to, 0, v, residual, inline)
}
func (n *Node) AddToEdgeDiv(to *Node, dv, v int64, residual, inline bool) {
	if n.Out[to] != to.In[n] {
		panic(fmt.Errorf("asymmetric edges %v %v", *n, *to))
	}
	if e := n.Out[to]; e != nil {
		e.WeightDiv += dv
		e.Weight += v
		if residual {
			e.Residual = true
		}
		if !inline {
			e.Inline = false
		}
		return
	}
	info := &Edge{Src: n, Dest: to, WeightDiv: dv, Weight: v, Residual: residual, Inline: inline}
	n.Out[to] = info
	to.In[n] = info
}
type NodeInfo struct {
	Name              string
	OrigName          string
	Address           uint64
	File              string
	StartLine, Lineno int
	Objfile           string
}
func (i *NodeInfo) PrintableName() string {
	return strings.Join(i.NameComponents(), " ")
}
func (i *NodeInfo) NameComponents() []string {
	var name []string
	if i.Address != 0 {
		name = append(name, fmt.Sprintf("%016x", i.Address))
	}
	if fun := i.Name; fun != "" {
		name = append(name, fun)
	}
	switch {
	case i.Lineno != 0:
		name = append(name, fmt.Sprintf("%s:%d", i.File, i.Lineno))
	case i.File != "":
		name = append(name, i.File)
	case i.Name != "":
	case i.Objfile != "":
		name = append(name, "["+filepath.Base(i.Objfile)+"]")
	default:
		name = append(name, "<unknown>")
	}
	return name
}
type NodeMap map[NodeInfo]*Node
type NodeSet map[NodeInfo]bool
type NodePtrSet map[*Node]bool
func (nm NodeMap) FindOrInsertNode(info NodeInfo, kept NodeSet) *Node {
	if kept != nil {
		if _, ok := kept[info]; !ok {
			return nil
		}
	}
	if n, ok := nm[info]; ok {
		return n
	}
	n := &Node{
		Info:        info,
		In:          make(EdgeMap),
		Out:         make(EdgeMap),
		LabelTags:   make(TagMap),
		NumericTags: make(map[string]TagMap),
	}
	nm[info] = n
	if info.Address == 0 && info.Lineno == 0 {
		n.Function = n
		return n
	}
	info.Address = 0
	info.Lineno = 0
	n.Function = nm.FindOrInsertNode(info, nil)
	return n
}
type EdgeMap map[*Node]*Edge
type Edge struct {
	Src, Dest *Node
	Weight, WeightDiv int64
	Residual bool
	Inline bool
}
func (e *Edge) WeightValue() int64 {
	if e.WeightDiv == 0 {
		return e.Weight
	}
	return e.Weight / e.WeightDiv
}
type Tag struct {
	Name          string
	Unit          string  
	Value         int64
	Flat, FlatDiv int64
	Cum, CumDiv   int64
}
func (t *Tag) FlatValue() int64 {
	if t.FlatDiv == 0 {
		return t.Flat
	}
	return t.Flat / t.FlatDiv
}
func (t *Tag) CumValue() int64 {
	if t.CumDiv == 0 {
		return t.Cum
	}
	return t.Cum / t.CumDiv
}
type TagMap map[string]*Tag
func SortTags(t []*Tag, flat bool) []*Tag {
	ts := tags{t, flat}
	sort.Sort(ts)
	return ts.t
}
func New(prof *profile.Profile, o *Options) *Graph {
	if o.CallTree {
		return newTree(prof, o)
	}
	g, _ := newGraph(prof, o)
	return g
}
func newGraph(prof *profile.Profile, o *Options) (*Graph, map[uint64]Nodes) {
	nodes, locationMap := CreateNodes(prof, o)
	seenNode := make(map[*Node]bool)
	seenEdge := make(map[nodePair]bool)
	for _, sample := range prof.Sample {
		var w, dw int64
		w = o.SampleValue(sample.Value)
		if o.SampleMeanDivisor != nil {
			dw = o.SampleMeanDivisor(sample.Value)
		}
		if dw == 0 && w == 0 {
			continue
		}
		for k := range seenNode {
			delete(seenNode, k)
		}
		for k := range seenEdge {
			delete(seenEdge, k)
		}
		var parent *Node
		residual := false
		labels := joinLabels(sample)
		for i := len(sample.Location) - 1; i >= 0; i-- {
			l := sample.Location[i]
			locNodes := locationMap[l.ID]
			for ni := len(locNodes) - 1; ni >= 0; ni-- {
				n := locNodes[ni]
				if n == nil {
					residual = true
					continue
				}
				if _, ok := seenNode[n]; !ok {
					seenNode[n] = true
					n.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, false)
				}
				if _, ok := seenEdge[nodePair{n, parent}]; !ok && parent != nil && n != parent {
					seenEdge[nodePair{n, parent}] = true
					parent.AddToEdgeDiv(n, dw, w, residual, ni != len(locNodes)-1)
				}
				parent = n
				residual = false
			}
		}
		if parent != nil && !residual {
			parent.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, true)
		}
	}
	return selectNodesForGraph(nodes, o.DropNegative), locationMap
}
func selectNodesForGraph(nodes Nodes, dropNegative bool) *Graph {
	gNodes := make(Nodes, 0, len(nodes))
	for _, n := range nodes {
		if n == nil {
			continue
		}
		if n.Cum == 0 && n.Flat == 0 {
			continue
		}
		if dropNegative && isNegative(n) {
			continue
		}
		gNodes = append(gNodes, n)
	}
	return &Graph{gNodes}
}
type nodePair struct {
	src, dest *Node
}
func newTree(prof *profile.Profile, o *Options) (g *Graph) {
	parentNodeMap := make(map[*Node]NodeMap, len(prof.Sample))
	for _, sample := range prof.Sample {
		var w, dw int64
		w = o.SampleValue(sample.Value)
		if o.SampleMeanDivisor != nil {
			dw = o.SampleMeanDivisor(sample.Value)
		}
		if dw == 0 && w == 0 {
			continue
		}
		var parent *Node
		labels := joinLabels(sample)
		for i := len(sample.Location) - 1; i >= 0; i-- {
			l := sample.Location[i]
			lines := l.Line
			if len(lines) == 0 {
				lines = []profile.Line{{}}  
			}
			for lidx := len(lines) - 1; lidx >= 0; lidx-- {
				nodeMap := parentNodeMap[parent]
				if nodeMap == nil {
					nodeMap = make(NodeMap)
					parentNodeMap[parent] = nodeMap
				}
				n := nodeMap.findOrInsertLine(l, lines[lidx], o)
				if n == nil {
					continue
				}
				n.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, false)
				if parent != nil {
					parent.AddToEdgeDiv(n, dw, w, false, lidx != len(lines)-1)
				}
				parent = n
			}
		}
		if parent != nil {
			parent.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, true)
		}
	}
	nodes := make(Nodes, len(prof.Location))
	for _, nm := range parentNodeMap {
		nodes = append(nodes, nm.nodes()...)
	}
	return selectNodesForGraph(nodes, o.DropNegative)
}
func ShortenFunctionName(f string) string {
	f = cppAnonymousPrefixRegExp.ReplaceAllString(f, "")
	f = goVerRegExp.ReplaceAllString(f, `${1}${2}`)
	for _, re := range []*regexp.Regexp{goRegExp, javaRegExp, cppRegExp} {
		if matches := re.FindStringSubmatch(f); len(matches) >= 2 {
			return strings.Join(matches[1:], "")
		}
	}
	return f
}
func (g *Graph) TrimTree(kept NodePtrSet) {
	oldNodes := g.Nodes
	g.Nodes = make(Nodes, 0, len(kept))
	for _, cur := range oldNodes {
		if len(cur.In) > 1 {
			panic("TrimTree only works on trees")
		}
		if _, ok := kept[cur]; ok {
			g.Nodes = append(g.Nodes, cur)
			continue
		}
		if len(cur.In) == 0 {
			for _, outEdge := range cur.Out {
				delete(outEdge.Dest.In, cur)
			}
			continue
		}
		if len(cur.In) != 1 {
			panic("Get parent assertion failed. cur.In expected to be of length 1.")
		}
		var parent *Node
		for _, edge := range cur.In {
			parent = edge.Src
		}
		parentEdgeInline := parent.Out[cur].Inline
		delete(parent.Out, cur)
		for _, outEdge := range cur.Out {
			child := outEdge.Dest
			delete(child.In, cur)
			child.In[parent] = outEdge
			parent.Out[child] = outEdge
			outEdge.Src = parent
			outEdge.Residual = true
			outEdge.Inline = parentEdgeInline && outEdge.Inline
		}
	}
	g.RemoveRedundantEdges()
}
func joinLabels(s *profile.Sample) string {
	if len(s.Label) == 0 {
		return ""
	}
	var labels []string
	for key, vals := range s.Label {
		for _, v := range vals {
			labels = append(labels, key+":"+v)
		}
	}
	sort.Strings(labels)
	return strings.Join(labels, `\n`)
}
func isNegative(n *Node) bool {
	switch {
	case n.Flat < 0:
		return true
	case n.Flat == 0 && n.Cum < 0:
		return true
	default:
		return false
	}
}
func CreateNodes(prof *profile.Profile, o *Options) (Nodes, map[uint64]Nodes) {
	locations := make(map[uint64]Nodes, len(prof.Location))
	nm := make(NodeMap, len(prof.Location))
	for _, l := range prof.Location {
		lines := l.Line
		if len(lines) == 0 {
			lines = []profile.Line{{}}  
		}
		nodes := make(Nodes, len(lines))
		for ln := range lines {
			nodes[ln] = nm.findOrInsertLine(l, lines[ln], o)
		}
		locations[l.ID] = nodes
	}
	return nm.nodes(), locations
}
func (nm NodeMap) nodes() Nodes {
	nodes := make(Nodes, 0, len(nm))
	for _, n := range nm {
		nodes = append(nodes, n)
	}
	return nodes
}
func (nm NodeMap) findOrInsertLine(l *profile.Location, li profile.Line, o *Options) *Node {
	var objfile string
	if m := l.Mapping; m != nil && m.File != "" {
		objfile = m.File
	}
	if ni := nodeInfo(l, li, objfile, o); ni != nil {
		return nm.FindOrInsertNode(*ni, o.KeptNodes)
	}
	return nil
}
func nodeInfo(l *profile.Location, line profile.Line, objfile string, o *Options) *NodeInfo {
	if line.Function == nil {
		return &NodeInfo{Address: l.Address, Objfile: objfile}
	}
	ni := &NodeInfo{
		Address: l.Address,
		Lineno:  int(line.Line),
		Name:    line.Function.Name,
	}
	if fname := line.Function.Filename; fname != "" {
		ni.File = filepath.Clean(fname)
	}
	if o.OrigFnNames {
		ni.OrigName = line.Function.SystemName
	}
	if o.ObjNames || (ni.Name == "" && ni.OrigName == "") {
		ni.Objfile = objfile
		ni.StartLine = int(line.Function.StartLine)
	}
	return ni
}
type tags struct {
	t    []*Tag
	flat bool
}
func (t tags) Len() int      { return len(t.t) }
func (t tags) Swap(i, j int) { t.t[i], t.t[j] = t.t[j], t.t[i] }
func (t tags) Less(i, j int) bool {
	if !t.flat {
		if t.t[i].Cum != t.t[j].Cum {
			return abs64(t.t[i].Cum) > abs64(t.t[j].Cum)
		}
	}
	if t.t[i].Flat != t.t[j].Flat {
		return abs64(t.t[i].Flat) > abs64(t.t[j].Flat)
	}
	return t.t[i].Name < t.t[j].Name
}
func (ns Nodes) Sum() (flat int64, cum int64) {
	for _, n := range ns {
		flat += n.Flat
		cum += n.Cum
	}
	return
}
func (n *Node) addSample(dw, w int64, labels string, numLabel map[string][]int64, numUnit map[string][]string, format func(int64, string) string, flat bool) {
	if flat {
		n.FlatDiv += dw
		n.Flat += w
	} else {
		n.CumDiv += dw
		n.Cum += w
	}
	if labels != "" {
		t := n.LabelTags.findOrAddTag(labels, "", 0)
		if flat {
			t.FlatDiv += dw
			t.Flat += w
		} else {
			t.CumDiv += dw
			t.Cum += w
		}
	}
	numericTags := n.NumericTags[labels]
	if numericTags == nil {
		numericTags = TagMap{}
		n.NumericTags[labels] = numericTags
	}
	if format == nil {
		format = defaultLabelFormat
	}
	for k, nvals := range numLabel {
		units := numUnit[k]
		for i, v := range nvals {
			var t *Tag
			if len(units) > 0 {
				t = numericTags.findOrAddTag(format(v, units[i]), units[i], v)
			} else {
				t = numericTags.findOrAddTag(format(v, k), k, v)
			}
			if flat {
				t.FlatDiv += dw
				t.Flat += w
			} else {
				t.CumDiv += dw
				t.Cum += w
			}
		}
	}
}
func defaultLabelFormat(v int64, key string) string {
	return strconv.FormatInt(v, 10)
}
func (m TagMap) findOrAddTag(label, unit string, value int64) *Tag {
	l := m[label]
	if l == nil {
		l = &Tag{
			Name:  label,
			Unit:  unit,
			Value: value,
		}
		m[label] = l
	}
	return l
}
func (g *Graph) String() string {
	var s []string
	nodeIndex := make(map[*Node]int, len(g.Nodes))
	for i, n := range g.Nodes {
		nodeIndex[n] = i + 1
	}
	for i, n := range g.Nodes {
		name := n.Info.PrintableName()
		var in, out []int
		for _, from := range n.In {
			in = append(in, nodeIndex[from.Src])
		}
		for _, to := range n.Out {
			out = append(out, nodeIndex[to.Dest])
		}
		s = append(s, fmt.Sprintf("%d: %s[flat=%d cum=%d] %x -> %v ", i+1, name, n.Flat, n.Cum, in, out))
	}
	return strings.Join(s, "\n")
}
func (g *Graph) DiscardLowFrequencyNodes(nodeCutoff int64) NodeSet {
	return makeNodeSet(g.Nodes, nodeCutoff)
}
func (g *Graph) DiscardLowFrequencyNodePtrs(nodeCutoff int64) NodePtrSet {
	cutNodes := getNodesAboveCumCutoff(g.Nodes, nodeCutoff)
	kept := make(NodePtrSet, len(cutNodes))
	for _, n := range cutNodes {
		kept[n] = true
	}
	return kept
}
func makeNodeSet(nodes Nodes, nodeCutoff int64) NodeSet {
	cutNodes := getNodesAboveCumCutoff(nodes, nodeCutoff)
	kept := make(NodeSet, len(cutNodes))
	for _, n := range cutNodes {
		kept[n.Info] = true
	}
	return kept
}
func getNodesAboveCumCutoff(nodes Nodes, nodeCutoff int64) Nodes {
	cutoffNodes := make(Nodes, 0, len(nodes))
	for _, n := range nodes {
		if abs64(n.Cum) < nodeCutoff {
			continue
		}
		cutoffNodes = append(cutoffNodes, n)
	}
	return cutoffNodes
}
func (g *Graph) TrimLowFrequencyTags(tagCutoff int64) {
	for _, n := range g.Nodes {
		n.LabelTags = trimLowFreqTags(n.LabelTags, tagCutoff)
		for s, nt := range n.NumericTags {
			n.NumericTags[s] = trimLowFreqTags(nt, tagCutoff)
		}
	}
}
func trimLowFreqTags(tags TagMap, minValue int64) TagMap {
	kept := TagMap{}
	for s, t := range tags {
		if abs64(t.Flat) >= minValue || abs64(t.Cum) >= minValue {
			kept[s] = t
		}
	}
	return kept
}
func (g *Graph) TrimLowFrequencyEdges(edgeCutoff int64) int {
	var droppedEdges int
	for _, n := range g.Nodes {
		for src, e := range n.In {
			if abs64(e.Weight) < edgeCutoff {
				delete(n.In, src)
				delete(src.Out, n)
				droppedEdges++
			}
		}
	}
	return droppedEdges
}
func (g *Graph) SortNodes(cum bool, visualMode bool) {
	switch {
	case visualMode:
		g.Nodes.Sort(EntropyOrder)
	case cum:
		g.Nodes.Sort(CumNameOrder)
	default:
		g.Nodes.Sort(FlatNameOrder)
	}
}
func (g *Graph) SelectTopNodePtrs(maxNodes int, visualMode bool) NodePtrSet {
	set := make(NodePtrSet)
	for _, node := range g.selectTopNodes(maxNodes, visualMode) {
		set[node] = true
	}
	return set
}
func (g *Graph) SelectTopNodes(maxNodes int, visualMode bool) NodeSet {
	return makeNodeSet(g.selectTopNodes(maxNodes, visualMode), 0)
}
func (g *Graph) selectTopNodes(maxNodes int, visualMode bool) Nodes {
	if maxNodes > 0 {
		if visualMode {
			var count int
			for i, n := range g.Nodes {
				tags := countTags(n)
				if tags > maxNodelets {
					tags = maxNodelets
				}
				if count += tags + 1; count >= maxNodes {
					maxNodes = i + 1
					break
				}
			}
		}
	}
	if maxNodes > len(g.Nodes) {
		maxNodes = len(g.Nodes)
	}
	return g.Nodes[:maxNodes]
}
func countTags(n *Node) int {
	count := 0
	for _, e := range n.LabelTags {
		if e.Flat != 0 {
			count++
		}
	}
	for _, t := range n.NumericTags {
		for _, e := range t {
			if e.Flat != 0 {
				count++
			}
		}
	}
	return count
}
func (g *Graph) RemoveRedundantEdges() {
	for i := len(g.Nodes); i > 0; i-- {
		n := g.Nodes[i-1]
		in := n.In.Sort()
		for j := len(in); j > 0; j-- {
			e := in[j-1]
			if !e.Residual {
				break
			}
			if isRedundantEdge(e) {
				delete(e.Src.Out, e.Dest)
				delete(e.Dest.In, e.Src)
			}
		}
	}
}