그래프를 XML로 표현하기

Question

안녕하세요 XML로 그래프를 표현하는 최선의 방법은 노드가 부모 노드의 자식 일 수 있고 다른 자식 노드의 부모 일 수 있습니다. 그것은 자신을 참조 할 수 있으며 여러 노드가 동일한 부모를 가질 수 있습니다. 노드에는 여러 개의 부모가있을 수 있습니다. 모든 노드는 같은 클래스의 노드입니다. 효율적으로 구축하여 부모 노드에서 자식 노드를 배울 수 있다면 모든 노드를 반복하지 않고도 특정 자식 태그로 이동할 수 있습니다. 가능한가? 여기 예를 들어 는

A->B,C,D 

B->C,D 

그것은

<Node name=A> 
<childNode name=B> 
<childNode name=C> 
<childNode name=D> 
</Node> 

<Node name=B> 
<childNode name=C> 
<childNode name=D> 
</Node> 

그래서 이것보다 더 좋은 방법이있는 것처럼 보일 수 있습니다, 개요인가? 즉 B에서 자식을 얻을 때마다 기본적으로 모든 노드를 반복하고 이름 속성을 B와 일치시켜 B를 나타내는 노드를 찾습니다. 어떻게 든 더 빨리 할 수 ​​있습니까?

Answer 1

처음으로 생각한 그래프가 아니기 때문에 GraphML을 사용하지 않으시겠습니까?

GraphML은 그래프를위한 포괄적이고 사용하기 쉬운 파일 형식입니다. 은 그래프의 구조적 속성을 설명하는 언어 코어와 응용 프로그램 관련 데이터를 추가하는 유연한 확장 메커니즘으로 구성됩니다.

그래프의 다른 많은 파일 형식과 달리 GraphML은 사용자 지정 구문을 사용하지 않습니다. 대신 XML을 기반으로하므로 을 생성하거나 보관하는 모든 종류의 서비스 또는 처리 그래프에 대해 공통으로 사용하는 것이 가장 적합합니다 ( ).

Answer 2

글쎄, 내가 완전히 당신의 문제를 이해한다고 말할 수는 없지만 XML 파일에서 높은 수준의 언어로 (지시 된) 그래프를 재구성하려고한다고 생각한다. 고수준 언어로 어떤 표현을 사용했는지 알면 도움이 될 것입니다. 또는 실제로 언어. 가정 C + + 및 인접 목록 :

나는 map<string, Node*>을 먼저 만들고 노드에 이름을 매핑합니다. 내 XML 모양은 다음과 같습니다.

이것은 다소 콤팩트한데, 나는 항상 좋은 SAX 파서로 구문 분석 할 수 있습니다. 그렇지 않으면, 내가 그들을 저장 : 모두 끝 노드가 맵에 일단

if(mapping.find(from) == map.end()) map.insert(make_pair(from, new Node())); 
if(mapping.find(to) == map.end()) map.insert(make_pair(to, new Node())); 

, 우리가 가장자리를 추가 할 수 있습니다 내가 가장자리를 순차적으로 읽을 때, 나는 이미 내지도에서 노드가 있는지 확인 :

mapping[from]->add_egde_to(mapping[to]); 

구문 분석이 완료되면지도에 노드가 있으며 이름순으로 정렬됩니다.

어쨌든, 당신에게 아이디어를 줄 수있는 graph representations에 관한 Wikipedia의 요약을보고 싶을 수도 있습니다.