A class for node maps. More...

#include <node_map.hpp>

Public Member Functions
	NodeMap (std::size_t num_nodes_g, std::size_t num_nodes_h)
	Default constructor. More...

	NodeMap (const NodeMap &node_map)
	Copy constructor. More...

void	operator= (const NodeMap &node_map)
	Assignment operator. More...

void	clear ()
	Clears the node map.

bool	empty () const
	Checks if the node map is empty. More...

std::size_t	num_source_nodes () const
	Returns number of source nodes contained in the node map. More...

std::size_t	num_target_nodes () const
	Returns number of target nodes contained in the node map. More...

bool	complete (const GEDGraph &g, const GEDGraph &h) const
	Checks if the node map is complete. More...

GEDGraph::NodeID	image (GEDGraph::NodeID node) const
	Returns image of a node. More...

GEDGraph::NodeID	pre_image (GEDGraph::NodeID node) const
	Returns pre-image of a node. More...

void	as_relation (std::vector< Assignment > &relation) const
	Constructs the representation as relation. More...

double	induced_cost () const
	Returns the induced cost. More...

void	add_assignment (GEDGraph::NodeID i, GEDGraph::NodeID k)
	Add node substitution, insertion, or deletion to the node map. More...

void	erase_image (GEDGraph::NodeID node)
	Erases image of a node. More...

void	erase_pre_image (GEDGraph::NodeID node)
	Erases pre-image of a node. More...

void	set_induced_cost (double induced_cost)
	Sets the induced cost of the node map. More...

bool	operator< (const NodeMap &node_map) const
	Compares this node map to another node map. More...

bool	operator== (const NodeMap &node_map) const
	Checks if two node maps are the same. More...

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &os, const NodeMap &node_map)
	Streams a node map. More...

Detailed Description

A class for node maps.

Node maps are relations between the node sets of two graphs augmented with one dummy node each such that each real node is assigned at most once. The exact definition can be found in: D. B. Blumenthal, J. Gamper. On the exact computation of the graph edit distance. Pattern Recogn. Lett. 2018, in press.

Definition at line 43 of file node_map.hpp.

Constructor & Destructor Documentation

◆ NodeMap() [1/2]

ged::NodeMap::NodeMap	(	std::size_t	num_nodes_g,
		std::size_t	num_nodes_h
	)

Default constructor.

Parameters

[in]	num_nodes_g	Number of nodes in first input graph.
[in]	num_nodes_h	Number of nodes in second input graph.

Definition at line 33 of file node_map.ipp.

◆ NodeMap() [2/2]

ged::NodeMap::NodeMap ( const NodeMap & node_map )

Copy constructor.

Parameters

[in] node_map Node map that should be copied.

Definition at line 39 of file node_map.ipp.

Member Function Documentation

◆ add_assignment()

void ged::NodeMap::add_assignment	(	GEDGraph::NodeID	i,
		GEDGraph::NodeID	k
	)

Add node substitution, insertion, or deletion to the node map.

Parameters

[in]	i	Source node. If ged::GEDGraph::dummy_node(), the method adds a node insertion to the node map.
[in]	k	Target node. If ged::GEDGraph::dummy_node(), the method adds a node deletion to the node map.

Note: If both i and k equal ged::GEDGraph::dummy_node(), calling this method has no effect.

Definition at line 183 of file node_map.ipp.

◆ as_relation()

void ged::NodeMap::as_relation ( std::vector< Assignment > & relation ) const

Constructs the representation as relation.

Parameters

[out] relation Contains the pairs of nodes in the relation. The first member of a pair contained in the relation is a node in the first graph or the dummy node, the second member is a node in the second graph or the dummy node.

Definition at line 164 of file node_map.ipp.

◆ complete()

bool ged::NodeMap::complete	(	const GEDGraph &	g,
		const GEDGraph &	h
	)		const

Checks if the node map is complete.

Parameters

[in]	g	Source graph.
[in]	h	Target graph.

Returns: Boolean true if and only if, for all nodes in the graphs g and h, the node map contains a substitution, an insertion, or a deletion.

Definition at line 93 of file node_map.ipp.

◆ empty()

bool ged::NodeMap::empty ( ) const

Checks if the node map is empty.

Returns: Boolean true if the map is empty and false otherwise.

Definition at line 65 of file node_map.ipp.

◆ erase_image()

void ged::NodeMap::erase_image ( GEDGraph::NodeID node )

Erases image of a node.

Parameters

[in] node Node whose image is to be erased.

Definition at line 122 of file node_map.ipp.

◆ erase_pre_image()

void ged::NodeMap::erase_pre_image ( GEDGraph::NodeID node )

Erases pre-image of a node.

Parameters

[in] node Node whose pre-image is to be erased.

Definition at line 149 of file node_map.ipp.

◆ image()

GEDGraph::NodeID ged::NodeMap::image ( GEDGraph::NodeID node ) const

Returns image of a node.

Parameters

[in] node Node whose image is to be returned.

Returns: Node to which node node is assigned.

Definition at line 110 of file node_map.ipp.

◆ induced_cost()

double ged::NodeMap::induced_cost ( ) const

Returns the induced cost.

Returns: The cost induced by the node map. Equals std::numeric_limits<double>::infinity() if the induced has not been set by call to set_induced_cost().

Definition at line 210 of file node_map.ipp.

◆ num_source_nodes()

std::size_t ged::NodeMap::num_source_nodes ( ) const

Returns number of source nodes contained in the node map.

Returns: Number of source nodes.

Definition at line 81 of file node_map.ipp.

◆ num_target_nodes()

std::size_t ged::NodeMap::num_target_nodes ( ) const

Returns number of target nodes contained in the node map.

Returns: Number of target nodes.

Definition at line 87 of file node_map.ipp.

◆ operator<()

bool ged::NodeMap::operator< ( const NodeMap & node_map ) const

Compares this node map to another node map.

Parameters

[in] node_map The node to which this node map should be compared.

Returns: Boolean true if the induced cost is smaller than the induced cost of node_map and false otherwise.

Definition at line 216 of file node_map.ipp.

◆ operator=()

void ged::NodeMap::operator= ( const NodeMap & node_map )

Assignment operator.

Parameters

[in] node_map Node map that should be assigned.

Definition at line 46 of file node_map.ipp.

◆ operator==()

bool ged::NodeMap::operator== ( const NodeMap & node_map ) const

Checks if two node maps are the same.

Parameters

[in] node_map The node map to which this node map should be compared.

Returns: Boolean true if both node maps are the same and false otherwise.

Definition at line 222 of file node_map.ipp.

◆ pre_image()

GEDGraph::NodeID ged::NodeMap::pre_image ( GEDGraph::NodeID node ) const

Returns pre-image of a node.

Parameters

[in] node Node whose pre_image is to be returned.

Returns: Node which is assigned to node node.

Definition at line 137 of file node_map.ipp.

◆ set_induced_cost()

void ged::NodeMap::set_induced_cost ( double induced_cost )

Sets the induced cost of the node map.

Parameters

[in] induced_cost The induced cost of the node map.

Definition at line 204 of file node_map.ipp.

Friends And Related Function Documentation

◆ operator<<()

std::ostream & operator<<	(	std::ostream &	os,
		const NodeMap &	node_map
	)

Parameters

[in,out]	os	Output stream.
[in]	node_map	The node map that should be streamed.

Returns: The output stream os.

Definition at line 226 of file node_map.ipp.

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

src/env/node_map.hpp
src/env/node_map.ipp

Public Member Functions

Related Functions

Detailed Description

Constructor & Destructor Documentation

◆ NodeMap() [1/2]

◆ NodeMap() [2/2]

Member Function Documentation

◆ add_assignment()

◆ as_relation()

◆ complete()

◆ empty()

◆ erase_image()

◆ erase_pre_image()

◆ image()

◆ induced_cost()

◆ num_source_nodes()

◆ num_target_nodes()

◆ operator<()

◆ operator=()

◆ operator==()

◆ pre_image()

◆ set_induced_cost()

Friends And Related Function Documentation

◆ operator<<()