Introduction

Graphlite is a lightweight generic graph library that supports

node properties
edge properties
directed/undirected graphs
multi-edges & self-loops
user-specified data structures for the adjacency list and neighbor containers

in a pay-for-what-you-use manner thanks to template metaprogramming.

There are a number of C++ graph libraries in the marketplace, among which the Boost Graph Library(BGL) is the best-known. The downside of the BGL is that even though it's header-only, it still has Boost as its dependency. This library, being a generic header-only graph library, is very much inspired by the BGL, except that it is completely self-contained and all the functionality is in one singular header file, src/graph_lite.h.

Note that unlike the BGL, this library offers the graph data structure but not the various graph algorithms. The data structure alone can already prove useful for simple tasks that only require graph traversal. Even for tasks that require graph algorithms, the usage tends to be limited to one or two graph algorithms, which can be readily implemented on top of the data structure, and, even better, shared with others.

This library requires C++ 17 (or higher).

Documentation

Graph and its Iterators
Queries
Graph Editing

1. Graph and its Iterators

Construction of a `Graph`

We start with the template parameters of the Graph class.

template<typename NodeType=int, typename NodePropType=void, typename EdgePropType=void,
        EdgeDirection direction=EdgeDirection::UNDIRECTED,
        MultiEdge multi_edge=MultiEdge::DISALLOWED,
        SelfLoop self_loop=SelfLoop::DISALLOWED,
        Map adj_list_spec=Map::UNORDERED_MAP,
        Container neighbors_container_spec=Container::UNORDERED_SET>
class Graph;

NodeType Type of nodes in the graph. Must not be cv-qualified or a reference. Must support operator<< and operator==. Must support operator< if adjacency list is a std::map. Must support hashing if adjacency list is a std::unorder_map
NodePropType Type of node properties. void if not needed. Must not be cv-qualified or a reference
EdgePropType Type of edge properties. void if not needed. Must not be cv-qualified or a reference
EdgeDirection direction Non-type template parameter that takes value from the enum below. Determines if the graph should be directed or undirected

enum class EdgeDirection { DIRECTED, UNDIRECTED };

MultiEdge multi_edge Non-type template parameter that takes value from the enum below. Determines if multi-edges are allowed. If ALLOWED, no runtime check for multi-edges will happen during edge addition. Otherwise, runtime check will occur and edge addition will fail if the edge is already present

enum class MultiEdge { ALLOWED, DISALLOWED };

SelfLoop self_loop Non-type template parameter that takes value from the enum below. Determines if self-loops are allowed. If ALLOWED, no runtime check for self-loops will happen during edge addition. Otherwise, runtime check will occur and edge addition will fail if the edge being added is a self-loop

enum class SelfLoop { ALLOWED, DISALLOWED };

Map adj_list_spec Non-type template parameter that takes value from the enum below. Determines the data structure of the adjacency list

enum class Map { MAP, UNORDERED_MAP };

Container neighbors_container_spec Non-type template parameter that takes value from the enum below. Determines the data structure in which the neighbors of each node should be stored
- if multi_edge is DISALLOWED, MULTISET and UNORDERED_MULTISET are not supported
- if multi_edge is ALLOWED, SET and UNORDERED_SET are not supported

enum class Container { VEC, LIST, SET, UNORDERED_SET, MULTISET, UNORDERED_MULTISET };

Performance tip:

Prefer Container::VEC if graph modification is infrequent

Prefer SET/UNORDERED_SET/MULTISET/UNORDERED_MULTISET if graph modification is frequent

Use LIST only when (1) NodeType is not hashable (ruling out unordered_maps) (2) NodeType doesn't support operator< (ruling out maps), and (3) iterator invalidation is absolutely unacceptable (ruling out VEC).

Examples

//(default)undirected simple graph using hashtable for adj list and hashset for neighbors
Graph g_0;
// directed graph with edge weights, using rb tree for adj list and vector for neighbors
Graph<std::string, void, double, 
      EdgeDirection::DIRECTED, MultiEdge::DISALLOWED, SelfLoop::DISALLOWED, 
      Map::MAP, Container::VEC> g_1;

For the rest of the documentation we refer to the full type(with template params) of Graph as GType.

Node Iterators

Much like the STL containers, Graph also has custom iterators. The iterator types can be accessed as

typename GType::Iterator non_const_it;
typename GType::ConstIterator const_it;

The begin and end iterators can be accessed using the following

Iterator begin() noexcept;
Iterator end() noexcept;
ConstIterator begin() const noexcept;
ConstIterator end() const noexcept;

which enables the following loops for graph traversal

for (auto it=g.begin(); it!=g.end(); ++it) {
    // classic for loop
}
for (const auto& v: g) {
    // range-based for loop
}

Examples

// NodePropType is void
Graph<int> g; 
for (const int& node: g) {  // print out all nodes
    std::cout << node << " ";
}

// NodePropType is double
Graph<int, double> g_non_const;
// not using range-for here saves one look-up
for (auto it=g_non_const.begin(); it!=g_non_const.end(); ++it) {
    // g_non_const.node_prop(*it) = 0.0; // this does the same as the line below
    g_non_const.node_prop(it) = 0.0; // zero out all node prop
}

// g_const is const
const Graph<int, double>& g_const = g_non_const;
for (auto it=g_const.begin(); it!=g_const.end(); ++it) {
    // g_const.node_prop(it) = 0.0; WON'T COMPILE! node_prop returns const ref
}

Neighbor Iterators

Just as Iterator/ConstIterator iterates through the adjacency list,

typename GType::NeighborsConstIterator const_nbr_it;
typename GType::NeighborsIterator nbr_it;

iterates through the neighbors of each node.

If EdgePropType is void, both *const_nbr_it and *nbr_it have type const NodeType&
If EdgePropType is not void, both *const_nbr_it and *nbr_it have type std::pair. The first fields are both const NodeType. The second fields exposes a public method

const EdgePropType& prop() const  // called by const_nbr_it->second.prop()
EdgePropType& prop()  // called by nbr_it->second.prop()

Instead of returning a reference to the actual neighbor container, this library returns a pair of neighbor iterators, also known as a NeighborsView, defined below

using NeighborsView = std::pair<NeighborsIterator, NeighborsIterator>;
using NeighborsConstView = std::pair<NeighborsConstIterator,
                                     NeighborsConstIterator>;

For UNDIRECTED graphs, we can query the neighbors of a node by calling the member function neighbors; meanwhile, for DIRECTED graphs, a node can have both in-neighbors and out-neighbors. If we have two nodes, u, v, and a directed edge (u -> v), then u is an in-neighbor of v and v is an out-neighbor of u. We query the out/in-neighbors of a node in a directed graph by calling out_neighbors or in_neighbors.

Examples

// graphs with (1) no node property (2) edge property with type double
Graph<int, void, double, EdgeDirection::UNDIRECTED> udg;
for (auto it=udg.begin(); it!=udg.end(); ++it) {
    auto [nbr_begin, nbr_end] = udg.neighbors(it);
    for (auto nbr_it=nbr_begin; nbr_it!=nbr_end; ++nbr_it) {
        // zero out edge property for edge (node, 42)
        if (nbr_it->first==42) {
            nbr_it->second.prop() = 0.0;
        }
    }
}

// edge property is immutable for a const graph
const auto& const_udg = udg;
for (auto it=const_udg.begin(); it!=const_udg.end(); ++it) {
    auto [nbr_begin, nbr_end] = const_udg.neighbors(it);
    for (auto nbr_it=nbr_begin; nbr_it!=nbr_end; ++nbr_it) {
        if (nbr_it->first==42) { // nbr_it->second.prop() has type const double&
            // nbr_it->second.prop() = 0.0; WON'T COMPILE!
        }
    }
}

// directed graphs
Graph<int, void, double, EdgeDirection::DIRECTED> dg;
for (auto it=dg.begin(); it!=dg.end(); ++it) {
    auto [out_nbr_begin, out_nbr_end] = dg.out_neighbors(it);
    for (auto out_nbr_it=out_nbr_begin; 
              out_nbr_it!=out_nbr_end; ++out_nbr_it) {
        // zero out edge property for edge (node -> 42)
        if (out_nbr_it->first==42) {
            out_nbr_it->second.prop() = 0.0;
        }
    }
}

Invalidation Rules for Iterators

Both node and neighbor iterators follow the iterator invalidation rules of their underlying STL containers, as summarized by this SO answer.

For example

If Map::UNORDERED_MAP is chosen, existing node iterators may be invalidated after adding or removing nodes due to rehashing
If Container::SET is chosen, existing neighbor iterators will not be invalidated by the addition/removal of (other) edges
Modifying node/edge properties never invalidates existing iterators

2. Queries

Find a node by value

ConstIterator find(const T& node_identifier) const noexcept;
Iterator find(const T& node_identifier) noexcept;

Searches the graph for a node with value equivalent to node_identifier and returns an iterator to it if found; otherwise it returns Graph::end().

node_identifier must be implicitly or explicitly convertible to NodeType.

Examples

Graph g;
typename Graph::Iterator pos = g.find(123);
const Graph& cg = g;
typename Graph::ConstIterator cpos = cg.find(123);

Test whether a node exists in the graph

bool has_node(const T& node_identifier) const noexcept;

Returns true if the node is in the graph. node_identifier must be implicitly or explicitly convertible to NodeType.

Return size

size_t size() const noexcept;

Returns the number of nodes in the graph.

Return edge count

int num_edges() const noexcept;

Returns the number of edges in the graph.

Count the number of edges between two nodes

int count_edges(const U& source_iv, const V& target_iv) const noexcept;

Returns the number of edges going out of source_iv and into target_iv.

Returns 0 if either source_iv or target_iv doesn't represent an existing node.

Each of source_iv and target_iv can be either an iterator or a value.

Examples

Graph g;
auto pos_0 = g.find(0);
auto pos_1 = g.find(1);
// these four do the same thing
g.count_edges(0, 1);
g.count_edges(pos_0, pos_1);
g.count_edges(0, pos_1);
g.count_edges(pos_0, 1);

Get the neighbors of a node

(1) Exclusive to undirected graphs

NeighborsConstView neighbors(const T& node_iv) const;
NeighborsView neighbors(const T& node_iv);

Returns a pair of iterators marking the beginning and the end of the neighbors of node_iv.

node_iv can be either an iterator or a value.

An exception will be thrown if node_iv does not represent an existing node.

(2) Exclusive to directed graphs

NeighborsConstView out_neighbors(const T& node_iv) const;
NeighborsView out_neighbors(const T& node_iv);
NeighborsConstView in_neighbors(const T& node_iv) const;
NeighborsView in_neighbors(const T& node_iv);

Returns a pair of iterators marking the beginning and the end of out/in-neighbors of node_iv.

node_iv can be either an iterator or a value.

An exception will be thrown if node_iv does not represent an existing node.

Examples

Graph<int, void, void, EdgeDirection::UNDIRECTED> udg;
auto [nbr_begin, nbr_end] = udg.neighbors(123);

Graph<int, void, void, EdgeDirection::DIRECTED> dg;
auto pos_123 = dg.find(123);
auto [out_nbr_begin, out_nbr_end] = dg.out_neighbors(pos_123);
auto [in_nbr_begin, in_nbr_end] = dg.in_neighbors(pos_123);

Count the neighbors of a node

(1) Exclusive to undirected graphs

int count_neighbors(const T& node_iv) const;

Returns the number of neighbors of node_iv.

An exception will be thrown if node_iv does not represent an existing node.

(2) Exclusive to directed graphs

int count_out_neighbors(const T& node_iv) const;
int count_in_neighbors(const T& node_iv) const;

Returns the number of out/in-neighbors of node_iv.

An exception will be thrown if node_iv does not represent an existing node.

Almost always more efficient than calling std::distance on the iterator pair.

Find a neighbor of a node by value

(1) Exclusive to undirected graphs

std::pair<bool, NeighborsConstIterator> 
find_neighbor(const U& src_iv, const V& tgt_identifier) const;

std::pair<bool, NeighborsIterator> 
find_neighbor(const U& src_iv, const V& tgt_identifier);

Returns a pair (is_found, neighbor_pos). The first field is true if a node with value equivalent to tgt_identifier is found within the neighborhood of src_iv. The second field is an iterator pointing to the neighbor if found at all.

src_iv can be either an iterator or a value. tgt_identifier must be implicitly or explicitly convertible to NodeType.

An exception will be thrown if src_iv does not represent an existing node.

(2) Exclusive to directed graphs

std::pair<bool, NeighborsConstIterator> 
find_out_neighbor(const U& src_iv, const V& tgt_identifier) const;

std::pair<bool, NeighborsIterator> 
find_out_neighbor(const U& src_iv, const V& tgt_identifier);

std::pair<bool, NeighborsConstIterator> 
find_in_neighbor(const U& src_iv, const V& tgt_identifier) const;

std::pair<bool, NeighborsIterator> 
find_in_neighbor(const U& src_iv, const V& tgt_identifier);

Similar to its undirected counterpart, except that the search for tgt_identifier will be carried out in the out/in-neighborhood of src_iv.

An exception will be thrown if src_iv does not represent an existing node.

Examples

Graph<int, void, void, EdgeDirection::UNDIRECTED> udg;
auto [found_0_1, pos_0_1] = udg.find_neighbor(0, 1);

Graph<int, void, void, EdgeDirection::DIRECTED> dg;
auto pos_1 = dg.find(1);
auto [found_1_0, pos_1_0] = dg.find_out_neighbor(pos_1, 0);

Get node property

Exclusive to graphs with node properties

const NodePropType& node_prop(const T& node_iv) const;
NodePropType& node_prop(const T& node_iv);

node_iv can be either an iterator or a value.

An exception will be thrown if node_iv does not represent an existing node.

Examples

Graph<std::string, int> g;
std::cout << "Alice's age: " << g.node_prop("Alice") << "\n";

auto bob_pos = g.find("Bob");
std::cout << "Bob's age: " << g.node_prop(bob_pos) << "\n";

// Bob is actually 20
g.node_prop(bob_pos) = 20;
// Bob just had his birthday
g.node_prop(bob_pos)++;

const auto& cg = g;
// cg.node_prop("Alice") = 99;  // WON'T COMPILE! Assigning to const ref

Get edge property

Exclusive to graphs with edge properties

const EdgePropType& edge_prop(U&& source_iv, V&& target_iv) const;
EdgePropType& edge_prop(U&& source_iv, V&& target_iv);

Each of source_iv and target_iv can be either an iterator or a value.

An exception will be thrown if (source_iv, target_iv) does not represent an existing edge.

Graph<std::string, void, double> g;
auto beijing_pos = g.find("Beijing");
auto shanghai_pos = g.find("Shanghai");
// the many, many ways to retrieve the commuting hours between the two cities
LOG(g.edge_prop(beijing_pos, shanghai_pos));
LOG(g.edge_prop(beijing_pos, "Shanghai"));
LOG(g.edge_prop("Beijing", shanghai_pos));
LOG(g.edge_prop("Beijing", "Shanghai"));

auto [found, b2s_edge] = g.find_neighbor(beijing_pos, "Shanghai");
assert(found);
assert(b2s_edge->first=="Shanghai");
LOG(b2s_edge->second.prop());

// with the high-speed railway, now it takes only 4.5h
g.edge_prop("Beijing", "Shanghai") = 4.5;
// or, equivalently
b2s_edge->second.prop() = 4.5;

3. Graph Editing

Add nodes to the graph

(1) Exclusive to graphs without node properties

int add_nodes(T&& new_node, Args&&... args) noexcept;

Adds one or more nodes to the graph.

Re-adding an existing node results in an no-op. Returns the number of nodes actually added.

new_node must have the same type as NodeType; this is to prevent unwanted implicit conversion during node addition.

(2) Exclusive to graphs with node properties

int add_node_with_prop(NT&& new_node, NPT&&... prop) noexcept;

Adds a node with property to the graph.

Re-adding an existing node results in an no-op; in particular, the property of the existing node will not be changed. Returns the number of nodes actually added, in this case 0 or 1.

new_node must have the same type as NodeType. NodePropType must be constructible from prop.

Examples

Graph g;
assert(g.add_nodes(2, 3, 5, 7, 11) == 5);

Graph<std::string, int> sg;
sg.add_node_with_prop(std::string("Alice"), 21);
sg.add_node_with_prop(std::string("Bob"), 22);
// same_type requirement
// sg.add_node_with_prop("NO", 0);  // WON'T COMPILE! 
// "No" has type const char*, not std::string

Graph<int, std::map<std::string, int>> mg;
// unfortunately a map is NOT constructible from ONE pair; must use std::map explicitly
mg.add_node_with_prop(0, std::map<std::string, int>{{"age", 26}});
// construct node property (std::map<std::string, int>) in place with more than one pairs
mg.add_node_with_prop(0, std::make_pair("age", 21), std::make_pair("salary", 21000));

Remove nodes from the graph

int remove_nodes(const T& node_iv, const Args&... args) noexcept;

Removes one or more nodes from the graph, as well as the edges involving the nodes being removed.

Removing a non-existent node results in a no-op. Returns the number of nodes actually removed.

node_iv can be either an iterator or a value.

Caveat: Nodes are removed in the order they appear in the parameter list. Removing a node invalidates iterators to the node removed.

Examples

Graph<std::string> g;
g.add_nodes(std::string("Alice"), std::string("Bob"), std::string("Cyrus"));
assert(g.remove_nodes("Alice", "Derek") == 1);
// Bad idea!!! After the removal of "Bob", bob_pos becomes invalidated!
auto bob_pos = g.find("Bob");
g.remove_nodes("Bob", bob_pos);  // just don't

Add edges to the graph

(1) Exclusive to graphs without edge properties

int add_edge(U&& source_iv, V&& target_iv) noexcept;

Adds an edge to the graph.

The following attempts to add an edge will result in a no-op:

Either source_iv or target_iv not representing an existing node in the graph
Re-adding an existing edge when multi_edge is DISALLOWED
Adding a self-loop when self_loop is DISALLOWED

Each of source_iv and target_iv can be either an iterator or a value.

Returns the number of edges actually added, in this case 0 or 1.

(2) Exclusive to graphs with edge properties

int add_edge_with_prop(U&& source_iv, V&& target_iv, EPT&&... prop) noexcept;

Adds an edge with property to the graph.

The following attempts to add an edge will result in a no-op:

Either source_iv or target_iv not representing an existing node in the graph
Re-adding an existing edge when multi_edge is DISALLOWED
Adding a self-loop when self_loop is DISALLOWED

Each of source_iv and target_iv can be either an iterator or a value. EdgePropType must be constructible from prop.

Returns the number of edges actually added, in this case 0 or 1.

Examples

Graph g;
g.add_nodes(1, 2, 3);
g.add_edge(1, 3);
auto pos_2 = g.find(2);
g.add_edge(1, pos_2);
g.add_edge(pos_2, 3);

Graph<std::string, void, double> sg;
g.add_nodes(std::string("NY"), std::string("LA"));
g.add_edge_with_prop("NY", "LA", 2 * 24 + 19);

Graph<int, std::map<std::string, int>> mg;
// unfortunately a map is NOT constructible from ONE pair; must use std::map explicitly
mg.add_edge_with_prop(0, std::map<std::string, int>{{"age", 26}});
// a map is still constructible from more than one pairs though
mg.add_edge_with_prop(1, std::make_pair("age", 21), std::make_pair("salary", 21000));

Remove edges from the graph

(1) Remove all edges between an ordered pair of nodes

int remove_edge(const U& source_iv, const V& target_iv) noexcept;

Removes all edges with the form (source_iv, target_iv) from the graph.

Each of source_iv and target_iv can be either an iterator or a value.

Results in an no-op if

either source_iv or target_iv does not represent an existing node
(source_iv, target_iv) does not represent an existing edge

Returns the number of edges actually removed. 0 or 1 if multi_edge is DISALLOWED; [0, +\infty) if multi_edge is ALLOWED.

(2) Remove one edge from the graph by position

int remove_edge(ConstIterator source_pos, NeighborsConstIterator target_nbr_pos) noexcept;

Removes exactly one edge by position.

Especially useful when multi_edge is ALLOWED and a particular edge among the many parallel edges needs to be removed.

Always returns 1.

Examples

struct Travel {
    std::string means;
    double hours;
}
int main() {
    Graph<std::string, void, Travel, EdgeDirection::UNDIRECTED, 
          MultiEdge::ALLOWED, SelfLoop::DISALLOWED, Map::MAP, Container::MULTISET> us;
    us.add_nodes(std::string("NY"), std::string("LA"));
    us.add_edge_with_prop("NY", "LA", Travel{"walk", 912});
    us.add_edge_with_prop("NY", "LA", Travel{"bike", 244});
    us.add_edge_with_prop("NY", "LA", Travel{"car", 41});
    us.add_edge_with_prop("NY", "LA", Travel{"plane", 3});
    assert(us.count_edges("NY", "LA") == 4);
    // walking simply doesn't make much sense;
    auto ny_pos = us.find("NY");
    auto [n_begin, n_end] = us.neighbors(ny_pos);  
    // to remove it we must find it first
    auto walk_pos = std::find_if(n_begin, n_end, 
                                 [](const auto& p){ 
                                     // p is a std::pair
                                     const Travel& travel = p.second.prop();
                                     return travel.means == "walk"; 
                                 });
    us.remove_edge(ny_pos, walk_pos);  // calling (2)
    assert(us.count_edges(ny_pos, "LA") == 3);
    // now suppose a lockdown happens and all forms of travelling are banned
    int num_removed = us.remove_edge(ny_pos, "LA");  // calling (1)
    assert(num_removed == 3);
    assert(us.count_edges("NY", "LA") == 0);  // confirm removal
}

Name		Name	Last commit message	Last commit date
Latest commit History 23 Commits
.github/workflows		.github/workflows
lib		lib
src		src
tests		tests
.gitignore		.gitignore
.gitmodules		.gitmodules
CMakeLists.txt		CMakeLists.txt
LICENSE.txt		LICENSE.txt
README.md		README.md

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

Introduction

Documentation

1. Graph and its Iterators

Construction of a `Graph`

Node Iterators

Neighbor Iterators

Invalidation Rules for Iterators

2. Queries

Find a node by value

Test whether a node exists in the graph

Return size

Return edge count

Count the number of edges between two nodes

Get the neighbors of a node

(1) Exclusive to undirected graphs

(2) Exclusive to directed graphs

Count the neighbors of a node

(1) Exclusive to undirected graphs

(2) Exclusive to directed graphs

Find a neighbor of a node by value

(1) Exclusive to undirected graphs

(2) Exclusive to directed graphs

Get node property

Get edge property

3. Graph Editing

Add nodes to the graph

Remove nodes from the graph

Add edges to the graph

Remove edges from the graph

(1) Remove all edges between an ordered pair of nodes

(2) Remove one edge from the graph by position

About

Contributors 2

Languages

License

haasdo95/graphlite

Folders and files

Latest commit

History

Repository files navigation

Introduction

Documentation

1. Graph and its Iterators

Construction of a Graph

Node Iterators

Neighbor Iterators

Invalidation Rules for Iterators

2. Queries

Find a node by value

Test whether a node exists in the graph

Return size

Return edge count

Count the number of edges between two nodes

Get the neighbors of a node

(1) Exclusive to undirected graphs

(2) Exclusive to directed graphs

Count the neighbors of a node

(1) Exclusive to undirected graphs

(2) Exclusive to directed graphs

Find a neighbor of a node by value

(1) Exclusive to undirected graphs

(2) Exclusive to directed graphs

Get node property

Get edge property

3. Graph Editing

Add nodes to the graph

Remove nodes from the graph

Add edges to the graph

Remove edges from the graph

(1) Remove all edges between an ordered pair of nodes

(2) Remove one edge from the graph by position

About

Topics

Resources

License

Stars

Watchers

Forks

Contributors 2

Languages

Construction of a `Graph`