DHARTAPI.SpatialStructures.Graph Class Reference

A graph representing connections between points in space. More...

Inheritance diagram for DHARTAPI.SpatialStructures.Graph:

Public Member Functions
	Graph ()
	Construct a new empty graph in unmanaged memory.
void	AddEdge (Vector3D parent, Vector3D child, float cost, string cost_type="")
	Create a new edge between parent and child with cost. More...
void	AddEdge (int parent_id, int child_id, float cost, string cost_type="")
	Create a new edge between parent and child with cost. More...
NodeList	getNodes ()
	Get an array containing the graph's current nodes. More...
CSRInfo	CompressToCSR (string cost_type="")
	Compress the graph into a CSR representation, and get pointers to it. More...
ManagedFloatArray	AggregateEdgeCosts (GraphEdgeAggregation type, bool directed=true, string cost_type="")
	Summarize the edgecosts of every node in the graph. More...
float	GetCost (int parent, int child, string cost_type="")
	Get the cost of traversing between parent and child More...
int	GetNodeID (Vector3D node)
	Gets the ID of a node in the graph. More...
void	AddNodeAttribute (int id, string attribute, string score)
	Define a node attribute for the node at id. More...
void	AddNodeAttribute (string attribute, int[] ids, string[] scores)
	Add attribute to all node in ids, with their respective score in scores. More...
void	AddNodeAttribute< T > (string attribute, IEnumerable< T > scores)
	Add attribute to all node in ids, with their respective score in scores. More...
string[]	GetNodeAttributes (string attribute)
	Get the score of every node for a given attribute. More...
void	ClearNodeAttributes (string attribute)
	Clear an attribute and all of its scores from the graph. More...
int	NumNodes ()
	Get the number of nodes in this graph. More...
void	AttrsToCosts (string attribute_key, string cost_key, Direction dir)
	Generate a cost set based on a set of node parameters. More...
Public Member Functions inherited from DHARTAPI.NativeUtils.NativeObject
void	UpdatePressure (int new_pressure)
	Update the pressure of this object.

Protected Member Functions
override bool	ReleaseHandle ()
	Free the native memory managed by this class. More...

Additional Inherited Members
Public Attributes inherited from DHARTAPI.NativeUtils.NativeObject
int	pressure
	the size of the object pointed to in unmanaged memory in bytes. Used to exert pressure on the GC. More...
Properties inherited from DHARTAPI.NativeUtils.NativeObject
override bool	IsInvalid [get]
	There is no way to invalidate this class without destroying it, so will always return false.

Detailed Description

A graph representing connections between points in space.

Every Node in the graph contains an X,Y,Z coordinate which can be used to represent a specific point in space. This graph internally is stored as a Sparse Matrix for space efficency. Nodes are stored in a hashmap containing X,Y, and Z coordinates, allowing for quick indexing of specific nodes by location alone. Access to this graph's internal CSR is available through Graph.CompressToCSR().

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.

NodeAttributes

The graph is able to store an arbitrary amount of information about the nodes it contains as strings. Similar to alternate cost types, node attributes are each have a distinct key as their name, but instead of conatining information about edges in the graph, node attributes contain information about nodes. Unlike the cost algorithms in edgecosts, right now there is no functionality within DHARTAPI that populates the node attributes of the graph with any kind of metric, however the methods to add and clear node attributes are made available so you are free to add your own node attributes.

Note

To get the XYZ coordinates of a node from it's ID, use the ID as an index into the graph's nodes array returned by getNodes(); For example, if you want to get the node with an ID of 1 from the graph, you'd access the element at index 1 in the nodes array.

Invariant

1) The CSR maintained by this graph will always be valid.

2) Every unique unique node in the graph will be assigned a unique id. A Node is considered unique if it has an X,Y,Z location that is not within 0.0001 units of any other node in the graph.

Note

The graph offers some basic functionality to add edges and nodes but it's main use is to provide access to the output of the GraphGenerator and VisibilityGraph. If adding edges or alternate cost types please make sure to read the documentation for these functions and that all preconditions are followed.

See also

CompressToCSR to get a CSR representation of the graph.

Member Function Documentation

AddEdge() [1/2]

void DHARTAPI.SpatialStructures.Graph.AddEdge	(	int	parent_id,
		int	child_id,
		float	cost,
		string	cost_type = ""
	)

Create a new edge between parent and child with cost.

Parameters

parent_id	The ID of the parent node.
child_id	The ID of the child node.
cost	cost from parent to child.
cost_type	The type of cost to add this edge to. If left blank will add the edge to the graph's default cost type.

Precondition

1) If adding edges to a new cost type, the graph must first be compressed by calling CompressToCSR()

2) If adding a cost to a type that isn't the default cost type, the edge must already exist in the default cost type.

3) If the graph has already been compressed and alternate costs exist, then both parent and child already exist in the graph.

Postcondition

1) If the ID of either parent or child does not exist in the graph then New IDs will be assigned to them.

2) Existing representations of the this graph's CSR will be invalidated.

3) If cost_type is not blank, and does not refer to the default cost type or any other cost that already exists in the graph, a new cost type will be created.

Exceptions

LogicError	tried to add an alternate cost to the graph before it was compressed
InvalidCostOperation	Tried to add an alternate cost that doesn't exist in the graph's default cost type.

Warning

1) If an edge between parent and child already exists, this will overwrite that edge.

2) Calling this function will invalidate any existing CSRPtrs returned from the graph. Make sure to call CompressToCSR again continuing to access it.

Example

            
            // Create a graph, add an edge then compress it
            Graph G = new Graph();
            G.AddEdge(0, 1, 39);
            G.CompressToCSR();
 
            // Get this cost from the edge
            float cost_from_graph = G.GetCost(0, 1);
 
            // Print the retrieved cost
            Debug.WriteLine(cost_from_graph);
 

39

AddEdge() [2/2]

void DHARTAPI.SpatialStructures.Graph.AddEdge	(	Vector3D	parent,
		Vector3D	child,
		float	cost,
		string	cost_type = ""
	)

Create a new edge between parent and child with cost.

Parameters

parent	The X,Y,Z location for the parent node.
child	x,y,z location for the child
cost	cost for parent to child
cost_type	The type of cost to add the edge to.

Attention

This overload is meant for debugging. There are many issues that can occur with adding integers to the graph that don't already have nodes assigned. Instead use the overload of this function deals with vector 3.

Precondition

1) If adding edges to a new cost type, the graph has been compressed by calling CompressToCSR().

2) If adding a cost to a type that isn't the default cost type, the edge must already exist in the default cost type.

3) If the graph has already been compressed and alternate costs exist, then both parent and child already exist in the graph.

Postcondition

1) If the ID of either parent or child does not exist in the graph then New IDs will be assigned to them.

2) Existing representations of the this graph's CSR will be invalidated.

3) If cost_type is not blank, and does not refer to the default cost type or any other cost that already exists in the graph, a new cost type will be created.

Exceptions

LogicError	tried to add an alternate cost to the graph before it was compressed
InvalidCostOperation	Tried to add an alternate cost that doesn't exist in the graph's default cost type.

Warning

1) If an edge between parent and child already exists, this will overwrite that edge.

2) Calling this function will invalidate any existing CSRPtrs returned from the graph. Make sure to call CompressToCSR again continuing to access it.

Example

 
            // Create a new Graph, add an edge then compress it
            Graph G = new Graph();
            G.AddEdge(new Vector3D(0, 0, 2), new Vector3D(0, 0, 1), 39);
            G.CompressToCSR();
 
            // Get the cost form the edge we just added to ensure it exists
            float cost_from_graph = G.GetCost(0, 1);
 
            // Print the retrieved cost
            Debug.WriteLine(cost_from_graph);
 

39

AddNodeAttribute() [1/2]

void DHARTAPI.SpatialStructures.Graph.AddNodeAttribute	(	int	id,
		string	attribute,
		string	score
	)

Define a node attribute for the node at id.

Parameters

id	The ID of the node that will receive attribute.
attribute	The name of the attribute to use.
score	The score for attribute to store for this node.

Example

// Create a graph and add two edges to create nodes
Graph g = new Graph();
g.AddEdge(0, 1, 150);
g.AddEdge(0, 2, 100);
g.AddEdge(0, 3, 2);
 
// Add node attributes to the graph for the nodes
// we just created
g.AddNodeAttribute(2, "Attr", "200");
g.AddNodeAttribute(1, "Attr", "100");
g.AddNodeAttribute(0, "Attr", "0");
 
// Get scores for this attribute from the graph
var attr = g.GetNodeAttributes("Attr");
 
// Print results
foreach (var attribute in attr)
    Debug.WriteLine(attribute);

>>> 0
>>> 100
>>> 200

References DHARTAPI.SpatialStructures.Graph.AddNodeAttribute().

Referenced by DHARTAPI.SpatialStructures.Graph.AddNodeAttribute(), and DHARTAPI.SpatialStructures.Graph.AddNodeAttribute< T >().

AddNodeAttribute() [2/2]

void DHARTAPI.SpatialStructures.Graph.AddNodeAttribute	(	string	attribute,
		int[]	ids,
		string[]	scores
	)

Add attribute to all node in ids, with their respective score in scores.

Parameters

ids	IDs of nodes to assign scores to for attribute
attribute	Name of the attribute to assigns cores to for each node in ids
scores	Ordered ids of scores to add to the node at the id in ids at the same index

Precondition

the length of ids and scores must match

Example

// Create a graph and add two edges to create nodes
Graph g = new Graph();
g.AddEdge(0, 1, 150);
g.AddEdge(0, 2, 100);
 
// Create arrays for ids and scores
int[] ids = { 0, 1, 2 };
string[] scores = { "0", "100", "200" };
 
// Add them to the graph
g.AddNodeAttribute("Attr", ids, scores);
 
// Get scores for this attribute from the graph
var attr = g.GetNodeAttributes("Attr");
 
foreach (var attribute in attr)
    Debug.WriteLine(attribute);

>>> 0
>>> 100
>>> 200

AddNodeAttribute< T >()

void DHARTAPI.SpatialStructures.Graph.AddNodeAttribute< T >	(	string	attribute,
		IEnumerable< T >	scores
	)

Add attribute to all node in ids, with their respective score in scores.

Parameters

attribute	Name of the attribute to assign scores to for each node in the graph
scores	Ordered ids of scores to add to the node at the id in ids at the same index

Precondition

the length of scores must equal the number of nodes in the graph.

Exceptions

ArgumentException

The number of scores in scores isn't equal to the nubmer of nodes in the graph

Type Constraints

T

:

IFormattable

References DHARTAPI.SpatialStructures.Graph.AddNodeAttribute(), and DHARTAPI.SpatialStructures.Graph.NumNodes().

AggregateEdgeCosts()

ManagedFloatArray DHARTAPI.SpatialStructures.Graph.AggregateEdgeCosts	(	GraphEdgeAggregation	type,
		bool	directed = true,
		string	cost_type = ""
	)

Summarize the edgecosts of every node in the graph.

Parameters

type	The type of aggregation method to use.
directed	Whether or not the graph is directed. If set to true then each nodes's score will only consider incomning edges. Otherwise, each node's score will consider both outgoing and incoming edges.
cost_type	The type of cost to use for aggregating the edges.

Returns

An array of scores, in which each element corresponds to a node in the graph sorted by ID.

Precondition

If not left blank, cost_type must point to a valid cost in the graph.

Exceptions

KeyNotFoundException

Cost specified didn't match the default cost, or any other cost type defined in the graph.

Warning

This will compress the graph if it is not compressed already. If any edges were added between lat call to CompressToCSR and now, then any active CSRPtrs will be invalidated.

Remarks

The order of the scores returned bythis function match the order of the scores returned from Graph.getNodes. This can be especially useful for summarizing the results of a VisibilityGraph.

Example

            // Create a new graph and add some edges
            Graph g = new Graph();
            g.AddEdge(0, 1, 100);
            g.AddEdge(0, 2, 50);
            g.AddEdge(1, 2, 20);
 
            // Compress the graph before using it 
            g.CompressToCSR();

            var scores = g.AggregateEdgeCosts(GraphEdgeAggregation.SUM);
            var score_arr = scores.array;
            Debug.WriteLine(scores);

[150, 20, 0]

References DHARTAPI.SpatialStructures.Graph.CompressToCSR(), and DHARTAPI.SpatialStructures.Graph.NumNodes().

AttrsToCosts()

void DHARTAPI.SpatialStructures.Graph.AttrsToCosts	(	string	attribute_key,
		string	cost_key,
		Direction	dir
	)

Generate a cost set based on a set of node parameters.

Parameters

attribute_key	Attribute to create a new cost set from.
cost_key	Key for the newly generated cost set.
dir	Direction to use for calculating the cost of any edge. For example INCOMING will use the cost of the node being traveled to by the edge.

Exceptions

KeyNotFoundException

The parameter assinged by parameter_name is not the key of any node parameter in the graph.

Precondition

An attribute of attribute_key already exists in the graph

Postcondition

A new cost set will be created in the graph with a key of cost_key.

Example

            
            // Create a graph and add two edges to create nodes
            Graph g = new Graph();
            g.CompressToCSR();
            g.AddEdge(0, 1, 150);
            g.AddEdge(0, 2, 100);
 
            // Create arrays for ids and scores
            int[] ids = { 0, 1, 2 };
            string[] scores = { "0", "100", "200" };
 
            // Add them to the graph
            g.AddNodeAttribute("Attr", ids, scores);
 
            // Convert this to an edge cost
            g.AttrsToCosts("Attr", "new_cost", Direction.BOTH);
 
            // print results
            Debug.WriteLine(String.Format("0->1 = {0}, 0->2 = {1}", g.GetCost(0, 1, "new_cost"), g.GetCost(0, 2, "new_cost")));
 

0->1 = 100, 0->2 = 200

ClearNodeAttributes()

void DHARTAPI.SpatialStructures.Graph.ClearNodeAttributes

(

string

attribute

)

Clear an attribute and all of its scores from the graph.

Parameters

attribute

The unique key of the attribute to clear from the graph.

Example

// Create a graph and add two edges to create nodes
Graph g = new Graph();
g.AddEdge(0, 1, 150);
g.AddEdge(0, 2, 100);
 
// Create arrays for ids and scores
int[] ids = { 0, 1, 2 };
string[] scores = { "0", "100", "200" };
 
// Add them to the graph
g.AddNodeAttribute("Attr", ids, scores);
 
// Now try to delete
g.ClearNodeAttributes("Attr");
 
// check that this is truly gone
var node_attrs = g.GetNodeAttributes("Attr");
Debug.WriteLine(node_attrs.size());

>>> 0

CompressToCSR()

CSRInfo DHARTAPI.SpatialStructures.Graph.CompressToCSR

(

string

cost_type = ""

)

Compress the graph into a CSR representation, and get pointers to it.

Parameters

cost_type

Change the type of cost that's carried in the CSR's values array. If left blank, will use the graph's default cost type.

Remarks

The CSR pointers can be mapped to after retrieved from C++ using spans, or can be copied out of managed memory.

Exceptions

KeyNotFoundException

cost_type is not blank, the name of the graph's default cost type, or the name of any already defined cost type in the graph.

See also

CSRPtrs for more info on the CSR type and how to access it.

Example

            // Create a graph
            Graph G = new Graph();
 
            // Add an edge
            G.AddEdge(1, 2, 39);
            
            // Compress the graph to a CSR
            var default_ptrs = G.CompressToCSR();
            
            // Print the CSR
            Debug.Write(default_ptrs);

(nnz: 1, rows: 3, cols: 3)

Referenced by DHARTAPI.SpatialStructures.Graph.AggregateEdgeCosts(), and StringToEdgeCost.Main().

GetCost()

float DHARTAPI.SpatialStructures.Graph.GetCost	(	int	parent,
		int	child,
		string	cost_type = ""
	)

Get the cost of traversing between parent and child

Parameters

parent	Node that's being traversed from
child	Node that's being traversed to
cost_type	The cost type to retrieve. If blank, the graph's default cost will be used.

Returns

The cost of traversing from parent to child.

Precondition

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

2) The graph must first have been compressed using Graph.CompressToCSR().

Exceptions

LogicError	The graph wasn't compressed before calling this function.
KeyNotFoundExeption	The cost_type specified was not the default cost, blank, or the name of any cost that currently belongs to the graph.

Note

This is not a high performance function, since each index into the CSR requires an indexing operation. If multiple values are required, it is suggested to iterate through the pointers from Graph.CompressToCSR().

Example

 
            // Create a graph and add an edge
            Graph g = new Graph();
            g.AddEdge(0, 1, 100);
 
            // Compress the graph so we can read the edge
            g.CompressToCSR();
 
            // Retrieve the cost that we just added using GetCost
            float cost_in_graph = g.GetCost(0, 1);
            Debug.WriteLine(cost_in_graph);
 

100

GetNodeAttributes()

string[] DHARTAPI.SpatialStructures.Graph.GetNodeAttributes

(

string

attribute

)

Get the score of every node for a given attribute.

Parameters

attribute

The unique name of the attribute type to get from the graph fopr every node

Returns

If an attribute with the name of attribute, type was found in the graph, then an array of scores for each node is returned in order of ID. For example, the score of the node with id 10 would be stored at index 10, id 12 stored at index 12, etc. Nodes without scores for attribute will have empty strings at their indexes.

If attribute didn't exist in the graph, then an empty array of strings will be returned.

Example

            // Create a new graph and add some edges
            Graph g = new Graph();
            g.AddEdge(0, 1, 100);
            g.AddEdge(0, 2, 50);
            g.AddEdge(1, 2, 20);
 
            // Compress the graph before using it 
            g.CompressToCSR();

 
            // Add node attributes to the graph for the nodes
            // we just created
            g.AddNodeAttribute(2, "Attr", "200");
            g.AddNodeAttribute(1, "Attr", "100");
            g.AddNodeAttribute(0, "Attr", "0");
 
            // Get scores for this attribute from the graph
            var attr = g.GetNodeAttributes("Attr");
 
            // Print all results
            foreach (string score in attr)
                Debug.Write(score + ", ");
            Debug.WriteLine("");
 

0, 100, 200,

            // Add another node to the graph
            g.AddEdge(0, 4, 50);
 
            // Get the attributes again to update our list
            attr = g.GetNodeAttributes("Attr");
 
            // Print all results. Note how 4 is the empty string since it was not
            // Assigned a score for ATTR since it was added to the graph
            foreach (string score in attr)
                Debug.Write(score + ", ");
 

0, 100, 200, ,

GetNodeID()

int DHARTAPI.SpatialStructures.Graph.GetNodeID

(

Vector3D

node

)

Gets the ID of a node in the graph.

Parameters

node	The X,Y,Z position of a node to get the ID for.

Returns

The ID of the node, or -1 if the node isn't in the graph.

Examples

 
            // Create a graph
            Graph g = new Graph();
 
            // Create two nodes
            Vector3D node0 = new Vector3D(0, 0, 1);
            Vector3D node1 = new Vector3D(0, 0, 2);
 
            // Add an edge between them to add them to the graph
            g.AddEdge(node0, node1, 10);
 
            // Get their IDs from the graph
            int node_0_id = g.GetNodeID(node0);
            int node_1_id = g.GetNodeID(node1);
 
            // Print results
            Debug.WriteLine(node_0_id);
            Debug.WriteLine(node_1_id);

0
1

            // Create a third node and try to get it's id
            Vector3D node2 = new Vector3D(0, 0, 3);
            int node_2_id = g.GetNodeID(node2);
 
            Debug.WriteLine(node_2_id);

-1

Referenced by DHARTAPI.Pathfinding.ShortestPath.DijkstraShortestPath().

getNodes()

NodeList DHARTAPI.SpatialStructures.Graph.getNodes

(

)

Get an array containing the graph's current nodes.

Returns

An array of the graph's current nodes ordered by ID.

Example

            
            // Create a graph
            Graph G = new Graph();
 
            // Insert an edge between two nodes. This will effectively add the
            // nodes to the graph
            G.AddEdge(new Vector3D(0, 0, 2), new Vector3D(0, 0, 1), 39);
 
            // Get the nodes by calling G.getNodes();
            var nodes = G.getNodes();
            
            // Print the nodes
            Debug.WriteLine(nodes);
 

[(0, 0, 2), (0, 0, 1)]

NumNodes()

int DHARTAPI.SpatialStructures.Graph.NumNodes

(

)

Get the number of nodes in this graph.

Returns

The number of currently defined nodes in this graph

Remarks

This is used multiple times internally to get the size of the graph without needing to get its nodes.

Example

            // Create a new graph and add some edges
            Graph g = new Graph();
            g.AddEdge(0, 1, 100);
            g.AddEdge(0, 2, 50);
            g.AddEdge(1, 2, 20);
 
            // Compress the graph before using it 
            g.CompressToCSR();

 
            // Get the number of nodes in g
            int number_of_nodes = g.NumNodes();
 
            // Print 
            Debug.WriteLine(number_of_nodes);
 

3

Referenced by DHARTAPI.SpatialStructures.Graph.AddNodeAttribute< T >(), DHARTAPI.SpatialStructures.Graph.AggregateEdgeCosts(), DHARTAPI.Pathfinding.ShortestPath.DijkstraAllToAll(), and DHARTAPI.Pathfinding.ShortestPath.GeneratePredecessorAndDistanceMatricies().

ReleaseHandle()

override bool DHARTAPI.SpatialStructures.Graph.ReleaseHandle ( )

protected

Free the native memory managed by this class.

Note

the garbage collector will handle this automatically

Warning

Do not attempt to use this class after freeing it!

Returns

True. This is guaranteed to execute properly.

---

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

• src/Csharp/packages/spatialstructures/src/Graph.cs