HDC
概述
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着色算法忽略边的方向。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
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：
CALL hdc.graph.create("hdc-server-1", "hdc_coloring", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_coloring", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：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 |
|
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"
}
}
})
algo(k1_coloring).params({
project: "hdc_coloring",
return_id_uuid: "id",
version: 1
}).write({
file: {
filename_community_id: "f1.txt",
filename_ids: "f2.txt",
filename_num: "f3.txt"
}
})
结果：
_id,community_id
D,1
F,2
H,1
B,1
A,2
E,0
C,0
G,0
community_id,_ids
0,E;C;G;
2,F;A;
1,D;H;B;
community_id,count
0,3
2,2
1,3
数据库回写
将结果中的community_id写入指定点属性。该属性类型为uint32。
CALL algo.k1_coloring.write("hdc_coloring", {
params: {
loop_num: 10,
version: 2
},
return_params: {
db: {
property: "color"
}
}
})
algo(k1_coloring).params({
project: "hdc_coloring",
loop_num: 10,
version: 2
}).write({
db: {
property: "color"
}
})
统计回写
CALL algo.k1_coloring.write("hdc_coloring", {
params: {
version: 1
},
return_params: {
stats: {}
}
})
algo(k1_coloring).params({
project: "hdc_coloring",
version:1
}).write({
stats: {}
})
结果：
| community_count |
|---|
| 3 |
完整返回
CALL algo.k1_coloring("hdc_coloring", {
params: {
return_id_uuid: "id",
loop_num: 5,
version: 2
},
return_params: {}
}) YIELD r
RETURN r
exec{
algo(k1_coloring).params({
return_id_uuid: "id",
loop_num: 5,
version: 2
}) as r
return r
} on hdc_coloring
结果：
| _id | community_id |
|---|---|
| D | 1 |
| F | 2 |
| H | 1 |
| B | 1 |
| A | 2 |
| E | 0 |
| C | 0 |
| G | 0 |
流式返回
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
exec{
algo(k1_coloring).params({
return_id_uuid: "id",
loop_num: 15,
version: 1
}).stream() as r
group by r.community_id as communityID
with r, count(r) as nodeCounts
return table(communityID, nodeCounts)
} on hdc_coloring
结果：
| communityID | nodeCounts |
|---|---|
| 0 | 3 |
| 1 | 3 |
| 2 | 2 |
统计返回
CALL algo.k1_coloring("hdc_coloring", {
params: {},
return_params: {
stats: {}
}
}) YIELD res
RETURN res
exec{
algo(k1_coloring).params().stats() as res
return res
} on hdc_coloring
结果：
| community_count |
|---|
| 3 |