PostgreSQL Source Code
git master
Toggle main menu visibility
Main Page
Related Pages
Namespaces
Namespace List
Namespace Members
All
Functions
Variables
Data Structures
Data Structures
Data Structure Index
Class Hierarchy
Data Fields
All
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
~
Functions
_
a
f
h
i
n
o
p
r
s
~
Variables
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Enumerations
Files
File List
Globals
All
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Functions
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Variables
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Typedefs
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Enumerations
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
Enumerator
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
z
Macros
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
•
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Pages
bipartite_match.h
Go to the documentation of this file.
1
/*
2
* bipartite_match.h
3
*
4
* Copyright (c) 2015-2025, PostgreSQL Global Development Group
5
*
6
* src/include/lib/bipartite_match.h
7
*/
8
#ifndef BIPARTITE_MATCH_H
9
#define BIPARTITE_MATCH_H
10
11
/*
12
* Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V
13
* numbered 1..nV, and an adjacency map of undirected edges in the form
14
* adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum
15
* cardinality matching", which is defined as follows: a matching is a subset
16
* of the original edges such that no node has more than one edge, and a
17
* matching has maximum cardinality if there exists no other matching with a
18
* greater number of edges.
19
*
20
* This matching has various applications in graph theory, but the motivating
21
* example here is Dilworth's theorem: a partially-ordered set can be divided
22
* into the minimum number of chains (i.e. subsets X where x1 < x2 < x3 ...) by
23
* a bipartite graph construction. This gives us a polynomial-time solution to
24
* the problem of planning a collection of grouping sets with the provably
25
* minimal number of sort operations.
26
*/
27
typedef
struct
BipartiteMatchState
28
{
29
/* inputs: */
30
int
u_size
;
/* size of U */
31
int
v_size
;
/* size of V */
32
short
**
adjacency
;
/* adjacency[u] = [k, v1,v2,v3,...,vk] */
33
/* outputs: */
34
int
matching
;
/* number of edges in matching */
35
short
*
pair_uv
;
/* pair_uv[u] -> v */
36
short
*
pair_vu
;
/* pair_vu[v] -> u */
37
/* private state for matching algorithm: */
38
short
*
distance
;
/* distance[u] */
39
short
*
queue
;
/* queue storage for breadth search */
40
}
BipartiteMatchState
;
41
42
extern
BipartiteMatchState
*
BipartiteMatch
(
int
u_size,
int
v_size,
short
**adjacency);
43
44
extern
void
BipartiteMatchFree
(
BipartiteMatchState
*
state
);
45
46
#endif
/* BIPARTITE_MATCH_H */
BipartiteMatchState
struct BipartiteMatchState BipartiteMatchState
BipartiteMatch
BipartiteMatchState * BipartiteMatch(int u_size, int v_size, short **adjacency)
Definition:
bipartite_match.c:39
BipartiteMatchFree
void BipartiteMatchFree(BipartiteMatchState *state)
Definition:
bipartite_match.c:78
BipartiteMatchState
Definition:
bipartite_match.h:28
BipartiteMatchState::queue
short * queue
Definition:
bipartite_match.h:39
BipartiteMatchState::u_size
int u_size
Definition:
bipartite_match.h:30
BipartiteMatchState::adjacency
short ** adjacency
Definition:
bipartite_match.h:32
BipartiteMatchState::pair_vu
short * pair_vu
Definition:
bipartite_match.h:36
BipartiteMatchState::v_size
int v_size
Definition:
bipartite_match.h:31
BipartiteMatchState::matching
int matching
Definition:
bipartite_match.h:34
BipartiteMatchState::pair_uv
short * pair_uv
Definition:
bipartite_match.h:35
BipartiteMatchState::distance
short * distance
Definition:
bipartite_match.h:38
state
Definition:
regguts.h:323
src
include
lib
bipartite_match.h
Generated on Tue Jan 7 2025 06:13:24 for PostgreSQL Source Code by
1.9.4