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

[Brendan McKay]

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.

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