Networkx라는 그래프에 관련된 훌륭한 라이브러리가 있습니다.
이 라이브러리에 관련된 여러 글들을 인터넷에서 찾아보고 지금 진행하고 있는 Cable Auto Routing에 적용할 수 있다는 것을 알게되었습니다.
Cable Auto Routing은 두 장치를 연결하는 Cable의 최단 경로를 자동으로 찾는 것입니다.
Networkx의 shortest_path라는 함수를 이용하여 출발 노드에서 종료 노드에 도달하는 최단 경로를 구할 수 있습니다.
$$path = \text{nx.dijkstra_path}(G, \text{start_node}, \text{end_node}, weight)$$
아마 shortest_path 함수도 내부적으로 dijkstra 알고리즘을 사용할 것 같습니다.
Cable Auto Routing 프로젝트에서 dijkstra 알고리즘을 직접 구현하여 문제를 해결할 수도 있겠지만 이미 검증된 라이브러리를 사용하는 편이 훨씬 효율적이고(알고리즘 구현에 시간을 낭비할 필요가 없습니다.) 안전할것 입니다.
이 라이브러리를 Cable Auto Routing에 적용하기 전에 기능 테스트를 위한 데모 프로그램을 작성하기로 하였습니다.
데모 프로그램은 아래와 같은 기능을 가집니다.
- 최단 거리 검색
- 노드 생성
- 에지 생성
- 노드, 에지 정보를 파일로 저장 및 저장된 파일 읽어오기
Open 툴바를 눌러 노드와 에지 정보가 저장된 Json 파일을 읽습니다.
Networkx 툴바를 누르면 Networkx 관련 다이얼로그가 나타납니다.
Find 버튼을 눌러 사용자가 입력한 출발 노드에서 종료 노드까지의 최단 경로를 검색합니다.
 |
| 결과 화면(노란색이 최단 경로) |
노드를 생성할때 노드 이름과 3D 좌표를 입력합니다.
에지는 에지를 구성하는 두 노드 이름과 에지의 길이를 입력하도록 하였습니다. 에지의 길이는 에지를 구성하는 두 노드간의 거리를 부여하면 되지만 직선이 아닌 에지를 고려하여 사용자가 길이를 입력할 수 있도록 하였습니다.
Calc 버튼을 누르면 두 노드간의 직선 거리를 계산하여 Weight을 입력합니다.
Cable Way2의 Weight는 두 노드의 직선거리가 아니라 두 노드를 연결하는 곡선의 길이가 됩니다.
Add 버튼을 누르면 그래프에 에지를 추가합니다.
$$G.\text{add_edge}(\text{start_node}, \text{end_node}, weight)$$
노드와 에지 정보들은 Json 형식으로 파일로 저장하였습니다.
Save 버튼을 누르면 노드와 에지 정보들을 파일로 저장할 수 있습니다.
데모 프로그램에서는 VTK를 이용하여 그래프를 3D로 표현하였습니다.
Networkx는 Python으로 개발된 라이브러리이며 따라서 데모 프로그램으로 Python(PyQt5)으로 개발하였습니다.
Networkx는 순수 Python 라이브러리이기 때문에 C#에서 직접 사용할 수 없습니다.
하지만 Python에서 실행 파일을 만들고 C#에서 실행 파일을 실행 후 그 결과를 구할수 있습니다.
- private void run_cmd(string cmd, string args)
- {
- ProcessStartInfo start = new ProcessStartInfo();
- start.FileName = cmd;
- start.Arguments = args;
- start.UseShellExecute = false;
- start.RedirectStandardOutput = true;
- using (Process process = Process.Start(start))
- {
- using (StreamReader reader = process.StandardOutput)
- {
- string result = reader.ReadToEnd();
- Console.Write(result);
- }
- }
- }
데모 프로그램은 여기서 다운받을 수 있습니다.
샘플 Json 파일(networkx.json)을 포함하고 있습니다.
댓글
댓글 쓰기