filegraph

Documentation

Overview

Package filegraph implements a directed weighted graph of files, where the weight of edge (x, y), called distance, represents how much y is affected by changes in x. Such graph provides distance between any two files, and can order files by distance from/to a given file.

Index

• type EdgeReader
• type Node
• type Query
  • func (q *Query) Run(callback func(*ShortestPath) (keepGoing bool))
  • func (q *Query) ShortestPath(to Node) *ShortestPath
• type ShortestPath
  • func (r *ShortestPath) Path() []*ShortestPath

Types

type EdgeReader

type EdgeReader interface {
	// ReadEdges calls the callback for each edge of the given node.
	// If callback returns false, then iteration stops.
	//
	// May report multiple edges to the same node.
	// In context of Query, only the shortest one will influence the outcome.
	//
	// Idempotent: calling many times with the same `from` reports the same `to`
	// Node objects.
	ReadEdges(from Node, callback func(to Node, distance float64) (keepGoing bool))
}

EdgeReader reads edges of a node.

type Node

type Node interface {
	// Name returns node's name.
	// It is an forward-slash-separated path with "//" prefix,
	// e.g. "//foo/bar.cc".
	Name() string
}

Node is a node in a directed weighted graph of files. It is either a file or a directory.

The weight of edge (x, y), called distance, represents how much y is affected by changes in x. It is a value between 0 and +inf, where 0 means extremely affected and +inf means not affected at all.

type Query

type Query struct {
	// Sources are the nodes to start from.
	Sources []Node

	// EdgeReader is used to read adjacent nodes and distances.
	EdgeReader EdgeReader

	// MaxDistance, if positive, is the distance threshold.
	// Nodes further than this are considered unreachable.
	MaxDistance float64
	// contains filtered or unexported fields
}

Query finds shortest paths from any of Query.Sources to other nodes, producing a shortest-path tree (https://en.wikipedia.org/wiki/Shortest-path_tree).

It is based on Dijkstra's algorithm (https://en.wikipedia.org/wiki/Dijkstra's_algorithm).

func (*Query) Run

func (q *Query) Run(callback func(*ShortestPath) (keepGoing bool))

Run calls the callback for each node reachable from any of the sources. The nodes are reported in the distance-ascending order relative to the sources, starting from the sources themselves.

If the callback returns false, then the iteration stops.

func (*Query) ShortestPath

func (q *Query) ShortestPath(to Node) *ShortestPath

ShortestPath returns the shortest path to a node. Returns nil if the path does not exist. ShortestPath.Path() can be used to reconstruct the full path.

type ShortestPath

type ShortestPath struct {
	Node     Node
	Distance float64
	// Prev points to the previous node on the path from a source to this node.
	// It can be used to reconstruct the whole shortest path, starting from a
	// source.
	Prev *ShortestPath
}

ShortestPath represents the shortest path from one of sources to a node. ShortestPath itself is a node in a shortest path tree (https://en.wikipedia.org/wiki/Shortest-path_tree).

func (*ShortestPath) Path

func (r *ShortestPath) Path() []*ShortestPath

Path reconstructs the path from a query source to r.Node.