[Nauty] Efficient Filtering of Graphs Based on Matching-Number Constraints

[lczhangmath]

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;
}

-------------- next part --------------
A non-text attachment was scrubbed...
Name: nautyboost_matching.cpp
Type: text/x-c
Size: 3287 bytes
Desc: not available
URL: <https://mailman.anu.edu.au/pipermail/nauty/attachments/20251123/43c6daab/attachment.bin>