Algorithm for selecting all edges and vertices connected to one vertex

Question

I'm using Boost Graph to try and make sense of some dependency graphs I have generated in Graphviz Dot format.

Unfortunately I don't know very much about graph theory, so I have a hard time framing what I want to know in terms of graph theory lingo.

From a directed dependency graph with ~150 vertices, I'd like to "zoom in" on one specific vertex V, and build a subgraph containing V, all its incoming edges and their incoming edges, all its outgoing edges and their outgoing edges, sort of like a longest path through V.

These dependency graphs are pretty tangled, so I'd like to remove clutter to make it clearer what might affect the vertex in question.

For example, given;

     g
     |
     v
a -> b -> c -> d
|    |         |
v    v         |
e    f <-------+

if I were to run the algorithm on c, I think I want;

     g
     |
     v
a -> b -> c -> d -> f

Not sure if b -> f should be included as well... I think of it as all vertices "before" c should have their in-edges included, and all vertices "after" c should have their out-edges included, but it seems to me that that would lose some information.

It feels like there should be an algorithm that does this (or something more sensible, not sure if I'm trying to do something stupid, cf b->f above), but I'm not sure where to start looking.

Thanks!

Answer 1

Ok, so I'll translate and adapt my tutorial to your specific question. The documentation always assumes tons of "using namespace"; I won't use any so you know what is what. Let's begin :

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>

First, define a Vertex and an Edge :

struct Vertex{
    string name; // or whatever, maybe nothing
};
struct Edge{
    // nothing, probably. Or a weight, a distance, a direction, ...
};

Create the type or your graph :

typedef boost::adjacency_list<  // adjacency_list is a template depending on :
    boost::listS,               //  The container used for egdes : here, std::list.
    boost::vecS,                //  The container used for vertices: here, std::vector.
    boost::directedS,           //  directed or undirected edges ?.
    Vertex,                     //  The type that describes a Vertex.
    Edge                        //  The type that describes an Edge
> MyGraph;

Now, you can use a shortcut to the type of the IDs of your Vertices and Edges :

typedef MyGraph::vertex_descriptor VertexID;
typedef MyGraph::edge_descriptor   EdgeID;

Instanciate your graph :

MyGraph graph;

Read your Graphviz data, and feed the graph :

for (each Vertex V){
    VertexID vID = boost::add_vertex(graph); // vID is the index of a new Vertex
    graph[vID].name = whatever;
}

Notice that graph[ a VertexID ] gives a Vertex, but graph[ an EdgeID ] gives an Edge. Here's how to add one :

EdgeID edge;
bool ok;
boost::tie(edge, ok) = boost::add_edge(u,v, graphe); // boost::add_edge gives a std::pair<EdgeID,bool>. It's complicated to write, so boost::tie does it for us. 
if (ok)  // make sure there wasn't any error (duplicates, maybe)
    graph[edge].member = whatever you know about this edge

So now you have your graph. You want to get the VertexID for Vertex "c". To keep it simple, let's use a linear search :

MyGraph::vertex_iterator vertexIt, vertexEnd;
boost::tie(vertexIt, vertexEnd) = vertices(graph);
for (; vertexIt != vertexEnd; ++vertexIt){
    VertexID vertexID = *vertexIt; // dereference vertexIt, get the ID
    Vertex & vertex = graph[vertexID];
    if (vertex.name == std::string("c")){} // Gotcha
}

And finally, to get the neighbours of a vertex :

MyGraph::adjacency_iterator neighbourIt, neighbourEnd;
boost::tie(neighbourIt, neighbourEnd) = adjacent_vertices( vertexIdOfc, graph );
for(){you got it I guess}

You can also get edges with

std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor u, const adjacency_list& g)
std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const adjacency_list& g)
 // don't forget boost::tie !

So, for your real question :

• Find the ID of Vertex "c"
• Find in_edges recursively
• Find out_edges recursively

Example for in_edges (never compiled or tried, out of the top of my head):

void findParents(VertexID vID){
    MyGraph::inv_adjacency_iterator parentIt, ParentEnd;
    boost::tie(parentIt, ParentEnd) = inv_adjacent_vertices(vID, graph);
    for(;parentIt != parentEnd); ++parentIt){
        VertexID parentID = *parentIt;
        Vertex & parent = graph[parentID];
        add_edge_to_graphviz(vID, parentID); // or whatever
        findParents(parentID);
    }
}

For the other way around, just rename Parent into Children, and use adjacency_iterator / adjacent_vertices.

Answer 2

Here's how it ended up. I realized I needed to work entirely in terms of in-edges and out-edges:

// Graph-related types
typedef property < vertex_name_t, std::string > vertex_p;
typedef adjacency_list < vecS, vecS, bidirectionalS, vertex_p> graph_t;
typedef graph_t::vertex_descriptor vertex_t;
typedef std::set< graph_t::edge_descriptor > edge_set;

// Focussing algorithm
edge_set focus_on_vertex(graph_t& graph, const std::string& focus_vertex_name)
{
    const vertex_t focus_vertex = find_vertex_named(graph, focus_vertex_name);

    edge_set edges;
    collect_in_edges(graph, focus_vertex, edges);
    collect_out_edges(graph, focus_vertex, edges);

    return edges;
}

// Helpers
void collect_in_edges(const graph_t& graph, vertex_t vertex, edge_set& accumulator)
{
    typedef graph_t::in_edge_iterator edge_iterator;

    edge_iterator begin, end;
    boost::tie(begin, end) = in_edges(vertex, graph);
    for (edge_iterator i = begin; i != end; ++i)
    {
        if (accumulator.find(*i) == accumulator.end())
        {
            accumulator.insert(*i);
            collect_in_edges(graph, source(*i, graph), accumulator);
        }
    }
}

void collect_out_edges(const graph_t& graph, vertex_t vertex, edge_set& accumulator)
{
    typedef graph_t::out_edge_iterator edge_iterator;

    edge_iterator begin, end;
    boost::tie(begin, end) = out_edges(vertex, graph);
    for (edge_iterator i = begin; i != end; ++i)
    {
        if (accumulator.find(*i) == accumulator.end())
        {
            accumulator.insert(*i);
            collect_out_edges(graph, target(*i, graph), accumulator);
        }
    }
}

vertex_t find_vertex_named(const graph_t& graph, const std::string& name)
{
    graph_t::vertex_iterator begin, end;
    boost::tie(begin, end) = vertices(graph);
    for (graph_t::vertex_iterator i = begin; i != end; ++i)
    {
        if (get(vertex_name, graph, *i) == name)
            return *i;
    }

    return -1;
}

This also handles cycles before or after the vertex in question. My source dependency graph had cycles (shudder).

I made some attempts at generalizing collect_*_edges into a templated collect_edges, but I didn't have enough meta-programming debugging energy to spend on it.