概述
K-1着色算法将颜色分配给各点,确保相邻节点颜色不同,并且使用的颜色种类最少。
- U.V. Çatalyürek, J. Feo, A.H. Gebremedhin, M. Halappanavar, A. Pothen, Graph Coloring Algorithms for Multi-core and Massively Multithreaded Architectures (2018)
基本概念
距离-1图着色
距离-1图着色,也称作K-1图着色,是图论中的概念,其目标是将颜色(以整数0
,1
,2
等表示)分配给图中的节点,使得距离为1的节点(即相邻节点)颜色不同。着色问题还有一个目标,即使用颜色的数量最少。
图着色最著名的应用之一就是地图着色,也就是将地图上的地区(表示为节点)染色,确保相邻区域(即共享边界的区域)颜色不同。
图着色还有许多其他实际应用。例如,学校安排互不冲突的课程时,可以将每门课程视作一个节点,用边表示冲突(例如,两门课程需要同个教室)。图着色为每门课程分配一个“颜色”,对应不同的时间段。
贪心着色算法
图着色问题在最优解的情况下是NP-hard问题,使用贪婪算法可以获得近似最优解。
串行贪心着色算法
贪心算法开始时,初始化图中每个节点v
的颜色为未着色。算法按照以下步骤处理各节点v
:
- 对于每个相邻节点
w
和v
,将w
的颜色标记为v
的禁用颜色。 - 为节点
v
分配最小的可用颜色,该颜色与所有禁用颜色均不同。
算法按顺序为节点分配颜色,对于大型图来说,该过程可能成为制约计算的瓶颈。以下算法允许多个节点并行处理,同时可以妥善处理可能出现的冲突。
迭代并行贪心着色算法
迭代并行贪心着色算法是串行贪心着色算法的并行拓展,旨在利用现代多核分布式计算系统更加高效地处理大型图集。
算法将图中各点划分成独立集合,以便在多个并行线程中进行处理。每次迭代包括两个阶段:
- 初步着色阶段:与串行贪心着色算法相同,不同之处在于这是在多线程上并发执行的。
- 冲突检测阶段:每个线程识别出下次迭代中需要重新着色的节点子集,以解决两个相邻节点(位于不同线程)颜色相同的冲突。
当不再有节点需要重新染色时,算法停止。
特殊说明
- K-1着色算法忽略边的方向。
示例图集
创建示例图集:
xxxxxxxxxx
// 在空图集中逐行运行以下语句
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}, {_id:"H"}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"A", _to:"C"}, {_from:"A", _to:"D"}, {_from:"A", _to:"E"}, {_from:"A", _to:"G"}, {_from:"D", _to:"E"}, {_from:"D", _to:"F"}, {_from:"E", _to:"F"}, {_from:"G", _to:"D"}, {_from:"G", _to:"H"}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1
上,并命名为 hdc_coloring
:
xxxxxxxxxx
CALL hdc.graph.create("hdc-server-1", "hdc_coloring", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
参数
算法名:k1_coloring
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
---|---|---|---|---|---|
loop_num |
Integer | ≥1 | 5 |
是 | 迭代轮数。算法将在完成所有轮次后停止。该选项仅当version 为2 时生效 |
version |
Integer | 1 , 2 |
2 |
是 | 设置为1 时,运行串行贪心着色算法;设置为2 时,运行迭代并行贪心着色算法 |
return_id_uuid |
String | uuid , id , both |
uuid |
是 | 在结果中使用_uuid 、_id 或同时使用两者来表示点 |
在算法结果中,颜色相同的点属于同一个社区。
文件回写
该算法可生成三个文件:
配置项 |
内容 |
---|---|
filename_community_id |
|
filename_ids |
|
filename_num |
|
xxxxxxxxxx
CALL algo.k1_coloring.write("hdc_coloring", {
params: {
return_id_uuid: "id",
version: 1
},
return_params: {
file: {
filename_community_id: "f1.txt",
filename_ids: "f2.txt",
filename_num: "f3.txt"
}
}
})
结果:
xxxxxxxxxx
_id,community_id
D,1
F,2
H,1
B,1
A,2
E,0
C,0
G,0
数据库回写
将结果中的community_id
写入指定点属性。该属性类型为uint32
。
xxxxxxxxxx
CALL algo.k1_coloring.write("hdc_coloring", {
params: {
loop_num: 10,
version: 2
},
return_params: {
db: {
property: "color"
}
}
})
统计回写
xxxxxxxxxx
CALL algo.k1_coloring.write("hdc_coloring", {
params: {
version: 1
},
return_params: {
stats: {}
}
})
结果:
community_count |
---|
3 |
完整返回
xxxxxxxxxx
CALL algo.k1_coloring("hdc_coloring", {
params: {
return_id_uuid: "id",
loop_num: 5,
version: 2
},
return_params: {}
}) YIELD r
RETURN r
结果:
_id | community_id |
---|---|
D | 1 |
F | 2 |
H | 1 |
B | 1 |
A | 2 |
E | 0 |
C | 0 |
G | 0 |
流式返回
xxxxxxxxxx
CALL algo.k1_coloring("hdc_coloring", {
params: {
return_id_uuid: "id",
loop_num: 15,
version: 1
},
return_params: {
stream: {}
}
}) YIELD r
RETURN r.community_id AS communityID, count(r) AS nodeCounts GROUP BY communityID
结果:
communityID | nodeCounts |
---|---|
0 | 3 |
1 | 3 |
2 | 2 |
统计返回
xxxxxxxxxx
CALL algo.k1_coloring("hdc_coloring", {
params: {},
return_params: {
stats: {}
}
}) YIELD res
RETURN res
结果:
community_count |
---|
3 |