Checking that removing an edge on a graph will split the graph
I have a graph structure where I remove edges one by one until some conditions are met. My brain has completely stopped and I cannot find an efficient way to detect that removing an edge will split the graph in two or more graphs.
Brutforce's solution should be to do bfs until you can reach all nodes from a random node, but it will take too long with large graphs ...
Any ideas?
Edit: After a bit of searching, it seems that what I'm trying to do is very similar to fleury's algorithm, where I need to find if an edge is a "bridge" or not.
source to share
The edges that make the graph disconnected when deleted are called bridges . You can find them in O (| V | + | E |) with one depth search throughout the entire plot. The linked algorithm finds all "articulation points" (nodes that, if removed, make the graph disconnected). Any edge between two articulation points is a bridge (you can check this in a second pass around all edges).
//
// g: graph; v: current vertex id;
// r_p: parents (r/w); r_a: ascents (r/w); r_ap: art. points, bool array (r/w)
// n_v: bfs order-of-visit
//
void dfs_art_i(graph *g, int v, int *r_p, int *r_v, int *r_a, int *r_ap, int *n_v) {
int i;
r_v[v] = *n_v;
r_a[v] = *n_v;
(*n_v) ++;
// printf("entering %d (nv = %d)\n", v, *n_v);
for (i=0; i<g->vertices[v].n_edges; i++) {
int w = g->vertices[v].edges[i].target;
// printf("\t evaluating %d->%d: ", v, w);
if (r_v[w] == -1) {
// printf("...\n");
// This is the first time we find this vertex
r_p[w] = v;
dfs_art_i(g, w, r_p, r_v, r_a, r_ap, n_v);
// printf("\n\t ... back in %d->%d", v, w);
if (r_a[w] >= r_v[v]) {
// printf(" - a[%d] %d >= v[%d] %d", w, r_a[w], v, r_v[v]);
// Articulation point found
r_ap[i] = 1;
}
if (r_a[w] < r_a[v]) {
// printf(" - a[%d] %d < a[%d] %d", w, r_a[w], v, r_a[v]);
r_a[v] = r_a[w];
}
// printf("\n");
}
else {
// printf("back");
// We have already found this vertex before
if (r_v[w] < r_a[v]) {
// printf(" - updating ascent to %d", r_v[w]);
r_a[v] = r_v[w];
}
// printf("\n");
}
}
}
int dfs_art(graph *g, int root, int *r_p, int *r_v, int *r_a, int *r_ap) {
int i, n_visited = 0, n_root_children = 0;
for (i=0; i<g->n_vertices; i++) {
r_p[i] = r_v[i] = r_a[i] = -1;
r_ap[i] = 0;
}
dfs_art_i(g, root, r_p, r_v, r_a, r_ap, &n_visitados);
// the root can only be an AP if it has more than 1 child
for (i=0; i<g->n_vertices; i++) {
if (r_p[i] == root) {
n_root_children ++;
}
}
r_ap[root] = n_root_children > 1 ? 1 : 0;
return 1;
}
source to share
How do you select the edges to be removed? Can you tell us more about your problem area?
How big is your schedule? maybe BFS is just fine!
After you've written that you're trying to figure out if an edge is a bridge or not, I suggest you remove the edges in descending order of their measure of degree.
Essentially, an internode is a measure of the edges (or vertices) of centrality in a graph. Edges with a higher reciprocity value have a greater potential to be a bridge in the graph.
Check it out on the Internet, the algorithm is called the Girvan-Newman algorithm .
source to share