← Back to branch summary

~ubuntu-branches/ubuntu/raring/ceres-solver/raring

« back to all changes in this revision

Viewing changes to internal/ceres/graph.h

  • Committer: Package Import Robot
  • Author(s): Koichi Akabe
  • Date: 2012-06-04 07:15:43 UTC
  • Revision ID: package-import@ubuntu.com-20120604071543-zx6uthupvmtqn3k2
Tags: upstream-1.1.1
Import upstream version 1.1.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
internal/ceres/graph.h
 
1
// Ceres Solver - A fast non-linear least squares minimizer
 
2
// Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
 
3
// http://code.google.com/p/ceres-solver/
 
4
//
 
5
// Redistribution and use in source and binary forms, with or without
 
6
// modification, are permitted provided that the following conditions are met:
 
7
//
 
8
// * Redistributions of source code must retain the above copyright notice,
 
9
//   this list of conditions and the following disclaimer.
 
10
// * Redistributions in binary form must reproduce the above copyright notice,
 
11
//   this list of conditions and the following disclaimer in the documentation
 
12
//   and/or other materials provided with the distribution.
 
13
// * Neither the name of Google Inc. nor the names of its contributors may be
 
14
//   used to endorse or promote products derived from this software without
 
15
//   specific prior written permission.
 
16
//
 
17
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 
18
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
19
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
20
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 
21
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 
22
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 
23
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 
24
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 
25
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 
26
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 
27
// POSSIBILITY OF SUCH DAMAGE.
 
28
//
 
29
// Author: sameeragarwal@google.com (Sameer Agarwal)
 
30
 
 
31
#ifndef CERES_INTERNAL_GRAPH_H_
 
32
#define CERES_INTERNAL_GRAPH_H_
 
33
 
 
34
#include <limits>
 
35
#include <glog/logging.h>
 
36
#include "ceres/integral_types.h"
 
37
#include "ceres/map_util.h"
 
38
#include "ceres/collections_port.h"
 
39
#include "ceres/internal/macros.h"
 
40
#include "ceres/types.h"
 
41
 
 
42
namespace ceres {
 
43
namespace internal {
 
44
 
 
45
// A weighted undirected graph templated over the vertex ids. Vertex
 
46
// should be hashable and comparable.
 
47
template <typename Vertex>
 
48
class Graph {
 
49
 public:
 
50
  Graph() {}
 
51
 
 
52
  // Add a weighted vertex. If the vertex already exists in the graph,
 
53
  // its weight is set to the new weight.
 
54
  void AddVertex(const Vertex& vertex, double weight) {
 
55
    if (vertices_.find(vertex) == vertices_.end()) {
 
56
      vertices_.insert(vertex);
 
57
      edges_[vertex] = HashSet<Vertex>();
 
58
    }
 
59
    vertex_weights_[vertex] = weight;
 
60
  }
 
61
 
 
62
  // Uses weight = 1.0. If vertex already exists, its weight is set to
 
63
  // 1.0.
 
64
  void AddVertex(const Vertex& vertex) {
 
65
    AddVertex(vertex, 1.0);
 
66
  }
 
67
 
 
68
  // Add a weighted edge between the vertex1 and vertex2. Calling
 
69
  // AddEdge on a pair of vertices which do not exist in the graph yet
 
70
  // will result in undefined behavior.
 
71
  //
 
72
  // It is legal to call this method repeatedly for the same set of
 
73
  // vertices.
 
74
  void AddEdge(const Vertex& vertex1, const Vertex& vertex2, double weight) {
 
75
    DCHECK(vertices_.find(vertex1) != vertices_.end());
 
76
    DCHECK(vertices_.find(vertex2) != vertices_.end());
 
77
 
 
78
    if (edges_[vertex1].insert(vertex2).second) {
 
79
      edges_[vertex2].insert(vertex1);
 
80
    }
 
81
 
 
82
    if (vertex1 < vertex2) {
 
83
      edge_weights_[make_pair(vertex1, vertex2)] = weight;
 
84
    } else {
 
85
      edge_weights_[make_pair(vertex2, vertex1)] = weight;
 
86
    }
 
87
  }
 
88
 
 
89
  // Uses weight = 1.0.
 
90
  void AddEdge(const Vertex& vertex1, const Vertex& vertex2) {
 
91
    AddEdge(vertex1, vertex2, 1.0);
 
92
  }
 
93
 
 
94
  // Calling VertexWeight on a vertex not in the graph will result in
 
95
  // undefined behavior.
 
96
  double VertexWeight(const Vertex& vertex) const {
 
97
    return FindOrDie(vertex_weights_, vertex);
 
98
  }
 
99
 
 
100
  // Calling EdgeWeight on a pair of vertices where either one of the
 
101
  // vertices is not present in the graph will result in undefined
 
102
  // behaviour. If there is no edge connecting vertex1 and vertex2,
 
103
  // the edge weight is zero.
 
104
  double EdgeWeight(const Vertex& vertex1, const Vertex& vertex2) const {
 
105
    if (vertex1 < vertex2) {
 
106
      return FindWithDefault(edge_weights_, make_pair(vertex1, vertex2), 0.0);
 
107
    } else {
 
108
      return FindWithDefault(edge_weights_, make_pair(vertex2, vertex1), 0.0);
 
109
    }
 
110
  }
 
111
 
 
112
  // Calling Neighbors on a vertex not in the graph will result in
 
113
  // undefined behaviour.
 
114
  const HashSet<Vertex>& Neighbors(const Vertex& vertex) const {
 
115
    return FindOrDie(edges_, vertex);
 
116
  }
 
117
 
 
118
  const HashSet<Vertex>& vertices() const {
 
119
    return vertices_;
 
120
  }
 
121
 
 
122
  static double InvalidWeight() {
 
123
    return std::numeric_limits<double>::quiet_NaN();
 
124
  };
 
125
 
 
126
 private:
 
127
  HashSet<Vertex> vertices_;
 
128
  HashMap<Vertex, double> vertex_weights_;
 
129
  HashMap<Vertex, HashSet<Vertex> > edges_;
 
130
  HashMap<pair<Vertex, Vertex>, double> edge_weights_;
 
131
 
 
132
  DISALLOW_COPY_AND_ASSIGN(Graph);
 
133
};
 
134
 
 
135
}  // namespace internal
 
136
}  // namespace ceres
 
137
 
 
138
#endif  // CERES_INTERNAL_GRAPH_H_