5

I am planning on representing a fairly large, sparse, undirected graph structure in C++. This will be of the order of 10,000+ vertices, with each vertex having a degree of around 10.

I have read some background on representing graphs as adjaciency matrices or lists, but neighther of them seem suitable for what I want to do. In my scenario:

  • Each edge in the graph will have some properties (numeric values) attached
  • After the initial graph creation, edges can be deleted, but never created
  • Vertices will never be created or deleted
  • The main query operation on the graph will be a lookup, for an edge E, as to which other edges are connected to it. This is equivalent to finding the edges connected to the vertices at each end of E.

It is this final point which makes the adjacency matrix seem unsuitable. As far as I can see, each query would require 2*N operations, where N is the number of nodes in the graph.

I believe that the adjacency list would reduce the required operations, but seems unsuitable because of the parameters I am including with each edge - i.e. because the adjacency list stores each

Is there a better way to store my data such that these query operations will be quicker, and I can store each edge with its parameters? I don't want to start implementing something which isn't the right way to do it.

4

2 回答 2

7

在这里，我认为通常的面向对象方法没有问题。让您的Edge<V,E>和Vertex<V,E>类型V顶点存储的内容在哪里E，边存储的内容在哪里。每条边都有两个对其各自顶点的引用和两个索引，它们表示在各自顶点的哪个槽中查找该边：

template <typename V, typename E>
class Edge {
  struct Incidence {
    size_t index;
    Vertex<V,E>& v;
  };
  std::array<Incidence,2> vertices;
  E content;
};

template <typename V, typename E>
class Vertex {
  std::vector<Edge<V,E>*> edges;
};

如果删除一条边e，Vertex<V,E>::edges则将 的位置移动back到 的上一个位置e。恒定时间去除。将所有相邻边枚举到特定边的线性时间（在操作结果的大小中）。听起来不错。

于 2012-09-06T17:34:30.457 回答
1

这样的事情看起来可信吗？这存储边缘邻接：

#include <vector>
#include <map>

typedef int vertex;

struct edge
{
    vertex a,b;
    // other data
};

bool operator< (const edge &a, const edge &b)
{
    unsigned long long ahash = a.a;
    ahash << 32;
    ahash |= a.b;
    unsigned long long bhash = b.a;
    bhash << 32;
    bhash |= b.b;
    return ahash < bhash;
}

// support for your query operation
typedef std::map<edge, std::vector<edge &> > edge_adjacency;

看起来你有点想将边缘映射到顶点，然后使用一些非常标准的东西。

于 2012-09-06T17:23:02.077 回答