What's the most intelligent way to store the information of a selfmade graph?

I have a very long list of element, say $a1,a2, a3$,..., and they are all connected in that each is the child of many parents. E.g. $a74$ is associated with $a2,a55,a71$, and also contains information, like 'the name of $a74$ is bob. It's an upwards tree if you want, with the $a$'s as vertices.

Now I wonder what the most efficient way to store this information in Mathematica is, given that I might have to run exhaustive computation along that graph. I'll mainly call the list of $a$-symbols to use them to climb further and I want to compute statistics about the graph itself. Sometimes I'll need the names of the vertices or other information.

My naive ideas are to make all symbols a list

a74={{a2,a55,a71},"bob"};


and then $a74[[1]]$ is the partent list and so on.

Or maybe I could define fictions $n\rightarrow \text{list}$ and store the information in them, like

parent[a5]={a1,a4};

parent[a74]={a2,a55,a71};


and

name[a5]="mila";

name[a74]="bob";


Or a mix, depending on what I call more often?

Or are there structures, which simplify or automatize these kind of things?

I don't know yet how computationally difficult it's going to be, so the practical point might also be considered. In any case, I'd like to hear what seems to be not the way to do it.

What is the right way to do this and/or are there other options?

At the moment I'd just generate the lists as in the first example. In actuality, I will write the list in a text-file and only later read in the information to a Mathematica file.

• Could you please use only code blocks for code? Please don't use math mode, it breaks copying. Mar 13, 2012 at 9:17
• Three approaches come to mind: 1. use a Graph with each node being a list. 2. Use a Graph with each node being an integer index into a list of information associated with each node. 3. Use the properties framework of Graph (see SetProperty, etc.) I'd try 3. first because it's a built-in way, but I've never seriously used it, so I can't comment on potential problems. My main worry would be that these properties don't go that well with functional programming. Mar 13, 2012 at 9:19
• @Szabolcs Why don't you make this an answer? I also agree with your concerns (Graphs-s implementation seems to be a serious departure from the "everything is an expression" principle, immutability, etc. A proper way to do that IMO would be to introduce language support for mutable structs, make them fast and well-integrated, and build graphs on top of those). Besides, the OP seems to be interested in directed acyclic graphs, and moreover, does not seem to be in need of modifying them - so the advantages of mutable built-in Graph-s here are at all questionable IMO. Mar 13, 2012 at 9:29
• @Leonid I didn't make it an answer because right now I don't have time to play with it, and compare the approaches e.g. performance wise or by usability. But I thought it'd be good to comment anyway, in case someone would want to do it. A proper answer needs a bit more work (feel free to include the gist of my comments in an answer, either here or in any other case in the future) Mar 13, 2012 at 9:38
• @Szabolcs Yes, I realized that :). But, you are in danger of crossing the line and start really answering in comments :) I also don't have time for a proper answer now, so I decided not to answer at all, until I do. I can see your point though: the SE model is flawed, and answers coming later don't often get the attention they deserve. Mar 13, 2012 at 9:44

This might be a suitable use case for UpValues. UpValues (/:) associate the definition with the inner symbol, rather than the outer function, and can be used as a kind of tag. So you can define your data:

a5 /: parents[a5] = {a1, a4};
a5 /: name[a5] = "mila";
a74 /: parents[a74] = {a2, a55, a71};
a74 /: name[a74] = "bob";


The other question is how you are going to store the original data to be loaded into the UpValues. In your question you suggested it would be some sort of text file. I assume it is the form

a4 "alice" a3 a2
a9 "carol" a6 a4


so you can Import it into a normal Mathematica matrix.

You could then write a function to process the imported data. Notice the use of Repeated (..) in the Pattern (:). The With construct seemed to be necessary to avoid certain errors firing.

makeDef[d : {{_Symbol, _String, __Symbol}..}] :=
With[{nn = First[#]},
(UpValues[nn] = {name[nn] -> #[[2]],
parents[nn] -> Drop[#, 2]})] & /@ d


The output from this looks strange but the UpValues are then correct.

And then a simple function like this

makeFamilyGraph[p_List] :=
Graph[Flatten[Thread[parents[#] -> #] & /@ p],
VertexLabels -> (# -> name[#] & /@ p)]


Gives output like this:

makeFamilyGraph[{a4, a5, a9, a74}]