Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm for selecting all edges and vertices connected to one vertex

Tags:

c++

graph

boost

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!

like image 225
Kim Gräsman Avatar asked Feb 20 '11 10:02

Kim Gräsman


People also ask

Which of the following techniques algorithms can be used to find number of connected components in an undirected graph with V vertices and E edges?

We can use a traversal algorithm, either depth-first or breadth-first, to find the connected components of an undirected graph. If we do a traversal starting from a vertex v, then we will visit all the vertices that can be reached from v. These are the vertices in the connected component that contains v.

What is algorithm vertex?

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs ( ...

How do you find the number of vertices on a connected graph?

A graph with no loops and no parallel edges is called a simple graph. The maximum number of edges possible in a single graph with 'n' vertices is nC2 where nC2 = n(n – 1)/2. The number of simple graphs possible with 'n' vertices = 2nc2 = 2n(n-1)/2.

In what order are the strongly connected components SCCs found?

(a) In what order are the strongly connected components (SCCs) found? Ans: The strongly connected components determined in order are: E, B, A; HGI, CDFJ; The algorithm I have used to find the SCCs is: Step 1: Perform DFS on G and compute [pre(v),post(v)] interval for all v.


1 Answers

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.

like image 144
Calvin1602 Avatar answered Oct 24 '22 02:10

Calvin1602