Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit38f712d

Browse files
knizhnikkelvich
authored andcommitted
Add Bron–Kerbosch algorithm to find maximum clique in graph
1 parent8b256c1 commit38f712d

File tree

9 files changed

+166
-89
lines changed

9 files changed

+166
-89
lines changed

‎Makefile‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
MODULE_big = multimaster
2-
OBJS = multimaster.o arbiter.o bytebuf.o bgwpool.o pglogical_output.o pglogical_proto.o pglogical_receiver.o pglogical_apply.o pglogical_hooks.o pglogical_config.o
2+
OBJS = multimaster.o arbiter.o bytebuf.o bgwpool.o pglogical_output.o pglogical_proto.o pglogical_receiver.o pglogical_apply.o pglogical_hooks.o pglogical_config.o ddd.o bkb.o
33

44
EXTENSION = multimaster
55
DATA = multimaster--1.0.sql

‎arbiter.c‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -81,7 +81,7 @@ typedef struct
8181
MtmMessageCodecode;/* Message code: MSG_READY, MSG_PREPARE, MSG_COMMIT, MSG_ABORT */
8282
intnode;/* Sender node ID */
8383
TransactionIddxid;/* Transaction ID at destination node */
84-
TransactionIdsxid;/* TransactionIO at sender node */
84+
TransactionIdsxid;/* TransactionID at sender node */
8585
csn_tcsn;/* local CSN in case of sending data from replica to master, global CSN master->replica */
8686
nodemask_tdisabledNodeMask;/* bitmask of disabled nodes at the sender of message */
8787
}MtmArbiterMessage;
@@ -353,9 +353,11 @@ static void MtmOpenConnections()
353353

354354
staticboolMtmSendToNode(intnode,voidconst*buf,intsize)
355355
{
356-
while (!MtmWriteSocket(sockets[node],buf,size)) {
356+
while (sockets[node]<0||!MtmWriteSocket(sockets[node],buf,size)) {
357357
elog(WARNING,"Arbiter failed to write socket: %d",errno);
358-
close(sockets[node]);
358+
if (sockets[node] >=0) {
359+
close(sockets[node]);
360+
}
359361
sockets[node]=MtmConnectSocket(hosts[node],MtmArbiterPort+node+1,MtmReconnectAttempts);
360362
if (sockets[node]<0) {
361363
MtmOnLostConnection(node+1);
@@ -400,6 +402,8 @@ static void MtmAcceptOneConnection()
400402
close(fd);
401403
}else {
402404
elog(NOTICE,"Arbiter established connection with node %d",msg.node);
405+
BIT_CLEAR(ds->connectivityMask,msg.node-1);
406+
MtmOnConnectNode(msg.node);
403407
MtmRegisterSocket(fd,msg.node-1);
404408
sockets[msg.node-1]=fd;
405409
}

‎bkb.c‎

Lines changed: 30 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,22 @@
1+
#include"postgres.h"
2+
#include"bkb.h"
3+
14
/*
2-
* Bron–Kerbosch algorithm to find maximumclque in graph
5+
* Bron–Kerbosch algorithm to find maximumclique in graph
36
*/
47

58
typedefstruct {
69
intsize;
710
intnodes[MAX_NODES];
8-
}List;
11+
}NodeList;
912

10-
staticvoidlist_append(List*list,intn)
13+
staticvoidlist_append(NodeList*list,intn)
1114
{
12-
nodes[list->size++]=n;
15+
Assert(list->size<MAX_NODES);
16+
list->nodes[list->size++]=n;
1317
}
1418

15-
staticvoidlist_copy(List*dst,List*src)
19+
staticvoidlist_copy(NodeList*dst,NodeListconst*src)
1620
{
1721
inti;
1822
intn=src->size;
@@ -23,13 +27,15 @@ static void list_copy(List* dst, List* src)
2327
}
2428

2529

26-
staticvoidfindMaximumIndependentSet(List*cur,List*result,nodemask_t*graph,int*oldSet,intne,intce)
30+
staticvoidfindMaximumIndependentSet(NodeList*cur,NodeList*result,nodemask_t*graph,int*oldSet,intne,intce)
2731
{
2832
intnod=0;
2933
intminnod=ce;
3034
intfixp=-1;
3135
ints=-1;
32-
inti,j;
36+
inti,j,k;
37+
intnewce,newne;
38+
intsel;
3339
intnewSet[MAX_NODES];
3440

3541
for (i=0;i<ce&&minnod!=0;i++) {
@@ -39,8 +45,9 @@ static void findMaximumIndependentSet(List* cur, List* result, nodemask_t* graph
3945

4046
for (j=ne;j<ce;j++) {
4147
if (!BIT_CHECK(graph[p],oldSet[j])) {
42-
if (++cnt==minnod)
48+
if (++cnt==minnod) {
4349
break;
50+
}
4451
pos=j;
4552
}
4653
}
@@ -57,19 +64,19 @@ static void findMaximumIndependentSet(List* cur, List* result, nodemask_t* graph
5764
}
5865

5966

60-
for (intk=minnod+nod;k >=1;k--) {
61-
intsel=oldSet[s];
67+
for (k=minnod+nod;k >=1;k--) {
68+
sel=oldSet[s];
6269
oldSet[s]=oldSet[ne];
6370
oldSet[ne]=sel;
6471

65-
intnewne=0;
66-
for (inti=0;i<ne;i++) {
72+
newne=0;
73+
for (i=0;i<ne;i++) {
6774
if (BIT_CHECK(graph[sel],oldSet[i])) {
6875
newSet[newne++]=oldSet[i];
6976
}
7077
}
71-
intnewce=newne;
72-
for (inti=ne+1;i<ce;i++) {
78+
newce=newne;
79+
for (i=ne+1;i<ce;i++) {
7380
if (BIT_CHECK(graph[sel],oldSet[i])) {
7481
newSet[newce++]=oldSet[i];
7582
}
@@ -84,28 +91,30 @@ static void findMaximumIndependentSet(List* cur, List* result, nodemask_t* graph
8491
findMaximumIndependentSet(cur,result,graph,newSet,newne,newce);
8592
}
8693
}
87-
cur.size-=1;
94+
cur->size-=1;
8895
if (k>1) {
8996
for (s=++ne;BIT_CHECK(graph[fixp],oldSet[s]);s++);
9097
}
9198
}
9299
}
93100

94-
nodemask_tMtmFindMaxClique(nodemask_t*graphs,inn_nodes);
101+
nodemask_tMtmFindMaxClique(nodemask_t*graph,intn_nodes)
95102
{
96-
Listtmp;
97-
Listresult;
98-
nodemask_tmask=0;
103+
NodeListtmp;
104+
NodeListresult;
105+
nodemask_tmask;
99106
intall[MAX_NODES];
100107
inti;
108+
101109
tmp.size=0;
102110
result.size=0;
103111
for (i=0;i<n_nodes;i++) {
104-
all[i]=i;
112+
all[i]=i;
105113
}
106114
findMaximumIndependentSet(&tmp,&result,graph,all,0,n_nodes);
115+
mask=0;
107116
for (i=0;i<result.size;i++) {
108117
mask |= (nodemask_t)1 <<result.nodes[i];
109118
}
110-
return~mask;
119+
returnmask;
111120
}

‎bkb.h‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/*
2+
* Bron–Kerbosch algorithm to find maximum clique in graph
3+
*/
4+
#ifndef__BKB_H__
5+
#define__BKB_H__
6+
7+
#defineMAX_NODES 64
8+
9+
typedefuint64_tnodemask_t;
10+
#defineBIT_CHECK(mask,bit) (((mask) & ((nodemask_t)1 << (bit))) != 0)
11+
#defineBIT_CLEAR(mask,bit) (mask &= ~((nodemask_t)1 << (bit)))
12+
#defineBIT_SET(mask,bit) (mask |= ((nodemask_t)1 << (bit)))
13+
14+
externnodemask_tMtmFindMaxClique(nodemask_t*matrix,intn_modes);
15+
16+
#endif

‎ddd.c‎

Lines changed: 19 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
1-
#include<stddef.h>
2-
#include<stdlib.h>
3-
#include<string.h>
1+
#include"postgres.h"
2+
#include"access/clog.h"
3+
#include"storage/lwlock.h"
4+
#include"utils/hsearch.h"
5+
46
#include"ddd.h"
57

68

@@ -11,10 +13,10 @@ void MtmGraphInit(MtmGraph* graph)
1113

1214
staticinlineMtmVertex*findVertex(MtmGraph*graph,GlobalTransactionId*gtid)
1315
{
14-
xid_th=gtid->xid %MAX_TRANSACTIONS;
16+
uint32h=gtid->xid %MAX_TRANSACTIONS;
1517
MtmVertex*v;
16-
for (v=graph->hashtable[h];v!=NULL;v=v->next) {
17-
if (v->gtid==*gtid) {
18+
for (v=graph->hashtable[h];v!=NULL;v=v->collision) {
19+
if (EQUAL_GTID(v->gtid,*gtid)) {
1820
returnv;
1921
}
2022
}
@@ -29,30 +31,28 @@ static inline MtmVertex* findVertex(MtmGraph* graph, GlobalTransactionId* gtid)
2931
voidMtmGraphAdd(MtmGraph*graph,GlobalTransactionId*gtid,intsize)
3032
{
3133
GlobalTransactionId*last=gtid+size;
32-
MtmEdge*e,*next,*edges=NULL;
3334
while (gtid!=last) {
34-
Vertex*src=findVertex(graph,gtid++);
35+
MtmVertex*src=findVertex(graph,gtid++);
3536
while (gtid->node!=0) {
36-
Vertex*dst=findVertex(graph,gtid++);
37-
e= (MtmEdge*)palloc(sizeof(MtmEdge));
38-
dst->nIncomingEdges+=1;
37+
MtmVertex*dst=findVertex(graph,gtid++);
38+
MtmEdge*e= (MtmEdge*)palloc(sizeof(MtmEdge));
3939
e->dst=dst;
4040
e->src=src;
41-
e->next=v->outgoingEdges;
42-
v->outgoingEdges=e;
41+
e->next=src->outgoingEdges;
42+
src->outgoingEdges=e;
4343
}
4444
gtid+=1;
4545
}
4646
}
4747

4848
staticboolrecursiveTraverseGraph(MtmVertex*root,MtmVertex*v)
4949
{
50-
Edge*e;
51-
v->node=VISITED_NODE_MARK;
50+
MtmEdge*e;
51+
v->gtid.node=VISITED_NODE_MARK;
5252
for (e=v->outgoingEdges;e!=NULL;e=e->next) {
5353
if (e->dst==root) {
5454
return true;
55-
}elseif (e->dst->node!=VISITED_NODE_MAR&&recursiveTraverseGraph(root,e->dst)) {/* loop */
55+
}elseif (e->dst->gtid.node!=VISITED_NODE_MARK&&recursiveTraverseGraph(root,e->dst)) {/* loop */
5656
return true;
5757
}
5858
}
@@ -61,9 +61,9 @@ static bool recursiveTraverseGraph(MtmVertex* root, MtmVertex* v)
6161

6262
boolMtmGraphFindLoop(MtmGraph*graph,GlobalTransactionId*root)
6363
{
64-
Vertex*v;
65-
for (v=graph->hashtable[root->xid %MAX_TRANSACTIONS];v!=NULL;v=v->next) {
66-
if (v->gtid==*root) {
64+
MtmVertex*v;
65+
for (v=graph->hashtable[root->xid %MAX_TRANSACTIONS];v!=NULL;v=v->collision) {
66+
if (EQUAL_GTID(v->gtid,*root)) {
6767
if (recursiveTraverseGraph(v,v)) {
6868
return true;
6969
}

‎ddd.h‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
#ifndef__DDD_H__
2+
#define__DDD_H__
23

34
#include"multimaster.h"
45

@@ -20,8 +21,8 @@ typedef struct MtmVertex
2021

2122
typedefstructMtmGraph
2223
{
23-
MtmVertex*hashtable[MTM_MAX_TRANSACTIONS];
24-
}Graph;
24+
MtmVertex*hashtable[MAX_TRANSACTIONS];
25+
}MtmGraph;
2526

2627
externvoidMtmGraphInit(MtmGraph*graph);
2728
externvoidMtmGraphAdd(MtmGraph*graph,GlobalTransactionId*subgraph,intsize);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp