C++ API

class BaseNode

#include <base_node.h>

Base class for all vertex property classes in the GHL.

BaseNode provides core functionality for vertex properties, including:

Unique identification through ID management
Cloning capability for graph operations
GraphViz attribute generation for visualization
Optional serialization support

This class is designed to be inherited from when creating custom vertex property types. See the City class in examples/city.h for an example of proper inheritance and extension.

Public Functions

inline explicit BaseNode(int id = -1)

Constructs a BaseNode with the specified ID.

Parameters:: id – The unique identifier for the node. Defaults to -1 if not specified.

inline virtual std::shared_ptr<BaseNode> clone()

Creates a clone of the node.

This virtual method enables polymorphic cloning of nodes, which is essential for graph operations that require copying vertices.

Returns:: std::shared_ptr<BaseNode> A smart pointer to a new instance with the same properties.

virtual ~BaseNode() = default: Virtual destructor to ensure proper cleanup of derived classes.

inline int id() const

Gets the node’s ID.

Returns:: The unique identifier of the node.

inline void id(int id)

Sets the node’s ID.

Parameters:: id – The new unique identifier for the node.

inline bool operator==(const BaseNode &other) const

Equality comparison operator.

Nodes are considered equal if they have the same ID. This is used in graph algorithms that need to compare vertices.

Parameters:: other – The node to compare with.
Returns:: true if the nodes have the same ID, false otherwise.

inline virtual std::map<std::string, std::string, std::less<>> graphAttributes()

Generates GraphViz attributes for visualization.

This virtual method can be overridden by derived classes to customize the appearance of nodes in GraphViz output. The base implementation provides a simple label with the node’s ID.

Returns:: A map of GraphViz attribute names to values.

Private Members

int id_ = INT_MIN: Unique identifier for the node.

template<class T> class construct

struct edge_comp_helper

#include <graph_isomorphisms.h>

Helper struct for edge comparison during isomorphism detection.

Public Functions

inline edge_comp_helper(const GraphType &G1, const GraphType &G2, EdgeCompFunction ecf)

inline bool operator()(const EdgeDescriptor e1, const EdgeDescriptor e2) const

Public Members

const GraphType &G1_: Pattern graph reference.

const GraphType &G2_: Target graph reference.

EdgeCompFunction ecf_: Edge comparison callback.

template<typename VertexProperties, typename DirectionProperty, typename EdgeProperties = b::no_property> struct EdgeReplacementStruct

#include <graph.h>

Represents the replacement of an edge in a graph.

Template Parameters:

VertexProperties – Properties associated with vertices.
DirectionProperty – Boost direction selector for the graph.
EdgeProperties – Properties associated with edges (default: boost::no_property).

Public Types

using VertexDescriptor = Graph<VertexProperties, DirectionProperty, EdgeProperties>::vertex_descriptor: Vertex descriptor type.

Public Members

VertexDescriptor src_trg: The source or target vertex of the edge.

VertexDescriptor old_vertex: The old vertex to be replaced.

VertexDescriptor new_vertex: The new vertex replacing the old one.

EdgeProperties edge_properties: Properties of the edge being replaced.

template<typename VertexProperties_, typename DirectionProperty_, typename EdgeProperties_ = b::no_property> class ExtendedGraph

#include <graph.h>

A wrapper class around a Boost graph providing extended functionality.

Template Parameters:

VertexProperties – Properties associated with vertices.
DirectionProperty – Boost direction selector for the underlying graph.
EdgeProperties – Properties associated with edges (default: boost::no_property).

Public Types

using GraphType = Graph<VertexProperties_, DirectionProperty_, EdgeProperties_>: Alias for the graph type.

using VertexDescriptor = GraphType::vertex_descriptor: Descriptor for vertices.

using EdgeDescriptor = GraphType::edge_descriptor: Descriptor for edges.

using VertexProperties = VertexProperties_: Vertex property type.

using DirectionProperty = DirectionProperty_: Graph direction selector type.

using EdgeProperties = EdgeProperties_: Edge property type.

using IsoMap = std::map<VertexDescriptor, std::vector<VertexDescriptor>>: Mapping of pattern to target vertices.

using GraphEdgeReplacementStruct = EdgeReplacementStruct<VertexProperties, DirectionProperty, EdgeProperties>: Alias for edge replacement structure.

Public Functions

ExtendedGraph() = default: Default constructor.

inline explicit ExtendedGraph(GraphType graph)

Constructor initializing the graph with a given Boost graph instance.

Parameters:: graph – The Boost graph instance to initialize with.

virtual ~ExtendedGraph() = default: Virtual destructor.

inline GraphType &graph()

Accessor for the internal graph.

Returns:: A reference to the internal graph instance.

inline const GraphType &graph() const

Const accessor for the internal graph.

Returns:: A reference to the internal graph instance.

inline VertexDescriptor add_vertex(VertexProperties v = VertexProperties())

Adds a vertex to the graph.

Parameters:: v – The properties of the vertex to add (default constructed if not provided).
Returns:: The descriptor of the newly added vertex.

inline EdgeDescriptor add_edge(VertexDescriptor src, VertexDescriptor trg, EdgeProperties e = EdgeProperties())

Adds an edge between two vertices in the graph.

Parameters:

src – The source vertex of the edge.
trg – The target vertex of the edge.
e – The properties of the edge to add (default constructed if not provided).

Returns:

The descriptor of the newly added edge.

inline VertexDescriptor edge_source(EdgeDescriptor e) const

Retrieves the source vertex of a given edge.

Parameters:: e – The edge descriptor.
Returns:: The descriptor of the source vertex.

inline VertexDescriptor edge_target(EdgeDescriptor e) const

Retrieves the target vertex of a given edge.

Parameters:: e – The edge descriptor.
Returns:: The descriptor of the target vertex.

inline b::iterator_range<typename GraphType::vertex_iterator> vertex_range() const

Provides a range of all vertices in the graph.

Returns:: An iterator range of all vertices in the graph.

inline b::iterator_range<typename GraphType::edge_iterator> edge_range() const

Provides a range of all edges in the graph.

Returns:: An iterator range of all edges in the graph.

inline VertexProperties &operator[](const VertexDescriptor &v)

Accesses the properties of a vertex.

Parameters:: v – The vertex descriptor.
Returns:: A reference to the properties of the specified vertex.

inline const VertexProperties &operator[](const VertexDescriptor &v) const

Accesses the properties of a vertex (const).

Parameters:: v – The vertex descriptor.
Returns:: A reference to the properties of the specified vertex.

inline EdgeProperties &operator[](const EdgeDescriptor &e)

Accesses the properties of an edge.

Parameters:: e – The edge descriptor.
Returns:: A reference to the properties of the specified edge.

inline const EdgeProperties &operator[](const EdgeDescriptor &e) const

Accesses the properties of an edge (const).

Parameters:: e – The edge descriptor.
Returns:: A reference to the properties of the specified edge.

inline bool is_vertex_in_isomorphism(const VertexDescriptor &vertex, const IsoMap &isomorphism) const

Checks if a vertex exists in the isomorphism map.

Parameters:

vertex – The vertex to check.
isomorphism – The isomorphism map containing vertices.

Returns:

True if the vertex exists in the isomorphism map, false otherwise.

inline void print_dfs_graph() const

Performs a depth-first search (DFS) on the graph and prints events.

This function uses a custom DFS visitor to print initialization, start, discovery, and finish events for each vertex during the traversal.

inline void write_graph(const std::string &filename, bool render_pdf = true)

Writes the graph to a DOT file and optionally renders it as a PDF. This is not const as instances of this class keep an internal counter of the emitted graphs, and prefix it to the file name so that file names reflect the ordering of calls to this method.

Parameters:

filename – The base filename (without extension) for the output files.
render_pdf – If true, renders the DOT file to a PDF.

inline VertexDescriptor duplicate_vertex(int id_to_duplicate, CloneVertexFunction<VertexProperties> cvf, ModifyVertexPairFunction<VertexProperties> mvpf)

Duplicates a vertex in the graph, along with its edges.

Parameters:

id_to_duplicate – The ID of the vertex to duplicate.
cvf – A function to clone the properties of the vertex.
mvpf – A function to modify the pair of original and duplicated vertices.

Returns:

The descriptor of the newly duplicated vertex.

inline void add_vertex_after_vertex(VertexDescriptor v, const VertexProperties &new_vertex_properties)

Adds a vertex after a specified vertex and adjusts edges accordingly.

Parameters:

v – The vertex after which the new vertex will be added.
new_vertex_properties – The properties of the new vertex to add.

template<typename Predicate> inline void add_vertex_after_pred(Predicate pred, const VertexProperties &new_vertex_properties)

Adds a vertex after vertices that satisfy a given predicate.

Template Parameters:

Predicate – A callable that takes vertex properties and returns true if the vertex matches the criteria.

Parameters:

pred – The predicate function to filter vertices.
new_vertex_properties – The properties of the new vertex to add.

template<typename Predicate> inline void remove_vertex_pred(Predicate pred)

Removes all vertices that satisfy a predicate and reconnects edges.

For every matching vertex, in-edges are rewired to all out-vertices (excluding self-loops) before the vertex is cleared and erased. Vertex removal is processed in descending descriptor order to keep descriptors valid during mutation.

Template Parameters:: Predicate – Callable that accepts vertex properties and returns true when the vertex should be removed.
Parameters:: pred – Predicate applied to each vertex.

inline void add_vertex_before_vertex(VertexDescriptor v, const VertexProperties &new_vertex_properties)

Inserts a vertex immediately before an existing vertex.

Transfers all incoming edges of v to the new vertex and adds a single edge from the new vertex into v, effectively splitting inbound traffic through the new vertex.

Parameters:

v – Vertex to insert in front of
new_vertex_properties – Properties to assign to the inserted vertex

template<typename Predicate> inline void add_vertex_before_pred(Predicate pred, const VertexProperties &new_vertex_properties)

Inserts a vertex before every vertex that satisfies a predicate.

Copies vertex properties via clone() for each match to avoid sharing instances between insertions.

Template Parameters:

Predicate – Callable returning true when a vertex should be preceded.

Parameters:

pred – Predicate applied to vertex properties.
new_vertex_properties – Prototype properties for the inserted vertex.

inline void merge_vertices(VertexDescriptor v1, VertexDescriptor v2, std::function<bool(VertexDescriptor, VertexDescriptor)> can_merge)

Merges two vertices in the graph if they satisfy a given condition.

This function attempts to merge two specified vertices (v1 and v2). The vertices are merged by redirecting all in-edges and out-edges of v2 to v1 and then removing v2 from the graph. The merge only occurs if the provided ‘canMerge’ predicate returns true for the two vertices.

Parameters:

v1 – The first vertex to be merged.
v2 – The second vertex to be merged into the first.
can_merge – A predicate that takes two vertices and returns true if they can be merged.

inline std::set<VertexDescriptor, std::greater<>> replace_subgraph(const GraphType &ng, IsoMap &isomorphism, std::optional<std::function<void(std::vector<GraphEdgeReplacementStruct>, std::vector<GraphEdgeReplacementStruct>, std::vector<VertexDescriptor>, std::vector<VertexDescriptor>, GraphType&)>> reconnect_edges = std::nullopt)

Replace a matched subgraph with a new graph.

Adds all vertices/edges from ng into the current graph, maps them to the vertices being replaced as described by isomorphism, and reconnects external edges either via a custom reconnect_edges callback or a default root/leaf strategy. Vertices slated for removal are returned so callers can clean them up after edge reconstruction.

Parameters:

ng – Constructed replacement graph
isomorphism – Mapping from replacement vertices to matched vertices
reconnect_edges – Optional hook to override external edge rewiring

Returns:

Set of vertices that should be erased from the original graph

inline void fix_vertex_obj_ids()

Reassign IDs based on graph directionality.

Separate functions are required for directed and undirected graphs, since the concept of a root doesn’t exist in an undirected graph.

inline virtual void vertex_property_writer(std::ostream &out, const VertexDescriptor &v) const: Extension point for [write_graph]. Write the attributes of the vertex in dot format to the output stream.

inline virtual void edge_property_writer(std::ostream &out, const EdgeDescriptor&) const: Extension point for [write_graph]. Write the attributes of the edge in dot format to the output stream.

inline virtual void graph_properties_writer(std::ostream &out) const: Extension point for [write_graph]. Write the attributes of the vertex in dot format to the output stream.

inline void set_base_graph(const GraphType &g)

inline std::size_t num_vertices() const

Protected Functions

template<typename DP, typename std::enable_if_t<!std::is_same_v<DP, b::undirectedS>, int> = 0> inline void fix_vertex_obj_ids_impl(): Helper implementing ID reassignment for directed graphs.

template<typename DP, typename std::enable_if_t<std::is_same_v<DP, b::undirectedS>, int> = 0> inline void fix_vertex_obj_ids_impl(): Helper for undirected graphs.

Protected Attributes

Graph<VertexProperties_, DirectionProperty_, EdgeProperties_> graph_ = {}: Internal Boost graph instance.

template<typename VertexProperties, typename DirectionProperty, typename EdgeProperties = b::no_property> class ExtendedSubGraph

#include <subgraph.h>

Extends graph functionality with subgraph operations.

This class provides support for creating and managing subgraphs within a larger graph structure. It includes functionality for:

Managing vertex and edge properties with GraphViz attributes
Creating and tracking hierarchical subgraph relationships
Maintaining consistent vertex object IDs across the graph hierarchy
Generating visual representations through GraphViz

Template Parameters:

VertexProperties – The type of properties stored in vertices.
DirectionProperty – The directionality tag for the underlying graph.
EdgeProperties – The type of properties stored in edges (defaults to boost::no_property).

Public Types

using GraphType = b::subgraph<UnderlyingGraph>: Exposed subgraph type.

using VertexDescriptor = b::graph_traits<GraphType>::vertex_descriptor: Vertex descriptor type.

using EdgeDescriptor = b::graph_traits<GraphType>::edge_descriptor: Edge descriptor type.

Public Functions

inline GraphType &graph()

Accesses the underlying graph instance.

Returns:: Reference to the underlying graph.

inline const GraphType &graph() const

Accesses the underlying graph instance (const version).

Returns:: Const reference to the underlying graph.

inline std::pair<VertexDescriptor, VertexDescriptor> add_vertex(VertexProperties v, GraphType &subgraph)

Creates a vertex in both global and subgraph contexts.

Creates a vertex with the specified properties in both the global graph and the provided subgraph. The vertex’s GraphViz attributes are initialized based on the vertex properties.

Parameters:

v – Properties to assign to the new vertex
subgraph – The subgraph to add the vertex to

Returns:

A pair containing the global and local vertex descriptors

inline VertexDescriptor add_vertex(VertexProperties v = VertexProperties())

Creates a vertex in the global graph.

Parameters:: v – Properties to assign to the new vertex (default constructed if not provided)
Returns:: The descriptor of the newly created vertex

inline std::pair<VertexDescriptor, VertexDescriptor> add_vertex(GraphType &subgraph)

Creates a vertex with default properties in both contexts.

Creates a vertex with default-constructed properties in both the global graph and specified subgraph.

Parameters:: subgraph – The subgraph to add the vertex to
Returns:: A pair containing the global and local vertex descriptors

inline std::pair<EdgeDescriptor, bool> add_edge(VertexDescriptor source, VertexDescriptor target, EdgeProperties e, GraphType &subgraph)

Creates an edge with properties in a specific graph context.

Adds an edge between specified vertices with associated properties. The edge is created in the specified graph context and its GraphViz attributes are initialized.

Parameters:

source – Source vertex descriptor
target – Target vertex descriptor
e – Properties to assign to the new edge
subgraph – The graph or subgraph to add the edge to

Returns:

A pair containing the edge descriptor and a boolean indicating success

inline std::pair<EdgeDescriptor, bool> add_edge(VertexDescriptor source, VertexDescriptor target, EdgeProperties e = EdgeProperties())

Creates an edge with properties in the global graph.

Parameters:

source – Source vertex descriptor
target – Target vertex descriptor
e – Properties to assign to the new edge (default constructed if not provided)

Returns:

A pair containing the edge descriptor and a boolean indicating success

inline std::pair<EdgeDescriptor, bool> add_edge(VertexDescriptor source, VertexDescriptor target, GraphType &subgraph)

Creates an edge with default properties in a specific graph context.

Creates an edge with default-constructed properties between specified vertices in the given graph context.

Parameters:

source – Source vertex descriptor
target – Target vertex descriptor
subgraph – The graph or subgraph to add the edge to

Returns:

A pair containing the edge descriptor and a boolean indicating success

inline GraphType &add_subgraph(GraphType &curr_graph, const std::string &name)

Creates a new subgraph within the current graph.

Creates and initializes a new subgraph with the given name, setting up appropriate GraphViz attributes for visualization.

Parameters:

curr_graph – The parent graph to create the subgraph in.
name – The name to assign to the new subgraph.

Returns:

Reference to the newly created subgraph.

inline GraphType &add_subgraph(const std::string &name)

inline GraphType &operator[](const std::string &name)

Accesses a subgraph by name.

Retrieves a reference to a previously created subgraph using its assigned name. Throws std::out_of_range if the subgraph doesn’t exist.

Parameters:: name – The name of the subgraph to retrieve
Throws:: std::out_of_range – if no subgraph exists with the given name
Returns:: Reference to the requested subgraph

inline void update_graph_attributes()

Updates GraphViz attributes for all vertices.

Refreshes the GraphViz attributes for each vertex in the graph by calling their graphAttributes() method. This is useful after modifying vertex properties that affect visualization.

inline void fix_id_vertices()

Updates vertex object IDs to match their position in the graph.

Iterates through all vertices and sets their internal ID to match their vertex descriptor value, ensuring consistent identification across the graph.

Pre:: The graph must not be empty and vertices must have an ‘id’ member.

inline void write_graph(const std::string &filename)

Writes the graph to GraphViz format files.

Generates both a DOT file and a PDF visualization of the graph using GraphViz.

Parameters:: filename – Base name for the output files (without extension).

Private Types

using GraphvizAttributes = std::map<std::string, std::string, std::less<>>: GraphViz attribute map type.

using ExtendedVertexProperties = b::property<b::vertex_attribute_t, GraphvizAttributes, VertexProperties>: Vertex property with attributes.

using ExtendedEdgeProperties = b::property<b::edge_index_t, int, b::property<b::edge_attribute_t, GraphvizAttributes, EdgeProperties>>: Edge property with attributes/index.

using UnderlyingGraph = b::adjacency_list<b::vecS, b::vecS, DirectionProperty, ExtendedVertexProperties, ExtendedEdgeProperties, b::property<b::graph_name_t, std::string, b::property<b::graph_graph_attribute_t, GraphvizAttributes, b::property<b::graph_vertex_attribute_t, GraphvizAttributes, b::property<b::graph_edge_attribute_t, GraphvizAttributes>>>>>

Type definition for the underlying graph structure.

Combines the extended property types with Boost’s adjacency list and adds graph-level attributes for GraphViz visualization.

Private Members

b::subgraph<UnderlyingGraph> graph_

The underlying Boost subgraph instance.

Underlying graph storage with subgraph support.

std::map<std::string, b::subgraph<UnderlyingGraph>*> subgraphs_

Maps subgraphs to their names.

Named subgraphs keyed by identifier.

template<typename T, typename U = b::no_property> struct generic_edge_descriptor

#include <graph.h>

Descriptor for defining an edge in the graph.

Template Parameters:

T – The type of the vertex identifier.
U – The type of the edge properties (default: boost::no_property).

Public Members

T in_: Source vertex identifier.

T out_: Target vertex identifier.

U properties_: Properties associated with the edge.

template<class T> struct is_shared_ptr : public std::false_type: #include <subgraph.h>

template<class T> struct is_shared_ptr<std::shared_ptr<T>> : public std::true_type: #include <subgraph.h>

template<typename VertexProperties_, typename DirectionProperty_, typename EdgeProperties_ = boost::no_property> class Isomorphism

#include <graph_isomorphisms.h>

Base class for implementing graph isomorphism operations.

This class provides the framework for defining and discovering graph isomorphisms, as well as applying transformations based on discovered isomorphisms. It can be extended to implement specific isomorphism patterns and transformations.