The normalized input graphs used by GEDLIB. All labels are integers. More...

#include <ged_graph.hpp>

Public Types
typedef std::size_t	NodeID
	Internally used vertex ID type.

typedef detail::GedGraphAL::edge_descriptor	EdgeID
	Internally used edge ID type.

typedef std::vector< GEDGraph >::size_type	GraphID
	Type of internally used graph IDs.

typedef std::map< NodeID, NodeID >	NodeNodeMap
	Map that assigns node IDs to node IDs.

typedef std::map< NodeID, std::size_t >	NodeSizeTMap
	Map that assigns node IDs to integers.

typedef std::map< std::size_t, NodeID >	SizeTNodeMap
	Map that assigns node IDs to integers.

typedef detail::GedGraphAL::out_edge_iterator	incident_edge_iterator
	Iterator type for iterating over all the incident edges of a node in the graph.

typedef detail::GedGraphAL::edge_iterator	edge_iterator
	Iterator type for iterating over all edges of the graph.

typedef detail::GedGraphAL::vertex_iterator	node_iterator
	Iterator type for iterating over all nodes in the graph.

Public Member Functions
	GEDGraph ()
	Constructs an empty graph without meaningful ID.

	GEDGraph (GraphID id)
	Constructs an empty graph. More...

	GEDGraph (const GEDGraph &ged_graph)
	Copy constructor. More...

GraphID	id () const
	Returns the ID of the graph. More...

void	clear ()
	Clears the graph.

NodeID	add_node ()
	Adds a new vertex to the graph. More...

EdgeID	add_edge (NodeID tail, NodeID head)
	Adds a new edge to the graph. More...

void	set_label (NodeID node, LabelID label)
	Sets a node's label. More...

void	set_label (EdgeID edge, LabelID label)
	Sets a edges's label. More...

LabelID	get_node_label (NodeID node) const
	Returns the label of a given node. More...

LabelID	get_edge_label (EdgeID edge) const
	Returns the label of a given edge. More...

LabelID	get_edge_label (NodeID node_1, NodeID node_2) const
	Retrieves the label of an edge between two nodes or the dummy label if no edge exists. More...

void	setup_adjacency_matrix ()
	Prepares the adjacency matrix to allow quick retrieval of edges. More...

NodeID	tail (EdgeID edge) const
	Returns the tail of an edge. More...

NodeID	head (EdgeID edge) const
	Returns the head of an edge. More...

EdgeID	get_edge (NodeID tail, NodeID head) const
	Retrieves an edge from its incident nodes. More...

EdgeID	safe_get_edge (NodeID tail, NodeID head) const
	Retrieves an edge from its incident nodes. More...

bool	is_edge (NodeID tail, NodeID head) const
	Checks if an edge exists. More...

bool	safe_is_edge (NodeID tail, NodeID head) const
	Checks if an edge exists. More...

std::size_t	degree (NodeID node) const
	Returns node degree. More...

std::size_t	num_nodes () const
	Returns the number of nodes. More...

std::size_t	num_edges () const
	Returns the number of edges. More...

bool	initialized () const
	Checks if graph has already been initialized. More...

void	un_init ()
	Declare graph as un-initialized.

std::size_t	maxdeg () const
	Returns the maximum degree of the graph.

std::pair< node_iterator, node_iterator >	nodes () const
	Provides access to all nodes in the graph. More...

std::pair< edge_iterator, edge_iterator >	edges () const
	Provides access to all edge in the graph. More...

std::pair< incident_edge_iterator, incident_edge_iterator >	incident_edges (NodeID node) const
	Provides access to all incident edges of a node. More...

const detail::GedGraphAL &	get_adjacency_list () const
	Returns the internal adjacency list representation. More...

Static Public Member Functions
static NodeID	dummy_node ()
	Returns a dummy node. More...

static NodeID	undefined_node ()
	Returns an undefined node. More...

static EdgeID	dummy_edge ()
	Returns a dummy edge. More...

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

Detailed Description

The normalized input graphs used by GEDLIB. All labels are integers.

Definition at line 104 of file ged_graph.hpp.

Constructor & Destructor Documentation

◆ GEDGraph() [1/2]

ged::GEDGraph::GEDGraph ( GEDGraph::GraphID id )

Constructs an empty graph.

Parameters

[in] id The ID of the new graph.

Definition at line 41 of file ged_graph.ipp.

◆ GEDGraph() [2/2]

ged::GEDGraph::GEDGraph ( const GEDGraph & ged_graph )

Copy constructor.

Parameters

[in] ged_graph Graph that is to be copied.

Definition at line 48 of file ged_graph.ipp.

Member Function Documentation

◆ add_edge()

GEDGraph::EdgeID ged::GEDGraph::add_edge	(	NodeID	tail,
		NodeID	head
	)

Adds a new edge to the graph.

Parameters

[in]	tail	The tail of the newly added edge.
[in]	head	The head of the newly added edge

Returns: The ID of the newly added edge.

Definition at line 86 of file ged_graph.ipp.

◆ add_node()

GEDGraph::NodeID ged::GEDGraph::add_node ( )

Adds a new vertex to the graph.

Returns: The ID of the newly added vertex.

Definition at line 74 of file ged_graph.ipp.

◆ degree()

std::size_t ged::GEDGraph::degree ( NodeID node ) const

Returns node degree.

Parameters

[in] node Input node.

Returns: Degree of node node.

Definition at line 162 of file ged_graph.ipp.

◆ dummy_edge()

GEDGraph::EdgeID ged::GEDGraph::dummy_edge ( )

static

Returns a dummy edge.

Returns: ID of dummy edge.

Definition at line 68 of file ged_graph.ipp.

◆ dummy_node()

GEDGraph::NodeID ged::GEDGraph::dummy_node ( )

static

Returns a dummy node.

Returns: ID of dummy node.

Definition at line 56 of file ged_graph.ipp.

◆ edges()

std::pair< GEDGraph::edge_iterator, GEDGraph::edge_iterator > ged::GEDGraph::edges ( ) const

Provides access to all edge in the graph.

Returns: A pair of iterators whose first member points to the first edge in the graph and whose second member points past the last edge in the graph.

Definition at line 217 of file ged_graph.ipp.

◆ get_adjacency_list()

const detail::GedGraphAL & ged::GEDGraph::get_adjacency_list ( ) const

Returns the internal adjacency list representation.

Returns: Internal adjacency list representation.

Definition at line 156 of file ged_graph.ipp.

◆ get_edge()

GEDGraph::EdgeID ged::GEDGraph::get_edge	(	NodeID	tail,
		NodeID	head
	)		const

Retrieves an edge from its incident nodes.

Parameters

[in]	tail	First incident node of the edge.
[in]	head	Second incident node of the edge.

Returns: The ID of the edge that connects tail with head, if the edge exists. Otherwise, dummy_edge() is returned.

Warning: This function uses the adjacency matrix. Ensure you called setup_adjacency_matrix() before calling.

Definition at line 241 of file ged_graph.ipp.

◆ get_edge_label() [1/2]

LabelID ged::GEDGraph::get_edge_label ( EdgeID edge ) const

Returns the label of a given edge.

Parameters

[in] edge The ID of the edge whose label is to be returned.

Returns: The ID of the label of edge edge.

Definition at line 135 of file ged_graph.ipp.

◆ get_edge_label() [2/2]

LabelID ged::GEDGraph::get_edge_label	(	NodeID	node_1,
		NodeID	node_2
	)		const

Retrieves the label of an edge between two nodes or the dummy label if no edge exists.

Parameters

[in]	node_1	ID of first node.
[in]	node_2	ID of second node.

Returns: The label of the edge that connects node_1 with node_2 or the dummy label if no edge exists.

Definition at line 141 of file ged_graph.ipp.

◆ get_node_label()

LabelID ged::GEDGraph::get_node_label ( NodeID node ) const

Returns the label of a given node.

Parameters

[in] node The ID of the node whose label is to be returned.

Returns: The ID of the label of node node.

Definition at line 126 of file ged_graph.ipp.

◆ head()

GEDGraph::NodeID ged::GEDGraph::head ( EdgeID edge ) const

Returns the head of an edge.

Parameters

[in] edge The ID of the edge whose head is to be returned.

Returns: The ID of the head of edge's internal representation as directed edge.

Note: Since GEDGraphs are undirected, the head of an edge is not well defined. However, given the same edge ID, head() always returns the same node.

Definition at line 199 of file ged_graph.ipp.

◆ id()

GEDGraph::GraphID ged::GEDGraph::id ( ) const

Returns the ID of the graph.

Returns: ID of the graph.

Definition at line 184 of file ged_graph.ipp.

◆ incident_edges()

std::pair< GEDGraph::incident_edge_iterator, GEDGraph::incident_edge_iterator > ged::GEDGraph::incident_edges ( NodeID node ) const

Provides access to all incident edges of a node.

Parameters

[in] node ID of the node whose incident edges should be returned.

Returns: A pair of iterators whose first member points to the first incident edge of the node node and whose second member points past the last incident edge of the node node.

Definition at line 150 of file ged_graph.ipp.

◆ initialized()

bool ged::GEDGraph::initialized ( ) const

Checks if graph has already been initialized.

Returns: Boolean true if the adjacency matrix is up to date, false otherwise.

Definition at line 229 of file ged_graph.ipp.

◆ is_edge()

bool ged::GEDGraph::is_edge	(	NodeID	tail,
		NodeID	head
	)		const

Checks if an edge exists.

Parameters

[in]	tail	First node.
[in]	head	Second node.

Returns: Boolean true if there is an edge that connects tail with head, and false otherwise.

Warning: This function uses the adjacency matrix. Ensure you called setup_adjacency_matrix() before calling.

Definition at line 262 of file ged_graph.ipp.

◆ nodes()

std::pair< GEDGraph::node_iterator, GEDGraph::node_iterator > ged::GEDGraph::nodes ( ) const

Provides access to all nodes in the graph.

Returns: A pair of iterators whose first member points to the first node in the graph and whose second member points past the last node in the graph.

Definition at line 205 of file ged_graph.ipp.

◆ num_edges()

std::size_t ged::GEDGraph::num_edges ( ) const

Returns the number of edges.

Returns: Number of edges contained in the graph.

Definition at line 223 of file ged_graph.ipp.

◆ num_nodes()

std::size_t ged::GEDGraph::num_nodes ( ) const

Returns the number of nodes.

Returns: Number of nodes contained in the graph.

Definition at line 211 of file ged_graph.ipp.

◆ safe_get_edge()

GEDGraph::EdgeID ged::GEDGraph::safe_get_edge	(	NodeID	tail,
		NodeID	head
	)		const

Retrieves an edge from its incident nodes.

Parameters

[in]	tail	First incident node of the edge.
[in]	head	Second incident node of the edge.

Returns: The ID of the edge that connects tail with head, if the edge exists. Otherwise, dummy_edge() is returned.

Note: This function uses the adjacency list. It is hence slower than get_edge() but does not expect that setup_adjacency_matrix() has been called.

Definition at line 251 of file ged_graph.ipp.

◆ safe_is_edge()

bool ged::GEDGraph::safe_is_edge	(	NodeID	tail,
		NodeID	head
	)		const

Checks if an edge exists.

Parameters

[in]	tail	First node.
[in]	head	Second node.

Returns: Boolean true if there is an edge that connects tail with head, and false otherwise.

Note: This function uses the adjacency list. It is hence slower than is_edge() but does not expect that setup_adjacency_matrix() has been called.

Definition at line 272 of file ged_graph.ipp.

◆ set_label() [1/2]

void ged::GEDGraph::set_label	(	NodeID	node,
		LabelID	label
	)

Sets a node's label.

Parameters

[in]	node	The ID of the node whose label should be set.
[in]	label	The ID of the label that should be assigned to the node `node`.

Definition at line 114 of file ged_graph.ipp.

◆ set_label() [2/2]

void ged::GEDGraph::set_label	(	EdgeID	edge,
		LabelID	label
	)

Sets a edges's label.

Parameters

[in]	edge	The ID of the edge whose label should be set.
[in]	label	The ID of the label that should be assigned to the edge `edge`.

Definition at line 120 of file ged_graph.ipp.

◆ setup_adjacency_matrix()

void ged::GEDGraph::setup_adjacency_matrix ( )

Prepares the adjacency matrix to allow quick retrieval of edges.

Warning: Calls to the member add_edge() invalidate the matrix.

Definition at line 95 of file ged_graph.ipp.

◆ tail()

GEDGraph::NodeID ged::GEDGraph::tail ( EdgeID edge ) const

Returns the tail of an edge.

Parameters

[in] edge The ID of the edge whose tail is to be returned.

Returns: The ID of the tail of edge's internal representation as directed edge.

Note: Since GEDGraphs are undirected, the tail of an edge is not well defined. However, given the same edge ID, tail() always returns the same node.

Definition at line 178 of file ged_graph.ipp.

◆ undefined_node()

GEDGraph::NodeID ged::GEDGraph::undefined_node ( )

static

Returns an undefined node.

Returns: ID of undefined node.

Definition at line 62 of file ged_graph.ipp.

Friends And Related Function Documentation

◆ operator<<()

std::ostream & operator<<	(	std::ostream &	os,
		const GEDGraph &	graph
	)

Parameters

[in,out]	os	Output stream.
[in]	graph	The graph that should be streamed.

Returns: The output stream os.

Definition at line 281 of file ged_graph.ipp.

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

src/env/ged_graph.hpp
src/env/ged_graph.ipp

Public Types

Public Member Functions

Static Public Member Functions

Related Functions

Detailed Description

Constructor & Destructor Documentation

◆ GEDGraph() [1/2]

◆ GEDGraph() [2/2]

Member Function Documentation

◆ add_edge()

◆ add_node()

◆ degree()

◆ dummy_edge()

◆ dummy_node()

◆ edges()

◆ get_adjacency_list()

◆ get_edge()

◆ get_edge_label() [1/2]

◆ get_edge_label() [2/2]

◆ get_node_label()

◆ head()

◆ id()

◆ incident_edges()

◆ initialized()

◆ is_edge()

◆ nodes()

◆ num_edges()

◆ num_nodes()

◆ safe_get_edge()

◆ safe_is_edge()

◆ set_label() [1/2]

◆ set_label() [2/2]

◆ setup_adjacency_matrix()

◆ tail()

◆ undefined_node()

Friends And Related Function Documentation

◆ operator<<()