Debian Codegraph @

DESIGN

raw
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