Geek asks and answers

Efficient representation of edges in a C ++ graph structure

I plan to introduce a rather large, rare, non-directional chart structure in C ++. This will be of the order of 10,000 + vertices, each of which has a degree of about 10.

I read some background for representing graphs as adjacency matrices or lists, but they are more suitable for what I want to do. In my scenario:

  • Each edge in the graph will have some properties (numerical values) attached
  • After creating the initial graph, edges can be deleted, but never created.
  • Vertices will never be created or deleted.
  • The main query operation on the chart will search for edge E, to which other edges are attached to it. This is equivalent to finding edges associated with vertices at each end of E.

It is this endpoint that makes the adjacency matrix unusable. As far as I can tell, for each request, 2 * N operations will be required, where N is the number of nodes in the graph.

I believe that the adjacency list will reduce the required operations, but seems unsuitable due to the parameters that I include with each edge, i.e. because the adjacency list saves each

Is there a better way to store my data so that these query operations are faster and I can store each edge with its parameters? I do not want to start implementing something that is not suitable for this.

+5
source share
2 answers

- . 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. . ( ) . .

+7

- ? :

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

, , - .

+1

More articles:


All Articles