Server IP : 85.214.239.14 / Your IP : 3.144.98.43 Web Server : Apache/2.4.62 (Debian) System : Linux h2886529.stratoserver.net 4.9.0 #1 SMP Tue Jan 9 19:45:01 MSK 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.18 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, MySQL : OFF | cURL : OFF | WGET : ON | Perl : ON | Python : ON | Sudo : ON | Pkexec : OFF Directory : /usr/include/postgresql/9.6/server/lib/ |
Upload File : |
/* * bipartite_match.h * * Copyright (c) 2015-2016, PostgreSQL Global Development Group * * src/include/lib/bipartite_match.h */ #ifndef BIPARTITE_MATCH_H #define BIPARTITE_MATCH_H /* * Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V * numbered 1..nV, and an adjacency map of undirected edges in the form * adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum * cardinality matching", which is defined as follows: a matching is a subset * of the original edges such that no node has more than one edge, and a * matching has maximum cardinality if there exists no other matching with a * greater number of edges. * * This matching has various applications in graph theory, but the motivating * example here is Dilworth's theorem: a partially-ordered set can be divided * into the minimum number of chains (i.e. subsets X where x1 < x2 < x3 ...) by * a bipartite graph construction. This gives us a polynomial-time solution to * the problem of planning a collection of grouping sets with the provably * minimal number of sort operations. */ typedef struct BipartiteMatchState { /* inputs: */ int u_size; /* size of U */ int v_size; /* size of V */ short **adjacency; /* adjacency[u] = [k, v1,v2,v3,...,vk] */ /* outputs: */ int matching; /* number of edges in matching */ short *pair_uv; /* pair_uv[u] -> v */ short *pair_vu; /* pair_vu[v] -> u */ /* private state for matching algorithm: */ short *distance; /* distance[u] */ short *queue; /* queue storage for breadth search */ } BipartiteMatchState; extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency); extern void BipartiteMatchFree(BipartiteMatchState *state); #endif /* BIPARTITE_MATCH_H */