与えられたグラフを等価形式に効率的に縮小して表現する方法は？

Question

私は、stlを使ってC++で（見かけ上単純な）無向グラフ表現に苦労しています。 次のように通常は、私はベクトルの単純な配列を使用してグラフを保存します：

#include <iostream> 
#include <vectors> 
#define NODES 10 
using namespace std; 

int main(){ 
    vector<pair<int, int>> graph[NODES]; 
    int u,v, weight; 

    for(int i=0;i<10;i++){ 
     cin>>u>>v>>weight; 
     graph[u].push_back(make_pair(v,weight)); 
     graph[v].push_back(make_pair(u,weight)); 
    } 

    return 0; 
} 

をしかし、私はそれが困難な以下のシナリオのグラフを保存するために探しています：では

上のグラフでは、私は2種類のエッジaとbを持っています。端に隣接する頂点bは、同等のものと見なされます。したがって、これらの2つの頂点（この場合は2 & 6）は同等であり、それらをマージして1つとして表現する必要があります。

はしたがって、私は以下に示すように上記のグラフを削減し、格納したい：

注：削減しながら、時にはそれがいくつかのプロパティを侵害することが起こるかもしれません。エッジ1-6と2-6両方ラベルbと1-2を持っている場合、例えば、維持する一つのaは、それが曖昧になるラベルを有します。そのようなシナリオでは、グラフを検出してグラフが有効でないことを報告するにはどうすればよいですか？ベクトルの二つの配列は、その後、クロスチェックのようなものがそうであるように

これまでのところ、私はaとbラベルを格納することを考えていますが別々にエッジ。しかし、これはコード作成が非常に複雑で非常に面倒で、おそらくコード全体の複雑さが増します。

ご協力いただければ幸いです。ありがとう。

Answer 1

あなたは縁が、それが接続する2つの頂点ことをより多くの情報を持っているしたいので、あなたのようにエッジを定義することができます。

enum edge_type {a, b}; 
struct edge { 
    int v1; 
    int v2; 
    edge_type etype; 
} 

そして、このようなあなたのグラフを表す：

vector<edge> graph[NODES];