flow

Documentation

Overview

Package flow provides control flow analysis functions.

Index

• type DominatorTree
  • func Dominators(root graph.Node, g graph.Directed) DominatorTree
  • func DominatorsSLT(root graph.Node, g graph.Directed) DominatorTree
  • func (d DominatorTree) DominatedBy(id int64) []graph.Node
  • func (d DominatorTree) DominatorOf(id int64) graph.Node
  • func (d DominatorTree) Root() graph.Node
• type Interval
  • func (i *Interval) Edge(uid, vid int64) graph.Edge
  • func (i *Interval) From(id int64) graph.Nodes
  • func (i *Interval) HasEdgeBetween(xid int64, yid int64) bool
  • func (i *Interval) HasEdgeFromTo(uid, vid int64) bool
  • func (i *Interval) Head() graph.Node
  • func (i *Interval) ID() int64
  • func (i *Interval) Node(id int64) graph.Node
  • func (i *Interval) Nodes() graph.Nodes
  • func (i *Interval) To(id int64) graph.Nodes
• type IntervalGraph
  • func Intervals(g graph.Directed, eid int64) IntervalGraph
  • func (ig *IntervalGraph) Edge(uid, vid int64) graph.Edge
  • func (ig *IntervalGraph) From(id int64) graph.Nodes
  • func (ig *IntervalGraph) HasEdgeBetween(xid int64, yid int64) bool
  • func (ig *IntervalGraph) HasEdgeFromTo(uid, vid int64) bool
  • func (ig *IntervalGraph) Head() graph.Node
  • func (ig *IntervalGraph) Node(id int64) graph.Node
  • func (ig *IntervalGraph) Nodes() graph.Nodes
  • func (ig *IntervalGraph) To(id int64) graph.Nodes

Types

type DominatorTree

type DominatorTree struct {
	// contains filtered or unexported fields
}

DominatorTree is a flow graph dominator tree.

func Dominators

func Dominators(root graph.Node, g graph.Directed) DominatorTree

Dominators returns a dominator tree for all nodes in the flow graph g starting from the given root node.

func DominatorsSLT

func DominatorsSLT(root graph.Node, g graph.Directed) DominatorTree

DominatorsSLT returns a dominator tree for all nodes in the flow graph g starting from the given root node using the sophisticated version of the Lengauer-Tarjan algorithm. The SLT algorithm may outperform the simple LT algorithm for very large dense graphs.

func (DominatorTree) DominatedBy

func (d DominatorTree) DominatedBy(id int64) []graph.Node

DominatedBy returns a slice of all nodes immediately dominated by the node with the given ID. Elements of the slice are retained by the DominatorTree.

func (DominatorTree) DominatorOf

func (d DominatorTree) DominatorOf(id int64) graph.Node

DominatorOf returns the immediate dominator of the node with the given ID.

func (DominatorTree) Root

func (d DominatorTree) Root() graph.Node

Root returns the root of the tree.

type Interval

type Interval struct {
	// contains filtered or unexported fields
}

Interval I(h) is the maximal, single entry subgraph for which h (head) is the entry node and in which all closed paths contain h.

func (*Interval) Edge

func (i *Interval) Edge(uid, vid int64) graph.Edge

Edge returns the edge given 2 node id's if the edge exists. Else it returns null.

func (*Interval) From

func (i *Interval) From(id int64) graph.Nodes

From returns all nodes in g that can be reached directly from n.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*Interval) HasEdgeBetween

func (i *Interval) HasEdgeBetween(xid int64, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y without considering direction.

func (*Interval) HasEdgeFromTo

func (i *Interval) HasEdgeFromTo(uid, vid int64) bool

HasEdgeFromTo returns whether an edge exists in the graph from u to v.

func (*Interval) Head

func (i *Interval) Head() graph.Node

Head returns header node for an interval.

func (*Interval) ID

func (i *Interval) ID() int64

ID returns the ID number of the node.

func (*Interval) Node

func (i *Interval) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the interval, and nil otherwise.

func (*Interval) Nodes

func (i *Interval) Nodes() graph.Nodes

Nodes returns a node iterator for an interval.

func (*Interval) To

func (i *Interval) To(id int64) graph.Nodes

To returns all nodes in g that can reach directly to n.

The returned graph.Nodes is only valid until the next mutation of the receiver.

type IntervalGraph

type IntervalGraph struct {
	Intervals map[int64]*Interval
	// contains filtered or unexported fields
}

IntervalGraph contains the intervals and the edges between the intervals.

func Intervals

func Intervals(g graph.Directed, eid int64) IntervalGraph

Intervals returns the IntervalGraph containing the individual intervals of the directed graph in g when starting from the entry node identified by eid.

func (*IntervalGraph) Edge

func (ig *IntervalGraph) Edge(uid, vid int64) graph.Edge

Edge returns the edge given 2 node id's if the edge exists. Else it returns null.

func (*IntervalGraph) From

func (ig *IntervalGraph) From(id int64) graph.Nodes

From returns all nodes in g that can be reached directly from n.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*IntervalGraph) HasEdgeBetween

func (ig *IntervalGraph) HasEdgeBetween(xid int64, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y without considering direction.

func (*IntervalGraph) HasEdgeFromTo

func (ig *IntervalGraph) HasEdgeFromTo(uid, vid int64) bool

HasEdgeFromTo returns whether an edge exists in the graph from u to v.

func (*IntervalGraph) Head

func (ig *IntervalGraph) Head() graph.Node

Head returns header node for an IntervalGraph.

func (*IntervalGraph) Node

func (ig *IntervalGraph) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the IntervalGraph, and nil otherwise.

func (*IntervalGraph) Nodes

func (ig *IntervalGraph) Nodes() graph.Nodes

Nodes returns a node iterator for an IntervalGraph.

func (*IntervalGraph) To

func (ig *IntervalGraph) To(id int64) graph.Nodes

To returns all nodes in g that can reach directly to n.

The returned graph.Nodes is only valid until the next mutation of the receiver.