랜덤 DAG 생성
나는 지시 비순환 그래프에 대한 문제를 해결하고 있습니다.
하지만 몇몇 지시된 비순환 그래프에서 코드를 테스트하는 데 어려움을 겪고 있습니다.검정 그래프는 크고 비순환적이어야 합니다.
저는 비순환 방향 그래프를 생성하기 위한 코드를 작성하기 위해 많은 노력을 했습니다.하지만 매번 실패했습니다.
사용할 수 있는 순환 방향 그래프를 생성하는 기존 방법이 있습니까?
이것을 하는 C 프로그램을 만들었습니다.핵심은 노드를 '순위'를 매기고, 낮은 순위의 노드에서 높은 순위의 노드로 에지만 그리는 것입니다.
제가 작성한 프로그램은 DOT 언어로 인쇄됩니다.
다음은 코드 자체이며, 코드의 의미를 설명하는 코멘트는 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MIN_PER_RANK 1 /* Nodes/Rank: How 'fat' the DAG should be. */
#define MAX_PER_RANK 5
#define MIN_RANKS 3 /* Ranks: How 'tall' the DAG should be. */
#define MAX_RANKS 5
#define PERCENT 30 /* Chance of having an Edge. */
int main (void)
{
int i, j, k,nodes = 0;
srand (time (NULL));
int ranks = MIN_RANKS
+ (rand () % (MAX_RANKS - MIN_RANKS + 1));
printf ("digraph {\n");
for (i = 0; i < ranks; i++)
{
/* New nodes of 'higher' rank than all nodes generated till now. */
int new_nodes = MIN_PER_RANK
+ (rand () % (MAX_PER_RANK - MIN_PER_RANK + 1));
/* Edges from old nodes ('nodes') to new ones ('new_nodes'). */
for (j = 0; j < nodes; j++)
for (k = 0; k < new_nodes; k++)
if ( (rand () % 100) < PERCENT)
printf (" %d -> %d;\n", j, k + nodes); /* An Edge. */
nodes += new_nodes; /* Accumulate into old node set. */
}
printf ("}\n");
return 0;
}
테스트 실행을 통해 생성된 그래프는 다음과 같습니다.
https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs 에 대한 답은 다음과 같습니다. 그래프의 가장자리에 대한 인접 행렬 표현이 있으면 행렬이 삼각형보다 작으면 필요에 따라 DAG가 됩니다.
유사한 접근 방식은 노드의 임의 순서를 취한 다음 x < y인 경우에만 노드 x에서 y까지의 에지를 고려하는 것입니다.그 제약은 시공을 통해 당신의 DAGness도 얻을 수 있을 것입니다.노드를 표현하기 위해 구조를 사용하는 경우 메모리 비교는 노드를 순서화하는 하나의 임의적인 방법이 될 것입니다.
기본적으로 의사 코드는 다음과 같습니다.
for(i = 0; i < N; i++) {
for (j = i+1; j < N; j++) {
maybePutAnEdgeBetween(i, j);
}
}
여기서 N은 그래프의 노드 개수입니다.
의사코드는 N개의 노드가 주어진 잠재적 DAG의 수가
2^(n*(n-1)/2),
있기 때문에
n*(n-1)/2
순서 쌍("N choice 2")을 선택하고, 이들 사이에 에지를 가질지 말지 선택할 수 있습니다.
이 모든 합리적인 답변을 종합해 보십시오.
(다음에서는 생성된 그래프의 정점 수를 V, 에지 수를 E로 하여 E ≤ V(V-1)/2로 가정하였습니다.)
개인적으로 가장 유용한 답은 http://condor.depaul.edu/rjohnson/source/graph_ge.c 의 코드를 지적하는 Flavius의 댓글이라고 생각합니다.그 코드는 정말 간단해요. 댓글로 편리하게 설명할 수 있어요. 제가 재현해 놓은 거죠.
To generate a directed acyclic graph, we first
generate a random permutation dag[0],...,dag[v-1].
(v = number of vertices.)
This random permutation serves as a topological
sort of the graph. We then generate random edges of the
form (dag[i],dag[j]) with i < j.
실제로 코드가 하는 일은 다음을 반복하여 요청 수의 에지를 생성하는 것입니다.
- [0, V) 범위의 두 개의 숫자를 생성합니다.
- 만약 그들이 동등하다면, 그들을 거부할 것입니다.
- 첫 번째 것이 더 크면 교환합니다.
- 이전에 생성한 적이 있는 경우 거부합니다.
이 솔루션의 문제는 E가 최대 에지 수 V(V-1)/2에 가까워지면 알고리즘이 점점 더 많은 에지를 거부해야 하기 때문에 점점 더 느려진다는 것입니다.더 나은 해결책은 모든 V(V-1)/2 가능한 에지의 벡터를 만들고 임의로 셔플하고 셔플 목록에서 첫 번째(요청된 에지) 에지를 선택하는 것입니다.
저장자 샘플링 알고리즘은 k의 값으로부터 k의th 끝점을 추론할 수 있기 때문에 공간 O(E)에서 이를 수행할 수 있습니다.따라서 소스 벡터를 생성할 필요가 없습니다.하지만 여전히 O(V2) 시간이 필요합니다.
또는 Fisher-Yates 셔플(또는 원하는 경우 Knuth 셔플)을 수행하여 반복 후 중지할 수 있습니다.위키피디아에 제시된 FY 셔플 버전에서는 후행 항목이 생성되지만 알고리즘은 거꾸로도 작동합니다.
// At the end of this snippet, a consists of a random sample of the
// integers in the half-open range [0, V(V-1)/2). (They still need to be
// converted to pairs of endpoints).
vector<int> a;
int N = V * (V - 1) / 2;
for (int i = 0; i < N; ++i) a.push_back(i);
for (int i = 0; i < E; ++i) {
int j = i + rand(N - i);
swap(a[i], a[j]);
a.resize(E);
O(E) 시간만 필요하지만 O(N2) 공간이 필요합니다.사실 이것은 약간의 속임수로 O(E) 공간으로 개선될 수 있지만 SO 코드 스니펫은 너무 작아서 결과를 담을 수 없기 때문에 O(E) 공간과 O(Elog E) 시간에 좀 더 간단한 것을 제공하겠습니다.적어도 다음과 같은 클래스 DAG가 있다고 가정합니다.
class DAG {
// Construct an empty DAG with v vertices
explicit DAG(int v);
// Add the directed edge i->j, where 0 <= i, j < v
void add(int i, int j);
};
이제 다음과 같습니다.
// Return a randomly-constructed DAG with V vertices and and E edges.
// It's required that 0 < E < V(V-1)/2.
template<typename PRNG>
DAG RandomDAG(int V, int E, PRNG& prng) {
using dist = std::uniform_int_distribution<int>;
// Make a random sample of size E
std::vector<int> sample;
sample.reserve(E);
int N = V * (V - 1) / 2;
dist d(0, N - E); // uniform_int_distribution is closed range
// Random vector of integers in [0, N-E]
for (int i = 0; i < E; ++i) sample.push_back(dist(prng));
// Sort them, and make them unique
std::sort(sample.begin(), sample.end());
for (int i = 1; i < E; ++i) sample[i] += i;
// Now it's a unique sorted list of integers in [0, N-E+E-1]
// Randomly shuffle the endpoints, so the topological sort
// is different, too.
std::vector<int> endpoints;
endpoints.reserve(V);
for (i = 0; i < V; ++i) endpoints.push_back(i);
std::shuffle(endpoints.begin(), endpoints.end(), prng);
// Finally, create the dag
DAG rv;
for (auto& v : sample) {
int tail = int(0.5 + sqrt((v + 1) * 2));
int head = v - tail * (tail - 1) / 2;
rv.add(head, tail);
}
return rv;
}
랜덤 방향 그래프를 생성한 다음 사이클에 대한 깊이 우선 검색을 수행할 수 있습니다.사이클을 찾으면 에지를 삭제하여 사이클을 끊습니다.
최악의 경우 O(VE)인 것 같습니다.각 DFS에서 O(V)를 사용하고 각 DFS에서 하나 이상의 에지를 제거합니다(최대 E).
모든 V^2 가능한 간선을 균일하게 임의로 선택하여 방향 그래프를 생성하고 임의의 간선을 임의의 순서로 DFS하고 삭제하면 모든 가능한 단에 대해 균일한 분포(또는 적어도 그에 가까운 분포)를 얻을 수 있습니다.
매우 간단한 접근 방식은 다음과 같습니다.
아래 대각선 행렬의 인덱스를 반복하여 에지를 랜덤하게 할당합니다(위의 링크에 의해 제시된 바와 같이: https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs)
이렇게 하면 두 개 이상의 구성 요소가 포함된 DAG가 제공됩니다.분할 집합 데이터 구조를 사용하여 구성요소 간에 에지를 생성하여 병합할 수 있는 구성요소를 제공할 수 있습니다.
분리 집합은 여기에 설명되어 있습니다. https://en.wikipedia.org/wiki/Disjoint-set_data_structure
연결되지 않을 수 있는 랜덤 DAG 생성
여기 연결되지 않을 수도 있는 랜덤 DAG를 생성하는 간단한 알고리즘이 있습니다.
const randomDAG = (x, n) => {
const length = n * (n - 1) / 2;
const dag = new Array(length);
for (let i = 0; i < length; i++) {
dag[i] = Math.random() < x ? 1 : 0;
}
return dag;
};
const dagIndex = (n, i, j) => n * i + j - (i + 1) * (i + 2) / 2;
const dagToDot = (n, dag) => {
let dot = "digraph {\n";
for (let i = 0; i < n; i++) {
dot += ` ${i};\n`;
for (let j = i + 1; j < n; j++) {
const k = dagIndex(n, i, j);
if (dag[k]) dot += ` ${i} -> ${j};\n`;
}
}
return dot + "}";
};
const randomDot = (x, n) => dagToDot(n, randomDAG(x, n));
new Viz().renderSVGElement(randomDot(0.3, 10)).then(svg => {
document.body.appendChild(svg);
});<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/viz.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/full.render.js"></script>이 코드 조각을 몇 번 실행하면 연결되지 않은 DAG가 나타날 수 있습니다.
그럼 이 코드는 어떻게 작동하는 겁니까?
DAG(Directed Asyclic Graph)는 위상학적으로 정렬된 무방향 그래프일 뿐입니다.의 무방향 그래프n다를 수 .n * (n - 1) / 2꼭짓점에서 자신으로 반복되는 모서리나 모서리를 세지 않는 모서리.이제 아래쪽 꼭지점에서 위쪽 꼭지점으로 가는 모서리만 가질 수 있습니다.따라서 모든 모서리의 방향이 미리 결정됩니다.
, 의 , 1 DAG 를를 DAG를 수 .n * (n - 1) / 2가장자리 역기가장자리 무게:0가장자리가 없음을 의미합니다.따라서, 우리는 단지 임의의 0 또는 1 배열을 만들고, 그것이 우리의 임의의 DAG입니다.
꼭짓점으로부터의 모서리ijn점,,i < j 에 .kk = n * i + j - (i + 1) * (i + 2) / 2.
연결된 DAG 생성
랜덤 DAG를 생성하면 다음 기능을 사용하여 연결되어 있는지 확인할 수 있습니다.
const isConnected = (n, dag) => {
const reached = new Array(n).fill(false);
reached[0] = true;
const queue = [0];
while (queue.length > 0) {
const x = queue.shift();
for (let i = 0; i < n; i++) {
if (i === n || reached[i]) continue;
const j = i < x ? dagIndex(n, i, x) : dagIndex(n, x, i);
if (dag[j] === 0) continue;
reached[i] = true;
queue.push(i);
}
}
return reached.every(x => x); // return true if every vertex was reached
};
연결되지 않은 경우에는 항상 보체가 연결됩니다.
const complement = dag => dag.map(x => x ? 0 : 1);
const randomConnectedDAG = (x, n) => {
const dag = randomDAG(x, n);
return isConnected(n, dag) ? dag : complement(dag);
};
가장자리가 30%인 랜덤 DAG를 생성하면 보체가 70%의 가장자리를 갖게 됩니다.서에 값,서x50% 입니다.그러나 가장자리 비율보다 연결에 신경을 쓴다면 거래 단절자가 되어서는 안 됩니다.
마지막으로, 모든 것을 종합하는 것입니다.
const randomDAG = (x, n) => {
const length = n * (n - 1) / 2;
const dag = new Array(length);
for (let i = 0; i < length; i++) {
dag[i] = Math.random() < x ? 1 : 0;
}
return dag;
};
const dagIndex = (n, i, j) => n * i + j - (i + 1) * (i + 2) / 2;
const isConnected = (n, dag) => {
const reached = new Array(n).fill(false);
reached[0] = true;
const queue = [0];
while (queue.length > 0) {
const x = queue.shift();
for (let i = 0; i < n; i++) {
if (i === n || reached[i]) continue;
const j = i < x ? dagIndex(n, i, x) : dagIndex(n, x, i);
if (dag[j] === 0) continue;
reached[i] = true;
queue.push(i);
}
}
return reached.every(x => x); // return true if every vertex was reached
};
const complement = dag => dag.map(x => x ? 0 : 1);
const randomConnectedDAG = (x, n) => {
const dag = randomDAG(x, n);
return isConnected(n, dag) ? dag : complement(dag);
};
const dagToDot = (n, dag) => {
let dot = "digraph {\n";
for (let i = 0; i < n; i++) {
dot += ` ${i};\n`;
for (let j = i + 1; j < n; j++) {
const k = dagIndex(n, i, j);
if (dag[k]) dot += ` ${i} -> ${j};\n`;
}
}
return dot + "}";
};
const randomConnectedDot = (x, n) => dagToDot(n, randomConnectedDAG(x, n));
new Viz().renderSVGElement(randomConnectedDot(0.3, 10)).then(svg => {
document.body.appendChild(svg);
});<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/viz.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/full.render.js"></script>이 코드 조각을 몇 번 실행하면 다른 코드보다 훨씬 더 많은 에지를 가진 DAG를 볼 수 있습니다.
일정 비율의 에지로 연결된 DAG 생성
연결과 일정 비율의 에지를 모두 고려하는 경우 다음 알고리즘을 사용할 수 있습니다.
- 완전히 연결된 그래프부터 시작합니다.
- 가장자리를 무작위로 제거합니다.
- 가장자리를 제거한 후 그래프가 계속 연결되어 있는지 확인합니다.
- 더 이상 연결되어 있지 않으면 해당 에지를 다시 추가합니다.
이 알고리즘은 이전 방법만큼 효율적이지 않다는 점에 유의해야 합니다.
const randomDAG = (x, n) => {
const length = n * (n - 1) / 2;
const dag = new Array(length).fill(1);
for (let i = 0; i < length; i++) {
if (Math.random() < x) continue;
dag[i] = 0;
if (!isConnected(n, dag)) dag[i] = 1;
}
return dag;
};
const dagIndex = (n, i, j) => n * i + j - (i + 1) * (i + 2) / 2;
const isConnected = (n, dag) => {
const reached = new Array(n).fill(false);
reached[0] = true;
const queue = [0];
while (queue.length > 0) {
const x = queue.shift();
for (let i = 0; i < n; i++) {
if (i === n || reached[i]) continue;
const j = i < x ? dagIndex(n, i, x) : dagIndex(n, x, i);
if (dag[j] === 0) continue;
reached[i] = true;
queue.push(i);
}
}
return reached.every(x => x); // return true if every vertex was reached
};
const dagToDot = (n, dag) => {
let dot = "digraph {\n";
for (let i = 0; i < n; i++) {
dot += ` ${i};\n`;
for (let j = i + 1; j < n; j++) {
const k = dagIndex(n, i, j);
if (dag[k]) dot += ` ${i} -> ${j};\n`;
}
}
return dot + "}";
};
const randomDot = (x, n) => dagToDot(n, randomDAG(x, n));
new Viz().renderSVGElement(randomDot(0.3, 10)).then(svg => {
document.body.appendChild(svg);
});<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/viz.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/full.render.js"></script>도움이 되길 바랍니다.
편집: 작업(작업이 처리되는 순서)이 지시된 비순환 그래프로 정의되는 시퀀스 유연성과 함께 유연한 잡샵 스케줄링 문제라는 스케줄링 문제를 해결하던 중 처음 이 게시물을 발견했습니다.이 아이디어는 알고리즘을 사용하여 여러 개의 임의 방향 그래프(job)를 생성하고 스케줄링 문제의 인스턴스를 생성하여 내 알고리즘을 테스트하는 것이었습니다.이 게시물의 끝에 있는 코드는 제가 인스턴스를 생성할 때 사용했던 코드의 기본 버전입니다.인스턴스 생성기는 여기서 찾을 수 있습니다.
저는 파이썬으로 번역하고 몇 가지 기능을 통합하여 랜덤 DAG의 과도 집합을 만들었습니다.이러한 방식으로 생성된 그래프는 도달 가능성이 동일한 최소 에지 수를 가집니다.
출력을 모델 코드(오른쪽)에 붙여넣어 전이 그래프를 http://dagitty.net/dags.html 에서 시각화할 수 있습니다.
알고리즘의 파이썬 버전
import random
class Graph:
nodes = []
edges = []
removed_edges = []
def remove_edge(self, x, y):
e = (x,y)
try:
self.edges.remove(e)
# print("Removed edge %s" % str(e))
self.removed_edges.append(e)
except:
return
def Nodes(self):
return self.nodes
# Sample data
def __init__(self):
self.nodes = []
self.edges = []
def get_random_dag():
MIN_PER_RANK = 1 # Nodes/Rank: How 'fat' the DAG should be
MAX_PER_RANK = 2
MIN_RANKS = 6 # Ranks: How 'tall' the DAG should be
MAX_RANKS = 10
PERCENT = 0.3 # Chance of having an Edge
nodes = 0
ranks = random.randint(MIN_RANKS, MAX_RANKS)
adjacency = []
for i in range(ranks):
# New nodes of 'higher' rank than all nodes generated till now
new_nodes = random.randint(MIN_PER_RANK, MAX_PER_RANK)
# Edges from old nodes ('nodes') to new ones ('new_nodes')
for j in range(nodes):
for k in range(new_nodes):
if random.random() < PERCENT:
adjacency.append((j, k+nodes))
nodes += new_nodes
# Compute transitive graph
G = Graph()
# Append nodes
for i in range(nodes):
G.nodes.append(i)
# Append adjacencies
for i in range(len(adjacency)):
G.edges.append(adjacency[i])
N = G.Nodes()
for x in N:
for y in N:
for z in N:
if (x, y) != (y, z) and (x, y) != (x, z):
if (x, y) in G.edges and (y, z) in G.edges:
G.remove_edge(x, z)
# Print graph
for i in range(nodes):
print(i)
print()
for value in G.edges:
print(str(value[0]) + ' ' + str(value[1]))
get_random_dag()
아래 그림에서 위의 파이썬 코드에 의해 생성된 많은 중복 에지가 있는 랜덤 DAG를 볼 수 있습니다.
코드를 적용하여 동일한 그래프(동일한 도달 가능성)를 생성했지만 가능한 가장 적은 수의 에지를 생성했습니다.이것은 또한 경과적 감소라고도 불립니다.
def get_random_dag():
MIN_PER_RANK = 1 # Nodes/Rank: How 'fat' the DAG should be
MAX_PER_RANK = 3
MIN_RANKS = 15 # Ranks: How 'tall' the DAG should be
MAX_RANKS = 20
PERCENT = 0.3 # Chance of having an Edge
nodes = 0
node_counter = 0
ranks = random.randint(MIN_RANKS, MAX_RANKS)
adjacency = []
rank_list = []
for i in range(ranks):
# New nodes of 'higher' rank than all nodes generated till now
new_nodes = random.randint(MIN_PER_RANK, MAX_PER_RANK)
list = []
for j in range(new_nodes):
list.append(node_counter)
node_counter += 1
rank_list.append(list)
print(rank_list)
# Edges from old nodes ('nodes') to new ones ('new_nodes')
if i > 0:
for j in rank_list[i - 1]:
for k in range(new_nodes):
if random.random() < PERCENT:
adjacency.append((j, k+nodes))
nodes += new_nodes
for i in range(nodes):
print(i)
print()
for edge in adjacency:
print(str(edge[0]) + ' ' + str(edge[1]))
print()
print()
결과:
다음을 사용하여 그래프를 만듭니다.n노드와 각 노드 쌍 사이의 가장자리n1그리고.n2한다면n1 != n2그리고.n2 % n1 == 0.
저는 최근에 수용된 답변을 다시 시행해보았는데, 그것이 불확정적이라는 것을 알게 되었습니다.min_per_rank 매개 변수를 적용하지 않으면 노드가 0개인 그래프로 끝날 수 있습니다.
이를 방지하기 위해 for loops를 함수로 감싼 다음 각 순위가 끝난 후 다음을 확인했습니다.min_per_rank만족했습니다.자바스크립트 구현은 다음과 같습니다.
https://github.com/karissa/random-dag
그리고 승인된 답변의 메인 루프를 대체할 의사-C 코드도 있습니다.
int pushed = 0
int addRank (void)
{
for (j = 0; j < nodes; j++)
for (k = 0; k < new_nodes; k++)
if ( (rand () % 100) < PERCENT)
printf (" %d -> %d;\n", j, k + nodes); /* An Edge. */
if (pushed < min_per_rank) return addRank()
else pushed = 0
return 0
}
알고리즘을 테스트하기 위해 노드 계층을 기반으로 랜덤 그래프를 생성했습니다.이것은 Python 스크립트(인접 목록도 인쇄)입니다.노드 연결 확률 백분율을 변경하거나 계층을 추가하여 약간 다른 그래프 또는 "더 큰" 그래프를 가질 수 있습니다.
# Weighted DAG generator by forward layers
import argparse
import random
parser = argparse.ArgumentParser("dag_gen2")
parser.add_argument(
"--layers",
help="DAG forward layers. Default=5",
type=int,
default=5,
)
args = parser.parse_args()
layers = [[] for _ in range(args.layers)]
edges = {}
node_index = -1
print(f"Creating {len(layers)} layers graph")
# Random horizontal connections -low probability-
def random_horizontal(layer):
for node1 in layer:
# Avoid cycles
for node2 in filter(
lambda n2: node1 != n2 and node1 not in map(lambda el: el[0], edges[n2]),
layer,
):
if random.randint(0, 100) < 10:
w = random.randint(1, 10)
edges[node1].append((node2, w))
# Connect two layers
def connect(layer1, layer2):
random_horizontal(layer1)
for node1 in layer1:
for node2 in layer2:
if random.randint(0, 100) < 30:
w = random.randint(1, 10)
edges[node1].append((node2, w))
# Start nodes 1 to 3
start_nodes = random.randint(1, 3)
start_layer = []
for sn in range(start_nodes + 1):
node_index += 1
start_layer.append(node_index)
# Gen nodes
for layer in layers:
nodes = random.randint(2, 5)
for n in range(nodes):
node_index += 1
layer.append(node_index)
# Connect all
layers.insert(0, start_layer)
for layer in layers:
for node in layer:
edges[node] = []
for i, layer in enumerate(layers[:-1]):
connect(layer, layers[i + 1])
# Print in DOT language
print("digraph {")
for node_key in [node_key for node_key in edges.keys() if len(edges[node_key]) > 0]:
for node_dst, weight in edges[node_key]:
print(f" {node_key} -> {node_dst} [label={weight}];")
print("}")
print("---- Adjacency list ----")
print(edges)
언급URL : https://stackoverflow.com/questions/12790337/generating-a-random-dag
'source' 카테고리의 다른 글
| 만드는 법만드는 법항상 풀스크린? (0) | 2023.10.09 |
|---|---|
| jQuery로 텍스트 색상을 변경하려면 어떻게 해야 합니까? (0) | 2023.10.09 |
| ThickBox가 닫혔을 때 이벤트를 어떻게 트리거하시겠습니까? (0) | 2023.10.09 |
| 이미지 파일을 양식 데이터에 추가 - Cordova/Angular (0) | 2023.10.09 |
| 동적으로 jQuery UI 변경 대화상자 버튼 텍스트 (0) | 2023.10.09 |