24#ifndef SUBGRAPH_ENUMERATION_H
25#define SUBGRAPH_ENUMERATION_H 1
82#define DEBUGGING_DPHYP 0
86#define HYPERGRAPH_PRINTF printf
88#define HYPERGRAPH_PRINTF(...)
93template <
class Receiver>
97 std::string ret =
"{";
106 snprintf(
buf,
sizeof(
buf),
"R%zu", node_idx + 1);
180 return just_grown_by & ~m_last_just_grown_by;
184 return just_grown_by;
191 assert(
IsSubset(neighborhood, full_neighborhood));
288 NodeMap *full_neighborhood_arg) {
289 assert(
IsSubset(just_grown_by, subgraph));
292 *full_neighborhood_arg;
296 cache->
InitSearch(just_grown_by, &neighborhood, &full_neighborhood);
297 assert(
IsSubset(neighborhood, full_neighborhood));
299 for (
size_t node_idx :
BitsSetIn(to_search)) {
303 neighborhood |= g.
nodes[node_idx].simple_neighborhood;
307 for (
size_t edge_idx : g.
nodes[node_idx].complex_edges) {
313 full_neighborhood |= e.
right;
329 neighborhood &= ~(subgraph | forbidden);
330 full_neighborhood |= neighborhood;
332 cache->
Store(just_grown_by, neighborhood, full_neighborhood);
335 "Neighborhood of %s (calculated on %s) with forbidden %s = %s\n",
339 *full_neighborhood_arg = full_neighborhood;
350template <
class Receiver>
353 NodeMap full_neighborhood,
NodeMap neighborhood, Receiver *receiver) {
359 neighborhood &= ~subgraph;
371 if (
Overlaps(g.
nodes[seed_idx].simple_neighborhood, subgraph)) {
372 for (
size_t edge_idx : g.
nodes[seed_idx].simple_edges) {
374 assert(e.
left == seed);
376 if (receiver->FoundSubgraphPair(subgraph, seed, edge_idx / 2)) {
382 for (
size_t edge_idx : g.
nodes[seed_idx].complex_edges) {
385 if (receiver->FoundSubgraphPair(subgraph, seed, edge_idx / 2)) {
406 forbidden | subgraph | (neighborhood &
TablesBetween(0, seed_idx));
407 NodeMap new_full_neighborhood = 0;
409 &cache, &new_full_neighborhood);
411 new_neighborhood, new_forbidden, receiver)) {
424template <
class Receiver>
428 Receiver *receiver) {
430 "Expanding connected subgraph, subgraph=%s neighborhood=%s "
441 "Trying to grow-and-complement %s by %s (out of %s) [connected=%d]\n",
443 PrintSet(neighborhood).c_str(), receiver->HasSeen(subgraph | grow_by));
448 NodeMap grown_subgraph = subgraph | grow_by;
449 if (receiver->HasSeen(grown_subgraph)) {
451 NodeMap new_full_neighborhood = full_neighborhood;
454 &new_full_neighborhood);
467 new_neighborhood |= forbidden & ~TablesBetween(0, lowest_node_idx);
472 new_neighborhood |= neighborhood;
475 new_full_neighborhood, new_neighborhood,
493 NodeMap grown_subgraph = subgraph | grow_by;
498 NodeMap new_forbidden = (forbidden | neighborhood) & ~grown_subgraph;
499 assert(!
IsSubset(grown_subgraph, new_forbidden));
502 NodeMap new_full_neighborhood = full_neighborhood;
505 &new_full_neighborhood);
508 new_full_neighborhood, new_neighborhood, new_forbidden,
531template <
class Receiver>
533 NodeMap subgraph_full_neighborhood,
534 NodeMap complement, Receiver *receiver) {
535 for (
size_t node_idx :
BitsSetIn(complement & subgraph_full_neighborhood)) {
537 if (
Overlaps(g.
nodes[node_idx].simple_neighborhood, subgraph)) {
538 for (
size_t edge_idx : g.
nodes[node_idx].simple_edges) {
543 if (receiver->FoundSubgraphPair(subgraph, complement, edge_idx / 2)) {
552 for (
size_t edge_idx : g.
nodes[node_idx].complex_edges) {
558 if (receiver->FoundSubgraphPair(subgraph, complement, edge_idx / 2)) {
580template <
class Receiver>
583 NodeMap subgraph_full_neighborhood,
585 NodeMap forbidden, Receiver *receiver) {
586 assert(
IsSubset(subgraph, forbidden));
587 assert(!
IsSubset(complement, forbidden));
590 "Trying to expand complement %s (subgraph is %s, forbidden is %s)\n",
604 NodeMap grown_complement = complement | grow_by;
605 if (receiver->HasSeen(grown_complement)) {
607 grown_complement, receiver)) {
626 NodeMap grown_complement = complement | grow_by;
631 NodeMap new_forbidden = (forbidden | neighborhood) & ~grown_complement;
632 assert(!
IsSubset(grown_complement, new_forbidden));
635 NodeMap new_full_neighborhood = 0;
638 &cache, &new_full_neighborhood);
641 subgraph_full_neighborhood, grown_complement,
642 new_neighborhood, new_forbidden, receiver)) {
666template <
class Receiver>
668 for (
int seed_idx = g.
nodes.size() - 1; seed_idx >= 0; --seed_idx) {
669 if (receiver->FoundSingleNode(seed_idx)) {
682 neighborhood, receiver)) {
685 if (
ExpandSubgraph(g, seed_idx, seed, full_neighborhood, neighborhood,
686 forbidden | seed, receiver)) {
uint64_t TablesBetween(unsigned start, unsigned end)
Definition: bit_utils.h:207
BitIteratorAdaptor< CountBitsDescending > BitsSetInDescending(uint64_t state)
Definition: bit_utils.h:126
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:221
constexpr uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:178
uint64_t IsolateLowestBit(uint64_t x)
Definition: bit_utils.h:217
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:229
BitIteratorAdaptor< CountBitsAscending > BitsSetIn(uint64_t state)
Definition: bit_utils.h:123
Definition: bit_utils.h:139
Definition: subgraph_enumeration.h:163
NodeMap m_last_just_grown_by
Definition: subgraph_enumeration.h:201
NodeMap m_last_neighborhood
Definition: subgraph_enumeration.h:204
const NodeMap m_taboo_bit
Definition: subgraph_enumeration.h:200
NeighborhoodCache(NodeMap neighborhood)
Definition: subgraph_enumeration.h:165
NodeMap InitSearch(NodeMap just_grown_by, NodeMap *neighborhood, NodeMap *full_neighborhood)
Definition: subgraph_enumeration.h:173
NodeMap m_last_full_neighborhood
Definition: subgraph_enumeration.h:203
void Store(NodeMap just_grown_by, NodeMap neighborhood, NodeMap full_neighborhood)
Definition: subgraph_enumeration.h:189
static char buf[MAX_BUF]
Definition: conf_to_src.cc:73
Definition of an undirected (join) hypergraph.
Definition: buf0block_hint.cc:30
Definition: hypergraph.cc:30
NodeMap FindNeighborhood(const Hypergraph &g, NodeMap subgraph, NodeMap forbidden, NodeMap just_grown_by, NeighborhoodCache *cache, NodeMap *full_neighborhood_arg)
Find the neighborhood of the given subgraph (S); informally, the set of nodes immediately reachable f...
Definition: subgraph_enumeration.h:285
std::string PrintSet(NodeMap x)
Definition: subgraph_enumeration.h:96
bool EnumerateComplementsTo(const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap full_neighborhood, NodeMap neighborhood, Receiver *receiver)
Definition: subgraph_enumeration.h:351
bool EnumerateAllConnectedPartitions(Receiver *receiver)
bool TryConnecting(const Hypergraph &g, NodeMap subgraph, NodeMap subgraph_full_neighborhood, NodeMap complement, Receiver *receiver)
Definition: subgraph_enumeration.h:532
bool ExpandComplement(const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap subgraph_full_neighborhood, NodeMap complement, NodeMap neighborhood, NodeMap forbidden, Receiver *receiver)
Definition: subgraph_enumeration.h:581
uint64_t NodeMap
Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 6...
Definition: node_map.h:40
bool ExpandSubgraph(const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap full_neighborhood, NodeMap neighborhood, NodeMap forbidden, Receiver *receiver)
Definition: subgraph_enumeration.h:425
Definition: hypergraph.h:81
NodeMap left
Definition: hypergraph.h:86
NodeMap right
Definition: hypergraph.h:87
Definition: hypergraph.h:90
Mem_root_array< Node > nodes
Definition: hypergraph.h:93
Mem_root_array< Hyperedge > edges
Definition: hypergraph.h:94
#define HYPERGRAPH_PRINTF(...)
Definition: subgraph_enumeration.h:88