README
¶
GraphMatrix
Simplified, efficient sparse matrix representations for unweighted graphs
Implementation of CSC Sparse Matrices representing boolean types.
There is no nzval vector; a point is defined or undefined.
Installation
With Go installed, package installation is performed using go get.
go get -u github.com/sbromberger/graphmatrix
Acknowledgements
Inspiration and some code taken / modified from James Bowman's sparse package
Documentation
¶
Overview ¶
Graphmatrix provides an implementation of sparse matrices used to describe unweighted graphs. Matrices are represented by two vectors representing a CSR sparse matrix index, with no `nzval` vector. Methods for setting and testing at a given (row, col) index are provided, as well as an iterator over all set points.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func SearchSorted32 ¶
SearchSorted32 finds a value x in sorted vector v. Returns index and true/false indicating found. lo and hi constrains search to these Indices. If lo/hi are out of bounds, return -1 and false unless the vector is empty, in which case return 0 and false.
Types ¶
type GraphMatrix ¶
type GraphMatrix struct {
IndPtr []uint64 // indexes into Indices - must be twice the width of Indices.
Indices []uint32 // contains the row values for each column. A stride represents the outneighbors of a vertex at col j.
}
GraphMatrix holds a row index and vector of column pointers. If a point is defined at a particular row i and column j, an edge exists between vertex i and vertex j. GraphMatrices thus represent directed graphs; undirected graphs must explicitly set the reverse edge from j to i.
func NewFromSortedIJ ¶
func NewFromSortedIJ(s []uint32, d []uint32) (GraphMatrix, error)
func (GraphMatrix) Dim ¶
func (g GraphMatrix) Dim() uint32
Dim returns the (single-axis) dimension of the GraphMatrix.
func (GraphMatrix) GetIndex ¶
func (g GraphMatrix) GetIndex(r, c uint32) bool
GetIndex returns true if the value at (r, c) is defined.
func (GraphMatrix) GetRow ¶
func (g GraphMatrix) GetRow(r uint32) ([]uint32, error)
GetRow returns the 'n'th row slice, or an empty slice if empty.
func (*GraphMatrix) N ¶
func (g *GraphMatrix) N() uint64
N returns the number of defined values in the GraphMatrix.
func (GraphMatrix) NewNZIter ¶
func (g GraphMatrix) NewNZIter() NZIter
NewNZIter creates a new graphmatrix iterator over a graphmatrix.
func (*GraphMatrix) SetIndex ¶
func (g *GraphMatrix) SetIndex(r, c uint32) error
SetIndex sets the value at (r, c) to true. This can be a relatively expensive operation as it can force reallocation as the vectors increase in size.
func (GraphMatrix) String ¶
func (g GraphMatrix) String() string
String is used for pretty printing.
type NZIter ¶
type NZIter struct {
// contains filtered or unexported fields
}
NZIter is an iterator over the defined points in the graphmatrix. If NZIter.Done is true, there are no more points defined. Changing the graphmatrix in the middle of an iteration will lead to undefined (and almost certainly unwanted) behavior.
func (*NZIter) Next ¶
Next returns the next nonzero entry in the iterator, returning its row and column. The iterator state is modified so that subsequent calls to `Next()` will retrieve successive nonzero values. Once all values are produced, `Next()` will set the iterator's `Done` field to `true` and will return `0, 0`.
Source Files