0
$\begingroup$

I have a collection of graph nodes which are connected to each other.

I wrote a DFS algorithm to recursively search the connectivity of the graph to find all connected nodes, however due to the size of the network, it is taking too long.

To improve the performance, I wanted to assign tags to the nodes, as MAJOR and NOT-MAJOR, such that I can create a new graph that only contains the connections from MAJOR nodes to other MAJOR nodes, sort of illustrated in the photo below where the big circle denotes MAJOR and the red dot denotes NOT-MAJOR:

enter image description here

The desired result would be taking the left graph and compressing it down to the right.

The data I am working through is very large, and there are a lot of interconnections, many islands, and always at least 1 major node.

I have written a second version of my DFS function to take the graph and a major node, traverse each connected node to the major and check if the connected node is a major node, if so then append that major node to a new list, and return the list as the new connections, otherwise return a list only containing the major node itself.

But this is still taking a very long time to pass through the entire network, with the program sometimes crashing due to maximum recursion depth exceeded (Which tells me I have not implemented this very well).

Is there a better way I can approach this compression problem?

$\endgroup$
  • 1
    $\begingroup$ Your task isn't really well-defined. I still don't know what you want to accomplish. However, you might want to take a look at the topic of graph sparsification. $\endgroup$ – Yuval Filmus May 1 at 16:02
  • 3
    $\begingroup$ You are highlighting a programming issue, maximum recursion depth exceeded. You might want to convert your recursion to an iterative algorithm using a stack. $\endgroup$ – Yuval Filmus May 1 at 16:03
  • $\begingroup$ python-specific questions are off-topic here. $\endgroup$ – Yuval Filmus May 1 at 17:30
  • 2
    $\begingroup$ You mention that you are interested in performance, and that your algorithm is too slow. If you switch from python to C, the algorithm will likely run orders of magnitudes faster. $\endgroup$ – Yuval Filmus May 1 at 17:30
  • $\begingroup$ Whenever performance is concerned, relevant statistics should be included. For example, how many nodes and how many interconnections are there? If you got the precise numbers, great. Otherwise, rough estimates should be helpful enough as well. $\endgroup$ – Apass.Jack May 3 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.