[Nauty] Efficient Filtering of Graphs Based on Matching-Number Constraints
Dima Pasechnik
dima at pasechnik.info
Mon Nov 24 18:26:44 AEDT 2025
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 525 bytes
Desc: not available
URL: <https://mailman.anu.edu.au/pipermail/nauty/attachments/20251124/a0ee62a4/attachment-0001.sig>
More information about the Nauty
mailing list