4
$\begingroup$

I'm not sure if this is a Mathematica problem, math problem or a CS problem, so if this is off-topic please transfer it.

In the package Combinatorica there is a function ListGraphs[n,m] which returns all nonisomorphic undirected graphs with n vertices and m edges. What algorithm does it use? All I can think of is to enumerate all graphs with n vertices and m edges brute-force, and check isomorphism for each graph. But I don't think that's effective. Is there a better algorism for this task? Thanks!

$\endgroup$
6
$\begingroup$

You can find the code for the function in the file Combinatorica.m:

nb = NotebookOpen[ToFileName[{$InstallationDirectory, "AddOns", "Packages", 
            "Combinatorica"}, "Combinatorica.m"]];
NotebookFind[nb, "ListGraphs[n_Integer?Positive, m_Integer]"]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.