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

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 TemplatedEdge e1, const TemplatedEdge e2) const

Public Members

const GraphType &G1_

const GraphType &G2_

EdgeCompFunction ecf_

template<typename VertexProperties, 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.
EdgeProperties – Properties associated with edges (default: boost::no_property).

Public Members

Vertex<VertexProperties, EdgeProperties> src_trg

Vertex<VertexProperties, EdgeProperties> old_vertex

Vertex<VertexProperties, EdgeProperties> new_vertex

EdgeProperties edge_properties

template<typename VertexProperties, 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.
EdgeProperties – Properties associated with edges (default: boost::no_property).

Public Types

using GraphType = Graph<VertexProperties, EdgeProperties>

using TemplatedVertex = Vertex<VertexProperties, EdgeProperties>

using TemplatedEdge = Edge<VertexProperties, EdgeProperties>

using IsoMap = std::map<TemplatedVertex, std::vector<TemplatedVertex>>

using TemplatedEdgeReplacementStruct = EdgeReplacementStruct<VertexProperties, EdgeProperties>

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 TemplatedVertex 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 TemplatedEdge add_edge(TemplatedVertex src, TemplatedVertex 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 TemplatedVertex edge_source(TemplatedEdge e) const

Retrieves the source vertex of a given edge.

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

inline TemplatedVertex edge_target(TemplatedEdge 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 TemplatedVertex &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 TemplatedVertex &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 TemplatedEdge &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 TemplatedEdge &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 TemplatedVertex &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)

inline TemplatedVertex 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(TemplatedVertex 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)

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

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

inline void merge_vertices(TemplatedVertex v1, TemplatedVertex v2, std::function<bool(TemplatedVertex, TemplatedVertex)> 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<TemplatedVertex, std::greater<>> replace_subgraph(const GraphType &ng, IsoMap &isomorphism, std::optional<std::function<void(std::vector<TemplatedEdgeReplacementStruct>, std::vector<TemplatedEdgeReplacementStruct>, std::vector<TemplatedVertex>, std::vector<TemplatedVertex>, GraphType&)>> reconnect_edges = std::nullopt)

inline void fix_vertex_obj_ids(): Reassign the IDs of nodes to match their indices in the graph. This might be necessary after mutations in the graph. Applying isomorphisms calls this transparently already.

inline virtual void vertex_property_writer(std::ostream &out, const TemplatedVertex &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 TemplatedEdge&) const: Extension point for [write_graph]. Write the attributes of the edge in dot format to the output stream.

inline void set_base_graph(const GraphType &g)

Public Members

int curr_graph = 0

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.

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

Protected Attributes

Graph<VertexProperties, EdgeProperties> graph_ = {}

template<typename VertexProperties, 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.
EdgeProperties – The type of properties stored in edges (defaults to boost::no_property).

Public Types

using GraphType = b::subgraph<UnderlyingGraph>: Type alias for the graph implementation.

using Vertex = b::graph_traits<GraphType>::vertex_descriptor: Type alias for vertex descriptors.

using Edge = b::graph_traits<GraphType>::edge_descriptor: Type alias for edge descriptors.

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<Vertex, Vertex> 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 Vertex 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<Vertex, Vertex> 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<Edge, bool> add_edge(Vertex source, Vertex 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<Edge, bool> add_edge(Vertex source, Vertex 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<Edge, bool> add_edge(Vertex source, Vertex 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<>>: Type alias for GraphViz attribute maps.

using ExtendedVertexProperties = b::property<b::vertex_attribute_t, GraphvizAttributes, VertexProperties>: Type for vertex properties extended with GraphViz attributes.

using ExtendedEdgeProperties = b::property<b::edge_index_t, int, b::property<b::edge_attribute_t, GraphvizAttributes, EdgeProperties>>: Type for edge properties extended with GraphViz attributes and indices.

using UnderlyingGraph = b::adjacency_list<b::vecS, b::vecS, b::bidirectionalS, 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.

std::map<std::string, b::subgraph<UnderlyingGraph>*> subgraphs_: Maps subgraphs to their names.

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_

T out_

U properties_

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 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.