Ask Your Question

Adapt the nauty_directg function

asked 2019-10-11 13:01:38 +0100

PepijnWissing gravatar image

Dear reader,

For a research interest, I would like to generate the collection of non-isomorphic digraphs on a given graph, with a given subset of the edges fixed. Naturally, simply generating the full collection using digraphs.nauty_directg() and removing the undesirable members of the obtained collection would be functional, but it's quite the waste of computing time to take this approach. Hence, I was wondering whether I'd be able to get under the hood of the nauty_directg function to create my own adapted version, which simply skips over the orientation of the edges listed in some input argument. Would anyone be able to help me get started with this endeavor?

Best, Pepijn

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2019-10-11 16:04:06 +0100

rburing gravatar image

Entering digraphs.nauty_directg?? into a SageMath session will show you the source code of the function.

In this case it simply calls an external program directg which is part of nauty.

You can download and edit that program's source code, compile your new version, and call that one instead.

To edit the source code you should start by looking at the file directg.c. Good luck!

edit flag offensive delete link more

answered 2019-10-11 19:03:23 +0100

tmonteil gravatar image

You can have a look at:

sage: digraphs?

and read starting from ORDERLY GENERATION section. Indeed, digraphs is also a function that can generate isomorphism classes of digraphs with some property, as long as that property is stable with respect to vertex or edge deletion. Perhaps you could tune a property corresponding to your problem (which is not clear from your description).

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-10-11 13:01:38 +0100

Seen: 228 times

Last updated: Oct 11 '19