Can vertices in graphs be lists?

Question

I would like to construct a graph iteratively via a for loop, using the function VertexAdd. The nice thing about VertexAdd is that it will add a vertex only if it does not already exist in the graph. The vertices in my graph should be actually lists of numbers, but this leads to problems since VertexAdd[g,list] will add a vertex for every element of the list and not one vertex for the whole list. Is there a direct solution to this, or do I have to do something ugly, like for example convert the list to a string (and then later back, when refering to the vertices)? Note that I don't want to label the vertices, the lists should BE the vertices.

Answer 1

Yes, vertices can be lists, but you should be aware that some functions do not handle such graphs well. Several such problems were fixed recently, so if you want to work with such graphs, I recommend that you use the latest version of Mathematica.

In this case, you can do this:

g = Graph[{}];

g = VertexAdd[g, {{1, 2, 3}}];

VertexList[g]
(* {{1, 2, 3}} *)

Even in the latest version, some functions mishandle graphs which have lists as vertices. Specifically, the notation they use is ambiguous and unlike in the case of VertexAdd, there is no way to disambiguate.

Consider for example this graph:

g = Graph[{1, 2, {1, 2}}, {1 <-> {1, 2}, 2 <-> {1, 2}}, VertexLabels -> Automatic]

You can think of it as the bipartite graph representing the inclusion relations between sets ({1,2}) and some elements (1 and 2).

Now you want to delete vertices 1 and 2. It is not possible with a single VertexDelete because VertexDelete[g, {1,2}] will delete {1,2}, not 1 and 2. Well, I guess you can use the workaround of first deleting 1 and then deleting 2, but that's awfully slow on a large graph.

Subgraph suffers from the same problem.

Overall, if you have an arbitrary graph g and some vertices v1, v2, v3, all of which may be passed by a user to a function you wrote (i.e. you have no control over the vertex names), there is no way to reliably take the subgraph induced by v1, v2, v3. There is no guarantee that Subgraph[g, {v1,v2,v3}] will return that.

I repeat, Mathematica has no way to reliably take a subgraph of a graph. You can't even trust such fundamental operations. That's how well-designed Mathematica's Graph is.

Yes, I reported this to Wolfram Research, not just once, but many times over the years. The oldest report I sent was from January 2018 (Mathematica 11.2 era), but the problem was discussed on this site earlier than that. As is typical, the Graph developers at Wolfram refused to provide any comment, and they also didn't fix this. That's how much they care about creating an actually working system, and that's how much they listen to their users. Don't expect their attitude to change, it's been like this for years.