0
$\begingroup$

I have a graph $G=(V,E)$ that consists of many disconnected directed subgraphs, some of them may be cyclic. (Basically a "forest" consisting of directed trees and some directed disconnected cyclic graphs added into it).

I want to find all of these disconnected subgraphs and turn them into stars given by the key of the node.

I've built a directed graph (using Python's networkx library) and now I am kinda stuck how to find those disconnected subgraphs, because some of those subgraphs will have source and some of those wont.

How to proceed? Thanks!

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ What do you mean "turn them into stars"? $\endgroup$ – fade2black Aug 18 '17 at 17:21
  • $\begingroup$ graphs that topologically resemble stars. en.wikipedia.org/wiki/Star_%28graph_theory%29 $\endgroup$ – PeterBocan Aug 18 '17 at 17:44
  • 2
    $\begingroup$ I know what star is, but suppose you find all disconnected components $C_1,C_2, \dots C_n$, so what do you mean by "turn them into stars given by the key of the node"? Connect all components to a single node by $n$ edges? $\endgroup$ – fade2black Aug 18 '17 at 17:48
  • $\begingroup$ Oh sorry, I mean, all those components $C_1, C_2, \dots, C_n$ morph into $S_1, S_2, \dots, S_n$ where $S_1, \dots, S_n$ are stars and also disconnected directed subgraphs among each other. The number of disconnected components will not change, the edges have to. $\endgroup$ – PeterBocan Aug 18 '17 at 22:11
  • 1
    $\begingroup$ What do you mean by "morph"? It sounds like you are talking about making some changes to the graph, but what kinds of changes are allowed and what kinds of changes aren't allowed? Or do you mean that you don't want the graph to be changed but you just want to group the vertices in some way? In that case what do you plan to do if a component $C_i$ isn't a star? What if it has some other shape? I don't understand what you are asking. Can you edit the question to define more carefully what the desired output is, and how it relates to the input? $\endgroup$ – D.W.♦ Aug 19 '17 at 1:55
2
$\begingroup$

Probably you want to compute weakly connected components, a subgraph having a path between every two vertices in the underlying undirected graph. Computing the weakly connected components is easy: first transform the directed graph into undirected by removing "directions" of each edge and run DFS/BFS on that graph (by looping on vertices!). Alternatively, if you're interested in the strongly connected components then you should run one of the algorithms computing SCCs. This gives you components $C_1, \dots, C_n$.

Then you can do whatever you want to do on these components.

| cite | improve this answer | | | | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.