그래프 구조를 직렬화하는 방법은 무엇입니까?
https://stackoverflow.com/questions/51783
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
플랫 파일과 관계형 데이터베이스는 구조화된 데이터를 직렬화하는 메커니즘을 제공합니다.XML은 구조화되지 않은 트리형 데이터를 직렬화하는 데 탁월합니다.
그러나 많은 문제는 그래프로 가장 잘 표현됩니다.예를 들어 열 시뮬레이션 프로그램은 저항성 가장자리를 통해 서로 연결된 온도 노드에서 작동합니다.
그렇다면 그래프 구조를 직렬화하는 가장 좋은 방법은 무엇입니까?관계형 데이터베이스가 복잡한 개체 웹을 직렬화할 수 있는 것과 같은 방식으로 XML이 어느 정도 이를 수행할 수 있다는 것을 알고 있습니다.일반적으로 작동하지만 쉽게 추악해질 수 있습니다.
저는 graphviz 프로그램에서 사용하는 도트 언어에 대해 알고 있지만 이것이 최선의 방법인지는 잘 모르겠습니다.이 질문은 아마도 학계에서 연구하고 있는 종류의 문제일 것입니다. 이에 대해 논의하는 논문을 참고하고 싶습니다.
해결책
그래프를 메모리에 어떻게 표현하나요?
기본적으로 두 가지 (좋은) 옵션이 있습니다.
희소 그래프에는 인접 목록 표현이 가장 적합하고 조밀한 그래프에는 행렬 표현이 사용됩니다.
이러한 표현을 사용한 경우 대신 해당 표현을 직렬화할 수 있습니다.
꼭 그래야 한다면 사람이 읽을 수 있는 자신만의 직렬화 알고리즘을 생성하도록 선택할 수도 있습니다.예를 들어, "일반" 행렬을 사용하는 것처럼 행렬 표현을 작성할 수 있습니다.다음과 같이 열과 행, 그리고 그 안의 모든 데이터를 인쇄하세요.
1 2 3
1 #t #f #f
2 #f #f #t
3 #f #t #f
(이것은 최적화되지 않고 가중치가 적용되지 않은 표현이지만 유향 그래프에 사용될 수 있습니다)
다른 팁
일반적으로 XML의 관계는 상위/하위 관계로 표시됩니다.XML은 그래프 데이터를 처리할 수 있지만 이 방식으로는 처리할 수 없습니다.XML에서 그래프를 처리하려면 다음을 사용해야 합니다. xs:ID 그리고 xs:IDREF 스키마 유형.
예에서 node/@id는 xs:ID 유형이고 link/@ref는 xs:IDREF 유형이라고 가정합니다.다음 XML은 1 -> 2 -> 3 -> 1의 세 노드의 주기를 보여줍니다.
<data>
<node id="1">
<link ref="2"/>
</node>
<node id="2">
<link ref="3"/>
</node>
<node id="3">
<link ref="1"/>
</node>
</data>
많은 개발 도구는 ID 및 IDREF도 지원합니다.저는 Java의 JAXB(Java XML Binding.dll)를 사용했습니다.이를 통해 이를 지원합니다. @XmlID 그리고 @XmlIDREF 주석.일반 Java 객체를 사용하여 그래프를 작성한 다음 JAXB를 사용하여 XML에 대한 실제 직렬화를 처리할 수 있습니다.
XML은 매우 장황합니다.그럴 때마다 저는 직접 굴립니다.다음은 3노드 방향성 비순환 그래프의 예입니다.매우 컴팩트하며 필요한 모든 작업을 수행합니다.
0: foo
1: bar
2: bat
----
0 1
0 2
1 2
여러분에게 친숙할 수 있는 한 가지 예는 Java 직렬화입니다.이는 각 개체 인스턴스가 노드가 되고 각 참조가 가장자리가 되는 그래프로 효과적으로 직렬화됩니다.사용된 알고리즘은 재귀적이지만 중복을 건너뜁니다.따라서 의사 코드는 다음과 같습니다.
serialize(x):
done - a set of serialized objects
if(serialized(x, done)) then return
otherwise:
record properties of x
record x as serialized in done
for each neighbour/child of x: serialize(child)
물론 또 다른 방법은 XML이나 기타 선호하는 직렬화 형식 또는 인접 행렬로 수행할 수 있는 노드 및 가장자리 목록으로 사용하는 것입니다.
인접 목록과 인접 행렬은 메모리에서 그래프를 표현하는 두 가지 일반적인 방법입니다.이 두 가지 중에서 결정할 때 가장 먼저 내려야 할 결정은 최적화하려는 대상입니다.예를 들어 정점의 이웃 목록을 가져와야 하는 경우 인접 목록은 매우 빠릅니다.반면에 가장자리 존재에 대해 많은 테스트를 수행하거나 마르코프 체인의 그래프 표현이 있는 경우 아마도 인접 행렬을 선호할 것입니다.
고려해야 할 다음 질문은 메모리에 얼마나 들어가야 하는지입니다.대부분의 경우 그래프의 간선 수가 가능한 간선의 총 수보다 훨씬 작은 경우 실제로 존재하는 간선만 저장하면 되므로 인접 목록이 더 효율적입니다.좋은 매체는 0이 아닌 항목의 벡터를 왼쪽 위에서 오른쪽 아래로 유지하는 압축된 희소 행 형식으로 인접 행렬을 나타내는 것입니다. 해당 벡터는 0이 아닌 항목을 찾을 수 있는 열을 나타냅니다. 열 항목 벡터의 각 행의 시작을 나타내는 세 번째 벡터입니다.
[[0.0, 0.0, 0.3, 0.1]
[0.1, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.5, 0.2, 0.0, 0.3]]
다음과 같이 표현될 수 있습니다:
vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3]
cols: [2, 3, 0, 0, 1, 4]
rows: [0, 2, null, 4]
압축된 희소 행은 사실상 인접 목록(열 인덱스는 동일한 방식으로 작동함)이지만 형식은 행렬 연산에 좀 더 명확하게 적용됩니다.
