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