2
이 그래프 고려해그래프의주기 균형을 유지하는 방법은 무엇입니까?
(괄호 무게) 번째 이미지 "균형"는, 즉 각 노드가 다른 노드로 중량의 적당한 양을 보낸다, 그리고 엔드 노드가 동일한 갖는다 가중치를 시작 노드로 사용합니다.
이제 그래프가 비어 있다고 가정 해 봅니다 (가장자리는 다른 노드로 보내지는 % 가중치를 알고 있지만 그래프에는 아직 가중치가 없습니다). 시작 노드에 20의 가중치를두면 두 번째 이미지에 표시된 것과 같이 최종 그래프가 균형을 이루도록 어떻게 만들 수 있습니까? 모든 노드에서 가중치가 일정해질 때까지 반복적으로 그래프를 업데이트해야하지만, 가장 좋은 방법은 무엇입니까?
편집 : 다음은 내가 도움을 줄 수있는 프로젝트에서이 문제와 관련된 Java 코드입니다. 이 코드에 사용 된 일부 기능에 대한 정보는 없지만 큰 그림을 얻는 것이 좋습니다.
참고 :
nb_stations : 많은 변수 이름이 여기에 프랑스에있는 그들 중 일부에 대한 빠른 번역 한 것입니다 노드의 양
m_listeStations : 모든 노드
ID_ARRIVEE의 목록 : 시작 노드의 ID (" 그래프
POIDS : "
RESEAU) 그래프에서 시작 무게
호 : 귀하의 그래프는로 무엇 알려져있다
// build the distribution matrix
public float[] buildDistribution() {
int nb_stations = m_listeStations.size();
float[] distribution = new float[nb_stations];
Arrays.fill(distribution, 0);
distribution[findIndexStation(findStation(Reseau.ID_ARRIVEE))] = findStation(Reseau.ID_ARRIVEE).getPoids();
return distribution;
}
// build the transition matrix
public float[][] buildTransition() {
int nb_stations = m_listeStations.size();
float[][] transition = new float[nb_stations][nb_stations];
for (float[] ligne : transition) {
Arrays.fill(ligne, 0);
}
for (int i = 0; i < nb_stations; ++i) {
List<Arc> arcsOut = m_listeStations.get(i).getArcsOut();
for (int j = 0; j < arcsOut.size(); ++j) {
transition[i][findIndexStation(arcsOut.get(j).getCible())] = arcsOut.get(j).getPoidsRelatif();
}
}
int indexArrivee = findIndexStation(findStation(Reseau.ID_ARRIVEE));
transition[indexArrivee][indexArrivee] = 1; // arrivée continuelle
return transition;
}
// this function does one iteration of distribution*transition to converge toward the real weights
public float[] convergeDistribution(float[] in_distribution, float[][] in_transition) {
int nb_stations = m_listeStations.size();
float[] converge = new float[nb_stations];
Arrays.fill(converge, 0);
for (int i = 0; i < nb_stations; ++i) {
for (int j = 0; j < nb_stations; ++j) {
converge[i] += in_distribution[j] * in_transition[j][i];
}
}
return converge;
}