3
\$\begingroup\$

I'm working on a SparseGraph which reflects the mathematical notion of a graph. All code included here works in all of the basic test cases that I've tried. However, I'm most concerned about the iterators (which iterate through each edge in the graph). Other concerns are style, readability, and other matters involving aesthetics. Particularly, I would like to know if the assumptions I made for the iterator classes are reasonable (for some definition of "reasonable").

The only file that needs to be reviewed is "SparseGraph.h". I'll add some other classes (that don't necessarily need to be reviewed) which should be helpful for anyone who would like to try out the SparseGraph.

Graph_Enums.h

/*
    Graph_Enums.h

    This header contains a helpful enumeration
    when working with graphs.

    AldenB
    May 16, 2017
*/
#ifndef GRAPH_ENUMS_H
#define GRAPH_ENUMS_H

enum
{
    invalid_node_index = -1
};
#endif // GRAPH_ENUMS_H

SparseGraph.h

/*
    Sparse_Graph.h

    A sparse graph is a minimal collection of nodes and edges to represent a graph.
    This sparse graph is represented using an adjacency list.

    AldenB
    May 16, 2017
*/
#ifndef SPARSE_GRAPH_H
#define SPARSE_GRAPH_H

#include <iostream>
#include <vector>
#include <list>
#include "Graph_Enums.h"

template <typename NodeType, typename EdgeType>
class SparseGraph
{
public:
    class const_iterator;
    class const_reverse_iterator;
    using Node = NodeType;
    using Edge = EdgeType;
    using NodeList = std::vector<Node>;
    using EdgeList = std::list<Edge>;
    using AdjacencyList = std::vector<EdgeList>;

private:
    //NOTE: Any node with an index of invalid_node_index will be treated as a non-existent node
    //no matter where it is in the node list.

    //Each node index keys into its location in the NodeList
    //For example, a node with an index of 3 will be at index 3
    //in the NodeList. This is so we can have a O(1) lookup time
    //for nodes
    NodeList m_nodes;

    //The AdjacencyList holds all edges associated with a node.
    //For example, index 3 of the AdjacencyList holds an EdgeList
    //containing all the edges connected to the node with an index
    //of 3.
    AdjacencyList m_adj_list;

    bool edge_exists(int from, int to);

public:
    SparseGraph() {}
    ~SparseGraph() {}

    //----NODE STUFF--------------------------------------------------------
    //add_node() will only add nodes that currently do not exist.
    //set_node() will only change nodes that already exist
    void add_node(const Node& node);
    void set_node(const Node& node);

    //remove_node() removes the node with the specified index.
    //it will also remove all edges associated with the specified node.
    void remove_node(int index);

    //node access
    //unchecked access
    Node& operator[](int index);
    const Node& operator[](int index) const;

    //checked access
    Node& at(int index);
    const Node& at(int index) const;

    //----EDGE STUFF--------------------------------------------------------
    //add_edge() will only add edges that do not exist
    //set_edge() will only change edges that already exist
    void add_edge(const Edge& edge);

    //this will actually remove both edges connected to from and to.
    //i.e. Edge(from, to) and Edge(to, from)
    void remove_edge(int from, int to);

    //checked access
    Edge& get_edge(int from, int to);
    const Edge& get_edge(int from, int to) const;

    //----OTHER-------------------------------------------------------------
    void clear();

    const_iterator begin() const;
    const_iterator end() const;
    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;

    template<typename Node, typename Edge>
    friend std::ostream& operator<<(std::ostream& os, const SparseGraph<Node, Edge>& graph);
};



//----SparseGraph::const_iterator-------------------------------------------
//this const_iterator is meant to iterate through every Edge in the AdjacencyList.
//Note that operator++() and operator--() will skip over empty EdgeLists.
//It is the user's responsibility to ensure that edge_it is not initialized to
//the end of ANY EdgeList in the AdjacencyList.
template <typename NodeType, typename EdgeType>
class SparseGraph<NodeType, EdgeType>::const_iterator
{
private:
    using NodeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_iterator;
    using EdgeIterator = typename SparseGraph<NodeType, EdgeType>::EdgeList::const_iterator;

    NodeIterator m_node_it;
    EdgeIterator m_edge_it;
    const NodeIterator m_end;

public:
    const_iterator(NodeIterator node_it,
                   EdgeIterator edge_it,
                   NodeIterator end)
        : m_node_it{node_it}, m_edge_it{edge_it}, m_end{end} {}

    //prefix operator++()
    const_iterator& operator++()
    {
        //move to the next element
        m_edge_it++;

        //if we are at the end of an EdgeList, move to the beginning of
        //the next non-empty EdgeList
        while(m_edge_it == m_node_it->end() && ++m_node_it != m_end) {
            m_edge_it = m_node_it->begin();
        }
        return *this;
    }

    //postfix operator++()
    const_iterator operator++(int)
    {
        auto temp = *this;
        ++(*this);
        return temp;
    }

    //prefix operator--()
    const_iterator& operator--()
    {
        //are we at the beginning of an EdgeList?
        if(m_edge_it == m_node_it->begin()) {
            //move to the previous non-empty EdgeList.
            while((--m_node_it)->empty()) {};

            //set the edge iterator to the last element of the EdgeList.
            m_edge_it = --(m_node_it->rbegin().base());
        }

        //we are not at the beginning of an EdgeList
        else {
            m_edge_it--;
        }
        return *this;
    }

    //postfix operator--()
    const_iterator operator--(int)
    {
        const_iterator temp = *this;
        --(*this);
        return temp;
    }

    //----operator*()
    const typename SparseGraph<NodeType, EdgeType>::Edge& operator*() const
    {
        return *m_edge_it;
    }

    //operator->()
    const typename SparseGraph<NodeType, EdgeType>::Edge* operator->() const
    {
        return &(*m_edge_it);
    }

    //----operator==()
    bool operator==(const const_iterator& other) const
    {
        return m_node_it == other.m_node_it &&
               m_edge_it == other.m_edge_it;
    }

    //----operator!=()
    bool operator!=(const const_iterator& other) const
    {
        return !(*this == other);
    }
};



//----SparseGraph::reverse_const_iterator-----------------------------------
//the reverse_const_iterator should work semantically and holds the same assumptions as the const_iterator
template <typename NodeType, typename EdgeType>
class SparseGraph<NodeType, EdgeType>::const_reverse_iterator
{
private:
    using RNodeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_reverse_iterator;
    using REdgeIterator = typename SparseGraph<NodeType, EdgeType>::EdgeList::const_reverse_iterator;

    RNodeIterator m_rnode_it;
    REdgeIterator m_redge_it;
    const RNodeIterator m_rend;

public:
    const_reverse_iterator(RNodeIterator rnode_it,
                   REdgeIterator redge_it,
                   RNodeIterator rend)
        : m_rnode_it{rnode_it}, m_redge_it{redge_it}, m_rend{rend} {}

    //prefix operator++()
    const_reverse_iterator& operator++()
    {
        //move to the previous element
        m_redge_it++;

        //if we are past the beginning of an EdgeList, move to the last element of
        //the previous non-empty EdgeList
        while(m_redge_it == m_rnode_it->rend() && ++m_rnode_it != m_rend) {
            m_redge_it = m_rnode_it->rbegin();
        }
        return *this;
    }

    //postfix operator++()
    const_reverse_iterator operator++(int)
    {
        auto temp = *this;
        ++(*this);
        return temp;
    }

    //prefix operator--()
    const_reverse_iterator& operator--()
    {
        //are we at the last element of an EdgeList?
        if(m_redge_it == m_rnode_it->rbegin()) {
            //move to the next non-empty EdgeList.
            while((--m_rnode_it)->empty()) {};

            //set the reverse edge iterator to the first element of the EdgeList.
            m_redge_it = m_rnode_it->begin();
        }

        //we are not at the last element of an EdgeList
        else {
            m_redge_it--;
        }
        return *this;
    }

    //postfix operator--()
    const_reverse_iterator operator--(int)
    {
        const_reverse_iterator temp = *this;
        --(*this);
        return temp;
    }

    //----operator*()
    const typename SparseGraph<NodeType, EdgeType>::Edge& operator*() const
    {
        return *m_redge_it;
    }

    //operator->()
    const typename SparseGraph<NodeType, EdgeType>::Edge* operator->() const
    {
        return &(*m_redge_it);
    }

    //----operator==()
    bool operator==(const const_reverse_iterator& other) const
    {
        return m_rnode_it == other.m_rnode_it &&
               m_redge_it == other.m_redge_it;
    }

    //----operator!=()
    bool operator!=(const const_reverse_iterator& other) const
    {
        return !(*this == other);
    }
};



//----SPARSE_GRAPH----------------------------------------------------------

//----PRIVATE FUNCTIONS-----------------------------------------------------

template <typename NodeType, typename EdgeType>
bool SparseGraph<NodeType, EdgeType>::edge_exists(int from, int to)
{
    //assume that from is within the bounds of the AdjacencyList
    for(const Edge& e : m_adj_list[from]) {
        if(e.to() == to) {
            return true;
        }
    }
    return false;
}

//----PUBLIC FUNCTIONS------------------------------------------------------

//----add_node()
template <typename NodeType, typename EdgeType>
void SparseGraph<NodeType, EdgeType>::add_node(const NodeType& node)
{
    //range check
    if(node.index() < 0) {
        throw std::runtime_error{"SparseGraph::add_node(): Bad node index."};
    }
    //Don't overwrite an existing node unless it's invalid.
    if(node.index() < m_nodes.size()) {
        if(m_nodes[node.index()].index() == invalid_node_index) {
            m_nodes[node.index()] = node;
            return;
        }
        throw std::runtime_error{"SparseGraph::add_node(): Node already exists."};
    }

    //add an empty EdgeList for each node.
    while(m_nodes.size() < node.index()) {
        m_adj_list.push_back(EdgeList());
        m_nodes.push_back(NodeType(invalid_node_index));
    }
    m_adj_list.push_back(EdgeList());
    m_nodes.push_back(node);
}

//----set_node()
template <typename NodeType, typename EdgeType>
void SparseGraph<NodeType, EdgeType>::set_node(const NodeType& node)
{
    //range and validity check; we can only set to valid nodes.
    if(node.index() < 0 || node.index() >= m_nodes.size() ||
       m_nodes[node.index()].index() == invalid_node_index) {
        throw std::runtime_error{"SparseGraph::set_node(): Set to non-existent node."};
    }
    m_nodes[node.index()] = node;
}

//----remove_node()
template <typename NodeType, typename EdgeType>
void SparseGraph<NodeType, EdgeType>::remove_node(int index)
{
    //range check
    if(index < 0 || index >= m_nodes.size()) {
        throw std::runtime_error{"SparseGraph::remove_node(): Node index out of bounds."};
    }
    //validity check
    if(m_nodes[index].index() == invalid_node_index) {
        throw std::runtime_error{"SparseGraph::remove_node(): Node does not exist."};
    }
    m_nodes[index].set_index(invalid_node_index);

    //look through every EdgeList in the AdjacencyList
    //and remove any Edge that is connected to this node.
    for(int i = 0; i < m_adj_list.size(); ++i) {
        for(auto it = m_adj_list[i].begin(); it != m_adj_list[i].end(); ++it) {
            if(it->from() == index || it->to() == index) {
                it = m_adj_list[i].erase(it);
                --it;
            }
        }
    }
}

//----operator[]()
template <typename NodeType, typename EdgeType>
NodeType& SparseGraph<NodeType, EdgeType>::operator[](int index)
{
    return m_nodes[index];
}

//----operator[]() const
template <typename NodeType, typename EdgeType>
const NodeType& SparseGraph<NodeType, EdgeType>::operator[](int index) const
{
    return m_nodes[index];
}

//----at()
template <typename NodeType, typename EdgeType>
NodeType& SparseGraph<NodeType, EdgeType>::at(int index)
{
    //range check
    if(index < 0 || index >= m_nodes.size()) {
        throw std::runtime_error{"SparseGraph::at(): Index out of bounds."};
    }
    return m_nodes[index];
}

//----at() const
template <typename NodeType, typename EdgeType>
const NodeType& SparseGraph<NodeType, EdgeType>::at(int index) const
{
    //range check
    if(index < 0 || index >= m_nodes.size()) {
        throw std::runtime_error{"SparseGraph::at(): Index out of bounds."};
    }
    return m_nodes[index];
}

//----add_edge()
template <typename NodeType, typename EdgeType>
void SparseGraph<NodeType, EdgeType>::add_edge(const Edge& edge)
{
    //range check
    if(edge.from() < 0 || edge.from() >= m_adj_list.size() ||
       edge.to() < 0 || edge.to() >= m_adj_list.size()) {
        throw std::runtime_error{"SparseGraph::add_edge(): Edge index out of bounds."};
    }
    //existence check
    if(edge_exists(edge.from(), edge.to())) {
        throw std::runtime_error{"SparseGraph::add_edge(): Edge already exists."};
    }
    //make sure the Edge is added for both directions
    Edge reverse_edge = edge;
    reverse_edge.set_from(edge.to());
    reverse_edge.set_to(edge.from());

    m_adj_list[edge.from()].push_back(edge);
    m_adj_list[reverse_edge.from()].push_back(reverse_edge);
}

//----remove_edge()
template <typename NodeType, typename EdgeType>
void SparseGraph<NodeType, EdgeType>::remove_edge(int from, int to)
{
    //range check
    if(from < 0 || from >= m_adj_list.size() ||
       to < 0 || to >= m_adj_list.size()) {
        throw std::runtime_error{"SparseGraph::remove_edge(): Edge index out of bounds."};
    }
    //look for the Edge in its EdgeList and remove it if it's there.
    for(auto it = m_adj_list[from].begin(); it != m_adj_list[from].end(); ++it) {
        if(it->to() == to) {
            m_adj_list[from].erase(it);
            //also erase the Edge coming from the opposite direction
            for(auto opp_it = m_adj_list[to].begin(); opp_it != m_adj_list[to].end(); ++opp_it) {
                if(opp_it->to() == from) {
                    m_adj_list[to].erase(opp_it);
                }
            }
            return;
        }
    }
    throw std::runtime_error{"SparseGraph::remove_edge(): Edge does not exist."};
}

//----get_edge()
template <typename NodeType, typename EdgeType>
EdgeType& SparseGraph<NodeType, EdgeType>::get_edge(int from, int to)
{
    //range check
    if(from < 0 || from >= m_adj_list.size() ||
       to < 0 || to >= m_adj_list.size()) {
        throw std::runtime_error{"SparseGraph::get_edge(): Edge does not exist."};
    }
    //search for the Edge in its EdgeList.
    for(EdgeType& e : m_adj_list[from]) {
        if(e.from() == from && e.to() == to) {
            return e;
        }
    }
}

//----get_edge() const
template <typename NodeType, typename EdgeType>
const EdgeType& SparseGraph<NodeType, EdgeType>::get_edge(int from, int to) const
{
    //range check
    if(from < 0 || from >= m_adj_list.size() ||
       to < 0 || to >= m_adj_list.size()) {
        throw std::runtime_error{"SparseGraph::get_edge(): Edge does not exist."};
    }
    //try to find the Edge in its EdgeList
    for(const EdgeType& e : m_adj_list[from]) {
        if(e.from() == from && e.to() == to) {
            return e;
        }
    }
}

//----clear()
template <typename NodeType, typename EdgeType>
void SparseGraph<NodeType, EdgeType>::clear()
{
    m_nodes.clear();
    m_adj_list.clear();
}

//----begin()
template <typename NodeType, typename EdgeType>
typename SparseGraph<NodeType, EdgeType>::const_iterator SparseGraph<NodeType, EdgeType>::begin() const
{
    //Move to the first non-empty EdgeList in the AdjacencyList
    typename AdjacencyList::const_iterator begin_it = m_adj_list.begin();
    while(begin_it != m_adj_list.end() && begin_it->empty()) {
        begin_it++;
    }
    return SparseGraph<NodeType, EdgeType>::const_iterator(begin_it, begin_it->begin(), m_adj_list.end());
}

//----end()
template <typename NodeType, typename EdgeType>
typename SparseGraph<NodeType, EdgeType>::const_iterator SparseGraph<NodeType, EdgeType>::end() const
{
    return SparseGraph<NodeType, EdgeType>::const_iterator(m_adj_list.end(), m_adj_list.back().end(), m_adj_list.end());
}

//----rbegin()
template <typename NodeType, typename EdgeType>
typename SparseGraph<NodeType, EdgeType>::const_reverse_iterator SparseGraph<NodeType, EdgeType>::rbegin() const
{
    typename AdjacencyList::const_reverse_iterator rbegin_it = m_adj_list.rbegin();
    while(rbegin_it != m_adj_list.rend() && rbegin_it->empty()) {
        rbegin_it++;
    }
    return SparseGraph<NodeType, EdgeType>::const_reverse_iterator(rbegin_it, rbegin_it->rbegin(), m_adj_list.rend());
}

//----rend()
template <typename NodeType, typename EdgeType>
typename SparseGraph<NodeType, EdgeType>::const_reverse_iterator SparseGraph<NodeType, EdgeType>::rend() const
{
    return SparseGraph<NodeType, EdgeType>::const_reverse_iterator(m_adj_list.rend(), m_adj_list.front().rend(), m_adj_list.rend());
}

//----operator<<()
template <typename NodeType, typename EdgeType>
std::ostream& operator<<(std::ostream& os, const SparseGraph<NodeType, EdgeType>& graph)
{
    if(graph.m_adj_list.size() == 0) {
        return os << "<empty>";
    }
    for(unsigned int i = 0; i < graph.m_adj_list.size(); ++i) {
        os << i;
        if(graph.m_nodes[i].index() == invalid_node_index) {
            os << " (invalid)";
        }
        os << ":";
        for(const EdgeType& e : graph.m_adj_list[i]) {
            os << " " << e.to();
        }
        //don't add a newline to the last line
        if(i < graph.m_adj_list.size()-1) {
            os << '\n';
        }
    }
    return os;
}

#endif // SPARSE_GRAPH_H

Graph_Node

/*
    Graph_Node.h

    A graph node is exactly what you'd expect:
    a node on a graph.

    AldenB
    May 16, 2017
*/
#ifndef GRAPH_NODE_H
#define GRAPH_NODE_H

#include "Graph_Enums.h"

class GraphNode
{
public:
    GraphNode()
        : m_index{invalid_node_index} {}
    explicit GraphNode(int index)
        : m_index{index} {}
    virtual ~GraphNode() {}

    int index() const {return m_index;}
    void set_index(int index) {m_index = index;}

    bool operator==(const GraphNode& other)
    {
        return index() == other.index();
    }

    bool operator!=(const GraphNode& other)
    {
        return !(*this == other);
    }

private:
    int m_index;

};

std::ostream& operator<<(std::ostream& os, const GraphNode& node)
{
    return os << "(" << node.index() << ")";
}
#endif // GRAPH_NODE_H

Graph_Edge.h

/*
    Graph_Edge.h

    A graph edge represents a unidirectional connection
    between two nodes on a graph.

    Alden Bernitt
    May 16, 2017
*/
#ifndef GRAPH_EDGE_H
#define GRAPH_EDGE_H

#include "Graph_Enums.h"

class GraphEdge
{
public:
    GraphEdge()
        : m_from{invalid_node_index}, m_to{invalid_node_index} {}
    GraphEdge(int from, int to)
        : m_from{from}, m_to{to} {}
    virtual ~GraphEdge() {}

    int from() const {return m_from;}
    int to() const {return m_to;}

    void set_from(int from) {m_from = from;}
    void set_to(int to) {m_to = to;}

    bool operator==(const GraphEdge& other)
    {
        return from() == other.from() &&
               to() == other.to();
    }

    bool operator!=(const GraphEdge& other)
    {
        return !(*this == other);
    }

private:
    //a node can be minimally represented by its index.
    int m_from;
    int m_to;
};

std::ostream& operator<<(std::ostream& os, const GraphEdge& edge)
{
    return os << "(" << edge.from() << "," << edge.to() << ")";
}
#endif // GRAPH_EDGE_H
\$\endgroup\$
  • \$\begingroup\$ Have you considered to use a sparse matrix format like Coordinated Storage or Compressed Column? There you basically save all entries in one vector. It would make iterating much easier. Lookup for a specific entry could be slower, so its up to you to define which operation should be the focus on. \$\endgroup\$ – ab.o2c May 23 '17 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.