Message Boards Message Boards


Depth-First Search of a Directed Graph

Posted 9 years ago
2 Replies
4 Total Likes
I have a directed graph on Mathematica that looks like this:

{File1 -> File10, File3 -> File6, File3 ->File 12, etc.}

I would like to search the graph for  and break the graph into various connected components. I do not need to be able to visualize the graph itself, just get the text for its connected components. The graph has roughly 15000 nodes and 75000 edges.

If that graph is too large for Mathematica to dissolve into connected components, could you at least explain the code for dissolving a smaller graph into connected components? I'm fairly new to Mathematica and have heard of the ConnectedComponents command, but am unsure how to use it practically.

Thank you for your help emoticon
POSTED BY: Pat Dillon
2 Replies
There is a built in function:

g = RandomGraph[{15000, 75000}, DirectedEdges -> True];

ConnectedComponents[g] // Length
Out[]= 190
POSTED BY: Sam Carrettie
Posted 9 years ago
If graphs and Mathematica are an interest of yours then you might see if you can get a copy of "Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica(tm)" by Pemmaraju and Skiena. I think that is an essential book to have nearby when dealing with graphs in Mathematica.

Perhaps unfortunately, there have been some changes in Mathematica recently that make using the book slightly less convenient. Parts of the functionality of the graph theory package provided by the authors have been implemented inside Mathematica and that can cause some confusion.

This is an example from page 285 of the book using the package to look for connected components in a directed graph.
 In[1]:= << Combinatorica`
 During evaluation of In[1]:= General::compat: Combinatorica Graph and Permutations functionality has been
 superseded by preloaded functionality. The package now being loaded may conflict with this. Please see the
 Compatibility Guide for details.
 In[2]:= g = RandomGraph[20, 0.1, Type -> Directed]
 Out[2]= -Graph:<42,20,Directed>-

In[3]:= c = StronglyConnectedComponents[g]

Out[3]= {{1}, {2, 7}, {3}, {4, 10, 11, 12, 14, 17, 18}, {5}, {6}, {8}, {9}, {13}, {15}, {16}, {19}, {20}}

IF the directed graph you have constructed is backward compatible with the package then you might use this example to see if you can
get the connected components you are looking for.

You might consider starting with a smaller, but similar, graph and see if you can get everything working. Then you can scale up the size by 4x and if that still works then scale up by 4x again and again. This can give you some idea how the system might behave without throwing the whole problem at it, waiting for hours or days and having no idea whether it is going to be finished in hours or millenia.

If displaying the result c above might take too long you could append a semicolon which will calculate the result and store it in c without display. Then you could do something like Length[ c ] and see how many components there are. Then you might try something like Length[ First[ c ] ] to see how many verticies are in the first component, etc. If it is of practical size then you could display First[ c ] to see the verticies. Starting small to make sure you have the notation correct might be a good idea.

If there were a document somewhere that summed up all the changes between the older package and the newer kernel versions of the combinatorica functions that would be a very useful resource to have.
POSTED BY: Bill Simpson
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract