boost graph that doesn't allow circular references

Question

I'm new to boost graphs and are researching the graph that best fits my need. I need to create a dependency graph and given a vertex, I need access to in and out edges. An adjacency_list with Directed=bidirectionalS is what I'm thinking.

But I need to make sure when I call add_edge and that causes a circular reference then it has to error out. I can't seem to find how to do this.

Answer 1

In general, there's only one way to discover whether a graph is a-cyclic: traverse all nodes.

So you'd just need to check whether the graph is still a-cyclic after adding each edge.

However, depending on how you are adding the nodes, you can optimize. If, e.g. you add edges by traversing nodes from a source in DFS order, you can just keep track of nodes "seen" in the current path and refuse to add an out edge to those.

Simplistic example based on topological_sort Live On Coliru:

#include <iostream>  // for std::cout
#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/graphviz.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/function_output_iterator.hpp>

using namespace boost;

int main()
{
    srand(time(0));

    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
    const int num_vertices = 10;
    Graph g(num_vertices);

    // add random edges to the graph object
    for (size_t i = 0; i < 10; ++i)
    {
        auto f = rand()%num_vertices,
             s = rand()%num_vertices;

        add_edge(f, s, g);
        try {
            topological_sort(g, boost::make_function_output_iterator([](int){}));
        } catch(not_a_dag const& e)
        {
            remove_edge(f, s, g);
            std::cerr << "dropped edge: " << e.what() << "\n";
        }
    }

    write_graphviz(std::cout, g);
}

Creates random DAGs like

Answer 2

In boost graph BidirectinalS indicates that the edge will be having soruce and target vertices both. Here is the example for it:

#include <QtCore/QCoreApplication>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
using namespace std;
using namespace boost;


typedef boost::subgraph<boost::adjacency_list< boost::listS,
        boost::vecS,
        boost::bidirectionalS,
        boost::property<boost::vertex_index_t, int , property<boost::vertex_color_t, boost::default_color_type > > ,
        boost::property<boost::edge_index_t,int, property<boost::edge_color_t , default_color_type> > > >
        Graph;

 const int num_vertices = 5;
  Graph g(num_vertices);

  add_edge(0, 1, g);
  add_edge(1, 2, g);
  add_edge(1, 3, g);
  add_edge(2, 4, g);
  add_edge(3, 4, g);

  boost::graph_traits<Graph>::vertex_iterator VertexItr, VertexItr_end;
  boost::graph_traits<Graph>::in_edge_iterator in, in_end;
  boost::graph_traits<Graph>::out_edge_iterator out,out_end;

   typedef boost::graph_traits < Graph >::adjacency_iterator adjacency_iterator;

   // This loop is for getting in edges at vertex
  cout<<"In Edge :- "<<endl;

  for(boost::tie(VertexItr,VertexItr_end) = vertices(g); VertexItr != VertexItr_end; ++VertexItr) {
    cout << *VertexItr << " <-- ";
    for (boost::tie(in,in_end) = in_edges(*VertexItr, g); in != in_end; ++in)
      cout << source(*in, g) << "  ";
    cout << endl;
  }

  // This loop is for getting out edges from vertex
  cout<<endl<<"Out Edge :- "<<endl;
  for(boost::tie(VertexItr,VertexItr_end) = vertices(g); VertexItr != VertexItr_end; ++VertexItr) {
      cout<<*VertexItr<<"--->";
    for (boost::tie(out,out_end) = out_edges(*VertexItr, g); out != out_end; ++out)
      cout << target(*out, g) << "  ";
      cout << endl;
  }

  // This loop is for getting the neighbour vertices of vertex
  typedef boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
    IndexMap index = get(boost::vertex_index, g);
    cout<<"Adjacent vertices"<<endl;
    for(boost::tie(VertexItr,VertexItr_end) = vertices(g); VertexItr != VertexItr_end; ++VertexItr) {
        cout<<*VertexItr<<"--->";
    std::pair<adjacency_iterator, adjacency_iterator> neighbors =
      boost::adjacent_vertices(vertex(*VertexItr,g), g);

    for(; neighbors.first != neighbors.second; ++neighbors.first)
      {
      std::cout << index[*neighbors.first] << " ";
      }
    cout<<endl;
    }

return a.exec();
}

Answer 3

I found this section on the boost documentation discussing how to detect dependencies:

http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/file_dependency_example.html#sec:cycles

But for the adjacency_list the VertexList and EdgeList have to be of type vecS. There's discussion about this here: How to print a boost graph in graphviz with one of the properties displayed?