|
| template<typename V , typename E , typename EdgeType > |
| std::pair< std::vector< VertexId >, bool > | Ancestors (const Graph< V, E, EdgeType > &_graph, const VertexId &_vertex) |
| | Walk parent edges from _vertex up to a root and return the chain of ancestors in walk order (immediate parent first, root last) together with a flag indicating whether the walk terminated cleanly at a root (no parent) or was aborted by the cycle guard. In a tree this returns the unique parent chain; in a more general directed graph it follows the first incoming edge at each step (deterministic via the adjacency-list ordering) and aborts on cycles.
|
| |
| template<typename V , typename E , typename EdgeType > |
| std::vector< VertexId > | BreadthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from) |
| | Breadth first sort (BFS). Starting from the vertex == _from, it traverses the graph exploring the neighbors first, before moving to the next level neighbors.
|
| |
| template<typename V , typename E > |
| std::vector< UndirectedGraph< V, E > > | ConnectedComponents (const UndirectedGraph< V, E > &_graph) |
| | Calculate the connected components of an undirected graph. A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
|
| |
| template<typename V , typename E , typename EdgeType > |
| std::vector< VertexId > | DepthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from) |
| | Depth first sort (DFS). Starting from the vertex == _from, it visits the graph as far as possible along each branch before backtracking.
|
| |
| template<typename V , typename E , typename EdgeType > |
| std::unordered_set< VertexId > | DescendantsSet (const Graph< V, E, EdgeType > &_graph, const VertexId &_vertex) |
| | Set of all descendants of _vertex (including _vertex itself). Equivalent to BreadthFirstSort + insert-into-set, but avoids the intermediate vector copy. Matches the return shape downstream consumers (gz-sim's EntityComponentManager::Descendants) use.
|
| |
| template<typename V , typename E , typename EdgeType > |
| std::map< VertexId, CostInfo > | Dijkstra (const Graph< V, E, EdgeType > &_graph, const VertexId &_from, const VertexId &_to=kNullId) |
| | Dijkstra algorithm. Find the shortest path between the vertices in a graph. If only a graph and a source vertex is provided, the algorithm will find shortest paths from the source vertex to all other vertices in the graph. If an additional destination vertex is provided, the algorithm will stop when the shortest path is found between the source and destination vertex.
|
| |
| template<typename V , typename E , typename EdgeType > |
| bool | IsAncestor (const Graph< V, E, EdgeType > &_graph, const VertexId &_ancestor, const VertexId &_descendant) |
| | Test whether _ancestor lies on the parent chain above _descendant. O(depth) – walks _descendant up via Ancestors() and stops as soon as a match is found. Returns false for _a == _d (consistent with the strict ancestor relation).
|
| |
| template<typename V , typename E , typename EdgeType > |
| VertexId | LowestCommonAncestor (const Graph< V, E, EdgeType > &_graph, const VertexId &_a, const VertexId &_b) |
| | Lowest common ancestor of two vertices in a directed forest. Walks _a up to root collecting ancestors, then walks _b up until hitting one of those ancestors. O(depth_a + depth_b).
|
| |
| template<typename V , typename E , typename EdgeType > |
| Graph< V, E, EdgeType > | Subgraph (const Graph< V, E, EdgeType > &_graph, const VertexId &_root) |
| | Extract the subgraph induced by _root and all descendants reachable from it. Vertices and edges are copied (preserving ids, names, data, weights). All edges whose endpoints both lie in the reachable set are kept, including back-edges – so if the source graph contains cycles within the reachable region, the cycles are preserved in the result. Equivalent to "save just this entity and
everything beneath it" – the shape of operation gz-sim and sdformat would invoke when serializing a single model out of a world.
|
| |
| template<typename V , typename E > |
| UndirectedGraph< V, E > | ToUndirectedGraph (const DirectedGraph< V, E > &_graph) |
| | Copy a DirectedGraph to an UndirectedGraph with the same vertices and edges.
|
| |
