HF::Pathfinding Namespace Reference

Algorithms to find the shortest path between nodes in a HF::SpatialStructures::Graph. More...

Classes
class	BoostGraph
	A graph usable with the BoostGraphLibrary. More...
struct	BoostGraphDeleter
	Deleter for the BoostGraph. More...
struct	DistanceAndPredecessor
	Holds and maintains a distance and predecessor matrix. More...
struct	DistPred
	A single row of a distance and predecessor matrix. More...
struct	Edge_Cost
	Data stored for every edge in the BoostGraph. More...
struct	vertex_data
	Data stored for every vertex in the BoostGraph. More...

Typedefs
typedef boost::compressed_sparse_row_graph< boost::directedS, vertex_data, Edge_Cost >	graph_t
	Type of graph held by the BoostGraph. More...
typedef boost::graph_traits< graph_t >::vertex_descriptor	vertex_descriptor
	Quick alias to shorten the typename of vertex descriptors for our graph_t type. /summary> More...
typedef std::pair< int, int >	pair
	Shorten std::pair to simplify graph construction. More...

Functions
Path	ConstructShortestPathFromPred (int start, int end, const std::vector< size_t > &pred, const std::vector< float > &distances)
	Construct the shortest path from start to end using the given predecessor and distance vectors. More...
Path	ConstructShortestPathFromPred (int start, int end, const DistPred &dist_pred)
	Overload to call this with a distPred instead of the raw arrays. More...
DistPred	BuildDistanceAndPredecessor (const graph_t &g, int id)
	Build a row of the distance and predecessor matrices for the node at id. More...
Path	FindPath (BoostGraph *bg, int start_id, int end_id)
	Find a path between points A and B using Dijkstra's Shortest Path algorithm. More...
vector< Path >	FindPaths (BoostGraph *bg, const std::vector< int > &start_points, const std::vector< int > &end_points)
	Find a path from every id in start_ids to the matching end node in end_ids. More...
void	InsertPathsIntoArray (const BoostGraph *bg, const std::vector< int > &start_points, const std::vector< int > &end_points, HF::SpatialStructures::Path **out_paths, HF::SpatialStructures::PathMember **out_path_members, int *out_sizes)
	A special version of FindPaths optimized for the C_Interface. More...
DistanceAndPredecessor	GenerateDistanceAndPred (const BoostGraph &bg)
	Generate the distance and predecessor matricies for a specific boost graph. More...
std::unique_ptr< BoostGraph, BoostGraphDeleter >	CreateBoostGraph (const HF::SpatialStructures::Graph &g, const std::string &cost_type="")
	Create a new boost graph from a HF::SpatialStructures:Graph. More...
void	InsertAllToAllPathsIntoArray (BoostGraph *bg, HF::SpatialStructures::Path **out_paths, HF::SpatialStructures::PathMember **out_path_members, int *out_sizes)
	A special version of FindPaths optimized for the C_Interface, such that all paths possible from each node to every other node are generated. More...
std::vector< HF::SpatialStructures::Path >	FindAllPaths (BoostGraph *bg)
	Find a path from every node to every node (NOTE: Not implemented yet.) More...

Detailed Description

Algorithms to find the shortest path between nodes in a HF::SpatialStructures::Graph.

This namespace utilizes pathfinding algorithms from Boost internally.To make use of the algorithms in this namespace, first you must create a BoostGraph from the HF::SpatialStructures::Graph you want to find paths in.

See also

HF::SpatialStructures::Path for a description of the path datatype.

BoostGraph for details on generating a BoostGraph from a HF::SpatialStructures::Graph.

---

Class Documentation

HF::Pathfinding::Edge_Cost

struct HF::Pathfinding::Edge_Cost

Data stored for every edge in the BoostGraph.

Each edge in the graph only stores its weight as a float.

Definition at line 99 of file boost_graph.h.

Collaboration diagram for HF::Pathfinding::Edge_Cost:

Class Members
float	weight	Cost of traversing this edge.

HF::Pathfinding::vertex_data

struct HF::Pathfinding::vertex_data

Data stored for every vertex in the BoostGraph.

Every vertex stores in the graph stores it's index p and a unique double d.

Todo:

Is the double d needed?

Definition at line 111 of file boost_graph.h.

Collaboration diagram for HF::Pathfinding::vertex_data:

Class Members
double	d	Unknown may have been used for the colormap.
graph_traits< compressed_sparse_row_graph< directedS > >::vertex_descriptor	p	The index of a vertex in the CSR.

Typedef Documentation

graph_t

typedef boost::compressed_sparse_row_graph< boost::directedS, vertex_data, Edge_Cost > HF::Pathfinding::graph_t

Type of graph held by the BoostGraph.

Set the graph as directed, store vertex_data for each vertex store Edge_Cost for each edge.

Remarks

By changing the contents of this typedef, you can change the type of graph that the BoostGraph holds, and the the type of data stored for each vertex or edge.

See also

vertex_data for info on what every vertex in the graph holds.

Edge_Cost for info on what every edge in the graph holds.

Definition at line 135 of file boost_graph.h.

pair

typedef std::pair<int, int> HF::Pathfinding::pair

Shorten std::pair to simplify graph construction.

Definition at line 142 of file boost_graph.h.

vertex_descriptor

typedef boost::graph_traits<graph_t>::vertex_descriptor HF::Pathfinding::vertex_descriptor

Quick alias to shorten the typename of vertex descriptors for our graph_t type. /summary>

Definition at line 139 of file boost_graph.h.

Function Documentation

BuildDistanceAndPredecessor()

DistPred HF::Pathfinding::BuildDistanceAndPredecessor ( const graph_t &  g, int  id  )

inline

Build a row of the distance and predecessor matrices for the node at id.

Parameters

g	Graph to build the predecessor and distance matrices for.
id	The node to generate the predecessor and distance matrix for.

Returns

A DistPred containing the distance and predecessor arrays for ID in g.

Definition at line 146 of file path_finder.cpp.

References HF::Pathfinding::DistPred::distance, HF::Pathfinding::DistPred::predecessor, and HF::Pathfinding::Edge_Cost::weight.

Referenced by FindPath(), FindPaths(), and InsertPathsIntoArray().

Here is the caller graph for this function:

ConstructShortestPathFromPred() [1/2]

Path HF::Pathfinding::ConstructShortestPathFromPred ( int  start, int  end, const DistPred &  dist_pred  )

inline

Overload to call this with a distPred instead of the raw arrays.

Parameters

start	Starting point of the path to generate.
end	End point of the path to generate.
dist_pred	DistPred containing the predecessor and distance matricies start.

Definition at line 133 of file path_finder.cpp.

References ConstructShortestPathFromPred(), HF::Pathfinding::DistPred::distance, and HF::Pathfinding::DistPred::predecessor.

Here is the call graph for this function:

ConstructShortestPathFromPred() [2/2]

Path HF::Pathfinding::ConstructShortestPathFromPred ( int  start, int  end, const std::vector< size_t > &  pred, const std::vector< float > &  distances  )

inline

Construct the shortest path from start to end using the given predecessor and distance vectors.

Parameters

start	ID of the starting point.
end	ID of the end point.
pred	Predecessor matrix for the start node.
distances	Distance matrix for pred

Todo:

Replace exception with an assert statment. It shouldn't be triggered unless there's a problem with this algorithm?

Definition at line 78 of file path_finder.cpp.

References HF::SpatialStructures::Path::AddNode(), HF::SpatialStructures::Path::Reverse(), and HF::SpatialStructures::Path::size().

Referenced by ConstructShortestPathFromPred(), FindPath(), FindPaths(), and InsertPathsIntoArray().

Here is the call graph for this function:

Here is the caller graph for this function:

CreateBoostGraph()

std::unique_ptr< BoostGraph, BoostGraphDeleter > HF::Pathfinding::CreateBoostGraph	(	const HF::SpatialStructures::Graph &	g,
		const std::string &	cost_type = ""
	)

Create a new boost graph from a HF::SpatialStructures:Graph.

Parameters

g	The graph to create a BoostGraph from
cost_type	The name of the cost set in graph that will be used to construct this boost graph Leaving this as blank will use the cost type the graph was constructed with.

Returns

A unique_ptr to point to the new BoostGraph created from the HFGraph.

Precondition

1) If cost_type is specified, and is not an empty string, then cost_type must be the key of an already created cost in graph.

2) graph must be compressed.

Remarks

This returns a pointer since it insulates the caller from needing to import Boost, which is extremely useful for the C_Interface since its clients will not need to use boost at all and it doesn't need to go through the trouble of compiling all of the boost library (again). A unique pointer was chosen here so the caller doesn't need to worry about manually deleting the returned boost graph at a later point.

Exceptions

HF::Exceptions::NoCost

if cost_type was not left blank and no cost type with the key cost_type exists in graph.

// be sure to #include "path_finder.h", #include "boost_graph.h", #include "node.h",
// #include "graph.h", and #include <vector>
 
// For this example, we must have a BoostGraph instance to use with
// BoostGraphDeleter. In order to create a BoostGraph, we must first create a Graph
// instance first. We must prepare the nodes, their edges, and the weights
// (distances) of each edge.
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f);
 
// Create a container (vector) of nodes
std::vector<HF::SpatialStructures::Node> nodes = { node_0, node_1, node_2 };
 
// Create matrices for edges and distances, edges.size() == distances().size()
std::vector<std::vector<int>> edges = { { 1, 2 }, { 2 }, { 1 } };
std::vector<std::vector<float>> distances = { { 1.0f, 2.5f }, { 54.0f }, { 39.0f } };
 
// Now you can create a Graph - note that nodes, edges, and distances are passed by reference
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// Now we can create a smart pointer to a BoostGraph Note the type of boostGraph -
// it is a std::unique_ptr<HF::Pathfinding::BoostGraph,
// HF::Pathfinding::BoostGraphDeleter>. Use the auto keyword for type inference, or
// your choice of using statements/typedef to make the use of the type described
// above easier.
auto boostGraph = CreateBoostGraph(graph);

Definition at line 320 of file path_finder.cpp.

Referenced by CalculateDistanceAndPredecessor(), CreateAllToAllPaths(), CreatePath(), and CreatePaths().

Here is the caller graph for this function:

FindAllPaths()

std::vector< HF::SpatialStructures::Path > HF::Pathfinding::FindAllPaths

(

BoostGraph *

bg

)

Find a path from every node to every node (NOTE: Not implemented yet.)

Parameters

bg	Graph to generate all paths for. traversal

Returns

A list of every path that could be generated from this graph.

Calculate a permutation for every combination of nodes in the graph, then call FindPaths, OR Write a unique function inspired by FindPaths that just runs through a range of paths.

Remarks

May benefit from using an algorithm optimized for this like https://www.boost.org/doc/libs/1_73_0/libs/graph/doc/floyd_warshall_shortest.html.

Exceptions

std::out_of_memory

if the memory required is too large.

Warning

This will allocate a large amount of memory. Ensure that this won't run out of memory when called, or be prepared to catch an out of memory exception.

Todo:

Implement this function to the specifications outlined here.

// NOTE: HF::Pathfinding::FindAllPaths is not implemented yet.
 
// be sure to #include "path_finder.h", #include "boost_graph.h", and #include "graph.h"
 
// Create a Graph g, and compress it.
HF::SpatialStructures::Graph g;
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(2, 4, 1);
g.addEdge(3, 4, 5);
g.Compress();
 
// Create a boostGraph from g
auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
// Get the path from node (id 0) to node (id 4)
auto all_paths = HF::Pathfinding::FindAllPaths(boostGraph.get(), 0, 4);
 
// all_paths will contain all shortest paths for [node 0, node 4]

FindPath()

HF::SpatialStructures::Path HF::Pathfinding::FindPath	(	BoostGraph *	bg,
		int	start_id,
		int	end_id
	)

Find a path between points A and B using Dijkstra's Shortest Path algorithm.

Parameters

bg	The boost graph containing edges/nodes.
start_id	ID of the starting node.
end_id	ID of the ending node.

Returns

The shortest path between A and B.

To find the path, A row of the predecessor matrix is generated for node a, then followed until node B is reached. This algorithm is implemented using dijkstra_shortest_path from the BoostGraphLibrary https://www.boost.org/doc/libs/1_73_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html

Note

Use FindPaths for multiple paths as it's able to reuse a lot of work compared to running this in a loop.

// be sure to #include "path_finder.h", #include "boost_graph.h", and #include "graph.h"
 
// Create a Graph g, and compress it.
HF::SpatialStructures::Graph g;
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(2, 4, 1);
g.addEdge(3, 4, 5);
g.Compress();
 
// Create a boostGraph from g
auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
// Get the path from node (id 0) to node (id 3)
HF::SpatialStructures::Path path = HF::Pathfinding::FindPath(boostGraph.get(), 0, 3);
 
// Print the nodes along the shortest path
std::cout << "Shortest path from node id 0 to node id 3:" << std::endl;
for (auto p : path.members) {
    std::cout << p.node << std::endl;
}

Definition at line 166 of file path_finder.cpp.

References BuildDistanceAndPredecessor(), ConstructShortestPathFromPred(), and HF::Pathfinding::BoostGraph::g.

Referenced by CreatePath().

Here is the call graph for this function:

Here is the caller graph for this function:

FindPaths()

std::vector< HF::SpatialStructures::Path > HF::Pathfinding::FindPaths	(	BoostGraph *	bg,
		const std::vector< int > &	start_points,
		const std::vector< int > &	end_points
	)

Find a path from every id in start_ids to the matching end node in end_ids.

Parameters

bg	The boost graph containing edges/nodes.
start_points	Ordered list of starting points.
end_points	Ordered list of ending points.

Returns

An ordered array of paths matching the order of the pairs of start_id and end_id. Paths that could not be generated will be returned as paths with no nodes.

More efficient than calling FindPath manually in a loop. Sorts paths by starting point, calculates only one predecessor matrix per unique starting point, then finds a path for every pair.

Precondition

Length of start_points must match that of end_points.

Todo:

This isn't in parallel! Can be implemented using a similar approach to InsertPathsIntoArray.

// be sure to #include "path_finder.h", #include "boost_graph.h", and #include "graph.h"
 
// Create a Graph g, and compress it.
HF::SpatialStructures::Graph g;
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(2, 4, 1);
g.addEdge(3, 4, 5);
g.Compress();
 
// Create a boostGraph from g
auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
// Prepare the parents and children vectors -- We will be searching for the shortest
// path from node 0 to node 3, as well as the shortest path from node 0 to node 4.
std::vector<int> parents = { 0, 0 };
std::vector<int> children = { 3, 4 };
 
std::vector<HF::SpatialStructures::Path> paths
    = HF::Pathfinding::FindPaths(boostGraph.get(), parents, children);
 
// Get the shortest paths, which are already stored in paths
auto path_0_3 = paths[0];
auto path_0_4 = paths[1];
 
// Print the shortest path from node 0 to node 3
std::cout << "Shortest path from node id 0 to node id 3:" << std::endl;
for (auto p : path_0_3.members) {
    std::cout << p.node << std::endl;
}
 
// Print the shortest path from node 0 to node 4
std::cout << "Shortest path from node id 0 to node id 4:" << std::endl;
for (auto p : path_0_4.members) {
    std::cout << p.node << std::endl;
}

Definition at line 178 of file path_finder.cpp.

References BuildDistanceAndPredecessor(), ConstructShortestPathFromPred(), and HF::Pathfinding::BoostGraph::g.

Here is the call graph for this function:

GenerateDistanceAndPred()

DistanceAndPredecessor HF::Pathfinding::GenerateDistanceAndPred

(

const BoostGraph &

bg

)

Generate the distance and predecessor matricies for a specific boost graph.

Parameters

bg	Boost graph to generate the matricies from

Returns

A DistanceAndPredecessor containing pointers to the new distance and predecessor matricies

Warning

It is up to the caller to deallocate both arrays. This is mostly for the C_Interface, and as such ignores the safety that most other functions adhere to. It is the caller's responsibility to deallocate both arrays from this function.

Example

 
    // Create a graph with some edges
    Graph g;
 
    vector<Node> nodes = {
        Node(1,2,3), Node(4, 5, 6),
        Node(7, 8, 9), Node(10, 1, 2)
    };
    g.addEdge(nodes[0], nodes[1], 10); g.addEdge(nodes[1], nodes[2], 20);
    g.addEdge(nodes[0], nodes[2], 5); g.addEdge(nodes[1], nodes[0], 10);
    g.Compress();
 
    // Turn it into a boost graph
    auto bg = CreateBoostGraph(g);
 
    // Create distance/predecessor matricies from the boost graph
    auto matricies = GenerateDistanceAndPred(*bg.get());
 
    // print output
    std::cerr << "DIST PRED " << g.size() << std::endl;
    std::cerr << matricies << std::endl;
    
    // get matricies from the output
    vector<float>* distance_matrix = matricies.dist;
    vector<int>* predecessor_matrix = matricies.pred;
 

 
    // Free them since it's our responsibility.
    delete distance_matrix;
    delete predecessor_matrix;
    

[0.000000, 10.000000, 5.000000, 10.000000, 0.000000, 15.000000, -1.000000, -1.000000, 0.000000]
[0, 0, 0, 1, 1, 0, -1, -1, 2]

Definition at line 267 of file path_finder.cpp.

References HF::Pathfinding::BoostGraph::g, HF::Pathfinding::DistanceAndPredecessor::GetRowOfDist(), HF::Pathfinding::DistanceAndPredecessor::GetRowOfPred(), HF::Pathfinding::BoostGraph::p, and HF::Pathfinding::Edge_Cost::weight.

Referenced by CalculateDistanceAndPredecessor().

Here is the call graph for this function:

Here is the caller graph for this function:

InsertAllToAllPathsIntoArray()

void HF::Pathfinding::InsertAllToAllPathsIntoArray	(	BoostGraph *	bg,
		HF::SpatialStructures::Path **	out_paths,
		HF::SpatialStructures::PathMember **	out_path_members,
		int *	out_sizes
	)

A special version of FindPaths optimized for the C_Interface, such that all paths possible from each node to every other node are generated.

Parameters

bg	Boost graph to generate paths in
out_paths	Location for the the path pointer array to be created. Paths that could not be generated will be left as null pointers.
out_path_members	Location for the pathmember pointer array will be created. All path member pointers will point to the PathMembers of the Path in paths at the same location. Paths that could not be generated will be left as null pointers.
out_sizes	Output raw_array of integers that will cntain the length of every path in path_members. Paths that could not be generated will be left with a length of zero.

Precondition

The length of start_ids must match the length of end_ids.

Postcondition

1) out_path_members will point to a vector of pointers to vectors of PathMembers with an element for every path.

2) out_paths will point to a vector of pointers to paths with an element for every path.

3) out_sizes will point to an array of integers containing the size of every path in out_paths

Remarks

Usually the C-Interface is able to simply wrap existing functions with minimal code to make them accessible to exernal callers, however in this specific situation there were real performance gains to be found by implementing this function directly in HF::PathFinding itself. It's efficent and safe for that purpose, but FindPaths should be preferred outside of that context since this function can be quite dangerous if not handled properly.

Warning

The caller is responsible for freeing all of the memory allocated in out_paths and out_sizes. The contents of out_path_members will automatically be deleted when the path they belong to is deleted. Do not try to manually delete out_path_members or the path that owns it will throw a null pointer exception when it is deleted.

HF::SpatialStructures::Graph g;
 
// Add the edges
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(1, 4, 4);
g.addEdge(2, 4, 4);
g.addEdge(3, 5, 5);
g.addEdge(4, 6, 3);
g.addEdge(5, 6, 1);
 
// Always compress the graph after adding edges
g.Compress();
 
// Create a BoostGraph (std::unique_ptr)
auto bg = CreateBoostGraph(g);
 
// Total paths is node_count ^ 2
size_t node_count = g.Nodes().size();
size_t path_count = node_count * node_count;
 
// Pointer to buffer of (Path *)
Path** out_paths = new Path* [path_count];
// out_paths[i...path_count - 1] will be alloc'ed by InsertPathsIntoArray
 
// Pointer to buffer of (PathMember *)
PathMember** out_path_member = new PathMember* [path_count];
// out_path_member[i...path_count - 1] points to out_paths[i...path_count - 1]->GetPMPointer();
 
// Pointer to buffer of (int)
int* sizes = new int[path_count];
 
//
// The two loops for start_points and end_points
// are just for the output.
//
int curr_id = 0;
std::vector<int> start_points(path_count);
// Populate the start points,
// size will be (node_count)^2
for (int i = 0; i < node_count; i++) {
    for (int k = 0; k < node_count; k++) {
        start_points[curr_id++] = i;
    }
}
 
curr_id = 0;
 
std::vector<int> end_points(path_count);
// Populate the end points,
// size will be (node_count)^2
for (int i = 0; i < node_count; i++) {
    for (int k = 0; k < node_count; k++) {
        end_points[curr_id++] = k;
    }
}
 
InsertAllToAllPathsIntoArray(bg.get(), out_paths, out_path_member, sizes);
 
for (int i = 0; i < path_count; i++) {
    if (out_paths[i]) {
        // Always check if out_paths[i] is nonnull!
        int total_cost = 0;
        std::cout << "Path from " << start_points[i] << " to " << end_points[i] << std::endl;
 
        Path p = *out_paths[i];
        for (auto m : p.members) {
            total_cost += m.cost;
            std::cout << "node ID: " << m.node << "\tcost " << m.cost << std::endl;
        }
 
        std::cout << "Total cost: " << total_cost << std::endl;
        std::cout << "--------------------------" << std::endl;
    }
}
 
//
// Resource cleanup
//
if (sizes) {
    delete[] sizes;
    sizes = nullptr;
}
 
if (out_path_member) {
    delete[] out_path_member;
    out_path_member = nullptr;
}
 
if (out_paths) {
    for (int i = 0; i < path_count; i++) {
        if (out_paths[i]) {
            delete out_paths[i];
            out_paths[i] = nullptr;
        }
    }
}

Definition at line 329 of file path_finder.cpp.

References InsertPathsIntoArray(), and HF::Pathfinding::BoostGraph::p.

Referenced by CreateAllToAllPaths().

Here is the call graph for this function:

Here is the caller graph for this function:

InsertPathsIntoArray()

void HF::Pathfinding::InsertPathsIntoArray	(	const BoostGraph *	bg,
		const std::vector< int > &	start_points,
		const std::vector< int > &	end_points,
		HF::SpatialStructures::Path **	out_paths,
		HF::SpatialStructures::PathMember **	out_path_members,
		int *	out_sizes
	)

A special version of FindPaths optimized for the C_Interface.

Parameters

bg	Boost graph to generate paths in
start_points	An ordered list of start points to generate paths from.
end_points	An ordered list of end points to generate paths to.
out_paths	Location for the the path pointer array to be created. Paths that could not be generated will be left as null pointers.
out_path_members	Location for the pathmember pointer array will be created. All path member pointers will point to the PathMembers of the Path in paths at the same location. Paths that could not be generated will be left as null pointers.
out_sizes	Output raw_array of integers that will contain the length of every path in path_members. Paths that could not be generated will be left with a length of zero.

Precondition

The length of start_ids must match the length of end_ids.

Postcondition

1) out_path_members will point to a vector of pointers to vectors of PathMembers with an element for every path.

2) out_paths will point to a vector of pointers to paths with an element for every path.

3) out_sizes will point to an array of integers containing the size of every path in out_paths

Remarks

Usually the C-Interface is able to simply wrap existing functions with minimal code to make them accessible to exernal callers, however in this specific situation there were real performance gains to be found by implementing this function directly in HF::PathFinding itself. It's efficent and safe for that purpose, but FindPaths should be preferred outside of that context since this function can be quite dangerous if not handled properly.

Warning

The caller is responsible for freeing all of the memory allocated in out_paths and out_sizes. The contents of out_path_members will automatically be deleted when the path they belong to is deleted. Do not try to manually delete out_path_members or the path that owns it will throw a null pointer exception when it is deleted.

// be sure to #include "path_finder.h", #include "boost_graph.h", and #include "graph.h"
 
// Create a Graph g, and compress it.
HF::SpatialStructures::Graph g;
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(2, 4, 1);
g.addEdge(3, 4, 5);
g.Compress();
 
// Create a boostGraph from g
auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
// Prepare the parents and children vectors -- We will be searching for the shortest
// path from node 0 to node 3, as well as the shortest path from node 0 to node 4.
std::vector<int> parents = { 0, 0 };
std::vector<int> children = { 3, 4 };
 
// Create smart pointers to hold Path, PathMember and sizes
const int MAX_SIZE = 4;
std::unique_ptr<HF::SpatialStructures::Path[]> result_paths(new Path[MAX_SIZE]);
std::unique_ptr<HF::SpatialStructures::PathMember[]> result_path_members(new PathMember[MAX_SIZE]);
std::unique_ptr<int[]> result_sizes(new int[MAX_SIZE]);
 
// Retrieve raw pointers so their addresses can be passed to InsertPathsIntoArray
HF::SpatialStructures::Path* ppath = result_paths.get();
HF::SpatialStructures::PathMember* pmembers = result_path_members.get();
int* psizes = result_sizes.get();
 
// Use InsertPathsIntoArray
HF::Pathfinding::InsertPathsIntoArray(boostGraph.get(), parents, children, &ppath, &pmembers, psizes);

Definition at line 201 of file path_finder.cpp.

References BuildDistanceAndPredecessor(), ConstructShortestPathFromPred(), HF::Pathfinding::BoostGraph::g, HF::SpatialStructures::Path::GetPMPointer(), and HF::SpatialStructures::Path::size().

Referenced by CreatePaths(), and InsertAllToAllPathsIntoArray().

Here is the call graph for this function:

Here is the caller graph for this function: