[Nauty] generating all graphs with several types of undirected and directed relations

[Szabolcs Horvát]

Hello everyone,

I am looking to enumerate all non-isomorphic "graphs" in which all
vertex pairs have a relation, which can be of three non-directional
types, or unidirectional. Thus, A and B can have these relations:

A --1-- B
A --2-- B
A --3-- B
A ----> B
A <---- B

Does gtools have any facilities to do this?

Previously I was working with only two non-directional relations
instead of three, which made it easy to encode the problem into a
simple directed graph: between A and B we can have no edges, two
reciprocal edges (these are the two non-directional relations), or a
unidirectional edge in either direction (four cases in total). The
addition of an extra non-directional relation seems to complicate
things tremendously.

The usual recommendation to handle isomorphism checks with edge
colours/types is to encode the colours as various sorts of
subdivisions of edges. I don't think that's feasible here since I
don't just want to check isomorphism between two graphs, but generate
all such structures on a few vertices (hopefully at least 2 to 5). It
is difficult to generate graphs which are "decodable" from such a
representation. geng/directg can't do it as far as I can see.

To make the situation more complicated, I also need to handle
2-colouring of vertices.

Any advice on this topic would be much appreciated.

Best regards,
Szabolcs Horvát