Efficient representation of edges in a C++ graph structure

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 - ie 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.

---

I don't see a problem with the usual object oriented approach, here. Have your Edge<V,E> and Vertex<V,E> types where V is the content stored by vertices and E is the content stored by edges. Each edge has two references to its respective vertices and two indices that say at which slot in the respective vertex to look for this edge:

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;
};

If you remove an edge e , you go Vertex<V,E>::edges and move the position at the back to the previous position of e . Constant time removal. Linear time (in the size of the operation's result) for enumerating all adjacent edges to a particular edge. Sounds good to me.

---

Does something like this seem plausible? This stores edge adjacency:

#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;

It seems like you kind of want to map edges to vertices, and then use something pretty standard.

链接地址: http://www.djcxy.com/p/52374.html

上一篇: 将关于无向图边的数据存储在数据库中

下一篇: 在C ++图形结构中高效地表示边