| 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_
|
|
|