papers.adligo.com

AdjacencyMatrices

Author: Scott Morgan
Created: 2025-12-12
Edited: 2025-12-13
Id: 1.3.6.1.4.1.33097.1.0.20
Copywrite 2025 Adligo Inc

An AdjacencyMatrix represents Nodes#1.3.6.1.4.1.33097.1.0.14.0 (usually represented by circles) and Edges#1.3.6.1.4.1.33097.1.0.14.1 (usually represented by [curved] lines or arrows) which may belong to a single Graph#1.3.6.1.4.1.33097.1.0.14 or GraphSet#1.3.6.1.4.1.33097.1.0.15. They are square 2d Matrices.

Although Adjacency Matrices are often used to represent single NodeNetwork#1.3.6.1.4.1.33097.1.0.14. They may also represent a NodeNetworkSet#1.3.6.1.4.1.33097.1.0.15 of multiple NodeNetworks#1.3.6.1.4.1.33097.1.0.14 which are not connected by any Edges#1.3.6.1.4.1.33097.1.0.14.1. In other words, a NodeNetwork#1.3.6.1.4.1.33097.1.0.14 can be represented by an Adjacency Matrix, however an Adjacency Matrix it does not imply that only a single NodeNetwork#1.3.6.1.4.1.33097.1.0.14 exists in the matrix.

u: The total number of slots in the matrix.

r: The total number rows (and columns) in the matrix.

i: The total number of slots in the matrix which are marked as true indicating an Edge#1.3.6.1.4.1.33097.1.0.12.1

Since AdjacencyMatrices provide a cross-referencing of the relations between the Nodes#1.3.6.1.4.1.33097.1.0.12.0 in a Graph#1.3.6.1.4.1.33097.1.0.14 they allow fast operations which would be slow in other data structures.

For Example;

Performing a complete Walk of the matrix is expensive as you will encounter many non-adjacent segments of the matrix;

Although this can potentially be reduced with something like Implementation B and BinaryFractialRangeWalks the complete Walk will take some extra time.

This was moved under abstract since there could be multiple implementations (i.e.);

A boolean 2D array

The two (or more) different implementations would provide vastly different asymptotic and exact performance.