Lines Matching refs:graph
40 #include "ceres/graph.h"
46 // Compare two vertices of a graph by their degrees, if the degrees
51 explicit VertexTotalOrdering(const Graph<Vertex>& graph)
52 : graph_(graph) {}
62 const Graph<Vertex>& graph_;
68 explicit VertexDegreeLessThan(const Graph<Vertex>& graph)
69 : graph_(graph) {}
76 const Graph<Vertex>& graph_;
79 // Order the vertices of a graph using its (approximately) largest
80 // independent set, where an independent set of a graph is a set of
89 // Given a undirected graph G(V,E), the algorithm is a greedy BFS
96 int IndependentSetOrdering(const Graph<Vertex>& graph,
98 const HashSet<Vertex>& vertices = graph.vertices();
105 // Colors for labeling the graph during the BFS.
122 VertexTotalOrdering<Vertex>(graph));
134 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
146 // vertices in the graph.
163 // the vertices of the graph. The greedy independent set algorithm
172 int StableIndependentSetOrdering(const Graph<Vertex>& graph,
175 const HashSet<Vertex>& vertices = graph.vertices();
179 // Colors for labeling the graph during the BFS.
187 VertexDegreeLessThan<Vertex>(graph));
209 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
221 // vertices in the graph.
255 // the input graph. Caller owns the result.
257 // Finding degree 2 spanning tree of a graph is not always
258 // possible. For example a star graph, i.e. a graph with n-nodes
264 // constrained variant of Kruskal's algorithm. We start with a graph
265 // G_T with the same vertex set V as the input graph G(V,E) but an
271 // graph G.
273 Graph<Vertex>*
274 Degree2MaximumSpanningForest(const Graph<Vertex>& graph) {
277 Graph<Vertex>* forest = new Graph<Vertex>();
283 // Sort of the edges in the graph in decreasing order of their
284 // weight. Also add the vertices of the graph to the Maximum
285 // Spanning Tree graph and set each vertex to be its own connected
287 const HashSet<Vertex>& vertices = graph.vertices();
292 forest->AddVertex(vertex1, graph.VertexWeight(vertex1));
295 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex1);
303 const double weight = graph.EdgeWeight(vertex1, vertex2);
340 // the same weight as the original graph.
341 const double edge_weight = graph.EdgeWeight(vertex1, vertex2);
