All data structures can be represented as graphs. I use the term "graph" for
a collection of nodes (dots) and edges. (The rest of this paragraph
introduces this concept of graph, as per
this definition, for
those not familiar with it.)
Imagine a set of islands connected
by bridges; the nodes are the islands; the bridges are the edges.
[1] Seven Bridges of Konigsburg, Wikipedia,
https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsbe...
Graph Theory,
https://discrete.openmathbooks.org/dmoi3/ch_graphtheory.html
A
different kind of example is a conflict graph;
the program reads a set of courses, a set
of students, and for each student, the courses that
student wants to take;
the nodes would be courses; every time two or more students
want to take the same two courses,
the program creates an edge between those two courses. [2]
[2] Runa Ganguli and Siddhartha Roy,
"A Study on Course Timetabling based on the Graph Coloring Approach"
International Journal of Computational and Applied Mathematics,
Volume 2, No 17, 469-485.
A computer program would process this graph to schedule the courses
so there are no conflicts or few conflicts. In other words, it would
try to satisfy as many students as possible.
This is in contrast with the term "graph" that one saw in high school or
junior high school; that represents a function. An
example would be the line chart where the height of a child
is on the y-axis with their age on their x-axis and a point representing
each time their height was taken and with lines connecting one height data
point to another.
All data structures can be represented as graphs.
For example, a hypergraph can be represented as a graph where each hyperedge corresponds to a node and connected to the nodes to which the hyperedge.
Objects in a mechanical engineering CAD system
or graphics display
system are often kept as
the winged-edge configuration. That is, we know for each edge, the adjacent faces and for each faces, the edges.
Thus, the face is a "hyperedge" with
the edges in the diagram being
the nodes. [3]
[3] https://en.wikipedia.org/wiki/Winged_edge
Stanford Technical Report STAN CS 320
Bruce G. Baumgart, "Winged Edge Polyhedron Representation"
http://i.stanford.edu/pub/cstr/reports/cs/tr/72/320/CS-TR-72...
Charles Eastman and Kevin Walter
Geometric Modeling Using the Euler Operators , Carnegie
Mellon University DRC 15-279, May 1979
Of course, any graph can be serialized.
Often, that would be done
in JSON or XML.
ChatGPT tells me that
the time to serialize a graph is O(V+E) for adjacency lists and O(V^2) for
adjacency matrices.
That is, any data structure represented
as a collection
of pointers
can be converted into text in time
linear to the amount of information
in the data structure.
Adjacency matrices are used when we want to quickly see whether one entity
is connected to another; but it is at the cost of space and time to serialize.
Assume one is tracking which students are taking (or are interested in taking)
which course. In the computer, the programmer can put this into a rectangular
array of size CS where C is the number of courses and S is the number of
students. When dumped into text naively into text, this would take space
and time writing to disk
proportional to CS. On the other hand, assume that this is a sparse
array; on average, each student is only interested in taking 10 courses.
We can represent this as a list of average size 10 for each student, or
time 10S. (Or more precisely, 10S+C.)
We call in computer science, the relation between students and courses as
a many-many relationship.
See also: [4]
https://stackoverflow.com/questions/51783/how-to-serialize-a...
That is the power of sparsity, it reduces the time from a product to a linear
function. (The classic graph is a many-many relation
of something to itself. That is, which island is connected to another
island by a bridge, which course is connected to another one by a
student interested in both, or which city is connected to another city
by a direct flight.) The average number of connections for
each entity to another entity is the sparsity, m.
Thus, the time to write the data for a sparse representation is
represented by mN where N is the number of entities (or nodes).
By a little verbal sleight of hand, we say that the many-many relationship
of students courses is a graph where some nodes are labled "student" and others
are represented "course."
Throughout the above discussions, I ignore the
constant which is the time to write one connection to
the file; in this discussion, I ignore it
in most of the discussion for simplicity.
Similarly, with space, there is a proportionality constant--how many bits
or bytes does it take to record one student-course connection or one bridge
in the island-graph example.
As an aside not relevant to my discussion but relevant to
the entire discussion, I just saw a news article on storing JSON on binary.
https://devclass.com/2024/01/16/sqlites-new-support-for-bina...