title: Efficient representation of edges in a C++ graph structure
body: <p>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.</p>
  
  <p>I have read some <a href="http://www.algolist.net/Data_structures/Graph/Internal_representation">background</a> on representing graphs as adjaciency matrices or lists, but neighther of them seem suitable for what I want to do. In my scenario:</p>
  
  <ul>
  <li>Each edge in the graph will have some properties (numeric values) attached</li>
  <li>After the initial graph creation, edges can be deleted, but never created</li>
  <li>Vertices will never be created or deleted</li>
  <li>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.</li>
  </ul>
  
  <p>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.  </p>
  
  <p>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 </p>
  
  <p>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.</p>