Store one graph in two representations
A graph's vertex count alone does not decide its best representation. Build directed graphs on two hundred vertices and store each as a byte-per-cell adjacency matrix and compressed sparse rows. Exclude self loops and duplicate edges. CSR uses thirty-two-bit offsets and destination indices. Before comparing storage, assert that every row exposes exactly the same neighbors in both forms.
Equal information is essential. If one representation also stores weights or reverse edges, its memory cost describes a different task. This experiment uses unweighted directed edges. An undirected extension needs an explicit policy for storing both directions. Distinguish mathematical edge count, stored entries and allocated bytes. Comparing labels such as matrix and list without those contracts can make an apparently precise memory result meaningless.
Predict logical bytes first
With V equal to two hundred, the matrix contains forty thousand bytes. CSR has V plus one offsets and E destinations, giving four times (V plus one plus E) bytes with thirty-two-bit entries. There are 39,800 possible nonself directed edges. At one percent density, E is 398 and predicted CSR payload is 2,396 bytes. At ten percent, 3,980 edges require 16,724 bytes.
At fifty percent, 19,900 edges require 80,404 CSR bytes, exceeding the byte matrix. The break-even depends on actual element types. A bit-packed matrix would have a different payload again. The experiment's byte-per-cell choice is explicit, not a claim that all adjacency matrices use that representation. Predict from stored arrays before measuring runtime objects so the numerical comparison has a clear basis.
| Density | Edges | Byte matrix | 32-bit CSR |
|---|---|---|---|
| 1% | 398 | 40,000 B | 2,396 B |
| 10% | 3,980 | 40,000 B | 16,724 B |
| 50% | 19,900 | 40,000 B | 80,404 B |
Fix generation and measurement scope
Save the code as graph.py and run it with Python on Linux using only the standard library. Seed seven chooses a fixed number of distinct candidate edges for each density, then sorts them for row construction. Assert that the integer array item size is four bytes. If another runtime has a different width, revise the type or prediction rather than silently comparing against the old formula.
The candidate-edge and chosen-edge lists also consume memory. Consequently the reported process peak RSS is not the isolated cost of either graph representation. This example compares logical payload and object sizes while demonstrating their difference from a process-wide measure. A strict standalone RSS comparison would need separate processes and a defined baseline; do not subtract these mixed-process figures and label the result per-representation memory.
Check every row before reporting memory
The matrix sets position i times V plus j. CSR appends a row's destinations and then records the next offset. Row i spans offsets[i] through offsets[i plus one], excluding the end. An empty row uses equal adjacent offsets. There must be V plus one offsets so the final row also has an explicit end; the last offset equals the total stored destinations.
Assert neighbor equality for all two hundred rows before printing capacity numbers. A smaller representation that dropped edges has not solved the same problem. Output vertex and edge counts, logical payload, sys.getsizeof object sizes and process peak RSS as separately named fields. Identify exactly which fields correspond to the prediction formula. This prevents several incompatible meanings of memory from being presented as one interchangeable measurement.
import array,random,resource,sys
n=200;rng=random.Random(7)
for fraction in [0.01,0.1,0.5]:
pairs=[(i,j) for i in range(n) for j in range(n) if i!=j];edges=sorted(rng.sample(pairs,int(len(pairs)*fraction)))
matrix=bytearray(n*n);offsets=array.array('I',[0]);columns=array.array('I');cursor=0
assert offsets.itemsize==columns.itemsize==4
for i in range(n):
while cursor<len(edges) and edges[cursor][0]==i:
j=edges[cursor][1];matrix[i*n+j]=1;columns.append(j);cursor+=1
offsets.append(len(columns))
for i in range(n):assert [j for j in range(n) if matrix[i*n+j]]==list(columns[offsets[i]:offsets[i+1]])
logical_csr=4*(n+1+len(edges));logical_matrix=n*n
assert logical_csr==offsets.itemsize*len(offsets)+columns.itemsize*len(columns)
print('vertices=',n,'edges=',len(edges),'matrix_bytes=',logical_matrix,'csr_bytes=',logical_csr,'objects_bytes=',sys.getsizeof(matrix),sys.getsizeof(offsets)+sys.getsizeof(columns),'process_peak_rss_KiB=',resource.getrusage(resource.RUSAGE_SELF).ru_maxrss)
print('same directed graph, no self loops or duplicate edges; all rows matched')
Interpret only what was measured
Logical predictions should match array lengths and element widths. sys.getsizeof additionally includes object management and allocation slack, so it can exceed payload bytes. Peak RSS depends on construction history and reports the whole process. The code labels Linux ru_maxrss in KiB; other operating systems may use another unit. Preserve OS and Python version with results.
The experiment does not time neighbor iteration or single-edge membership queries. Matrix indexing and CSR neighbor traversal support different operation patterns, but their actual latency was not measured by comparing byte counts. Cache effects and Python loop overhead are additional factors. Restrict conclusions to measured storage, then design a separate timing workload with identical queries and verified answers if performance is the next question.
For a representation-specific RSS comparison, launch separate processes with identical preparation and measurement boundaries. The single-process observation here cannot isolate either representation's incremental resident memory.
Distinguish construction peak from retained representation
This generator enumerates every possible edge before sampling, so temporary construction memory is quadratic even when retained CSR payload is linear in V plus E. A very large sparse-graph experiment should stream generation or consume an existing edge list instead. The completed representation's space bound does not automatically describe its builder's peak usage.
Preserve semantic graph equality when changing generation. Sorting and deduplication add their own temporary work. Separate reading input, constructing, retaining and querying the representation. Comparing whole-process RSS with only the final CSR formula and calling the difference waste confuses measurement boundaries.
For a rerun, keep Python version, array width and graph contracts explicit. If a result changes, first decide whether logical payload changed or whether object overhead and process-wide state changed. That classification makes the observed numbers useful rather than treating every memory field as an interchangeable implementation score.
Exercise: calculate a changed-density case
For V equal to one hundred and E equal to five hundred with the same types, the matrix payload is ten thousand bytes and CSR is four times 601, or 2,404 bytes. At three thousand edges, CSR becomes 12,404 bytes and exceeds the matrix. Solve the break-even from the formulas, then choose densities on both sides for an additional run.
A bit-packed hundred-by-hundred matrix has 1,250 logical bytes before management overhead, but changes access operations and tail handling. Do not reuse earlier object-size or speed claims after changing representation. The example creates no network or database resources; retain only source and reported results as needed. Explain input contracts, semantic equality, predicted storage and measurement scope together rather than selecting one attractive byte count.