그래프 구조를 직렬화하는 방법은 무엇입니까?

Question

플랫 파일과 관계형 데이터베이스는 구조화 된 데이터를 직렬화하는 메커니즘을 제공합니다. XML은 구조화되지 않은 트리와 유사한 데이터를 직렬화하는 데 적합합니다.

그러나 많은 문제가 그래프로 가장 잘 표현됩니다. 예를 들어, 열 시뮬레이션 프로그램은 저항 에지를 통해 서로 연결된 온도 노드와 함께 작동합니다.

그래서 그래프 구조를 직렬화하는 가장 좋은 방법은 무엇입니까? XML은 어느 정도까지는 관계형 데이터베이스가 객체의 복잡한 웹을 직렬화 할 수있는 것과 같은 방식으로 수행 할 수 있습니다. 일반적으로 작동하지만 쉽게 못 생길 수 있습니다.

graphviz 프로그램에서 사용하는 도트 언어에 대해 알고 있지만이 방법이 가장 좋은 방법인지 확신 할 수 없습니다. 이 질문은 아마도 학계가 진행하고있는 일종의 일일 것이며,이 문제를 논의하는 논문에 대한 언급을 원하고 싶습니다.

Answer 1

어떻게 그래프를 메모리에 나타 냅니까?

• an adjacency list representation
• 인접성 목록을 표현 최고의 스파 스 그래프 사용되는 an adjacency matrix representation

하고, 조밀 한 그래프의 행렬 표현 :
은 기본적으로 두 가지 (좋은) 옵션을 사용할 수 있습니다 .

이러한 표현을 사용한 경우에는 대신 이러한 표현을 직렬화 할 수 있습니다.

사람이 읽을 수있는이 인 경우에도 자신 만의 직렬화 알고리즘을 만들 수 있습니다.너무처럼 행과 열, 모든 데이터를 인쇄 :

1 2 3 
1 #t #f #f 
2 #f #f #t 
3 #f #t #f 

(이 비입니다 예를 들어, 당신은 당신이 어떤 "정상"매트릭스와 함께 할 것 같은 행렬 표현을 쓸 수 가중치가없는 표현이지만 방향성 그래프에 사용될 수 있음)

Answer 2

XML이 매우 상세합니다. 내가 할 때마다 나는 내 자신을 굴린다. 다음은 3 노드 지향 비순환 그래프의 예제입니다. 그것은 매우 컴팩트하고 내가이해야 할 모든 것을 수행합니다 우리가하고 XML에서 테스트를 직렬화 Xstream (자바)를 사용 CubicTest에 덜 학술 더 실용적인 노트에

0: foo 
1: bar 
2: bat 
---- 
0 1 
0 2 
1 2 

Answer 3

을. Xstream은 그래프 구조의 객체 관계를 처리하므로 원본과 결과 XML을보고 두 가지를 배울 수 있습니다. 당신은 추한 부분에 대해 맞지만, 생성 된 XML 파일은 꽤 보이지 않습니다.

Answer 4

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로 수행, 또는 다른 선호 직렬화 형식으로, 또는 인접 행렬로 할 수있는 노드와 엣지의 목록과 같다.

Answer 5

일반적으로 XML의 관계는 부모/자식 관계로 표시됩니다. XML은 그래프 데이터를 처리 할 수 ​​있지만 이런 식으로 처리 할 수는 없습니다. XML의 그래프를 처리하려면 xs:ID 및 xs:IDREF 스키마 유형을 사용해야합니다.

예를 들어 node/@ id가 xs : ID 유형이고/@ ref가 xs : IDREF 유형이라고 가정합니다. 다음 XML은 3 개의 노드 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도 지원합니다. 나는 바인딩 자바의 JAXB (자바 XML을 사용했다. 그것은 @XmlID과 @XmlIDREF 주석을 통해 다음을 지원합니다. 당신은 일반 자바 객체를 사용하여 그래프를 생성하고 XML로 실제 직렬화를 처리하기 위해 JAXB를 사용할 수 있습니다.

Answer 6

인접 목록과 인접성을 행렬은 메모리에서 그래프를 표현하는 두 가지 일반적인 방법입니다.이 두 가지를 결정할 때 가장 먼저해야 할 결정은 최적화하려는 것입니다. 예를 들어 인접 목록은 매우 빠르게 나타납니다. 반면에 에지 존재에 대해 많은 테스트를하거나 마크 로프 체인의 그래프 표현을 사용한다면 인접 매트릭스를 선호 할 것입니다.

다음 질문은 고려해야 할 점은 당신이 얼마나 기억에 적합해야하는지입니다. 대부분의 경우 그래프의 가장자리 수가 가능한 전체 가장자리 수보다 훨씬 작은 경우 실제로 존재하는 가장자리 만 저장하면되므로 인접성 목록이 더 효율적입니다. 행복한 매체는 인접한 행렬을 압축 된 희소 행 형식으로 표현하는 것입니다.이 형식에서는 0이 아닌 항목의 벡터를 왼쪽 상단에서 오른쪽 하단으로 유지하고, 해당 벡터는 0이 아닌 항목을 찾을 수있는 열을 나타냅니다. 열 입력 벡터에서 각 행의 시작을 나타내는 세 번째 벡터.

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] 

압축 희소 행에 인접리스트는 (열 인덱스가 동일한 방식으로 작동) 유효하지만 형식은 행렬 연산을 좀 더 명확하게라는 것으로 :

[[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]] 

같이 표현 될 수있다.