[Nauty] Efficient Filtering of Graphs Based on Matching-Number Constraints
Brendan McKay
Brendan.McKay at anu.edu.au
Mon Nov 24 20:01:24 AEDT 2025
Hi Dima,
Both of those can be done already. See Section 19 of the manual for
inserting a filter into geng.
Also, if geng.c is compiled with -DGENG_MAIN=something then it
becomes a callable function with name 'something'. There is an example
callgeng2 in the package that calls geng in multiple threads. Here are
the 11-vertex graphs in 6 threads on a 6-core cpu:
% callgeng2 -N6 -u 11
>Z 1018997864 graphs made in 208.52 cpu-seconds, 37.21 seconds real time.
This compares to 185 seconds for one thread.
Brendan.
On 24/11/2025 6:26 pm, Dima Pasechnik via Nauty wrote:
> On Mon, Nov 24, 2025 at 02:25:54PM +1100, Brendan McKay via Nauty wrote:
>> As Matthew wrote, it is unlikely that the conversion time is large
>> compared to finding the maximum matching, unless you are dealing with
>> very small graphs. There is also the cost of the i/o, which is likely to
>> be greater than the conversion cost.
>>
>> There is one thing you can do quickly. When readg() reads the graph6
>> input, it keeps the input string in addition to converting it to the graph
>> format. If you want to just write the most recently read graph in the
>> same format, you can do "writelast(stdout)" instead of
>> "writeg6(stdout,ng,m,n)". Then the output will be identical to the input.
>>
>> A second option, this time requiring work, is to avoid the double
>> conversion graph6->graph->BGL by writing code that converts directly
>> from the input string to BGL format. Graph6 strings are just text lines
>> in the input file so you can read them using getline(), or fgets() if
>> you are happy with a size limit. Then you can write the graphs passing
>> the test using fputs() or the corresponding C++ function.
> I was thinking along the lines of writing a geng filter which calls a
> function to compute the size of a maximum matching.
>
> Or refactor geng so that it can be called used as a callable library.
>
> Just in case,
> Dima
>
>> Brendan.
>>
>> On 24/11/2025 2:24 am, lczhangmath via Nauty wrote:
>>> Dear community,
>>>
>>> I once asked whether nauty provides an option for filtering graphs by their number of matchings. As far as I can tell, such a feature does not currently exist, so I have been trying to implement it myself using Boost. My approach is to read graphs in graph6 format and then compute the number of matchings.
>>>
>>> However, this approach also has a drawback: I first use readg to read the graph6 strings from the data stream, and in the end I output them again using writeg6 in the required format. This means that I am spending time both decoding and re-encoding graph6, which feels somewhat wasteful. What I would like to ask is whether there is a more efficient way to handle this.
>>>
>>>
>>>
>>> Best wishes
>>> Licheng
>>>
>>>
>>>
>>>
>>> PS:
>>> /* ------------------------------------------------------------
>>> C++ program:
>>> - Read graphs in graph6 format using nauty's readg()
>>> - Convert each graph into a Boost adjacency_list
>>> - Compute maximum matching using Boost
>>> - Filtering options:
>>> --eq k (matching number == k)
>>> --le k (matching number <= k)
>>> --ge k (matching number >= k)
>>> - Output:
>>> Only graph6 strings for graphs that pass the filter
>>> - Summary of counts printed to stderr
>>>
>>>
>>> Compile:
>>> g++ nauty_bgl.cpp -I. -L. -lnauty -lboost_graph -o nauty_bgl
>>> ------------------------------------------------------------ */
>>>
>>>
>>> extern"C" {
>>> #include"nauty.h"
>>> #include"gtools.h"
>>> }
>>>
>>>
>>> #include<boost/graph/adjacency_list.hpp>
>>> #include<boost/graph/max_cardinality_matching.hpp>
>>> #include<iostream>
>>> #include<vector>
>>> #include<string>
>>> #include<cstdlib>
>>>
>>>
>>> /* --------------------- Command-line filter options ----------------------- */
>>>
>>>
>>> enumFilterType { NONE, EQ, LE, GE };
>>> FilterTypefilter_type = NONE;
>>> intfilter_k = -1;
>>>
>>>
>>> /* Parse filtering options */
>>> voidparse_args(intargc, char**argv)
>>> {
>>> if (argc == 3)
>>> {
>>> std::stringopt = argv[1];
>>> filter_k = std::atoi(argv[2]);
>>>
>>>
>>> if (opt=="--eq") filter_type = EQ;
>>> elseif (opt=="--le") filter_type = LE;
>>> elseif (opt=="--ge") filter_type = GE;
>>> }
>>> }
>>>
>>>
>>> /* ---------------- Convert nauty graph to BGL adjacency_list --------------- */
>>>
>>>
>>> template<typenameG>
>>> voidnauty_to_bgl(graph*ng, intn, intm, G&g)
>>> {
>>> for (intv = 0; v < n; ++v) {
>>> set *row = GRAPHROW(ng, v, m);
>>> for (intu = v + 1; u < n; ++u)
>>> if (ISELEMENT(row, u))
>>> add_edge(v, u, g);
>>> }
>>> }
>>>
>>>
>>> /* -------------------------------- Main ----------------------------------- */
>>>
>>>
>>> intmain(intargc, char**argv)
>>> {
>>> parse_args(argc, argv);
>>>
>>>
>>> graph *ng;
>>> intn, m;
>>>
>>>
>>> typedefboost::adjacency_list<boost::vecS, boost::vecS,
>>> boost::undirectedS> BGLGraph;
>>>
>>>
>>> longlongtotal = 0; // graphs read
>>> longlongkept = 0; // graphs passing the filter
>>>
>>>
>>> while ((ng = readg(stdin, NULL, 0, &m, &n)) != NULL)
>>> {
>>> total++;
>>>
>>>
>>> /* Build a BGL graph */
>>> BGLGraph g(n);
>>> nauty_to_bgl(ng, n, m, g);
>>>
>>>
>>> /* Compute maximum matching */
>>> std::vector<boost::graph_traits<BGLGraph>::vertex_descriptor> mate(n);
>>> boost::edmonds_maximum_cardinality_matching(g, &mate[0]);
>>> intmatching_size = boost::matching_size(g, &mate[0]);
>>>
>>>
>>> /* Apply filter */
>>> boolkeep = true;
>>> if (filter_type == EQ) keep = (matching_size == filter_k);
>>> elseif (filter_type == LE) keep = (matching_size <= filter_k);
>>> elseif (filter_type == GE) keep = (matching_size >= filter_k);
>>>
>>>
>>> if (!keep) {
>>> FREES(ng);
>>> continue;
>>> }
>>>
>>>
>>> kept++;
>>>
>>>
>>> /* Only output the graph6 string */
>>> writeg6(stdout, ng, m, n);
>>>
>>>
>>> FREES(ng);
>>> }
>>>
>>>
>>> /* Print summary to stderr */
>>> std::cerr<<"Total graphs read: "<<total<<"\n";
>>> std::cerr<<"Graphs passed filter: "<<kept<<"\n";
>>>
>>>
>>> return0;
>>> }
>>>
>>>
>>> _______________________________________________
>>> Nauty mailing list
>>> Nauty at anu.edu.au
>>> https://mailman.anu.edu.au/mailman/listinfo/nauty
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> https://mailman.anu.edu.au/mailman/listinfo/nauty
>>
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> https://mailman.anu.edu.au/mailman/listinfo/nauty
More information about the Nauty
mailing list