지난 글에 이어 이번 포스팅에서는 지난 포스팅에서 만든 워크플로우를 토대로 깊이 우선 탐색(DFS)를 적용하여 워크플로우의 테스트 케이스를 추출해보도록 하겠습니다.
워크플로우 테스트 케이스 추출 #
깊이 우선 탐색(DFS) 알고리즘을 코드적으로 구현하기 위해서는 그래프 클래스, 그래프를 구성하는 노드 클래스, 실질적인 검색을 수행하는 DFS 클래스가 필요합니다.
각각의 필요한 클래스를 작성하여 최종적으로는 워크플로우에 적용해보도록 하겠습니다.
노드 클래스 #
노드 클래스를 선언해보겠습니다.
그래프의 노드(Node)란 그래프에서 하나의 요소를 나타내는 기본 단위입니다. 노드는 그래프의 한 지점을 나타내며, 이 지점은 데이터를 저장할 수 있습니다. 각 노드는 고유한 식별자(일반적으로 숫자 또는 문자열)와 해당 노드와 연결된 다른 노드의 정보를 포함하는 인접 리스트와 같은 구조를 가질 수 있습니다.
다만 일반적인 노드 클래스와 다르게 위의 워크플로우를 표현하기 위해 고려되어야 할 점은, 워크플로우의 링크에는 String 형태의 링크 이름이 있다는 점 입니다. 이를 표현하기 위해 일반적인 노드 클래스와는 다르게 인접 노드를 리스트를 구성할 때 링크이름과 인접노드를 함께 저장하는 Map 형태의 데이터를 담았습니다.
class Node {
// id: 노드의 고유 식별자
private int id;
// name: 노드의 이름 또는 레이블
private String name;
// adjNodeList: 인접 노드 정보를 담는 리스트. 현재 노드와 인접 노드를 연결하는 링크의 이름도 함께 저장함.
// Map<linkName:String, node:Node>
private List<Map<String, Node>> adjNodeList;
public Node(int id, String name) {
this.id = id;
this.name = name;
this.adjNodeList = new ArrayList<>();
}
public int getId() {
return id;
}
public String getName() {
return name;
}
public List<Map<String, Node>> getAdjNodeList() {
return adjNodeList;
}
public void addAdjacentNode(String linkName, Node node) {
Map<String, Node> link = new HashMap<>();
link.put(linkName, node);
adjNodeList.add(link);
}
}
그래프 클래스 #
그래프 클래스를 선언해보겠습니다.
해당 알고리즘을 위한 그래프는 단순합니다. 그래프는 노드들의 집합체로써만 기능할 겁니다.
class Graph {
// Map<id:Integer, node:Node>
private Map<Integer, Node> nodes;
public Graph() {
nodes = new HashMap<>();
}
public void addNode(Node node) {
nodes.put(node.getId(), node);
}
public Node getNode(int id) {
return nodes.get(id);
}
}
DFS 클래스 #
스택과 재귀 호출을 이용한 DFS 검색 알고리즘이 구현된 DFS 클래스를 작성해보겠습니다.
DFS 클래스는 그래프와 노드의 방문여부를 기록하고 체크할 Set
또한 깊이 우선 탐색을 위해 스택을 사용한 재귀적인 탐색을 하는 메소드와 스택에 저장된 노드정보를 이용하여 경로 정보를 생성하는 메소드를 가지고 있습니다.
public class DFS {
// 그래프
private Graph graph;
// 방문한 노드 집합
private Set<Node> visited;
/**
* DFS 클래스의 생성자
*
* @param graph 그래프 객체
*/
public DFS(Graph graph) {
this.graph = graph;
visited = new HashSet<>();
}
/**
* 시작 노드부터 목표 노드까지의 모든 경로를 찾는 재귀적인 깊이 우선 탐색(Depth-First Search) 알고리즘
*
* @param node 현재 노드
* @param target 목표 노드
* @param linkName 현재 노드와 다음 노드를 연결하는 링크의 이름
* @param allPaths 모든 경로가 저장될 리스트
* @param stack 현재까지의 경로가 저장된 스택
*/
public void findAllPaths(Node node, Node target, String linkName, List<List<Map<String, Node>>> allPaths, Stack<Map<String, Node>> stack) {
// 현재 노드를 방문한 것으로 표시
visited.add(node);
// 현재 노드와 해당 링크 정보를 스택에 추가
Map<String, Node> stackMap = new HashMap<>();
stackMap.put(linkName, node);
stack.push(stackMap);
// 목표 노드에 도달했을 경우, 경로를 생성하고 리스트에 추가
if (node == target) {
allPaths.add(createPath(stack));
} else {
// 현재 노드의 인접 노드들을 탐색하며 재귀적으로 경로를 찾음
for (Map<String, Node> adjNode : node.getAdjNodeList()) {
for (Map.Entry<String, Node> entry : adjNode.entrySet()) {
String nextLinkName = entry.getKey();
Node nextNode = entry.getValue();
// 방문하지 않은 인접 노드일 경우 재귀 호출
if (!visited.contains(nextNode)) {
findAllPaths(nextNode, target, nextLinkName, allPaths, stack);
}
}
}
}
// 백트래킹을 위해 방문 여부를 되돌림
visited.remove(node);
// 현재 노드를 스택에서 제거
stack.pop();
}
/**
* 스택에 저장된 노드를 이용하여 경로를 생성
*
* @param stack 스택에 저장된 노드 경로 정보
* @return 생성된 경로 리스트
*/
private List<Map<String, Node>> createPath(Stack<Map<String, Node>> stack) {
List<Map<String, Node>> path = new ArrayList<>();
// 스택에 저장된 경로를 순회하며 경로 리스트를 생성
for (Map<String, Node> stackItem : stack) {
for (Map.Entry<String, Node> entry : stackItem.entrySet()) {
Map<String, Node> nodeMap = new HashMap<>();
nodeMap.put(entry.getKey(), entry.getValue());
path.add(nodeMap);
}
}
return path;
}
}
워크플로우 예시 #
지난 포스팅에서 만든 워크플로우로 깊이 우선 탐색 알고리즘을 적용하여 프로그램을 통해 테스트 케이스를 추출해보겠습니다.
워크플로우 그래프 선언 #
워크플로우를 그래프로 선언하기 위해서는 각 노드에 id를 붙여야 합니다.
각 노드를 넘버링하고 그래프로 선언해보도록 하겠습니다.
Graph graph = new Graph();
// 노드 생성
Node node1 = new Node(0, "START");
Node node2 = new Node(1, "결재중 상태");
Node node3 = new Node(2, "1단계 승인");
Node node4 = new Node(3, "2단계 승인자 할당 확인");
Node node5 = new Node(4, "승인됨 상태");
Node node6 = new Node(5, "2단계 승인");
Node node7 = new Node(6, "재작업 상태");
Node node8 = new Node(7, "재작업");
Node node9 = new Node(8, "END");
// 인접 노드 추가
node1.addAdjacentNode("COMPLETE", node2);
node2.addAdjacentNode("COMPLETE", node3);
node3.addAdjacentNode("승인", node4);
node4.addAdjacentNode("할당되지 않음", node5);
node3.addAdjacentNode("반려", node7);
node4.addAdjacentNode("할당됨", node6);
node6.addAdjacentNode("승인", node5);
node6.addAdjacentNode("반려", node7);
node7.addAdjacentNode("COMPLETE", node8);
node8.addAdjacentNode("COMPLETE", node2);
node5.addAdjacentNode("COMPLETE", node9);
// 그래프 생성
graph.addNode(node1);
graph.addNode(node2);
graph.addNode(node3);
graph.addNode(node4);
graph.addNode(node5);
graph.addNode(node6);
graph.addNode(node7);
graph.addNode(node8);
graph.addNode(node9);
// 시작 노드와 목표 노드 설정
Node startNode = node1;
Node targetNode = node9;
링크 이름이 포함된 인접노드로 구성된 그래프가 생성되었습니다.
위에서 생성한 그래프를 기반으로 DFS 클래스를 사용하여 모든 경로 정보를 저장하고, 저장된 경로 정보를 출력해보도록 하겠습니다.
DFS dfs = new DFS(graph);
List<List<Map<String, Node>>> allPaths = new ArrayList<>();
Stack<Map<String, Node>> stack = new Stack<>();
dfs.findAllPaths(startNode, targetNode, "", allPaths, stack);
// Print all paths
int i = 0;
for (List<Map<String, Node>> path : allPaths) {
++i;
System.out.print("CASE " + i + " : ");
for (Map<String, Node> node : path) {
for (Map.Entry<String, Node> entry : node.entrySet()) {
String linkName = entry.getKey();
String nodeName = entry.getValue().getName();
// linkName이 비어있지 않은 경우 링크 이름을 포함하여 출력
String linkPrefix = linkName.length() > 0 ? " >(" + linkName + ")> " : "";
System.out.print(linkPrefix + nodeName);
}
}
System.out.println();
}
다음은 콘솔에서 출력된 결과입니다.
어떤 노드와 링크를 거쳐 시작 노드에서 종료 노드까지 도달 하는지에 대한 모든 경우의 수가 출력된 것을 확인할 수 있습니다.
마무리하며 #
복잡한 워크플로우의 모든 경우의 수를 추출하고 해당 워크플로우를 검증하기 위한 테스트케이스를 확인하기 위한 방법으로깊이 우선 탐색(DFS) 알고리즘을 사용하기 위한 연구를 마무리하겠습니다.
워크플로우를 통해 복잡한 비즈니스 로직을 도식화 하는 경우에, 해당 워크플로우를 검증하기 위한 테스트케이스 추출과정을 수작업으로 진행하기에는 무리가 있습니다. 본 포스팅의 시도를 적용하면 예제에서 적용한 워크플로우 보다 더욱 복잡도 높은 워크플로우의 테스트 케이스 추출시에 유용하게 사용할 수 있을거라 예상됩니다.