Lines Matching refs:graph
39 #include "ceres/graph.h"
44 // Compare two vertices of a graph by their degrees.
48 explicit VertexDegreeLessThan(const Graph<Vertex>& graph)
49 : graph_(graph) {}
59 const Graph<Vertex>& graph_;
62 // Order the vertices of a graph using its (approximately) largest
63 // independent set, where an independent set of a graph is a set of
72 // Given a undirected graph G(V,E), the algorithm is a greedy BFS
79 int IndependentSetOrdering(const Graph<Vertex>& graph,
81 const HashSet<Vertex>& vertices = graph.vertices();
88 // Colors for labeling the graph during the BFS.
105 VertexDegreeLessThan<Vertex>(graph));
117 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
129 // vertices in the graph.
163 // the input graph. Caller owns the result.
165 // Finding degree 2 spanning tree of a graph is not always
166 // possible. For example a star graph, i.e. a graph with n-nodes
172 // constrained variant of Kruskal's algorithm. We start with a graph
173 // G_T with the same vertex set V as the input graph G(V,E) but an
179 // graph G.
181 Graph<Vertex>*
182 Degree2MaximumSpanningForest(const Graph<Vertex>& graph) {
185 Graph<Vertex>* forest = new Graph<Vertex>();
191 // Sort of the edges in the graph in decreasing order of their
192 // weight. Also add the vertices of the graph to the Maximum
193 // Spanning Tree graph and set each vertex to be its own connected
195 const HashSet<Vertex>& vertices = graph.vertices();
200 forest->AddVertex(vertex1, graph.VertexWeight(vertex1));
203 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex1);
211 const double weight = graph.EdgeWeight(vertex1, vertex2);
248 // the same weight as the original graph.
249 const double edge_weight = graph.EdgeWeight(vertex1, vertex2);