The default constructor exists only for the benefit of STL containers. The graph must be initialized (using the assignment operator) before it is used.
Note that most of the parameters are passed by const reference and must exist for the duration of the Graph object. Notes on parameters: "options": - the GraphOptions used to build the Graph. In some cases these can be different than the options provided by the Layer. "vertices": - a vector of S2Points indexed by VertexId. "edges": - a vector of VertexId pairs (sorted in lexicographic order) indexed by EdgeId. "input_edge_id_set_ids": - a vector indexed by EdgeId that allows access to the set of InputEdgeIds that were mapped to the given edge, by looking up the returned value (an InputEdgeIdSetId) in "input_edge_id_set_lexicon". "input_edge_id_set_lexicon": - a class that maps an InputEdgeIdSetId to a set of InputEdgeIds. "label_set_ids": - a vector indexed by InputEdgeId that allows access to the set of labels that were attached to the given input edge, by looking up the returned value (a LabelSetId) in the "label_set_lexicon". "label_set_lexicon": - a class that maps a LabelSetId to a set of S2Builder::Labels. "is_full_polygon_predicate": - a predicate called to determine whether a graph consisting only of polygon degeneracies represents the empty polygon or the full polygon (see s2builder.h for details).
A loop consisting of a sequence of edges.
Builds polylines from a set of edges. If "polyline_type" is PATH, then only vertices of indegree and outdegree 1 (or degree 2 in the case of undirected edges) will appear in the interior of polylines. This essentially generates one polyline for each edge chain in the graph. If "polyline_type" is WALK, then polylines may pass through the same vertex or even the same edge multiple times (if duplicate edges are present), and each polyline will be as long as possible. This option is useful for reconstructing a polyline that has been snapped to a lower resolution, since snapping can cause edges to become identical.
Convenience class to return the set of labels associated with a given graph edge. Note that due to snapping, one graph edge may correspond to several different input edges and will have all of their labels. This class is the preferred way to retrieve edge labels.
A class that maps vertices to their outgoing edge ids. Example usage: VertexOutMap out(g); for (Graph::EdgeId e : out.edge_ids(v)) { ... } for (const Graph::Edge& edge : out.edges(v)) { ... }
Builds loops from a set of directed edges, turning left at each vertex until a repeated edge is found (i.e., LoopType::CIRCUIT). The loops are further grouped into connected components, where each component consists of one or more loops connected by shared vertices.
Indicates whether loops should be simple cycles (no repeated vertices) or circuits (which allow repeated vertices but not repeated edges). In terms of how the loops are built, this corresponds to closing off a loop at the first repeated vertex vs. the first repeated edge.
Indicates whether polylines should be "paths" (which don't allow duplicate vertices, except possibly the first and last vertex) or "walks" (which allow duplicate vertices and edges).
Returns the endpoints of the given edge (as vertex indices).
Returns the entire set of edges.
Builds loops from a set of directed edges, turning left at each vertex until either a repeated vertex (for LoopType::SIMPLE) or a repeated edge (for LoopType::CIRCUIT) is found. (Use LoopType::SIMPLE if you intend to construct an S2Loop.)
Returns a vector of edge ids sorted in lexicographic order by (destination, origin). All of the incoming edges to each vertex form a contiguous subrange of this ordering.
Returns a vector of EdgeIds sorted by minimum input edge id. This is an approximation of the input edge ordering.
Returns a map "m" that maps each edge e=(v0,v1) to the following outgoing edge around "v1" in clockwise order. \(This corresponds to making a "left turn" at the vertex.\) By starting at a given edge and making only left turns, you can construct a loop whose interior does not contain any edges in the same connected component.
Returns a vector containing the minimum input edge id for every edge. If an edge has no input ids, kNoInputEdgeId is used.
Given a graph such that every directed edge has a sibling, returns a map from EdgeId to the sibling EdgeId. This method is identical to GetInEdgeIds() except that (1) it requires edges to have siblings, and (2) undirected degenerate edges are grouped together in pairs such that one edge is the sibling of the other. Handles duplicate edges correctly and is also consistent with GetLeftTurnMap().
Builds loops from a set of undirected edges, turning left at each vertex until either a repeated vertex (for LoopType::SIMPLE) or a repeated edge (for LoopType::CIRCUIT) is found. The loops are further grouped into "components" such that all the loops in a component are connected by shared vertices. Finally, the loops in each component are divided into two "complements" such that every edge in one complement is the sibling of an edge in the other complement. This corresponds to the fact that given any set of non-crossing undirected loops, there are exactly two possible interpretations of the region that those loops represent (where one possibility is the complement of the other). This method does not attempt to resolve this ambiguity, but instead returns both possibilities for each connected component and lets the client choose among them.
Low-level method that returns an integer representing the entire set of input edge ids that were snapped to the given edge. The elements of the IdSet can be accessed using input_edge_id_set_lexicon().
Low-level method that returns a vector where each element represents the set of input edge ids that were snapped to a particular output edge.
Returns a mapping from an InputEdgeIdSetId to a set of input edge ids.
Returns the set of input edge ids that were snapped to the given edge. ("Input edge ids" are assigned to input edges sequentially in the order they are added to the builder.) For example, if input edges 2 and 17 were snapped to edge 12, then input_edge_ids(12) returns a set containing the numbers 2 and 17. Example usage:
Convenience method that calls is_full_polygon_predicate() to determine whether a graph that consists only of polygon degeneracies represents the empty polygon or the full polygon (see s2builder.h for details).
Returns a method that determines whether a graph that consists only of polygon degeneracies represents the empty polygon or the full polygon (see s2builder.h for details).
Low-level method that returns an integer representing the set of labels associated with a given input edge. The elements of the IdSet can be accessed using label_set_lexicon().
Low-level method that returns a vector where each element represents the set of labels associated with a particular output edge.
Returns a mapping from a LabelSetId to a set of labels.
Returns the set of labels associated with a given input edge. Example: for (Label label : g.labels(input_edge_id)) { ... }
Like GetSiblingMap(), but constructs the map starting from the vector of incoming edge ids returned by GetInEdgeIds(). (This operation is a no-op except unless undirected degenerate edges are present, in which case such edges are grouped together in pairs to satisfy the requirement that every edge must have a sibling edge.)
Returns the minimum input edge id that was snapped to this edge, or -1 if no input edges were snapped (see SiblingPairs::CREATE). This is useful for layers that wish to preserve the input edge ordering as much as possible (e.g., to ensure idempotency).
Returns the total number of edges in the graph.
Returns the number of vertices in the graph.
Returns the vertex at the given index.
Returns the entire set of vertices.
Rotates the edges of "loop" if necessary so that the edge(s) with the largest input edge ids are last. This ensures that when an output loop is equivalent to an input loop, their cyclic edge orders are the same. "min_input_ids" is the output of GetMinInputEdgeIds().
Sorts the given edge chains (i.e., loops or polylines) by the minimum input edge id of each chains's first edge. This ensures that when the output consists of multiple loops or polylines, they are sorted in the same order as they were provided in the input.
Given a set of vertices and edges, removes all vertices that do not have any edges and returned the new, minimal set of vertices. Also updates each edge in "edges" to correspond to the new vertex numbering. (Note that this method does *not* merge duplicate vertices, it simply removes vertices of degree zero.)
Given an unsorted collection of edges, transform them according to the given set of GraphOptions. This includes actions such as discarding degenerate edges; merging duplicate edges; and canonicalizing sibling edge pairs in several possible ways (e.g. discarding or creating them). The output is suitable for passing to the Graph constructor.
Given an edge (src, dst), returns the reverse edge (dst, src).
Defines a value larger than any valid InputEdgeId.
The following value of InputEdgeId means that an edge does not corresponds to any input edge.
An S2Builder::Graph represents a collection of snapped edges that is passed to a Layer for assembly. (Example layers include polygons, polylines, and polygon meshes.) The Graph object does not own any of its underlying data; it is simply a view of data that is stored elsewhere. You will only need this interface if you want to implement a new Layer subtype.
The graph consists of vertices and directed edges. Vertices are numbered sequentially starting from zero. An edge is represented as a pair of vertex ids. The edges are sorted in lexicographic order, therefore all of the outgoing edges from a particular vertex form a contiguous range.
S2Builder::Graph is movable and copyable. Note that although this class does not own the underlying vertex and edge data, S2Builder guarantees that all Graph objects passed to S2Builder::Layer::Build() methods will remain valid until all layers have been built.
TODO(ericv): Consider pulling out the methods that are helper functions for Layer implementations (such as GetDirectedLoops) into s2builderutil_graph.h.