#include <ImFusion/Graph/Graph.h>

Class for representing a (potentially directed) graph. More...

Inheritance diagram for Graph:

Detailed Description

Class for representing a (potentially directed) graph.

Such a graph is an AbstractGraph that is guaranteed to have several invariants enforced:

For each edge (i, j), there is the edge (j, i) in the graph. For undirected graphs these are the same. For directed graphs, one of them may be missing (i.e. std::nullopt).
Each node has a fixed number of features (see the m_nodeFeatures member).
Each edge has a fixed number of features (see the m_edgeFeatures member). These invariants ensure that:

Deleting a node is O(log(N)) (assuming some fixed number of edges per node).

Features can be accessed by index, and are guaranteed to exist. Self-loops are allowed. To allow for access that preserves the above invariants, a functional interface is provided.

Classes
class	EdgeInfo
	Information stored at each edge of the graph. More...

struct	FeatureDescriptor

class	NodeInfo
	Information stored at each node of the graph. More...

Public Types
enum class	Dimension { Dimension2D , Dimension3D }

enum class	Type { Directed , Undirected }

enum class	TraversalStrategy { BFS , DFS }

using	NodeIndex = size_t

using	Neighborhood = std::map<NodeIndex, std::optional<EdgeInfo>>

Public Types inherited from Data
enum	Kind { UNKNOWN = 0 , IMAGE = 1 , VOLUME = 2 , IMAGESET = 3 , VOLUMESET = 4 , IMAGESTREAM = 5 , VOLUMESTREAM = 6 , POINTSET = 7 , SURFACE = 8 , TRACKINGSTREAM = 9 , LIVETRACKINGSTREAM = TRACKINGSTREAM , TRACKINGDATA = 10 , TREE = 11 , TENSOR = 12 , POLYDATASTREAM = 13 , STEREOIMAGESET = 14 , STEREOIMAGESTREAM = 15 , VOLUMETRICMESH = 16 }
	Kind of data. More...

enum	Modality { NA = 0 , XRAY = 1 , CT = 2 , MRI = 3 , ULTRASOUND = 4 , VIDEO = 5 , NM = 6 , OCT = 7 , LABEL = 8 , DISTANCE = 9 }
	Image modality of the data. More...

Public Member Functions
	Graph (Type type=Type::Undirected, Dimension dim=Dimension::Dimension3D)

Data::Kind	kind () const override
	Return the kind of this data.

Data::Modality	modality () const override
	Return the modality of this data.

Pose::TransformationConvention	matrixConvention () const override
	Defines whether the internally stored matrices in derived classes map from or to the world coordinate system.

Geometry::AlignedBox	bounds () const override
	Returns the axis-aligned bounding box of this data in world space.

void	addEdgeFeatureDescriptors (std::vector< FeatureDescriptor > f)
	Adds edge feature descriptors and populates edge feature vectors with the descriptors default values.

void	addNodeFeatureDescriptors (std::vector< FeatureDescriptor > f)
	Adds node feature descriptors and populates feature vectors with the descriptors default values.

void	clearFeatureDescriptors ()
	Clears all node and edge feature descriptors.

NodeIndex	addNode (NodeInfo nodeData)
	Adds a new node with the given NodeInfo. The node index is assigned as the current max index + 1.

bool	addOrReplaceNode (NodeIndex index, NodeInfo nodeData)
	Set the node-info at the given node to the given value.

const NodeInfo &	node (NodeIndex nodeIndex) const
	Returns the NodeInfo for the given node index.

bool	hasNode (NodeIndex nodeIndex) const
	Checks if a node with the given index exists.

const std::optional< EdgeInfo > &	edge (NodeIndex nodeIndexStart, NodeIndex nodeIndexEnd) const
	Returns the edge (EdgeInfo) between two nodes, if it exists.

int	numNodes () const
	Returns the number of nodes in the graph.

int	maxNodeIdx () const
	Returns the maximum node index currently in use.

void	removeNode (NodeIndex nodeIndex)
	Removes the node with the specified index.

void	editNode (NodeIndex nodeIndex, const std::function< void(NodeInfo &)> &f)
	Edits the node data at the given index using the provided function.

void	editEachNode (const std::function< void(NodeIndex, NodeInfo &)> &f)
	Applies the given function to each node.

void	editEachNode (const std::function< void(NodeIndex, NodeInfo &, const Neighborhood &neighborhood)> &f)
	Applies the given function to each node with access to its neighborhood, i.e. connected nodes and edges.

Properties &	nodeAttributes (NodeIndex nodeIndex)
	Returns access to the properties of the node at the given index.

const Properties &	nodeAttributes (NodeIndex nodeIndex) const

const Neighborhood &	neighborhood (NodeIndex nodeIndex) const
	Returns the neighborhood of a given node, i.e. info on its neighboring nodes and edges.

void	forEachNode (const std::function< void(NodeIndex, const NodeInfo &)> &f, Graph::NodeIndex start, TraversalStrategy strategy=TraversalStrategy::DFS) const
	Traverse graph in BFS or DFS from the given node and run a function for each node of the graph.

void	forEachNode (const std::function< void(NodeIndex, const NodeInfo &, const EdgeInfo *)> &f, Graph::NodeIndex start, TraversalStrategy strategy=TraversalStrategy::DFS) const
	Traverse graph in BFS or DFS from the given node and run a function for each node of the graph along with the incoming edge (nullptr for the start node)

void	forEachNode (const std::function< void(NodeIndex, const NodeInfo &)> &f) const
	Run a function for each node of the graph.

void	forEachNode (const std::function< void(NodeIndex, const NodeInfo &, const Neighborhood &neighborhood)> &f) const
	Run a function for each node of the graph, the function is given the node, its index, and the edges connected to the node.

void	traverse (NodeIndex startNode, const std::function< const Graph::NodeInfo (const std::vector< const Graph::NodeInfo > &)> &nextNode) const
	Traverse a path through the graph. The graph is non-intersecting. The function obtains a vector of possible next nodes on the path, and should choose a value from it (or nullptr to stop).

void	traverse (NodeIndex startNode, const std::function< const Graph::NodeInfo (Graph::NodeIndex, const Graph::NodeInfo &, const std::vector< const Graph::NodeInfo > &)> &nextNode) const

void	traverse (NodeIndex startNode, const std::function< const Graph::NodeInfo (Graph::NodeIndex, const Graph::NodeInfo &, const std::vector< const Graph::NodeInfo > &, const std::vector< Graph::NodeIndex > &)> &nextNode) const

void	addEdge (NodeIndex nodeIndexStart, NodeIndex nodeIndexEnd, EdgeInfo edgeData)
	Add an edge. The edge is assumed to not exist. The node indexes must exist.

void	removeEdge (NodeIndex nodeIndexStart, NodeIndex nodeIndexEnd)
	Rmove an edge. If the edge does not exist, nothing happens.

int	numEdges () const
	Returns the number of edges. For undirected graphs, edges are not counted twice.

void	forEachEdge (std::function< void(const EdgeInfo &, const NodeInfo &from, const NodeInfo &to)> f) const
	Iterate over all edges in the graph.

void	forEachEdge (std::function< void(const EdgeInfo &, NodeIndex from, NodeIndex to)> f) const
	Iterate over all edges in the graph.

void	forEachEdge (std::function< void(const EdgeInfo &, NodeIndex fromIndex, const NodeInfo &from, NodeIndex toIndex, const NodeInfo &to)> f) const
	Iterate over all edges in the graph.

template<typename T, typename Init>
Init	accumulateNodes (T Op, Init init) const
	Run a reduction over the graph.

template<typename NodeT, typename EdgeT>
Graph	transform (NodeT nodeT, EdgeT edgeT, std::optional< std::vector< FeatureDescriptor > > outputNodeFeatures=std::nullopt, std::optional< std::vector< FeatureDescriptor > > outputEdgeFeatures=std::nullopt) const
	Create a graph with the same structure as this graph, but with different node and edge data.

void	editEachEdge (const std::function< void(EdgeInfo &, const NodeInfo &from, const NodeInfo &to)> &f)
	Edit each edge in place. For undirected graphs, the function f is called on only half the edges, the remaining half is computed using EdgeInfo::reverse;.

void	editEachEdge (const std::function< void(EdgeInfo &, NodeIndex from, NodeIndex to)> &f)
	Edit each edge in place. For undirected graphs, the function f is called on only half the edges, the remaining half is computed using EdgeInfo::reverse;.

void	editEachEdge (const std::function< void(EdgeInfo &, NodeIndex fromIndex, const NodeInfo &from, NodeIndex toIndex, const NodeInfo &to)> &f)
	Edit each edge in place. For undirected graphs, the function f is called on only half the edges, the remaining half is computed using EdgeInfo::reverse;.

void	editEdge (NodeIndex nodeIndexStart, NodeIndex nodeIndexEnd, const std::function< void(EdgeInfo &)> &f)
	Edit an edge. For undirected graphs, the symmetrized edge is updated directly.

std::optional< int >	getEdgeFeatureIdx (const std::string &featureName) const
	Find index of specific edge feature.

int	getOrCreateEdgeFeatureIdx (const std::string &featureName, double defaultValue)
	Find index of specific edge feature or create feature.

std::optional< int >	getNodeFeatureIdx (const std::string &featureName) const
	Find index of specific node feature.

int	getOrCreateNodeFeatureIdx (const std::string &featureName, double defaultValue)
	Find index of specific node feature or create feature.

void	setDirected ()
	Sets the graph type to Directed.

Type	type () const
	Returns the graph type.

Dimension	dimension () const
	Returns the graph dimension.

void	setDimension (Dimension dim)
	Sets the graph dimension.

bool	empty () const
	Checks if the graph has no edges.

const std::vector< FeatureDescriptor > &	nodeFeatureDescriptors () const
	Returns the descriptors of node features.

const std::vector< FeatureDescriptor > &	edgeFeatureDescriptors () const
	Returns the descriptors of edge features.

int	numNodeFeatures () const
	Returns the number of node features.

int	numEdgeFeatures () const
	Returns the number of edge features.

void	removeNodeFeatures (const std::vector< std::size_t > &indicesToRemove)
	Removes node features by their indices.

void	removeNodeFeatures (const std::vector< std::string > &featuresToRemove)
	Removes node features by their names.

void	removeEdgeFeatures (const std::vector< std::size_t > &indicesToRemove)
	Removes edge features by their indices.

void	removeEdgeFeatures (const std::vector< std::string > &featuresToRemove)
	Removes edge features by their names.

Public Member Functions inherited from Data
	Data (const std::string &name="")

	Data (const Data &other)

Data &	operator= (const Data &other)

virtual	~Data ()
	Mandatory virtual destructor.

const std::string &	name () const
	Return the name of this data.

void	setName (const std::string &name)
	Sets the name of this data.

virtual bool	isAnnotationType () const
	Return whether this data type is visualized through an annotation (e.g. mesh)

const DataComponentList &	components () const
	Returns the list of DataComponents for this data.

DataComponentList &	components ()

virtual std::string	describe () const
	Human readable description of the data for showing in the info bar.

virtual void	setMatrixFromWorld (const mat4 &m)
	Set matrix mapping from the world coordinate system to the data coordinate system.

virtual void	setMatrixToWorld (const mat4 &m)
	Set matrix mapping from the data coordinate system to the world coordinate system.

virtual mat4	matrixFromWorld () const
	Get matrix mapping from the world coordinate system to the data coordinate system.

virtual mat4	matrixToWorld () const
	Get matrix mapping from the data coordinate system to the world coordinate system.

virtual mat4	matrix () const
	Return the transformation matrix.

virtual void	setMatrix (const mat4 &m)
	Set the transformation matrix.

Protected Member Functions
void	fixNodeInfo (NodeInfo &nodeDataInOut)
	Ensure that all invariants for nodeDataInOut are met, by force.

void	fixEdgeInfo (EdgeInfo &edgeDataInOut)
	Ensure that all invariants for edgeDataInOut are met, by force.

Protected Member Functions inherited from Data
void	swapWith (Data &other)
	Swaps the data and emits a matrix and name changed signal for both.

Protected Attributes
NodeIndex	m_maxNodeIndex {0}

detail::GraphImpl< std::optional< EdgeInfo >, NodeInfo, NodeIndex >	m_graphImpl

Protected Attributes inherited from Data
mat4	m_matrix
	Transformation matrix.

std::recursive_mutex *	m_matrixMutex
	Used to internally synchronize access to the matrix of data.

DataComponentList	m_dataComponentList
	The list of DataComponents for this data.

Additional Inherited Members
Static Public Member Functions inherited from Data
static std::string	modalityString (Data::Modality m)
	Return the name of an image modality.

static Data::Modality	stringToModality (const std::string &s)
	Returns the modality corresponding to a modality string or NA if nothing matches.

Public Attributes inherited from Data
Signal< const Data * >	signalDeleted
	Signal emitted when this instance is deleted.

Signal< const Data * >	signalMatrixChanged
	Signal emitted when the transformation of this Data has changed.

Signal< std::string >	signalNameChanged
	Signal emitted when the name changed.

Member Function Documentation

◆ kind()

Data::Kind kind ( ) const

inlineoverridevirtual

Return the kind of this data.

Implements Data.

◆ modality()

Data::Modality modality ( ) const

inlineoverridevirtual

Return the modality of this data.

The default implementation will always return NA, sub classes may override this method.

Reimplemented from Data.

◆ matrixConvention()

Pose::TransformationConvention matrixConvention ( ) const

inlineoverridevirtual

Defines whether the internally stored matrices in derived classes map from or to the world coordinate system.

Changes the behavior of the default implementations of matrixToWorld and matrixFromWorld.

Implements Data.

◆ bounds()

Geometry::AlignedBox bounds ( ) const

overridevirtual

Returns the axis-aligned bounding box of this data in world space.

Warning: Depending on the underlying data type this calling function may be computationally expensive! Do not call this method more often than needed, unless it is known that the caching behavior is implemented.

Implements Data.

◆ addOrReplaceNode()

bool addOrReplaceNode	(	NodeIndex	index,
		NodeInfo	nodeData )

Set the node-info at the given node to the given value.

If the node does not exist, it is created.

Returns: true if the node was added, false if it was replaced.

◆ forEachNode()

void forEachNode ( const std::function< void(NodeIndex, const NodeInfo &, const Neighborhood &neighborhood)> & f ) const

Run a function for each node of the graph, the function is given the node, its index, and the edges connected to the node.

Warning: : Entries of the map that are std::nullopt should be treated as non-edges. These can only occur for directed graphs.

◆ forEachEdge() [1/3]

void forEachEdge ( std::function< void(const EdgeInfo &, const NodeInfo &from, const NodeInfo &to)> f ) const

Iterate over all edges in the graph.

For undirected graphs: the function f is called for either the edge or its reverse (but not both), depending on the order of the nodes.

◆ forEachEdge() [2/3]

void forEachEdge ( std::function< void(const EdgeInfo &, NodeIndex from, NodeIndex to)> f ) const

Iterate over all edges in the graph.

For undirected graphs: the function f is called for either the edge or its reverse (but not both), depending on the order of the nodes.

◆ forEachEdge() [3/3]

void forEachEdge ( std::function< void(const EdgeInfo &, NodeIndex fromIndex, const NodeInfo &from, NodeIndex toIndex, const NodeInfo &to)> f ) const

Iterate over all edges in the graph.

For undirected graphs: the function f is called for either the edge or its reverse (but not both), depending on the order of the nodes.

◆ transform()

template<typename NodeT, typename EdgeT>

Graph transform	(	NodeT	nodeT,
		EdgeT	edgeT,
		std::optional< std::vector< FeatureDescriptor > >	outputNodeFeatures = std::nullopt,
		std::optional< std::vector< FeatureDescriptor > >	outputEdgeFeatures = std::nullopt ) const

Create a graph with the same structure as this graph, but with different node and edge data.

Parameters

nodeT	A function that takes argument (nodeIndex, const NodeData&) and returns an object of type NodeData
edgeT	A function that transforms the edge data.
outputNodeFeatures	Optional output feature descriptors for the nodes.
outputEdgeFeatures	Optional output feature descriptors for the edges.

◆ fixNodeInfo()

void fixNodeInfo ( NodeInfo & nodeDataInOut )

protected

Ensure that all invariants for nodeDataInOut are met, by force.

i.e resizes feature vectors to have the correct size

◆ fixEdgeInfo()

void fixEdgeInfo ( EdgeInfo & edgeDataInOut )

protected

Ensure that all invariants for edgeDataInOut are met, by force.

i.e resizes feature vectors to have the correct size

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

ImFusion/Graph/Graph.h

Detailed Description

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Function Documentation

◆ kind()

◆ modality()

◆ matrixConvention()

◆ bounds()

◆ addOrReplaceNode()

◆ forEachNode()

◆ forEachEdge() [1/3]

◆ forEachEdge() [2/3]

◆ forEachEdge() [3/3]

◆ transform()

◆ fixNodeInfo()

◆ fixEdgeInfo()