[Nauty] generating all graphs with several types of undirected and directed relations
Szabolcs Horvát
szhorvat at gmail.com
Mon May 27 22:32:02 AEST 2024
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
More information about the Nauty
mailing list