23#ifndef SUBGRAPH_ENUMERATION_H
24#define SUBGRAPH_ENUMERATION_H 1
81#define DEBUGGING_DPHYP 0
85#define HYPERGRAPH_PRINTF printf
87#define HYPERGRAPH_PRINTF(...)
92template <
class Receiver>
96 std::string ret =
"{";
105 snprintf(
buf,
sizeof(
buf),
"R%zu", node_idx + 1);
179 return just_grown_by & ~m_last_just_grown_by;
183 return just_grown_by;
190 assert(
IsSubset(neighborhood, full_neighborhood));
287 NodeMap *full_neighborhood_arg) {
288 assert(
IsSubset(just_grown_by, subgraph));
291 *full_neighborhood_arg;
295 cache->
InitSearch(just_grown_by, &neighborhood, &full_neighborhood);
296 assert(
IsSubset(neighborhood, full_neighborhood));
298 for (
size_t node_idx :
BitsSetIn(to_search)) {
302 neighborhood |= g.
nodes[node_idx].simple_neighborhood;
306 for (
size_t edge_idx : g.
nodes[node_idx].complex_edges) {
312 full_neighborhood |= e.
right;
328 neighborhood &= ~(subgraph | forbidden);
329 full_neighborhood |= neighborhood;
331 cache->
Store(just_grown_by, neighborhood, full_neighborhood);
334 "Neighborhood of %s (calculated on %s) with forbidden %s = %s\n",
338 *full_neighborhood_arg = full_neighborhood;
349template <
class Receiver>
352 NodeMap full_neighborhood,
NodeMap neighborhood, Receiver *receiver) {
358 neighborhood &= ~subgraph;
370 if (
Overlaps(g.
nodes[seed_idx].simple_neighborhood, subgraph)) {
371 for (
size_t edge_idx : g.
nodes[seed_idx].simple_edges) {
373 assert(e.
left == seed);
375 if (receiver->FoundSubgraphPair(subgraph, seed, edge_idx / 2)) {
381 for (
size_t edge_idx : g.
nodes[seed_idx].complex_edges) {
384 if (receiver->FoundSubgraphPair(subgraph, seed, edge_idx / 2)) {
405 forbidden | subgraph | (neighborhood &
TablesBetween(0, seed_idx));
406 NodeMap new_full_neighborhood = 0;
408 &cache, &new_full_neighborhood);
410 new_neighborhood, new_forbidden, receiver)) {
423template <
class Receiver>
427 Receiver *receiver) {
429 "Expanding connected subgraph, subgraph=%s neighborhood=%s "
440 "Trying to grow-and-complement %s by %s (out of %s) [connected=%d]\n",
442 PrintSet(neighborhood).c_str(), receiver->HasSeen(subgraph | grow_by));
447 NodeMap grown_subgraph = subgraph | grow_by;
448 if (receiver->HasSeen(grown_subgraph)) {
450 NodeMap new_full_neighborhood = full_neighborhood;
453 &new_full_neighborhood);
466 new_neighborhood |= forbidden & ~TablesBetween(0, lowest_node_idx);
471 new_neighborhood |= neighborhood;
474 new_full_neighborhood, new_neighborhood,
492 NodeMap grown_subgraph = subgraph | grow_by;
497 NodeMap new_forbidden = (forbidden | neighborhood) & ~grown_subgraph;
498 assert(!
IsSubset(grown_subgraph, new_forbidden));
501 NodeMap new_full_neighborhood = full_neighborhood;
504 &new_full_neighborhood);
507 new_full_neighborhood, new_neighborhood, new_forbidden,
530template <
class Receiver>
532 NodeMap subgraph_full_neighborhood,
533 NodeMap complement, Receiver *receiver) {
534 for (
size_t node_idx :
BitsSetIn(complement & subgraph_full_neighborhood)) {
536 if (
Overlaps(g.
nodes[node_idx].simple_neighborhood, subgraph)) {
537 for (
size_t edge_idx : g.
nodes[node_idx].simple_edges) {
542 if (receiver->FoundSubgraphPair(subgraph, complement, edge_idx / 2)) {
551 for (
size_t edge_idx : g.
nodes[node_idx].complex_edges) {
557 if (receiver->FoundSubgraphPair(subgraph, complement, edge_idx / 2)) {
579template <
class Receiver>
582 NodeMap subgraph_full_neighborhood,
584 NodeMap forbidden, Receiver *receiver) {
585 assert(
IsSubset(subgraph, forbidden));
586 assert(!
IsSubset(complement, forbidden));
589 "Trying to expand complement %s (subgraph is %s, forbidden is %s)\n",
603 NodeMap grown_complement = complement | grow_by;
604 if (receiver->HasSeen(grown_complement)) {
606 grown_complement, receiver)) {
625 NodeMap grown_complement = complement | grow_by;
630 NodeMap new_forbidden = (forbidden | neighborhood) & ~grown_complement;
631 assert(!
IsSubset(grown_complement, new_forbidden));
634 NodeMap new_full_neighborhood = 0;
637 &cache, &new_full_neighborhood);
640 subgraph_full_neighborhood, grown_complement,
641 new_neighborhood, new_forbidden, receiver)) {
665template <
class Receiver>
667 for (
int seed_idx = g.
nodes.size() - 1; seed_idx >= 0; --seed_idx) {
668 if (receiver->FoundSingleNode(seed_idx)) {
681 neighborhood, receiver)) {
684 if (
ExpandSubgraph(g, seed_idx, seed, full_neighborhood, neighborhood,
685 forbidden | seed, receiver)) {
uint64_t TablesBetween(unsigned start, unsigned end)
Definition: bit_utils.h:208
BitIteratorAdaptor< CountBitsDescending > BitsSetInDescending(uint64_t state)
Definition: bit_utils.h:133
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:222
uint64_t IsolateLowestBit(uint64_t x)
Definition: bit_utils.h:218
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:230
uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:185
BitIteratorAdaptor< CountBitsAscending > BitsSetIn(uint64_t state)
Definition: bit_utils.h:130
Definition: bit_utils.h:146
Definition: subgraph_enumeration.h:162
NodeMap m_last_just_grown_by
Definition: subgraph_enumeration.h:200
NodeMap m_last_neighborhood
Definition: subgraph_enumeration.h:203
const NodeMap m_taboo_bit
Definition: subgraph_enumeration.h:199
NeighborhoodCache(NodeMap neighborhood)
Definition: subgraph_enumeration.h:164
NodeMap InitSearch(NodeMap just_grown_by, NodeMap *neighborhood, NodeMap *full_neighborhood)
Definition: subgraph_enumeration.h:172
NodeMap m_last_full_neighborhood
Definition: subgraph_enumeration.h:202
void Store(NodeMap just_grown_by, NodeMap neighborhood, NodeMap full_neighborhood)
Definition: subgraph_enumeration.h:188
Definition of an undirected (join) hypergraph.
Definition: buf0block_hint.cc:29
Definition: hypergraph.cc:29
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:284
std::string PrintSet(NodeMap x)
Definition: subgraph_enumeration.h:95
bool EnumerateComplementsTo(const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap full_neighborhood, NodeMap neighborhood, Receiver *receiver)
Definition: subgraph_enumeration.h:350
bool EnumerateAllConnectedPartitions(Receiver *receiver)
bool TryConnecting(const Hypergraph &g, NodeMap subgraph, NodeMap subgraph_full_neighborhood, NodeMap complement, Receiver *receiver)
Definition: subgraph_enumeration.h:531
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:580
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:39
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:424
Definition: hypergraph.h:79
NodeMap left
Definition: hypergraph.h:84
NodeMap right
Definition: hypergraph.h:85
Definition: hypergraph.h:88
Mem_root_array< Node > nodes
Definition: hypergraph.h:91
Mem_root_array< Hyperedge > edges
Definition: hypergraph.h:92
#define HYPERGRAPH_PRINTF(...)
Definition: subgraph_enumeration.h:87