Function isUndirectedGraph

include/util/graph_utils.hpp:13–48

/// This function checks if the graph (consisting of directed edges) is undirected
template <typename GraphT> bool isUndirectedGraph(const GraphT &graph)
{
    for (auto source = 0u; source < graph.GetNumberOfNodes(); ++source)
    {
        for (auto edge = graph.BeginEdges(source); edge < graph.EndEdges(source); ++edge)
        {
            const auto &data = graph.GetEdgeData(edge);

            auto target = graph.GetTarget(edge);
            BOOST_ASSERT(target != SPECIAL_NODEID);

            bool found_reverse = false;
            for (auto rev_edge = graph.BeginEdges(target); rev_edge < graph.EndEdges(target);
                 ++rev_edge)
            {
                auto rev_target = graph.GetTarget(rev_edge);
                BOOST_ASSERT(rev_target != SPECIAL_NODEID);

                if (rev_target != source)
                {
                    continue;
                }

                BOOST_ASSERT_MSG(!found_reverse, "Found more than one reverse edge");
                found_reverse = true;
            }

            if (!found_reverse)
            {
                return false;
            }
        }
    }

    return true;
}

/// Since DynamicGraph assumes directed edges we have to make sure we transformed
/// the compressed edge format into single directed edges. We do this to make sure