| 1 |
*** NOTE THAT THE INTERNALS OF GRAPH 0.50 ARE COMPLEX *** |
| 2 |
*** AND (ALMOST INTENTIONALLY) UNDERDOCUMENTED. *** |
| 3 |
*** YOU ARE NOT SUPPOSED TO BE ABLE TO ACCESS *** |
| 4 |
*** THE INTERNALS DIRECTLY. *** |
| 5 |
|
| 6 |
The design goals of Graph 0.5 were flexibility and being able to |
| 7 |
represent even the more unusual graphs like graphs with reference-counted |
| 8 |
edges and vertices, multi(edge or vertex)graphs (an edge or vertex can |
| 9 |
"be present" more than once), hyper(edge)graphs (an edge can join more |
| 10 |
than two edges), and hypervertexgraphs (vertices of more than one, errm, |
| 11 |
vertex). |
| 12 |
|
| 13 |
As you can see (or rather, not see) being fast was not a design goal. |
| 14 |
|
| 15 |
Note that while the underlying data structures can do the above |
| 16 |
(and even a little bit beyond those), the common graph algorithms |
| 17 |
don't either (at best) understand at all the more esoteric graphs, |
| 18 |
or (at worst) break horribly, either by producing wrong results, |
| 19 |
crashing, or looping infinitely (isn't it nice to have options?). |
| 20 |
It is hoped that the people needing algorithms on the more esoteric |
| 21 |
graphs will write their own algorithms or enhance the current ones to |
| 22 |
cope better. |
| 23 |
|
| 24 |
While the data structures (into which we will get in a moment) |
| 25 |
are flexible, extra care was taken to optimize the common case |
| 26 |
(your usual non-counted non-hyper graphs) so that too much time |
| 27 |
memory isn't wasted in being overly general. Some waste does |
| 28 |
happen, so in general the code is 2-4 times slower than the |
| 29 |
previous generation, Graph 0.2xxx. |
| 30 |
|
| 31 |
Another complicating factor not really stemming from graph theory but |
| 32 |
from Perl itself was that some people wanted to be able to have Perl |
| 33 |
objects that have stringify overload as graph vertices. Also this is |
| 34 |
now possible (the "refvertexed" parameter), at least based on very |
| 35 |
light testing. It is very likely, though, that in some corners of the |
| 36 |
code this will still not work (it requires an extra step in handling |
| 37 |
vertices, and I quite probably forgot some spots). |
| 38 |
|
| 39 |
The most basic data structure of Graphs is a Map. A map consists of |
| 40 |
zero or more 'coordinates' and a data item that can be found by |
| 41 |
following the set of coordinates. The data item can also be missing |
| 42 |
which means that the set of coordinates exists. The set of |
| 43 |
coordinates can be ordered or unordered, and it can also be |
| 44 |
"uniquefying" or not on the coordinates. For the vertices the |
| 45 |
coordinates are strings, but there is a mapping from those strings to |
| 46 |
integers, and the edge coordinates use those integers. Maps come in |
| 47 |
different complexities: light, vertex, and heavy. A 'light' map is |
| 48 |
used if the elements have nothing fancy like for example attributes |
| 49 |
(it is basically just using a hash for the vertices and a hash of |
| 50 |
hashes for the edges), a 'heavy' map is used if they do. A 'vertex' |
| 51 |
map is a simplified version of a 'heavy' map used only for 'normal' |
| 52 |
(non-hyper) vertices. |
| 53 |
|
| 54 |
A vertex is an AdjacencyMap of one coordinate, an edge is a AdjacencyMap |
| 55 |
of two coordinates. (If we are talking about non-hyper cases.) |
| 56 |
|
| 57 |
Therefore an ordinary Graph is at its heart a tuple of AdjacencyMaps |
| 58 |
or in familiar terms (V, E). |
| 59 |
|
| 60 |
The rather complex design means that one is not really able (not without |
| 61 |
considerable and future-fragile effort) to derive from Graph and expect |
| 62 |
to be able to directly access and manipulate the internal data structures. |
| 63 |
|
| 64 |
Multiplicity in its most basic form is handled by having an additional |
| 65 |
counter for an (AdjacencyMap) item and then incrementing and |
| 66 |
decrementing that appropriately. When the counter goes to zero, |
| 67 |
a full delete takes place: this is called countvertexed/countedged. |
| 68 |
To be really "multi" each vertex or edge needs to have its own |
| 69 |
identity and existence and to be able to store its own data: this is |
| 70 |
called multivertexed/multiedged. |
| 71 |
|
| 72 |
The hyperness is handled by having separate slots for each |
| 73 |
AdjacencyMap item arity: zero, one (for vertices), two (for edges), |
| 74 |
and so forth. |
| 75 |
|
| 76 |
Both the multiplicity (count/multi) and hyperness are set up on demand |
| 77 |
when those features are requested at Graph creation, in the normal |
| 78 |
case the data structures are as simple as possible. The implementation |
| 79 |
is done by switching the internal implementation between ::Light, |
| 80 |
::Vertex, and ::Heavy classes. This is all done automatically |
| 81 |
and internally AND ONE IS NOT SUPPOSED TO USE THOSE CLASSES DIRECTLY. |
| 82 |
|
| 83 |
Attributes are part of (non-'light') AdjacencyMaps, this means that |
| 84 |
each vertex and edge can have its own attributes. Also Graphs can |
| 85 |
have attributes, but unfortunately Graph attributes do not currently |
| 86 |
use the AdjacencyMap abstraction for storing their attributes. |
| 87 |
|