Implement https://stackoverflow.com/questions/67619958

subs.cpp

#include <fstream>
#include <vector>
#include <set>

#include "cPathFinder.h"

// this is a C++ wrapper for boost graph
// https://github.com/JamesBremner/PathFinder

cPathFinder finder;

typedef std::pair< std::vector<int>, int > testedSubGraph_t;

std::vector< testedSubGraph_t > vTests;

testedSubGraph_t best;

bool isConnected(std::vector<int> &sg)
{
    // construct subgraph
    cPathFinder subfinder;

    // loop over node pairs in subgraph
    for (int ku = 0; ku < sg.size(); ku++)
        for (int kv = ku + 1; kv < sg.size(); kv++)
        {
            if (finder.IsAdjacent(
                    sg[ku], sg[kv]))
            {
                // node pair are linked
                subfinder.addLink( ku, kv, 1 );
            }
        }

    return( subfinder.IsConnected() );
}

int countNeighbourColors(std::vector<int> &sg)
{
    std::set<std::string> colors;

    // loop over nodes in subgraph
    for (int ku = 0; ku < sg.size(); ku++)
    {
        // loop over nodes in original graph
        for (int kv = 0; kv < finder.nodeCount(); kv++)
        {
            // node in subgraph, so not a neighbour
            if (std::find(sg.begin(), sg.end(), kv) != sg.end())
                continue;

            // node not connected, so not neighbour to this subgraph node
            if (!finder.IsAdjacent(
                    sg[ku], kv))
                continue;

            // found a subgraph neighbour
            // save its colour if not already seen
            colors.insert(finder.nodeColor(kv));
        }
    }
    // return number of uniquely colored neighbours
    return colors.size();
}

void subgraphTest(std::vector<int> &sg)
{
    // is subgraph nodes all connected?
    if (!isConnected( sg ))
        return;

    // count uniquely colored neighbours
    int colors = countNeighbourColors( sg );

    testedSubGraph_t tsg;
    tsg.first = sg;
    tsg.second = colors;
    vTests.push_back( tsg );

    // save best subgraph found so far
    if (colors < best.second )
    {
        best.second = colors;
        best.first = sg;
    }
}

/** Subgraph builder and tester ( recursive )
 * @param[in] sg subgraph built so far
 * @param[in] M subgraph size required
 * @param[in] start first unchecked node to be added
 * 
 * If the subgraph is completed and has the fewest uniquely colored neightbours
 * store in bestSubgraph global and continue searching
 */
void subgraph(std::vector<int> &sg, int M, int start)
{
    //loop over remaining nodes
    for (int n = start; n < finder.nodeCount(); n++)
    {
        // add node to subgraph
        std::vector<int> msg(sg);
        msg.push_back(n);

        if ( msg.size() == M )
        {
            //subgraph has reached required size
            // test it
             subgraphTest( msg );
        }
        else
        {
            // subgraph needs more nodes
            // ( recursive call until there are the reuired number )
            subgraph(msg, M, n + 1);
        }

    }
    return;
}
main()
{
    best.second = 99999;
    int M = 4; // subgraph size

    // read input file
    finder.read("dat.txt");

    // std::ofstream f("g.dot");
    // f << finder.pathViz();

    // recursive search through subgraphs
    std::vector<int> sg;
    subgraph(sg, M, 0);

    // display best result
    std::cout << "\nsubgraph ";
    for (int n : best.first)
        std::cout << finder.nodeName(n) << ", ";
    std::cout << "  has " << best.second << " differently colored neighbours\n";

    // display all results
    for( auto& t : vTests )
    {
        for( int n : t.first )
            std::cout << finder.nodeName(n) << " ";
        std::cout << "  colors " << t.second << "\n";
    }
}