동적 생성은 파이썬과 Networkx

Question

의 조건은 I 노드의 목록을 가지고 : 내가 어떤 그래프를 만들하려는

n = [a1, a2, a3, a4, b1, b2, b3, b4] 

, 이는 두 개의 임의의 노드를 선택하고 내가 nx.shortest_path을 것이다 찾은 후 트리플의 모든 조합을 얻을 :

comb = [[A, A, A], [A, A, B], [A, B, A], [A, B, B], [B, A, A], [B, A, B], [B, B, A], [B, B, B]] 

경우 A 및 B 노드 a1, a2, a3, a4, b1, b2, b3, b4의 대응이다.

예를 들어, 알고리즘은 나를 위해 노드 사이의 경로를 생성하는 경우 : 다음

(a1, b1), (a2, a3), (a3, a4), (a3, b1), (b1, b2), (b2, b3) 

:

nx.shortest_path(g, a2, a4) == (a2, a3, a4), as a case representation (A, A, A) 
nx.shortest_path(g, a2, b1) == (a2, a3, b1), as a case representation (A, A, B) 
nx.shortest_path(g, a3, a1) == (a3, b1, a1), as a case representation (A, B, A) 

and so on all combinations with 'comb'. 

어떻게 당신이 알고리즘 측면에서 걸릴 것입니까?

Answer 1

몇 가지 아이디어와 부분적인 해결책.

그래프에서 방향이 지정되지 않은 것으로 보입니다.이 경우 꼭지점 X와 Y 사이의 최단 경로가 세 줄 (A, A, B)을 생성하면 Y와 X 사이의 최단 경로보다 삼중 항 (B, A, A).

아이디어는 방향에 관계없이 모든 세 쌍을 연속 된 문자로 포함하는 문자열부터 시작하는 것입니다. 삼중 항의 경우 AAABABBB 문자열입니다. 이제 A와 B를 다른 a와 b로 대체 할 수 있습니다. 그래프를 생성합니다 :

a1 - a2 - a3 - b1 - a4 - b2 - b3 - b4 

이 그래프는 조건을 만족합니다.

세 쌍둥이의 경우 우리는 초기 문자열을 대체하기에 충분한 노드가 있다는 행운이있었습니다. 노드가 충분하지 않은 경우 상위 그래프 노드를 병합하여 필요한 노드 수를 줄일 수 있습니다. 병합은 동일한 유형 (A 또는 B)의 두 노드 사이에서 이루어 지므로 길이가 < 2 * size_of_substrings - 1 인 루프를 생성하지 않습니다. 3 중 루프의 경우 루프 길이가 5 이상일 수 있습니다. 상위 문자열 (AAABABBB)의 경우 distance> = 5 인 동일한 유형의 노드가 없습니다. 루프에 대한 제약 조건은 노드 사이에 새로운 최단 경로를 생성하지 않는 것입니다.

길이가 4 인 하위 문자열로 사례를 검사하십시오. 초기 문자열 AAAABBAABABBAABBBB보다 큽니다. A 또는 B를 거리> = 7에 병합 할 수 있습니다. 예 : 첫 번째 A를 중간에 단일 A와 병합합니다. -> B

/-------\ 
AAAABBAAB 
| 
BBAABBBB 

참고 초기 스트링이 < 교환에 의해 대칭되어야한다 : 즉, 그래프를 생성한다. A의 동일한 감소로 반대 B를 줄일 수 있습니다.