Using std::map and std::pair to store attributes at graph edges in C++

Alec Jacobson

February 10, 2011

weblog/

I've been really battling with my old code in which I stored a graph by keeping a list of vertices and each vertex kept track of its neighbors. This is fine until you want to store attributes at the graph's edges. My solution is to store the edges in a std::map that is indexed by a pair of vertices. Here's a boiled-down example. For know my "vertices" are just represented as ints (their indices, for example). And I just want to store a single string at each edge (i,j). But you could change these to be their own structs or classes. I've also tried not to get too fancy with the overloading and extending the std::pair class which I use as a key. It's possible to do all sorts of tricks but this is the bare bones. Save this in a file called edge_map.cpp:

#include <map>
#include <string>
#include <cstdio>

// Make a short name for the edge map's key
typedef std::pair<int,int> EMK;
// Make a short name for the type stored at each edge, the edge map's value
typedef std::string EMV;
// Make a short name for the edge map
typedef std::map<EMK,EMV> EdgeMap;

int main()
{
  // Store some edges with values
  EdgeMap edge_map;
  edge_map[EMK(1,2)] = "Purple";
  edge_map[EMK(2,3)] = "Blue";
  edge_map[EMK(2,4)] = "Yellow";
  edge_map[EMK(2,5)] = "Red";
  edge_map[EMK(5,3)] = "Green";

  printf("Edge map contents:\n");
  // Loop over edges in edge_map
  for(
    EdgeMap::const_iterator emit = edge_map.begin();
    emit != edge_map.end();
    emit++)
  {
    printf("(%d,%d) %s\n",
      emit->first.first,
      emit->first.second,
      emit->second.c_str());
  }

  printf("\n");

  printf("Test for edges:\n");
  // Edge queries
  printf("(%d,%d): %s\n",1,3,(edge_map.count(EMK(1,3)) == 0 ? "No" : "Yes"));
  printf("(%d,%d): %s\n",1,5,(edge_map.count(EMK(1,5)) == 0 ? "No" : "Yes"));
  printf("(%d,%d): %s\n",1,2,(edge_map.count(EMK(1,2)) == 0 ? "No" : "Yes"));

  return 0;
}

Compile with:

g++ edge_map.cpp -o edge_map

And the running ./edge_map should print:

Edge map contents:
(1,2) Purple
(2,3) Blue
(2,4) Yellow
(2,5) Red
(5,3) Green

Test for edges:
(1,3): No
(1,5): No
(1,2): Yes

Note: With fancy operator overloading I think its possible to store an undirected graph so that queries in either direction return correctly (the above code is good for directed graphs or where the caller manages the "undirectedness").