diff options
Diffstat (limited to 'apps/plugins/puzzles/src/matching.h')
-rw-r--r-- | apps/plugins/puzzles/src/matching.h | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/matching.h b/apps/plugins/puzzles/src/matching.h index a4d3098efa..dbf424d044 100644 --- a/apps/plugins/puzzles/src/matching.h +++ b/apps/plugins/puzzles/src/matching.h | |||
@@ -77,4 +77,32 @@ size_t matching_scratch_size(int nl, int nr); | |||
77 | int matching(int nl, int nr, int **adjlists, int *adjsizes, | 77 | int matching(int nl, int nr, int **adjlists, int *adjsizes, |
78 | random_state *rs, int *outl, int *outr); | 78 | random_state *rs, int *outl, int *outr); |
79 | 79 | ||
80 | /* | ||
81 | * Diagnostic routine used in testing this algorithm. It is passed a | ||
82 | * pointer to a piece of scratch space that's just been used by | ||
83 | * matching_with_scratch, and extracts from it a labelling of the | ||
84 | * input graph that acts as a 'witness' to the maximality of the | ||
85 | * returned matching. | ||
86 | * | ||
87 | * The output parameter 'witness' should be an array of (nl+nr) | ||
88 | * integers, indexed such that witness[L] corresponds to an L-vertex (for | ||
89 | * L=0,1,...,nl-1) and witness[nl+R] corresponds to an R-vertex (for | ||
90 | * R=0,1,...,nr-1). On return, this array will assign each vertex a | ||
91 | * label which is either 0 or 1, and the following properties will | ||
92 | * hold: | ||
93 | * | ||
94 | * + all vertices not paired up by the matching are type L0 or R1 | ||
95 | * + every L0->R1 edge is used by the matching | ||
96 | * + no L1->R0 edge is used by the matching. | ||
97 | * | ||
98 | * The mere existence of such a labelling is enough to prove the | ||
99 | * maximality of the matching, because if there is any larger matching | ||
100 | * then its symmetric difference with this one must include at least | ||
101 | * one 'augmenting path', which starts at a free L-vertex and ends at | ||
102 | * a free R-vertex, traversing only unused L->R edges and only used | ||
103 | * R->L edges. But that would mean it starts at an L0, ends at an R1, | ||
104 | * and never follows an edge that can get from an 0 to a 1. | ||
105 | */ | ||
106 | void matching_witness(void *scratch, int nl, int nr, int *witness); | ||
107 | |||
80 | #endif /* MATCHING_MATCHING_H */ | 108 | #endif /* MATCHING_MATCHING_H */ |