Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(5)

Unified Diff: experimental/webgtt/graph.h

Issue 10928195: First round of dead file removal (Closed) Base URL: https://github.com/samclegg/nativeclient-sdk.git@master
Patch Set: Created 8 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « experimental/webgtt/build.scons ('k') | experimental/webgtt/graph.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: experimental/webgtt/graph.h
diff --git a/experimental/webgtt/graph.h b/experimental/webgtt/graph.h
deleted file mode 100644
index ea059cfcc424c22a4a043eb6ad98761f79feb03f..0000000000000000000000000000000000000000
--- a/experimental/webgtt/graph.h
+++ /dev/null
@@ -1,80 +0,0 @@
-// Copyright (c) 2011 The Native Client 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 EXPERIMENTAL_WEBGTT_GRAPH_H_
-#define EXPERIMENTAL_WEBGTT_GRAPH_H_
-
-/// @fileoverview This file provides an implementation of a Graph data
-/// structure, which constructs a graph given the number of vertices and the
-/// adjacency matrix. It implements the graph algorithms required by webgtt.cc,
-/// which handles browser communication. Basically, this data structure can be
-/// thought of as a wrapper for Boost's Graph interface (we internally use
-/// Boost's graph representation and algorithms). At the moment, only
-/// undirected, unweighted graphs are supported.
-///
-/// @author ragad@google.com (Raga Gopalakrishnan)
-
-#include <boost/graph/graph_traits.hpp>
-
-#include <vector>
-
-namespace graph {
-
-/// This function extends the Boost library of graph algorithms. It finds a
-/// coloring of the graph, given the adjacency matrix.
-///
-/// Definition: A valid coloring of a graph consists of a color for each
-/// vertex of the graph, such that no two vertices that are connected by an
-/// edge share the same color. A minimum coloring is a valid coloring that
-/// uses as few colors as possible.
-/// Algorithm Choice: Finding a minimum coloring is an NP-complete problem,
-/// and therefore, in this algorithm, we focus on finding a valid coloring.
-/// Of course, assigning each vertex a different color is a trivial valid
-/// coloring! But we want to do something better, that would use far fewer
-/// colors in most cases. We use a greedy coloring technique, and the Boost
-/// implementation of this technique, outlined at
-/// http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/constructing_algorithms.html
-///
-/// @param[in] graph The graph object.
-/// @param[in] order A property map object that maps vertex indices to their
-/// corresponding vertex descriptors.
-/// @param[in] color A property map object that maps vertex descriptors to
-/// their corresponding vertex colors.
-/// @return The number of colors used to color the graph.
-template <class VertexListGraph, class Order, class Color>
-typename boost::graph_traits<VertexListGraph>::vertices_size_type
-SequentialVertexColoring(const VertexListGraph& graph,
- Order order,
- const Color& color);
-
-/// The Graph class. This class is a wrapper for Boost's graph representation
-/// and algorithms.
-class Graph {
- public:
- /// The constructor creates a Graph object given the number of vertices and
- /// the adjacency matrix.
- ///
- /// @param[in] number_of_vertices The number of vertices in the graph.
- /// @param[in] adjacency_matrix The adjacency matrix of the graph.
- /// @constructor
- Graph(int number_of_vertices,
- std::vector< std::vector<int> > adjacency_matrix);
-
- /// This function returns a greedy vertex coloring of the graph. Internally,
- /// it uses SequentialVertexColoring, an algorithm provided here as an
- /// extension of Boost's graph algorithms.
- ///
- /// @return A vector containing a valid coloring of the graph.
- std::vector<int> GetColoring() const;
-
- private:
- int number_of_vertices_;
- std::vector< std::vector<int> > adjacency_matrix_;
- /// This disallows usage of the assignment constructor.
- void operator=(const Graph&);
-};
-
-} // namespace graph
-
-#endif // EXPERIMENTAL_WEBGTT_GRAPH_H_
« no previous file with comments | « experimental/webgtt/build.scons ('k') | experimental/webgtt/graph.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698