diff --git a/SConstruct b/SConstruct
index 38ae3f1..0f600a2 100644
--- a/SConstruct
+++ b/SConstruct
@@ -93,6 +93,7 @@
                    filesystem_copier_action.cc
                    filesystem_iterator.cc
                    file_writer.cc
+                   graph_utils.cc
                    gzip.cc
                    libcurl_http_fetcher.cc
                    omaha_hash_calculator.cc
@@ -117,6 +118,7 @@
                             file_writer_unittest.cc
                             filesystem_copier_action_unittest.cc
                             filesystem_iterator_unittest.cc
+                            graph_utils_unittest.cc
                             gzip_unittest.cc
                             http_fetcher_unittest.cc
                             mock_http_fetcher.cc
diff --git a/graph_types.h b/graph_types.h
new file mode 100644
index 0000000..afb7f64
--- /dev/null
+++ b/graph_types.h
@@ -0,0 +1,53 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__
+
+#include <map>
+#include <set>
+#include <utility>
+#include <vector>
+#include "base/basictypes.h"
+#include "update_engine/update_metadata.pb.h"
+
+// A few classes that help in generating delta images use these types
+// for the graph work.
+
+namespace chromeos_update_engine {
+
+struct EdgeProperties {
+  std::vector<Extent> extents;  // filesystem extents represented
+};
+
+struct Vertex {
+  Vertex() : index(-1), lowlink(-1), op(NULL) {}
+  typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
+  EdgeMap out_edges;
+
+  // We sometimes wish to consider a subgraph of a graph. A subgraph would have
+  // a subset of the vertices from the graph and a subset of the edges.
+  // When considering this vertex within a subgraph, subgraph_edges stores
+  // the out-edges.
+  typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
+  SubgraphEdgeMap subgraph_edges;
+
+  // For Tarjan's algorithm:
+  std::vector<Vertex>::size_type index;
+  std::vector<Vertex>::size_type lowlink;
+
+  // Other Vertex properties:
+  DeltaArchiveManifest_InstallOperation* op;
+
+  typedef std::vector<Vertex>::size_type Index;
+  static const Vertex::Index kInvalidIndex = -1;
+};
+
+typedef std::vector<Vertex> Graph;
+
+typedef std::pair<Vertex::Index, Vertex::Index> Edge;
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__
diff --git a/graph_utils.cc b/graph_utils.cc
new file mode 100644
index 0000000..79d5733
--- /dev/null
+++ b/graph_utils.cc
@@ -0,0 +1,41 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/graph_utils.h"
+#include "base/basictypes.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace graph_utils {
+
+uint64 EdgeWeight(const Graph& graph, const Edge& edge) {
+  uint64 weight = 0;
+  const vector<Extent>& extents =
+      graph[edge.first].out_edges.find(edge.second)->second.extents;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    weight += it->num_blocks();
+  }
+  return weight;
+}
+
+void AppendBlockToExtents(vector<Extent>* extents, uint64 block) {
+  if (!extents->empty()) {
+    Extent& extent = extents->back();
+    if (extent.start_block() + extent.num_blocks() == block) {
+      extent.set_num_blocks(extent.num_blocks() + 1);
+      return;
+    }
+  }
+  Extent new_extent;
+  new_extent.set_start_block(block);
+  new_extent.set_num_blocks(1);
+  extents->push_back(new_extent);
+}
+
+}  // namespace graph_utils
+
+}  // namespace chromeos_update_engine
diff --git a/graph_utils.h b/graph_utils.h
new file mode 100644
index 0000000..62ecfd5
--- /dev/null
+++ b/graph_utils.h
@@ -0,0 +1,31 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_UTILS_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_UTILS_H__
+
+#include <vector>
+#include "base/basictypes.h"
+#include "update_engine/graph_types.h"
+#include "update_engine/update_metadata.pb.h"
+
+// A few utility functions for graphs
+
+namespace chromeos_update_engine {
+
+namespace graph_utils {
+
+// Returns the number of blocks represented by all extents in the edge.
+uint64 EdgeWeight(const Graph& graph, const Edge& edge);
+
+// block must either be the next block in the last extent or a block
+// in the next extent. This function will not handle inserting block
+// into an arbitrary place in the extents.
+void AppendBlockToExtents(std::vector<Extent>* extents, uint64 block);
+
+}  // namespace graph_utils
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_UTILS_H__
diff --git a/graph_utils_unittest.cc b/graph_utils_unittest.cc
new file mode 100644
index 0000000..d947ddd
--- /dev/null
+++ b/graph_utils_unittest.cc
@@ -0,0 +1,41 @@
+// Copyright (c) 2009 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <utility>
+#include <vector>
+#include <gtest/gtest.h>
+#include "update_engine/graph_utils.h"
+
+using std::make_pair;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class GraphUtilsTest : public ::testing::Test {};
+
+TEST(GraphUtilsTest, SimpleTest) {
+  Graph graph(2);
+  
+  graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
+
+  vector<Extent>& extents = graph[0].out_edges[1].extents;
+
+  EXPECT_EQ(0, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 0);
+  EXPECT_EQ(1, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 1);
+  graph_utils::AppendBlockToExtents(&extents, 2);
+  EXPECT_EQ(1, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 4);
+  
+  EXPECT_EQ(2, extents.size());
+  EXPECT_EQ(0, extents[0].start_block());
+  EXPECT_EQ(3, extents[0].num_blocks());
+  EXPECT_EQ(4, extents[1].start_block());
+  EXPECT_EQ(1, extents[1].num_blocks());
+  
+  EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
+}
+
+}  // namespace chromeos_update_engine
diff --git a/utils.h b/utils.h
index de998f4..9354ba5 100644
--- a/utils.h
+++ b/utils.h
@@ -80,6 +80,11 @@
   return ret;
 }
 
+template<typename T>
+bool VectorContainsValue(const std::vector<T>& vect, const T& value) {
+  return std::find(vect.begin(), vect.end(), value) != vect.end(); 
+}
+
 // Returns the currently booted device. "/dev/sda1", for example.
 // This will not interpret LABEL= or UUID=. You'll need to use findfs
 // or something with equivalent funcionality to interpret those.