A Graph of nodes connected by edges that supports both integers and HF::SpatialStructures::Node. More...

#include <graph.h>

Collaboration diagram for HF::SpatialStructures::Graph:

Public Member Functions
	Graph (const std::vector< std::vector< int > > &edges, const std::vector< std::vector< float > > &distances, const std::vector< Node > &Nodes, const std::string &default_cost="Distance")
	Construct a graph from a list of nodes, edges, and distances. More...

	Graph (const std::string &default_cost_name="Distance")
	Construct an empty graph. More...

bool	HasEdge (const std::array< float, 3 > &parent, const std::array< float, 3 > &child, bool undirected=false) const
	Determine if the graph has an edge from parent to child. More...

bool	HasEdge (const Node &parent, const Node &child, const bool undirected=false, const std::string cost_type="") const
	Determine if the graph has an edge from parent to child. More...

bool	HasEdge (int parent, int child, bool undirected=false, const std::string &cost_type="") const

std::vector< Node >	Nodes () const
	Get a list of nodes from the graph sorted by ID. More...

std::vector< Edge >	GetUndirectedEdges (const Node &N, const std::string &cost_type="") const
	Get a list of all edges to and from node N. More...

std::vector< EdgeSet >	GetEdges () const
	Get every in the given graph as IDs. More...

std::vector< IntEdge >	GetIntEdges (int parent) const
	Get children of a specific node as integers. More...

std::vector< float >	AggregateGraph (COST_AGGREGATE agg_type, bool directed=true, const std::string &cost_type="") const
	Summarize the costs of every outgoing edge for every node in the graph. More...

const std::vector< Edge >	operator[] (const Node &n) const

void	addEdge (const Node &parent, const Node &child, float score=1.0f, const std::string &cost_type="")
	Add a new edge to the graph from parent to child. More...

void	addEdge (int parent_id, int child_id, float score, const std::string &cost_type="")
	Add a new edge to the graph from parent to child. More...

bool	hasKey (const Node &n) const
	Determine if n exists in the graph. More...

std::vector< std::array< float, 3 > >	NodesAsFloat3 () const
	Get a list of nodes as float arrays. More...

int	size () const
	Determine how many nodes are in the graph. More...

int	MaxID () const
	Calculate the maximum ID of any node in the graph. More...

int	getID (const Node &node) const
	Retrieve the ID for node in this graph. More...

void	Compress ()
	Compress the graph to a CSR and enable the usage of several functions. More...

CSRPtrs	GetCSRPointers (const std::string &cost_type="")
	Obtain the size of and pointers to the 3 arrays that comprise this graph's CSR. graph if it isn't compressed already More...

Node	NodeFromID (int id) const
	Retrieve the node that corresponds to id. More...

void	Clear ()
	Clear all nodes and edges from the graph. More...

std::vector< Node >	GetChildren (const Node &n) const
	Retrieve n's child nodes - n is a parent node More...

std::vector< Node >	GetChildren (const int parent_id) const
	Retrieve node parent_id's child nodes More...

Subgraph	GetSubgraph (const Node &parent_node, const std::string &cost_type="") const
	Retrieves a Subgraph using a Node. More...

Subgraph	GetSubgraph (int parent_id, const std::string &cost_type="") const
	Retrieves a Subgraph using a parent node ID. More...

void	AddNodeAttribute (int id, const std::string &attribute, const std::string &score)
	Add an attribute to the node at id More...

void	AddNodeAttributes (const std::vector< int > &id, const std::string &name, const std::vector< std::string > &scores)
	Add an attribute to the node at id. If the node at id already has a score for the attribute at name, then existing score should be overwritten More...

std::vector< std::string >	GetNodeAttributes (std::string attribute) const
	Get the score for the given attribute of every node in the graph. Nodes that do not have a score for this attribute should return an empty string for this array. More...

void	ClearNodeAttributes (std::string name)
	Clears the attribute at name and all of its contents from the internal hashmap More...

bool	DumpToJson (const std::string &path)

void	AddEdges (const EdgeSet &edges, const std::string &cost_name="")
	Add multiple edges to the graph. More...

void	AddEdges (const std::vector< EdgeSet > &edges, const std::string &cost_name="")
	Add an array of edges to the graph. More...

std::vector< EdgeSet >	GetEdges (const std::string &cost_name) const
	Get the edges of a specfic cost type. More...

std::vector< std::string >	GetCostTypes () const
	Get an array of all cost names within this graph. More...

float	GetCost (int parent_id, int child_id, const std::string &cost_type="") const
	get the cost from parent_id to child_id in the given cost_type. More...

void	Graph::AddEdges (const std::vector< std::vector< IntEdge > > &edges, const std::string &cost_type)
	Add a set of intedges to the graph. More...

void	ClearCostArrays (const std::string &cost_name="")
	Clear one or more cost arrays from the graph. More...

void	AttrToCost (const std::string &node_attribute, const std::string &cost_to_store_as, Direction consider=Direction::INCOMING)
	Generate edge costs from a set of node attributes. More...

Private Types
using	NodeAttributeValueMap = robin_hood::unordered_map< int, std::string >

Private Member Functions
int	getOrAssignID (const Node &input_node)
	Get the unique ID for this x, y, z position and assign it an new one if it doesn't already exist. More...

int	getOrAssignID (int input_int)
	Add an ID to the graph if it doesn't exist already. More...

bool	checkForEdge (int parent, int child) const
	Determine if an edge between parent and child exists in the graph. More...

void	CSRAddOrUpdateEdge (int parent_id, int child_id, float cost)
	Add a new edge cost to the CSR or update if if a cost already exists. More...

void	TripletsAddOrUpdateEdge (int parent_id, int child_id, float cost)
	Add a new edge to the triplets list. More...

void	ResizeIfNeeded ()
	Resize the CSR to fit all the nodes in ordered_nodes if needed. More...

bool	hasKey (int id) const
	Check if this ID has already been assigned. More...

bool	HasCostArray (const std::string &key) const
	Check if we have this edge matrix already defined. More...

EdgeCostSet &	GetCostArray (const std::string &key)
	Get a reference to the edge matrix at the given key. More...

EdgeCostSet &	GetOrCreateCostType (const std::string &name)
	Get a reference to the edge matrix, or create a new one if it doesn't exist. More...

EdgeCostSet &	CreateCostArray (const std::string &name)
	Create a new edge matrix. More...

const EdgeCostSet &	GetCostArray (const std::string &key) const
	Get a reference to the edge matrix at the given key. More...

bool	IsDefaultName (const std::string &name) const
	Check if this name belongs to the default graph. More...

int	FindValueArrayIndex (int parent_id, int child_id) const
	Get the index of the cost at parent/child. More...

void	InsertEdgeIntoCostSet (int parent_id, int child_id, float score, EdgeCostSet &cost_set)
	Add an edge to a cost set between parent_id and child_id. More...

void	InsertEdgesIntoCostSet (EdgeCostSet &cost_set, const std::vector< EdgeSet > &es)
	Insert edges for a specific cost type into a cost set. More...

void	InsertOrUpdateEdge (int parent_id, int child_id, float score, const std::string &cost_type)
	Insert an edge into the default cost array or a new cost array. More...

float	GetCostForSet (const EdgeCostSet &set, int parent_id, int child_id) const
	Get the cost of traversing the edge between parent and child using set. More...

std::vector< Edge >	GetEdgesForNode (int parent_id, bool undirected=false, const std::string &cost_type="") const
	Get the edges for the given node. More...

TempMatrix	MapCostMatrix (const std::string &cost_type) const
	Construct a temp matrix for the specific cost type. More...

bool	HasNodeAttribute (const std::string &key) const
	Check if this graph has a specific node attribute. More...

Private Attributes
int	next_id = 0
	The id for the next unique node. More...

std::vector< Node >	ordered_nodes
	A list of nodes contained by the graph. More...

robin_hood::unordered_map< Node, int >	idmap
	Maps a list of X,Y,Z positions to positions in ordered_nodes. More...

std::vector< Eigen::Triplet< float > >	triplets
	Edges to be converted to a CSR when Graph::Compress() is called. More...

bool	needs_compression = true
	If true, the CSR is inaccurate and requires compression. More...

robin_hood::unordered_map< std::string, NodeAttributeValueMap >	node_attr_map
	Node attribute type : Map of node id to node attribute. More...

std::string	active_cost_type
	The active edge matrix to use for the graph. More...

EdgeMatrix	edge_matrix
	The underlying CSR containing edge information. More...

std::string	default_cost = "Distance"

std::unordered_map< std::string, EdgeCostSet >	edge_cost_maps
	< The default cost type of the graph. More...

bool	has_cost_arrays = false
	Indicates that the graph has cost arrays. More...

bool	nodes_out_of_order = false
	Determines whether or not the graph is using integer nodes. More...

Detailed Description

A Graph of nodes connected by edges that supports both integers and HF::SpatialStructures::Node.

Internally, this object uses Eigen (https://eigen.tuxfamily.org/dox/group__TutorialSparse.html) to store and maintain a CSR matrix. The CSR is always stored as a n by n sparse matrix where n is the number of nodes in ordered_nodes.

Cost Types: This Graph is capable of holding multiple cost types for any of it's edges. Each cost type has a distinct key as it's name, such as "CrossSlope" or "EnergyExpenditure". Upon creation, the graph is assigned a default cost type, Distance which can be accessed explicitly by the key "Distance" or leaving the cost_type field blank. Alternate costs have corresponding edges in the default cost set, but different costs to traverse from the parent to the child node.

Invariant: 1) Every node in the graph will have a Unique ID with no repeats; 2) Any edge cost set will be a valid replacement for CSR's values array.

Definition at line 486 of file graph.h.

Member Typedef Documentation

◆ NodeAttributeValueMap

using HF::SpatialStructures::Graph::NodeAttributeValueMap = robin_hood::unordered_map<int, std::string>

private

Definition at line 487 of file graph.h.

Constructor & Destructor Documentation

◆ Graph() [1/2]

HF::SpatialStructures::Graph::Graph	(	const std::vector< std::vector< int > > &	edges,
		const std::vector< std::vector< float > > &	distances,
		const std::vector< Node > &	Nodes,
		const std::string &	default_cost = `"Distance"`
	)

Construct a graph from a list of nodes, edges, and distances.

Parameters

edges	Ordered array of arrays of edges for each node in nodes.
distances	Ordered array of distance from parent to child for each edge in edges.
Nodes	Ordered array of nodes to act as a parent to all children in it's array in edges.
default_cost	Default cost of the graph. This is the name of the first used cost.

Preallocates the matrix it in element by element and compresses it.

Precondition: 1) The size of all input arrays must match: (edges.size() == nodes.size() && nodes.size() == distances.size()); 2) For the node at nodes[i], edges[i] should contain an array for the id of all nodes that nodes[i] has an edge from and, and distances[i] should contain an array of the the distance from nodes[i] to one of the nodes it has an edge to in edges[i].

Note: After constructing a graph with this constructor, it will not be able to be modified. Use the empty constructor and use addEdge if you want to modify the graph after construction. This may change in the future.

Remarks: This constructor can offer "slightly higher performance and memory consumption" than constructing a graph using Graph::addEdge in a loop according to official eigen documentation, however it may not be feasible for certain situations where the entire graph isn't known before the constructor is called. The implementation is based on the algorithm from Eigen's documentation under the section Filling a Sparse Matrix https://eigen.tuxfamily.org/dox/group__TutorialSparse.html.

// be sure to #include "graph.h"
// 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);

◆ Graph() [2/2]

HF::SpatialStructures::Graph::Graph ( const std::string & default_cost_name = "Distance" )

Construct an empty graph.

Remarks: This can be used to create a new graph to later be filled with edges/nodes by calling Graph::addEdge() then calling Graph::Compress(). Implementation is based on the Eigen documentation for Filling a CSR: https://eigen.tuxfamily.org/dox/group__TutorialSparse.html.

See also: Graph::addEdge() for details on adding edges.; Graph::Compress() for details on compressing the graph.

// be sure to #include "graph.h"
HF::SpatialStructures::Graph graph;     // This represents an order-zero graph (null graph)
                                        // It lacks vertices and edges.

Member Function Documentation

◆ addEdge() [1/2]

void HF::SpatialStructures::Graph::addEdge	(	const Node &	parent,
		const Node &	child,
		float	score = `1.0f`,
		const std::string &	cost_type = `""`
	)

Add a new edge to the graph from parent to child.

Parameters

parent	Parent node of the edge.
child	Child node of the edge.
score	Cost of traversing from aprent to child.

If the parent or child node do not have an ID. An ID will be assigned automatically.

Warning: This will not work if the graph wasn't created from the empty constructor since it has no internal edge list to add to.

Remarks: This adds a new element to the triplet list so next time Compress is called, the value is added to the graph.

Todo:: How should this signal that the graph can't have edges added to it? Or how do we add edges to an existing graph quickly without adding to its edge list?

// be sure to #include "graph.h"
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// Create a pair of nodes
HF::SpatialStructures::Node n_parent(4.0f, 5.0f, 6.0f);
HF::SpatialStructures::Node n_child(7.0f, 8.0f, 9.0f);
 
graph.addEdge(n_parent, n_child);   // default score is 1.0f

Referenced by AddEdgeFromNodeIDs(), AddEdgeFromNodes(), HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the caller graph for this function:

◆ addEdge() [2/2]

void HF::SpatialStructures::Graph::addEdge	(	int	parent_id,
		int	child_id,
		float	score,
		const std::string &	cost_type = `""`
	)

Add a new edge to the graph from parent to child.

Parameters

parent	Parent node of the edge.
child	Child node of the edge.
score	Cost of traversing from aprent to child.

Parameters

cost_type Type of cost to add this edge to

If the parent or child ids don't exist in the dictionary, they will be added.

Warning: This will not work if the graph wasn't created from the empty constructor since it has no internal edge list to add to.

Remarks: This adds a new element to the triplet list so next time Compress is called, the value is added to the graph. (Note: if an edge exists between parent_id and child_id, the score value will be added to the existing score value for the edge formed by parent_id and child_id).

Exceptions

std::logic_error	Tried to add an edge to an alternate cost type when the graph isnt compressed
std::out_of_range	Tried to add an edge to an alternate cost type when it hasn't been added to the default graph

Todo:: How should this signal that the graph can't have edges added to it? Or how do we add edges to an existing graph quickly without adding to its edge list?

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
int parent = 1;
int child = 2;
 
graph.addEdge(parent, child, 1.0f);
graph.Compress();

◆ AddEdges() [1/2]

void HF::SpatialStructures::Graph::AddEdges	(	const EdgeSet &	edges,
		const std::string &	cost_name = `""`
	)

Add multiple edges to the graph.

Parameters

edges	The set of edges to add to the graph
cost_name	The cost_type to add the edges to. If this cost type doesn't exist in the graph yet, then it will be created. If left blank or set to the default name, then the edges will be added to the default cost type.

Precondition: 1) If adding edges to an alternate cost type, the edges must already have been added to the default graph.; 2) If adding an alternate edge to the graph, the graph must already be compressed

Exceptions

std::logic_error	Trying to add an edge to an alternate cost type when it's not compressed
std::out_of_range	Trying to add an edge to an alternate cost type when it hasn't already been added to the default graph2) If adding an alternate edge to the graph, the graph must already be compressed

Referenced by CalculateAndStoreCrossSlope(), and CalculateAndStoreEnergyExpenditure().

Here is the caller graph for this function:

◆ AddEdges() [2/2]

void HF::SpatialStructures::Graph::AddEdges	(	const std::vector< EdgeSet > &	edges,
		const std::string &	cost_name = `""`
	)

Add an array of edges to the graph.

◆ AddNodeAttribute()

void HF::SpatialStructures::Graph::AddNodeAttribute	(	int	id,
		const std::string &	attribute,
		const std::string &	score
	)

Add an attribute to the node at id

Parameters

id	The ID of the node that will receive attribute
attribute	The attribute that the node at ID will receive
score	The weight, or distance that extends from the node at id

// TODO example

◆ AddNodeAttributes()

void HF::SpatialStructures::Graph::AddNodeAttributes	(	const std::vector< int > &	id,
		const std::string &	name,
		const std::vector< std::string > &	scores
	)

Add an attribute to the node at id. If the node at id already has a score for the attribute at name, then existing score should be overwritten

Parameters

id	The container of IDs from which nodes will be retrieved and given attributes
name	The attribute that each node will receive
scores	The container of score, ordered by the container of node IDs

Precondition: The length of ids, and the length of scores must be equal

Exceptions

std::logic_error The length of scores and the length of ID do not match.

// TODO example

Referenced by AddNodeAttributes().

Here is the caller graph for this function:

◆ AggregateGraph()

std::vector< float > HF::SpatialStructures::Graph::AggregateGraph	(	COST_AGGREGATE	agg_type,
		bool	directed = `true`,
		const std::string &	cost_type = `""`
	)		const

Summarize the costs of every outgoing edge for every node in the graph.

Parameters

agg_type	Type of aggregation to use.
directed	If true, include both incoming and outgoing edges for calculating a node's score.

Returns: An ordered list of scores for agg_type on each node in the graph.

Remarks: Useful for getting scores from the VisibilityGraph.

Exceptions

std::out_of_range	if agg_type doesn't match any value of COST_AGGREGATE.
Std::exception	if the graph isn't compressed.

Time Complexity: If undirected: O(k) where k is the total number of edges in the graph.
If directed: O(n) where n is the total number of nodes in the graph.

See also: COST_AGGREGATE to see a list of supported aggregation types.
// be sure to #include "graph.h"

// 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

// Note: graph is compressed upon instantiation

HF::SpatialStructures::Graph graph(edges, distances, nodes);

// graph must be compressed, or a exception will be thrown

HF::SpatialStructures::COST_AGGREGATE aggregate = HF::SpatialStructures::COST_AGGREGATE::AVERAGE; // aggregate == 1 in this case

// directed parameter may be true or false

std::vector<float> aggregate_graph = graph.AggregateGraph(aggregate, true);

HF::SpatialStructures::COST_AGGREGATE
COST_AGGREGATE
Methods of aggregating the costs for edges for each node in the graph.
Definition: graph.h:28

HF::SpatialStructures::COST_AGGREGATE::AVERAGE
@ AVERAGE
Average the cost of all edges.

Referenced by AggregateCosts().

Here is the caller graph for this function:

◆ AttrToCost()

void HF::SpatialStructures::Graph::AttrToCost	(	const std::string &	node_attribute,
		const std::string &	cost_to_store_as,
		Direction	consider = `Direction::INCOMING`
	)

Generate edge costs from a set of node attributes.

Parameters

attr_key	Attribute to create a new cost set from.
cost_string	Name of the new cost set.
dir	Direction that the cost of the edge should be calculated in. For example INCOMING will use the cost of the node being traveled to by the edge.

Exceptions

std::out_of_range if node_attribute could not be found.

Example: // Define nodes

const vector<Node> Nodes = {

{1,1,1}, {2,2,2}, {3,3,3},{4,4,4}, {5,5,5}

};

// Define the graph, compress it then add edges

Graph G;

G.addEdge(Nodes[0], Nodes[2], 2);

G.addEdge(Nodes[0], Nodes[1], 1);

G.addEdge(Nodes[3], Nodes[0], 3);

G.addEdge(Nodes[2], Nodes[1], 4);

G.addEdge(Nodes[0], Nodes[4], 555);

G.Compress();

// Get the ids of every node since the graph assigns them

std::vector<int> ids(Nodes.size(), -1);

for (int i = 0; i < Nodes.size(); i++)

ids[i] = G.getID(Nodes[i]);

// Create node attributes

G.AddNodeAttribute(ids[0], test_attribute, "000");

G.AddNodeAttribute(ids[1], test_attribute, "111");

G.AddNodeAttribute(ids[2], test_attribute, "222");

G.AddNodeAttribute(ids[3], test_attribute, "333");

HF::SpatialStructures::Graph::Graph
Graph(const std::vector< std::vector< int > > &edges, const std::vector< std::vector< float > > &distances, const std::vector< Node > &Nodes, const std::string &default_cost="Distance")
Construct a graph from a list of nodes, edges, and distances.

HF::SpatialStructures::Graph::Nodes
std::vector< Node > Nodes() const
Get a list of nodes from the graph sorted by ID.

// Convert node attributes to graph costs based on the cost of the child node

G.AttrToCost(test_attribute, "output_str", Direction::INCOMING);

// Print out the cost of edge 3 to 0

printf("0->1: %f\n", G.GetCost(ids[0], ids[1], "output_str"));

HF::SpatialStructures::Direction::INCOMING
@ INCOMING

0->1: 111.000000

Referenced by GraphAttrsToCosts().

Here is the caller graph for this function:

◆ checkForEdge()

bool HF::SpatialStructures::Graph::checkForEdge	(	int	parent,
		int	child
	)		const

private

Determine if an edge between parent and child exists in the graph.

Iterates through every row in the parent's column to find child. If child is not found in this column, false is returned. If child can be found in this column, then true is returned.

Time Complexity: O(k) where k is the number of edges from parent.

// Get the index for parent and child

const int parent_index = parent;

const int child_index = child;

// If the parent is not even in the graph, or the graph doesn't have any zeros, return early.

// Calling the iterator in both of these cases is undefined behavior and should be avoided

if (!IsInRange(edge_matrix.nonZeros(), edge_matrix.rows(), parent)) return false;

// if (edge_matrix.nonZeros() <= 0 || edge_matrix.rows() <= parent) return false;

// Iterate through parent's row to see if it has child.

for (EdgeMatrix::InnerIterator it(edge_matrix, parent_index); it; ++it) {

if (it.col() == child_index) return true;

}

// If we've gotten to this point, then the child doesn't exist in parent's row

return false;

HF::SpatialStructures::Graph::edge_matrix
EdgeMatrix edge_matrix
The underlying CSR containing edge information.
Definition: graph.h:502

◆ Clear()

void HF::SpatialStructures::Graph::Clear ( )

Clear all nodes and edges from the graph.

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// If we want to remove all nodes and edges from graph, we may do so with Clear:
graph.Clear();                      // active_edge_matrix is zeroed out, buffer is squeezed,
                                    // triplets are also cleared, and
                                    // needs_compression == true

Referenced by ClearGraph().

Here is the caller graph for this function:

◆ ClearCostArrays()

void HF::SpatialStructures::Graph::ClearCostArrays ( const std::string & cost_name = "" )

Clear one or more cost arrays from the graph.

Parameters

cost_name Name of the cost array to clear. If equal to the default cost of this graph or empty string, will clear all existing cost arrays (except for the default)

Exceptions

NoCost if the costname specified not match either the default cost or any other cost type held by the graph.

Referenced by ClearGraph().

Here is the caller graph for this function:

◆ ClearNodeAttributes()

void HF::SpatialStructures::Graph::ClearNodeAttributes ( std::string name )

Clears the attribute at name and all of its contents from the internal hashmap

Parameters

name	The attribute that will be cleared from this graph's internal hashmap

Parameters

name

// TODO example

Referenced by ClearAttributeType().

Here is the caller graph for this function:

◆ Compress()

void HF::SpatialStructures::Graph::Compress ( )

Compress the graph to a CSR and enable the usage of several functions.

This won't do anything if called on an already compressed graph. The graph is "compressed" by resizing the edge matrix to the maximum ID of any node in triplets, then calling setFromTriplets().

Note: This function actually doesn't actually reduce memory usage since it keeps the edge list in order to allow for modifications to the graph. In the future, it may be beneficial allow for the user to pass in a boolean that would delete the triplet array if true.

Remarks: This method of constructing the CSR is based on Eigen's documentation for Filling a sparse matrix https://eigen.tuxfamily.org/dox/group__TutorialSparse.html.

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// Create a pair of nodes
HF::SpatialStructures::Node n_parent(4.0f, 5.0f, 6.0f);
HF::SpatialStructures::Node n_child(7.0f, 8.0f, 9.0f);
 
graph.addEdge(n_parent, n_child);   // default score is 1.0f
 
// In order to use GetEdges, or AggregateGraph, we must compress our graph instance
graph.Compress();                       // GetEdges and AggregateGraph are now usable

Referenced by Compress().

Here is the caller graph for this function:

◆ CreateCostArray()

EdgeCostSet & HF::SpatialStructures::Graph::CreateCostArray ( const std::string & name )

private

Create a new edge matrix.

Parameters

name	Unique name of the new cost array

Returns: A reference to the new edge cost set

Precondition: 1) name does not already belong to another cost array in the graph.; 2) name is not the default name in the graph or an empty string.

◆ CSRAddOrUpdateEdge()

void HF::SpatialStructures::Graph::CSRAddOrUpdateEdge	(	int	parent_id,
		int	child_id,
		float	cost
	)

private

Add a new edge cost to the CSR or update if if a cost already exists.

Parameters

parent_id	ID of the parent node.
child_id	ID of the child node
cost	Cost of traversing from parent to child

Remarks: This is called when the graph is compressed and the user tries to add a new edge.

Precondition: parent_id and child_id point to valid nodes in the graph.

Warning: This will invalidate any EdgeCostSets. Don't call this if you have edge cost sets.

◆ DumpToJson()

bool HF::SpatialStructures::Graph::DumpToJson ( const std::string & path )

◆ FindValueArrayIndex()

int HF::SpatialStructures::Graph::FindValueArrayIndex	(	int	parent_id,
		int	child_id
	)		const

private

Get the index of the cost at parent/child.

Parameters

parent_id	ID of the edge's parent.
child_id	ID of the edge's child.

Returns: -1 if there is no edge between parent and child. Otherwise returns the index in the values array that belongs to the cost of traversing from parent to child.

Determines the start and end bounds of the row belonging to parent_id using the CSR's outer_index_ptr, then searches these bounds in inner_indices for child_id. If a match is found, the distance from child_id to the beginning of the csr's inner_index array is calculated and returned.

Remarks: This is used in several places to index EdgeCostSets.

Precondition: parent_id is a valid node in the graph.

◆ GetChildren() [1/2]

std::vector< Node > HF::SpatialStructures::Graph::GetChildren ( const int parent_id ) const

Retrieve node parent_id's child nodes

Parameters

parent_id The parent node ID from which child nodes will be derived

Returns: A container of child nodes that form edges that extend from node parent_id

// TODO example

◆ GetChildren() [2/2]

std::vector< Node > HF::SpatialStructures::Graph::GetChildren ( const Node & n ) const

Retrieve n's child nodes - n is a parent node

Parameters

n	The parent node from which child nodes will be derived

Returns: A container of child nodes that form edges that extend from parent node n

// TODO example

◆ GetCost()

float HF::SpatialStructures::Graph::GetCost	(	int	parent_id,
		int	child_id,
		const std::string &	cost_type = `""`
	)		const

get the cost from parent_id to child_id in the given cost_type.

Parameters

parent_id	Node that's being traversed from.
child_id	Node that's being traversed to.
cost_type	Type of cost to get for this edge. If blank, the graph's default cost type will be used.

Returns: The cost of traversing from parent_id to child_id for cost_type.

Precondition: cost_type must be the name of a cost that already exists in the graph, or blank.

Referenced by GetEdgeCost().

Here is the caller graph for this function:

◆ GetCostArray() [1/2]

EdgeCostSet & HF::SpatialStructures::Graph::GetCostArray ( const std::string & key )

private

Get a reference to the edge matrix at the given key.

Parameters

key	Name of the cost to retrieve.

Returns: The EdgeCostArray with the name of key.

Exceptions

HF::Exceptions::NoCost if the given key doesn't exist

Precondition: key is not the default graph name or an empty string.

See also: HasCostArray for a way of checking that the cost type exists before calling in situations where throwing is not possible, or unwanted.

◆ GetCostArray() [2/2]

const EdgeCostSet & HF::SpatialStructures::Graph::GetCostArray ( const std::string & key ) const

private

Get a reference to the edge matrix at the given key.

Parameters

key	Name of the cost to retrieve.

Returns: The EdgeCostArray with the name of key.

Exceptions

HF::Exceptions::NoCost if the given cost doesn't exist.

See also: HasCostArray for a way of checking that the cost type exists before calling in situations where throwing is not possible, or unwanted.

◆ GetCostForSet()

float HF::SpatialStructures::Graph::GetCostForSet	(	const EdgeCostSet &	set,
		int	parent_id,
		int	child_id
	)		const

private

Get the cost of traversing the edge between parent and child using set.

Parameters

set	The set of edges to get this cost in
parent_id	ID of the edge's parent node.
child_id	ID of the edge's child node

Returns: NAN if no edge exists in set between parent_id and child_id. If an edge does exist betwen parent_id and child_id in set then returns the cost

Precondition: parent_id and child_id both belong to nodes that already exist in the graph.

◆ GetCostTypes()

std::vector< std::string > HF::SpatialStructures::Graph::GetCostTypes ( ) const

Get an array of all cost names within this graph.

Returns: A list of all cost_types that exist within this graph (excluding the default cost array).

◆ GetCSRPointers()

CSRPtrs HF::SpatialStructures::Graph::GetCSRPointers ( const std::string & cost_type = "" )

Obtain the size of and pointers to the 3 arrays that comprise this graph's CSR. graph if it isn't compressed already

Returns: Pointers and sizes of the arrays that comprise the CSR. If the CSR cannot be constructed due to factors such as an empty input array, then the CSRPtrs contain null values for it's pointers.

This will automatically call Compress if it hasn't been called already.

Remarks: This can be useful for reconstructing or mapping to the CSR without interacting with eigen at all. Numpy can directly make map the arrays returned by this function to it's own CSR implementation.

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// Create a pair of nodes
HF::SpatialStructures::Node n_parent(4.0f, 5.0f, 6.0f);
HF::SpatialStructures::Node n_child(7.0f, 8.0f, 9.0f);
 
graph.addEdge(n_parent, n_child);   // default score is 1.0f
 
// Graph will be compressed automatically be GetCSRPointers
CSRPtrs returned_csr = graph.GetCSRPointers();

See also: CSRPtrs.AreValid() for checking if the return value represents a valid CSR.

Referenced by GetCSRPointers().

Here is the caller graph for this function:

◆ GetEdges() [1/2]

std::vector< EdgeSet > HF::SpatialStructures::Graph::GetEdges ( ) const

Get every in the given graph as IDs.

Returns: An array of edgesets for every node in the graph (Graph in the form of IDs).

Exceptions

std::exception if the graph hasn't been compressed. compressed.

Time Complexity: O(k) where k is the number of edges in the graph.

// be sure to #include "graph.h"
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// graph must be compressed, or a exception will be thrown
 
// To brief, an EdgeSet has the following layout: struct EdgeSet { int parent;
// std::vector<IntEdge> children; };
//
// An IntEdge has the following layout: struct IntEdge { int child; float weight; };
 
// A std::vector<EdgeSet> is a Graph, in the form of IDs.
std::vector<HF::SpatialStructures::EdgeSet> edge_set = graph.GetEdges();

Referenced by HF::Pathfinding::BoostGraph::BoostGraph().

Here is the caller graph for this function:

◆ GetEdges() [2/2]

std::vector< EdgeSet > HF::SpatialStructures::Graph::GetEdges ( const std::string & cost_name ) const

Get the edges of a specfic cost type.

Parameters

cost_name The name of the cost to get edges for

Returns: An edge set for the edges of cost_name

Exceptions

HF::Exceptions::NoCost The cost at `cost_name` didn't exist in the graph

◆ GetEdgesForNode()

std::vector< Edge > HF::SpatialStructures::Graph::GetEdgesForNode	(	int	parent_id,
		bool	undirected = `false`,
		const std::string &	cost_type = `""`
	)		const

private

Get the edges for the given node.

Parameters

parent_id	Node to get the outgoing edges of
undirected	If this is true, then get both outgoing and incoming edges of parent_id
cost_type	Cost type to use for retrieved edges

Returns: All edges from (or to if undirected is true) parent_id for the given cost type

Exceptions

NoCost if cost_type isn't eh default graph and doesn't exist in the graph's cost types

◆ getID()

int HF::SpatialStructures::Graph::getID ( const Node & node ) const

Retrieve the ID for node in this graph.

Returns: The ID assigned to this node. -1 if it was not yet added to the graph

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
HF::SpatialStructures::Node other_node(55.0f, 66.1f, 15.5f, 9510);  // Let's construct a Node we know is not in graph.
bool has_key = graph.hasKey(other_node);                            // other_node does not exist in graph, so has_key == false;
 
int ID = graph.getID(other_node);                                   // ID will assigned -1, because other_node is not a part of graph.
 
// Likewise, if we pass a Node instance that indeed exists...
 
// Retrieve the nodes from the graph, or use the original instance of
// std::vector<Node> passed to Graph upon instantiation
std::vector<HF::SpatialStructures::Node> get_nodes = graph.Nodes();
 
// nodes[index] yields an instance of Node that we can pass to hasKey. Any node that
// exists with graph can be passed to this member function to determine if the graph
// has the node's key, or not.
int index = 2;                  // we assume for this example that index 2 is valid.
HF::SpatialStructures::Node good_node = get_nodes[index];
 
ID = graph.getID(good_node);    // ID > -1, i.e. it is a Node instance that exists within this Graph.

Referenced by GetNodeID().

Here is the caller graph for this function:

◆ GetIntEdges()

std::vector< IntEdge > HF::SpatialStructures::Graph::GetIntEdges ( int parent ) const

Get children of a specific node as integers.

◆ GetNodeAttributes()

std::vector< std::string > HF::SpatialStructures::Graph::GetNodeAttributes ( std::string attribute ) const

Get the score for the given attribute of every node in the graph. Nodes that do not have a score for this attribute should return an empty string for this array.

Parameters

attribute The attribute from which a container of scores will be obtained

Returns: A container of score, each in the form of a std::string, obtained from attribute

// TODO example

Referenced by GetNodeAttributes().

Here is the caller graph for this function:

◆ getOrAssignID() [1/2]

int HF::SpatialStructures::Graph::getOrAssignID ( const Node & input_node )

private

Get the unique ID for this x, y, z position and assign it an new one if it doesn't already exist.

If the node has not yet been seen by the graph, next_id will be assigned to it and incremented, then the node node will and its new id will be added to idmap. If the node has already been assigned an ID, then the ID will be returned directly from idmap.

Parameters

input_node Node to retrieve and potentially assign a new ID for.

Returns: The ID of input_node.

// definition of Graph::addEdge(const Node& parent, const Node& child, float score)

        
        // Get parent/child ids
        int parent_id = getOrAssignID(parent);
        int child_id = getOrAssignID(child);
    
        // If this is already compressed, update the CSR, otherwise add it to the list of triplets.
        InsertOrUpdateEdge(parent_id, child_id, score, cost_type);

◆ getOrAssignID() [2/2]

int HF::SpatialStructures::Graph::getOrAssignID ( int input_int )

private

Add an ID to the graph if it doesn't exist already.

Warning: Adding integer edges to the graph isn't entirely supported. This WILL create gaps in the CSR, and break the order of ordered_nodes.

// definition of Graph::addEdge(int parent_id, int child_id, float score)

 
        // Store these Ids in the hashmap if they don't exist already.
        getOrAssignID(child_id);
        getOrAssignID(parent_id);
 
        InsertOrUpdateEdge(parent_id, child_id, score, cost_type);

◆ GetOrCreateCostType()

EdgeCostSet & HF::SpatialStructures::Graph::GetOrCreateCostType ( const std::string & name )

private

Get a reference to the edge matrix, or create a new one if it doesn't exist.

Parameters

name	Name of the cost matrix to create or retrieve.

Returns: A reference to the existing cost array, or the newly created cost array.

Precondition: key is not the default name in the graph or an empty string.

◆ GetSubgraph() [1/2]

Subgraph HF::SpatialStructures::Graph::GetSubgraph	(	const Node &	parent_node,
		const std::string &	cost_type = `""`
	)		const

Retrieves a Subgraph using a Node.

Parameters

parent_node The parent node from which the Subgraph will be derived

Returns: A structure that consists of parent_node and the container of Edge that consists of the Edge that extend from parent

// TODO example

Referenced by HF::SpatialStructures::CostAlgorithms::CalculateCrossSlope(), and HF::SpatialStructures::CostAlgorithms::CalculateEnergyExpenditure().

Here is the caller graph for this function:

◆ GetSubgraph() [2/2]

Subgraph HF::SpatialStructures::Graph::GetSubgraph	(	int	parent_id,
		const std::string &	cost_type = `""`
	)		const

Retrieves a Subgraph using a parent node ID.

Parameters

parent_id The parent node id from which the Subgraph will be derived

Returns: A structure that consists of the node at parent_id and the container of Edge that consists of the Edge that extend from parent_id

// TODO example

◆ GetUndirectedEdges()

std::vector< Edge > HF::SpatialStructures::Graph::GetUndirectedEdges	(	const Node &	N,
		const std::string &	cost_type = `""`
	)		const

Get a list of all edges to and from node N.

Parameters

N	The Node to get edges from and to.

Returns: A list of edges to and from node N or an empty array if is not in the graph.

Time Complexity: O(k) where k is the number of edges in the graph since it needs to iterate through every edge in the graph to find the edges to this node.

See also: operator[] to get a list of directed edges only containing edges from N.

// be sure to #include "graph.h"
 
// 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);
 
// Retrieve the nodes from the graph, or use the original instance of
// std::vector<HF::SpatialStructures::Node> passed to Graph upon instantiation
std::vector<HF::SpatialStructures::Node> get_nodes = graph.Nodes();
 
// nodes[index] yields an instance of Node that we can pass to GetUndirectedEdges.
// Any node that exists with graph can be passed to this member function to retrieve
// a vector of undirected edges.
int index = 2;
std::vector<HF::SpatialStructures::Edge> undirected_edges = graph.GetUndirectedEdges(get_nodes[index]);

◆ Graph::AddEdges()

void HF::SpatialStructures::Graph::Graph::AddEdges	(	const std::vector< std::vector< IntEdge > > &	edges,
		const std::string &	cost_type
	)

Add a set of intedges to the graph.

Parameters

edges	An ordered vector of vectors in which each outer vector holds a vector of edges for the node at the ID of that index. For example the vector at index 0 would hold a vector of intedges for the node at ID 0.a
cost_type	The type of cost to add these edges to. If this cost type does not yet exist, then it will be created.

Precondition: 1) If adding edges to an alternate cost type, the edges must already have been added to the default graph.; 2) If adding an alternate edge to the graph, the graph must already be compressed

Exceptions

std::logic_error	Trying to add an edge to an alternate cost type when it's not compressed
std::out_of_range	Trying to add an edge to an alternate cost type when it hasn't already been added to the default graph2) If adding an alternate edge to the graph, the graph must already be compressed

◆ HasCostArray()

bool HF::SpatialStructures::Graph::HasCostArray ( const std::string & key ) const

private

Check if we have this edge matrix already defined.

Parameters

Unique key of the cost type to search for in the cost map.

Returns: True there is a cost with this name, false otherwise.

Precondition: Key does not belong to the default graph.

◆ HasEdge() [1/3]

bool HF::SpatialStructures::Graph::HasEdge	(	const Node &	parent,
		const Node &	child,
		const bool	undirected = `false`,
		const std::string	cost_type = `""`
	)		const

Determine if the graph has an edge from parent to child.

Parameters

parent	Parent of the edge to check for.
child	Child of the edge to check for.
undirected	If true, look for an edge from child to parent as well.

Returns: True if an edge between parentand child exists (also child and parent if undirected is true).

Remarks: Gets the IDs of both nodes, then calls the integer overload.

Exceptions

std::exception

if the graph is uncompressed.

// be sure to #include "graph.h"
 
// 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);
 
// last argument can be true/false for undirected/directed graph respectively
bool has_edge = graph.HasEdge(node_1, node_2, true);

◆ HasEdge() [2/3]

bool HF::SpatialStructures::Graph::HasEdge	(	const std::array< float, 3 > &	parent,
		const std::array< float, 3 > &	child,
		bool	undirected = `false`
	)		const

Determine if the graph has an edge from parent to child.

Parameters

parent	Parent of the edge to check for.
child	Child of the edge to check for.
undirected	If true, look for an edge from child to parent as well.

Returns: True if an edge between parent and child exists (also child and parent if undirected is true).

Remarks: Converts parent and child to Node then calls the node overload.

Exceptions

std::exception

if the matrix is uncompressed.

// be sure to #include "graph.h"
 
// 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);
 
// Prepare {x, y, z} coordinates (positions)
auto parent_pos = node_1.getArray();        // (2.0, 3.0, 4.0)
auto child_pos = node_2.getArray();         // (11.0, 22.0, 140.0)
 
// last argument can be true/false for undirected/directed graph respectively
bool has_edge = graph.HasEdge(parent_pos, child_pos, true);

◆ HasEdge() [3/3]

bool HF::SpatialStructures::Graph::HasEdge	(	int	parent,
		int	child,
		bool	undirected = `false`,
		const std::string &	cost_type = `""`
	)		const

◆ hasKey() [1/2]

bool HF::SpatialStructures::Graph::hasKey ( const Node & n ) const

Determine if n exists in the graph.

Parameters

n	Node to look for.

Returns: True if the node exists, false otherwise.

Performs a single hash to check if n exists in the hashmap.

Time Complexity: O(1) since it's a single hash function.

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
HF::SpatialStructures::Node other_node(55.0f, 66.1f, 15.5f, 9510);  // Let's construct a Node we know is not in graph.
bool has_key = graph.hasKey(other_node);    // other_node does not exist in graph, so has_key == false;
 
// Likewise, if we pass a Node instance that indeed exists...
 
// Retrieve the nodes from the graph, or use the original instance of
// std::vector<Node> passed to Graph upon instantiation
std::vector<HF::SpatialStructures::Node> get_nodes = graph.Nodes();
 
// nodes[index] yields an instance of Node that we can pass to hasKey. Any node that
// exists with graph can be passed to this member function to determine if the graph
// has the node's key, or not.
int index = 2;
HF::SpatialStructures::Node good_node = get_nodes[index];
 
has_key = graph.hasKey(good_node);      // now has_key is true

◆ hasKey() [2/2]

bool HF::SpatialStructures::Graph::hasKey ( int id ) const

private

Check if this ID has already been assigned.

Parameters

id	Id of the node to check

Returns: True if the ID has already been assigned to a node in the graph. False otherwise.

TimeComplexity: Performs a search over every node in the graph: O(n).

◆ HasNodeAttribute()

bool HF::SpatialStructures::Graph::HasNodeAttribute ( const std::string & key ) const

private

Check if this graph has a specific node attribute.

◆ InsertEdgeIntoCostSet()

void HF::SpatialStructures::Graph::InsertEdgeIntoCostSet	(	int	parent_id,
		int	child_id,
		float	score,
		EdgeCostSet &	cost_set
	)

private

Add an edge to a cost set between parent_id and child_id.

Parameters

parent_id	The id of the parent node in the graph
child_id	the ID of the child node in the graph

Exceptions

std::out_of_range no edge from parent_id to child_id exists in the default cost type.

Precondition: 1) An edge from parent to child already exists in the graph for the default cost type.; 2) parent_id and child_id are both IDs of nodes that already exist in the graph.

◆ InsertEdgesIntoCostSet()

void HF::SpatialStructures::Graph::InsertEdgesIntoCostSet	(	EdgeCostSet &	cost_set,
		const std::vector< EdgeSet > &	es
	)

private

Insert edges for a specific cost type into a cost set.

Parameters

cost_set	Set of costs to insert edges into.
es	An array of edge_sets containing parent and child nodes to add to the graph.

Precondition: All edges in es already exist in the default graph.

◆ InsertOrUpdateEdge()

void HF::SpatialStructures::Graph::InsertOrUpdateEdge	(	int	parent_id,
		int	child_id,
		float	score,
		const std::string &	cost_type
	)

private

Insert an edge into the default cost array or a new cost array.

Parameters

parent_id	ID of the edge's parent node
child_id	ID of the edge's child node
score	Cost of traversing from parent to child
cost_type	The type of cost to add this edge to

If the graph isn't compressed, calls TripletsAddOrUpdateEdge(). If the graph is compressed calls CSRAddOrUpdateEdge(). If the cost at cost_type doesn't exist, then it will be created.

Precondition: 1) parent_id and child_id already exist in the graph.; 2) If not using the default cost_type the must already be compressed.; 3) Any edges being added to alternate cost types already exist in the default graph.

Exceptions

std::logic_error	If trying to add an edge to an alternate cost type when the graph hasn't been compressed.
std::logic_error	If trying to add an edge between nodes that doesn't exist already in the graph.

◆ IsDefaultName()

bool HF::SpatialStructures::Graph::IsDefaultName ( const std::string & name ) const

private

Check if this name belongs to the default graph.

Parameters

name	The name to test against the default.

Returns: True if this name belongs to the default CSR. False otherwise.

Note: The default name is either the name the graph was constructed with ("Distance" if none) or an empty string that returns true when calling string.empty().

◆ MapCostMatrix()

TempMatrix HF::SpatialStructures::Graph::MapCostMatrix ( const std::string & cost_type ) const

private

Construct a temp matrix for the specific cost type.

Parameters

cost_type The type of cost to generate the temp matrix for

Returns: A newly constructed TempMatrix with the outer and inner indices of the default edge_matrix but the values of cost_type.

Precondition: 1) cost_type must be a valid cost type that already exists in the graph; 2) cost_type must not be the default cost type.

◆ MaxID()

int HF::SpatialStructures::Graph::MaxID ( ) const

Calculate the maximum ID of any node in the graph.

Returns: The maximum ID of any node ing the graph.

Note: This shouldn't be needed often, as unless this graph has integer edges, nodes will always be stored in order.

Referenced by HF::Pathfinding::BoostGraph::BoostGraph().

Here is the caller graph for this function:

◆ NodeFromID()

Node HF::SpatialStructures::Graph::NodeFromID ( int id ) const

Retrieve the node that corresponds to id.

Parameters

id	The ID of the node to get.

Returns: The node corresponding to id, by value.

Exceptions

std::out_of_range

id didn't belong to any node in the graph.

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// Let's retrieve node_1.
int desired_node_id = 2;
HF::SpatialStructures::Node node_from_id = graph.NodeFromID(desired_node_id);
 
// Note that NodeFromID ceases to work if the id argument provided does not exist as
// an ID among the nodes within graph

◆ Nodes()

std::vector< Node > HF::SpatialStructures::Graph::Nodes ( ) const

Get a list of nodes from the graph sorted by ID.

Returns: A sorted vector of nodes.

// be sure to #include "graph.h"
 
// 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);
 
// Nodes() returns a copy of the ordered_nodes field
std::vector<HF::SpatialStructures::Node> nodes_from_graph = graph.Nodes();

Referenced by HF::SpatialStructures::CostAlgorithms::CalculateCrossSlope(), HF::SpatialStructures::CostAlgorithms::CalculateEnergyExpenditure(), GenerateGraph(), GenerateGraphObstacles(), and GetAllNodesFromGraph().

Here is the caller graph for this function:

◆ NodesAsFloat3()

std::vector< std::array< float, 3 > > HF::SpatialStructures::Graph::NodesAsFloat3 ( ) const

Get a list of nodes as float arrays.

Returns: An array of float arrays containing the position of every node in the graph in order.

Remarks: May be useful for to functions that take arrays instead of nodes.

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// A container of std::array<float, 3> is constructed and populated within
// NodesAsFloat3, and returned. Each array of 3 floats represents a Node's position
// within the Cartesian coordinate system. { x, y, z }
std::vector<std::array<float, 3>> nodes_as_floats = graph.NodesAsFloat3();
 
// The two loops below will yield the same output
for (auto n : graph.Nodes()) {
    std::cout << "(" << n.x << "," << n.y << "," << n.z << ")" << std::endl;
}
 
for (auto a : nodes_as_floats) {
    std::cout << a << std::endl;
}

◆ operator[]()

const std::vector< Edge > HF::SpatialStructures::Graph::operator[] ( const Node & n ) const

Todo:: Should this just return an empty list instead of throwing?

// be sure to #include "graph.h"
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
// Retrieve the nodes from the graph, or use the original instance of
// std::vector<Node> passed to Graph upon instantiation
std::vector<HF::SpatialStructures::Node> get_nodes = graph.Nodes();
 
// nodes[index] yields an instance of Node that we can pass to GetUndirectedEdges.
// Any node that exists with graph can be passed to this member function to retrieve
// a vector of edges.
int index = 2;
HF::SpatialStructures::Node node = get_nodes[index];
 
// Note that if node does not exist within graph, that an exception will be thrown.
std::vector<HF::SpatialStructures::Edge> undirected_edges = graph[node];
 
// See a (node)->(child_node_0, child_node_1, ... child_node_n)
std::cout << node.getArray() << "->";
for (auto e : undirected_edges) {
    std::cout << e.child.getArray() << ", ";
}
std::cout << std::endl;

◆ ResizeIfNeeded()

void HF::SpatialStructures::Graph::ResizeIfNeeded ( )

private

Resize the CSR to fit all the nodes in ordered_nodes if needed.

If the CSR can already fit all of the ndoes in ordered_nodes then this won't do anything.

Postcondition: The CSR will be large enough to fit all of the nodes in ordered_nodes.

◆ size()

int HF::SpatialStructures::Graph::size ( ) const

Determine how many nodes are in the graph.

Returns: The number of nodes in the graph.

Size is directly returned from id_to_nodes.size().

// be sure to #include "graph.h"
 
// Create the nodes
HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f, 4);
HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f, 6);
 
// 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
// Note: graph is compressed upon instantiation
HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
int id_count = graph.size();          // We retrieve the size of the node id count within graph (3)

Referenced by HF::Pathfinding::BoostGraph::BoostGraph(), HF::VisibilityGraph::AllToAll(), HF::VisibilityGraph::AllToAllUndirected(), GetSizeOfGraph(), and HF::VisibilityGraph::GroupToGroup().

Here is the caller graph for this function:

◆ TripletsAddOrUpdateEdge()

void HF::SpatialStructures::Graph::TripletsAddOrUpdateEdge	(	int	parent_id,
		int	child_id,
		float	cost
	)

private

Add a new edge to the triplets list.

Parameters

parent_id	Id of the parent node.
child_id	Id of the child node.
cost	Cost of traversing from parent to child.

Precondition: parent_id and child_id point to valid nodes in the graph.

Member Data Documentation

◆ active_cost_type

std::string HF::SpatialStructures::Graph::active_cost_type

private

The active edge matrix to use for the graph.

Definition at line 501 of file graph.h.

◆ default_cost

std::string HF::SpatialStructures::Graph::default_cost = "Distance"

private

Definition at line 504 of file graph.h.

◆ edge_cost_maps

std::unordered_map<std::string, EdgeCostSet> HF::SpatialStructures::Graph::edge_cost_maps

private

< The default cost type of the graph.

Hashmap containing evey alternate cost type

Definition at line 505 of file graph.h.

◆ edge_matrix

EdgeMatrix HF::SpatialStructures::Graph::edge_matrix

private

The underlying CSR containing edge information.

Definition at line 502 of file graph.h.

◆ has_cost_arrays

bool HF::SpatialStructures::Graph::has_cost_arrays = false

private

Indicates that the graph has cost arrays.

If this is true, and the graph compresses again, then all cost arrays will be wrecked. An exception should be thrown in the case this happens, because this is misuse.

Definition at line 513 of file graph.h.

◆ idmap

robin_hood::unordered_map<Node, int> HF::SpatialStructures::Graph::idmap

private

Maps a list of X,Y,Z positions to positions in ordered_nodes.

Definition at line 494 of file graph.h.

◆ needs_compression

bool HF::SpatialStructures::Graph::needs_compression = true

private

If true, the CSR is inaccurate and requires compression.

Definition at line 497 of file graph.h.

◆ next_id

int HF::SpatialStructures::Graph::next_id = 0

private

The id for the next unique node.

Definition at line 490 of file graph.h.

◆ node_attr_map

robin_hood::unordered_map<std::string, NodeAttributeValueMap> HF::SpatialStructures::Graph::node_attr_map

private

Node attribute type : Map of node id to node attribute.

Definition at line 499 of file graph.h.

◆ nodes_out_of_order

bool HF::SpatialStructures::Graph::nodes_out_of_order = false

private

Determines whether or not the graph is using integer nodes.

This causes the graph to spend more time finding the maximum node ID, since it's not gauranteed edges will be added in order.

Definition at line 522 of file graph.h.

◆ ordered_nodes

std::vector<Node> HF::SpatialStructures::Graph::ordered_nodes

private

A list of nodes contained by the graph.

Definition at line 491 of file graph.h.

◆ triplets

std::vector<Eigen::Triplet<float> > HF::SpatialStructures::Graph::triplets

private

Edges to be converted to a CSR when Graph::Compress() is called.

Definition at line 496 of file graph.h.

The documentation for this class was generated from the following file:

Cpp/spatialstructures/src/graph.h

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ NodeAttributeValueMap

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

Member Function Documentation

◆ addEdge() [1/2]

◆ addEdge() [2/2]

◆ AddEdges() [1/2]

◆ AddEdges() [2/2]

◆ AddNodeAttribute()

◆ AddNodeAttributes()

◆ AggregateGraph()

◆ AttrToCost()

◆ checkForEdge()

◆ Clear()

◆ ClearCostArrays()

◆ ClearNodeAttributes()

◆ Compress()

◆ CreateCostArray()

◆ CSRAddOrUpdateEdge()

◆ DumpToJson()

◆ FindValueArrayIndex()

◆ GetChildren() [1/2]

◆ GetChildren() [2/2]

◆ GetCost()

◆ GetCostArray() [1/2]

◆ GetCostArray() [2/2]

◆ GetCostForSet()

◆ GetCostTypes()

◆ GetCSRPointers()

◆ GetEdges() [1/2]

◆ GetEdges() [2/2]

◆ GetEdgesForNode()

◆ getID()

◆ GetIntEdges()

◆ GetNodeAttributes()

◆ getOrAssignID() [1/2]

◆ getOrAssignID() [2/2]

◆ GetOrCreateCostType()

◆ GetSubgraph() [1/2]

◆ GetSubgraph() [2/2]

◆ GetUndirectedEdges()

◆ Graph::AddEdges()

◆ HasCostArray()

◆ HasEdge() [1/3]

◆ HasEdge() [2/3]

◆ HasEdge() [3/3]

◆ hasKey() [1/2]

◆ hasKey() [2/2]

◆ HasNodeAttribute()

◆ InsertEdgeIntoCostSet()

◆ InsertEdgesIntoCostSet()

◆ InsertOrUpdateEdge()

◆ IsDefaultName()

◆ MapCostMatrix()

◆ MaxID()

◆ NodeFromID()

◆ Nodes()

◆ NodesAsFloat3()

◆ operator[]()

◆ ResizeIfNeeded()

◆ size()

◆ TripletsAddOrUpdateEdge()

Member Data Documentation

◆ active_cost_type

◆ default_cost

◆ edge_cost_maps

◆ edge_matrix

◆ has_cost_arrays

◆ idmap

◆ needs_compression

◆ next_id

◆ node_attr_map

◆ nodes_out_of_order