{"id":491,"date":"2007-08-15T14:37:25","date_gmt":"2007-08-15T14:37:25","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/08\/15\/representing-graphs\/"},"modified":"2007-08-15T14:37:25","modified_gmt":"2007-08-15T14:37:25","slug":"representing-graphs","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/08\/15\/representing-graphs\/","title":{"rendered":"Representing Graphs"},"content":{"rendered":"

One of the reasons that I like about graph theory so much is because of
\nhow it ties into computer science. Graphs are fundamental to many problems in
\ncomputer science, and a lot of the work in graph theory has direct implications for
\nalgorithm design. It also has a lot of resonance for me, because the work I do involves
\ntons and tons of graphs: I don’t think I’ve gotten through a week of work in the last decade without
\nimplementing some kind of graph code.<\/p>\n

Since I’ve described a lot of graph algorithms, and I’m going to
\ndescribe even more, today I’m going to talk a bit about how to represent graphs
\nin programs, and some of the tradeoffs between different representations.<\/p>\n

<\/p>\n

There are two different basic graph representations: matrix-based representations, and list
\nbased representations.<\/p>\n

The matrix-based representation is called an adjacency matrix<\/em>. For a graph G with N nodes, an adjacency matrix is an N×N matrix of true\/false values, where entry [a,b] is true if and only if there is an edge between a and b. If G is an undirected graph, then the matrix is (obviously)
\nsymmetric: [a,b]=[b,a]. If the graph is directed, then [a,b]=true means that there is an edge from<\/em> a to<\/em> b.<\/p>\n

\"graph-rep-ex.png\"<\/p>\n

As usual, things are clearer with an example. So, over the right, we have a simple
\nten node undirected graph, with vertices A through J. Right below, there’s a 10×10 boolean
\ntable showing how the graph would be represented as an adjacency matrix. In the matrix,
\na value of “1” in a cell means that there’s an edge connected the corresponding vertex indices; a “0” indicates that there is not. <\/p>\n

represented as an adjacency matrix.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
<\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\n<\/tr>\n
A<\/th>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
B<\/th>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
C<\/th>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
D<\/th>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n<\/tr>\n
E<\/th>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
F<\/th>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
G<\/th>\n0<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
H<\/th>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
I<\/th>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
J<\/th>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/table>\n

The list-based representation, commonly called an adjacency list<\/em>, has a list for each vertex in the graph. For
\na vertex v, that list contains identifiers for the vertices which are adjacent to v. So again for our example:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
Vertex<\/th>\nNeighbors<\/th>\n<\/tr>\n
A<\/td>\nC <\/td>\n<\/tr>\n
B<\/td>\nF,G <\/td>\n<\/tr>\n
C<\/td>\nA,G <\/td>\n<\/tr>\n
D<\/td>\nG,I <\/td>\n<\/tr>\n
E<\/td>\nG,I,J <\/td>\n<\/tr>\n
F<\/td>\nB,G <\/td>\n<\/tr>\n
G<\/td>\nB,D,E,F,H,J <\/td>\n<\/tr>\n
H<\/td>\nG,I,J <\/td>\n<\/tr>\n
I<\/td>\nD,E,H <\/td>\n<\/tr>\n
J<\/td>\nE,G,H <\/td>\n<\/tr>\n<\/table>\n

A common optimization of the adjacency list is to use a data object to represent a vertex, and to use
\npointers\/references to vertex objects as the vertex identifiers in the adjacency list for a vertex. Depending
\non the application, the adjacency lists could be either arrays, linked lists, or some other similar structure.<\/p>\n

To give you some sense of what a simple bit of code looks like, here’s a pair of Python functions to check if two vertices x and y are
\nadjacent in a matrix. The first piece of code is for an adjacency matrix; the second for an adjacency list.<\/p>\n

\ndef IsAdjacentInMatrix(matrix, x, y):\nreturn matrix[x][y]\n<\/pre>\n
\ndef IsAdjacentInList(x, y):\nfor n in x.neighbors:\nif y == n:\nreturn true\nreturn false\n<\/pre>\n
When you’re writing a graph-based algorithm, choosing which representation – and which variation of which representation
\n– is one of your most important decisions. There’s no cut and dried correct answer: which representation is right is dependent on what you want to do, and what constraints you have. How fast you need things to be; how much memory you
\ncan afford to use; how big your graph is; how many edges you graph will have – all contribute to the choice of the best representation. <\/p>\n
The boolean adjacency matrix is very compact – you can get away with as little as N2<\/sup>\/2 bits of storage to
\nrepresent the edges in a graph. Certain algorithms – like transitive closure – are extremely efficient in the adjacency
\nmatrix. If you really only need to know the structure of the edges, and you don’t have other data that needs to be
\nassociated with the edges, then an adjacency matrix can be an extremely good choice. If your matrix is moderately sized,
\nyou can often get the entire adjacency matrix into the cache at once, which has a dramatic impact on performance.<\/p>\n
Even if you need to associate a little bit of information with an edge, that’s often easily doable using an adjacency
\nmatrix. For example, to represent a weighted graph, you can use the edge-weight as the value of the matrix entry if there
\nis an edge. (This does require that you be able to identify a value which will absolutely never be an edge weight, to use
\nto mark cells that are not edges. If you’re using floating point numbers for weight, then NaN is a good choice.) On the
\nother hand, if you have a very large matrix with very few edges, then an adjacency matrix will perform very poorly and
\nwaste an enormous amount of space. Consider a graph with 1 million vertices, and 1 million edges. That means that each
\nvertex has, on average, two edges – but you’re using one million bits per vertex. That’s very wasteful, and dealing with a
\nmatrix of 1012<\/sup> bits is not going to be particularly fast.<\/p>\n
 Using an adjacency list works much better if you have a sparse matrix – it only uses space for edges that are actually
\npresent in the graph. It’s also often easier to associate data with vertices and edges in a good way using adjacency lists;
\nand it can often produce better performance in that case as well, due to good locality. (When you traverse an edge in an
\nadjacency list using the pointer implementation described above, you’re pulling the vertex into your cache; then when you
\ngo to look at the data for the vertex, it’s hot in the cache. In an adjacency matrix, you’d use a separate table for that,
\nwhich would mean fetching from a different area of memory.)<\/p>\n
 The adjacency list is often better for certain kinds of graph traversals: if you need to walk through a graph
\ncollecting information about visited vertices, the locality properties of the adjacency list structure can have a great
\neffect on performance. But if you want to know something about connectivity, or simple pathfinding in a relatively dense
\ngraph, then the adjacency matrix is usually the right choice.<\/p>\n","protected":false},"excerpt":{"rendered":"
One of the reasons that I like about graph theory so much is because of how it ties into computer science. Graphs are fundamental to many problems in computer science, and a lot of the work in graph theory has direct implications for algorithm design. It also has a lot of resonance for me, because […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-491","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7V","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/491","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=491"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/491\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=491"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=491"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=491"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}