Java의 Max-Flow 그래프 시뮬레이션

Question

나는 각 팀의 현재 플레이된 게임 세트와 다음 게임의 일정을 검토하는 리그 스포츠용 Java 프로그램을 작성하고 이를 기반으로 플로우 네트워크 모델을 만듭니다.프로그램의 아이디어는 이미 탈락하여 승리할 가능성이 없거나 다른 팀과 한 자리를 공유할 가능성이 없는 팀을 찾는 것입니다.네트워크를 분석한 후(EdmondsKarp 알고리즘 적용) 팀이 탈락할지 여부를 알아냅니다.이제 나는 이것을 시뮬레이션하고 싶습니다.저는 JGraphT를 그래프 라이브러리로 사용하고 있으며 아마도 시각화를 위해 JGraph를 사용할 것입니다(이유:JGraphT 개체를 생성하면 JGraph 개체를 간단히 인스턴스화하고 그래프를 표시할 수 있습니다.저도 어제 Jung Framework에 대해 알아봤는데 좋은 것 같습니다.

가장 큰 문제는 시뮬레이션을 작성한 적이 없으며 "Hello World" 도움이 필요한 지점입니다.시뮬레이션이라고 하면 알고리즘 실행의 모든 ​​부분을 시각적으로 보여주고 싶다는 뜻입니다. 여기에 예제 시나리오가 있습니다.알고리즘은 증대 경로를 찾아야 하므로 모든 새로운 가장자리가 증대 경로에 추가되는 시기를 표시하고 싶습니다.사용자는 애니메이션을 재생하고 중지할 수 있습니다.또한 모든 가장자리 등의 흐름 변화를 보여주고 싶습니다.지금까지 알고리즘이 작동하고 있지만 시뮬레이션에 접근하는 방법을 모르겠습니다.시뮬레이션 실행을 위해 별도의 스레드를 사용해야 합니까?알고리즘으로 실행되지만 실제 알고리즘에 대한 지식도 없이 상태를 기록하는 별도의 클래스를 작성해야 할까요(실제 알고리즘의 성능을 방해하고 싶지 않기 때문입니다).현재 알고리즘을 사용하고 나중에 사용자에게 시뮬레이션을 표시하기 위해 사용할 수 있는 일부 데이터 구조의 실행 상태를 저장하기 위해 몇 줄을 추가해야 합니까?어떤 아이디어라도 도움이 될 수 있습니다.

Answer 1

내가 당신을 올바르게 이해한다면 당신은 방법을 묻는 것입니다. 생기 있게 하다 알고리즘을 실행하고 애니메이션 내에서 대화형으로 실행을 제어합니다. 이는 시뮬레이션과 완전히 다릅니다(시뮬레이션은 일반적으로 주어진 시간 간격에 걸쳐 모델을 실행합니다. 이는 사용자 상호 작용이나 애니메이션과는 아무 관련이 없지만 물론 가능합니다. 둘 다와도 결합됩니다).

문제를 상호 작용과 애니메이션이라는 두 가지 주요 부분으로 나누는 것이 좋습니다.둘 다 다음을 적용하여 해결할 수 있습니다. 모델 뷰 컨트롤러 접근하다:

• 알고리즘과 상호 작용하려면 구별하려는 '원자적 단계'를 식별하십시오.경로에 가장자리를 추가하는 것입니다.그런 다음 알고리즘을 확장하여 단계별로 작업하거나 알고리즘을 래핑하고 단계별 실행에 필요한 루틴을 제공하는 추가 클래스를 작성합니다.

• 알고리즘의 현재 상태를 애니메이션하려면 다음을 사용해야 합니다. 관찰자 패턴, 여기서 애니메이션 구성 요소는 관찰자이며 상태가 변경될 때마다 알고리즘에 의해 알림을 받습니다.경로에 가장자리가 추가되었습니다.또한 다음을 전달하여 실제 상태 변경을 설명할 수도 있습니다. 힌트 (예: 경로에 추가된 가장자리 개체)이렇게 하면 이전 상태와 새 상태의 차이를 더 쉽게 시각화할 수 있습니다.

스레딩 관련 질문:알고리즘은 아마도 추가 스레드에서 실행되어야 하며(매우 빠르지 않는 한) 애니메이션을 추가 스레드에 넣을 수도 있습니다(어차피 JGraph에서 이미 제공했을 수도 있습니다. 문서를 확인하거나 해당 구성 요소를 권장대로 사용하십시오).그러나 알고리즘의 런타임 성능은 애니메이션의 영향을 받는 것이 거의 확실하다는 점에 유의해야 합니다. ~이다 다른 스레드에서 실행 중(알림은 여전히 ​​알고리즘에 의해 수행되어야 하기 때문에) - 성능 분석에 주의하고 그러한 연구에는 애니메이션이 없는 버전을 사용하십시오.