SRM 713, D1, 500-Pointer (DFSCount)

James S. Plank

Sun Jul 2 22:46:57 EDT 2017
Let's attack this problem with an example graph:

This graph has a lot of nodes and edges, but the ones that we care about are the ones connected to node 0. If you remove node zero from the graph, there will be three connected components in the graph, which I've labeled A, B, and C.

Now, suppose that we are starting with node 0. There are only six edges out of node zero, so there are only six ways that the DFS can start. Now, suppose that the DFS starts with node 1. Since it's a DFS, it will visit all of the nodes in A, before it visits any of the nodes in B or C. Same thing if it starts with node 2.

Now, suppose it starts with node 3. That means it will visit all of the nodes in B before it visits any of the nodes in A or C. This observation helps us start a solution.


Now, suppose we focus solely on a connected component, like A. And suppose that we determine the number of DFS's in A, if we start from node 1. Let's call that D(A,1). We can construct a solution that counts all of the DFS' that start with node zero, that is a function of D(A,1) through D(A,6).

Let's affix an ordering of how we progress through the components -- suppose we go through A first, then B, and then C. The number of ways to go through component A may be calculated as:

D(A,1) + D(A,2)

Similarly, the number of ways to go through component B is D(A,3) + D(A,4), and the number of ways to go through component C is D(A,5) + D(A,6). Since these are independent, the number of ways to go through A, then B, then C is:

( D(A,1) + D(A,2) ) * ( D(A,3) + D(A,4) ) * ( D(A,5) + D(A,6) )

If you think about it, it doesn't matter what order you choose to go through the components. Once you choose an order, the number of ways to go through the components in that order is the equation above. Since there are 3! ways to go through the components, the number of ways to go through the graph starting with node zero is:

3! * ( D(A,1) + D(A,2) ) * ( D(A,3) + D(A,4) ) * ( D(A,5) + D(A,6) )


This now gives us a strategy for solving the problem: Your main program should sum up D(Graph,node) for every node in the original graph.

The base case of the recursion is when there is only one node in the component.

You need to figure out how to represent a component for the recursion. What I did was represent it with a string with N characters (assuming there are N nodes in the graph). If a node is in the component, then its character in the string is 'X'. Otherwise, it's '-'. Go ahead and write this program. You should be able to test it on examples 0, 1, 2 and 4.

To help you, I'm printing the output of these examples below. In the component string, I've labeled node as 's'. So, in example 0, the initial call in is D({0,1,2,3}, 0). I represent that with the string "sXXX". Now, the first thing I do in D is identify the connected components to node node. I do that in a string, where the components are labeled 'A', 'B', etc. For example, in Example 1, the graph is a line 0-1-2-3. When you call it on the whole graph with a starting node of 1 ("XsXX"), then there are two different components connected to node 1: {0} and {2,3}. That is represented with the string "A-BB".

UNIX> a.out 0
Calling D(XXX, 0)
- Nodes left: sXX Node =  0.  Comp = -AA.  Key = 110 0x0006 Will be using recursion.
- Nodes left: -sX Node =  1.  Comp = --A.  Key = 100 0x0004 Will be using recursion.
- Nodes left: --s Node =  2.  Comp = ---.  Key = 000 0x0000 Base case: No components left: 1
+ Nodes left: -sX Node =  1.               Key = 100 0x0004 Putting 1 into cache & returning.
- Nodes left: -Xs Node =  2.  Comp = -A-.  Key = 010 0x0002 Will be using recursion.
- Nodes left: -s- Node =  1.  Comp = ---.  Key = 000 0x0000 Base case: No components left: 1
+ Nodes left: -Xs Node =  2.               Key = 010 0x0002 Putting 1 into cache & returning.
+ Nodes left: sXX Node =  0.               Key = 110 0x0006 Putting 2 into cache & returning.
Calling D(XXX, 1)
- Nodes left: XsX Node =  1.  Comp = A-A.  Key = 101 0x0005 Will be using recursion.
- Nodes left: s-X Node =  0.  Comp = --A.  Key = 100 0x0004 Will be using recursion.
- Nodes left: --s Node =  2.  Comp = ---.  Key = 000 0x0000 In Cache: 1
+ Nodes left: s-X Node =  0.               Key = 100 0x0004 Putting 1 into cache & returning.
- Nodes left: X-s Node =  2.  Comp = A--.  Key = 001 0x0001 Will be using recursion.
- Nodes left: s-- Node =  0.  Comp = ---.  Key = 000 0x0000 Base case: No components left: 1
+ Nodes left: X-s Node =  2.               Key = 001 0x0001 Putting 1 into cache & returning.
+ Nodes left: XsX Node =  1.               Key = 101 0x0005 Putting 2 into cache & returning.
Calling D(XXX, 2)
- Nodes left: XXs Node =  2.  Comp = AA-.  Key = 011 0x0003 Will be using recursion.
- Nodes left: sX- Node =  0.  Comp = -A-.  Key = 010 0x0002 Will be using recursion.
- Nodes left: -s- Node =  1.  Comp = ---.  Key = 000 0x0000 In Cache: 1
+ Nodes left: sX- Node =  0.               Key = 010 0x0002 Putting 1 into cache & returning.
- Nodes left: Xs- Node =  1.  Comp = A--.  Key = 001 0x0001 Will be using recursion.
- Nodes left: s-- Node =  0.  Comp = ---.  Key = 000 0x0000 In Cache: 1
+ Nodes left: Xs- Node =  1.               Key = 001 0x0001 Putting 1 into cache & returning.
+ Nodes left: XXs Node =  2.               Key = 011 0x0003 Putting 2 into cache & returning.
6
UNIX> a.out 1
Calling D(XXXX, 0)
- Nodes left: sXXX Node =  0.  Comp = -AAA.  Key = 1110 0x000e Will be using recursion.
- Nodes left: -sXX Node =  1.  Comp = --AA.  Key = 1100 0x000c Will be using recursion.
- Nodes left: --sX Node =  2.  Comp = ---A.  Key = 1000 0x0008 Will be using recursion.
- Nodes left: ---s Node =  3.  Comp = ----.  Key = 0000 0x0000 Base case: No components left: 1
+ Nodes left: --sX Node =  2.                Key = 1000 0x0008 Putting 1 into cache & returning.
+ Nodes left: -sXX Node =  1.                Key = 1100 0x000c Putting 1 into cache & returning.
+ Nodes left: sXXX Node =  0.                Key = 1110 0x000e Putting 1 into cache & returning.
Calling D(XXXX, 1)
- Nodes left: XsXX Node =  1.  Comp = A-BB.  Key = 1101 0x000d Will be using recursion.
- Nodes left: s-XX Node =  0.  Comp = ----.  Key = 0000 0x0000 Base case: No components left: 1
- Nodes left: X-sX Node =  2.  Comp = ---A.  Key = 1000 0x0008 In Cache: 1
+ Nodes left: XsXX Node =  1.                Key = 1101 0x000d Putting 2 into cache & returning.
Calling D(XXXX, 2)
- Nodes left: XXsX Node =  2.  Comp = AA-B.  Key = 1011 0x000b Will be using recursion.
- Nodes left: Xs-X Node =  1.  Comp = A---.  Key = 0001 0x0001 Will be using recursion.
- Nodes left: s--X Node =  0.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: Xs-X Node =  1.                Key = 0001 0x0001 Putting 1 into cache & returning.
- Nodes left: XX-s Node =  3.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: XXsX Node =  2.                Key = 1011 0x000b Putting 2 into cache & returning.
Calling D(XXXX, 3)
- Nodes left: XXXs Node =  3.  Comp = AAA-.  Key = 0111 0x0007 Will be using recursion.
- Nodes left: XXs- Node =  2.  Comp = AA--.  Key = 0011 0x0003 Will be using recursion.
- Nodes left: Xs-- Node =  1.  Comp = A---.  Key = 0001 0x0001 In Cache: 1
+ Nodes left: XXs- Node =  2.                Key = 0011 0x0003 Putting 1 into cache & returning.
+ Nodes left: XXXs Node =  3.                Key = 0111 0x0007 Putting 1 into cache & returning.
6
UNIX> a.out 2
Calling D(XXXX, 0)
- Nodes left: sXXX Node =  0.  Comp = -AAA.  Key = 1110 0x000e Will be using recursion.
- Nodes left: -sXX Node =  1.  Comp = --AB.  Key = 1100 0x000c Will be using recursion.
- Nodes left: --sX Node =  2.  Comp = ----.  Key = 0000 0x0000 Base case: No components left: 1
- Nodes left: --Xs Node =  3.  Comp = ----.  Key = 0000 0x0000 Base case: No components left: 1
+ Nodes left: -sXX Node =  1.                Key = 1100 0x000c Putting 2 into cache & returning.
- Nodes left: -XsX Node =  2.  Comp = -A-A.  Key = 1010 0x000a Will be using recursion.
- Nodes left: -s-X Node =  1.  Comp = ---A.  Key = 1000 0x0008 Will be using recursion.
- Nodes left: ---s Node =  3.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: -s-X Node =  1.                Key = 1000 0x0008 Putting 1 into cache & returning.
+ Nodes left: -XsX Node =  2.                Key = 1010 0x000a Putting 1 into cache & returning.
- Nodes left: -XXs Node =  3.  Comp = -AA-.  Key = 0110 0x0006 Will be using recursion.
- Nodes left: -sX- Node =  1.  Comp = --A-.  Key = 0100 0x0004 Will be using recursion.
- Nodes left: --s- Node =  2.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: -sX- Node =  1.                Key = 0100 0x0004 Putting 1 into cache & returning.
+ Nodes left: -XXs Node =  3.                Key = 0110 0x0006 Putting 1 into cache & returning.
+ Nodes left: sXXX Node =  0.                Key = 1110 0x000e Putting 4 into cache & returning.
Calling D(XXXX, 1)
- Nodes left: XsXX Node =  1.  Comp = A-AA.  Key = 1101 0x000d Will be using recursion.
- Nodes left: s-XX Node =  0.  Comp = --AB.  Key = 1100 0x000c Will be using recursion.
- Nodes left: --sX Node =  2.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
- Nodes left: --Xs Node =  3.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: s-XX Node =  0.                Key = 1100 0x000c Putting 2 into cache & returning.
- Nodes left: X-sX Node =  2.  Comp = A--A.  Key = 1001 0x0009 Will be using recursion.
- Nodes left: s--X Node =  0.  Comp = ---A.  Key = 1000 0x0008 Will be using recursion.
- Nodes left: ---s Node =  3.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: s--X Node =  0.                Key = 1000 0x0008 Putting 1 into cache & returning.
+ Nodes left: X-sX Node =  2.                Key = 1001 0x0009 Putting 1 into cache & returning.
- Nodes left: X-Xs Node =  3.  Comp = A-A-.  Key = 0101 0x0005 Will be using recursion.
- Nodes left: s-X- Node =  0.  Comp = --A-.  Key = 0100 0x0004 Will be using recursion.
- Nodes left: --s- Node =  2.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: s-X- Node =  0.                Key = 0100 0x0004 Putting 1 into cache & returning.
+ Nodes left: X-Xs Node =  3.                Key = 0101 0x0005 Putting 1 into cache & returning.
+ Nodes left: XsXX Node =  1.                Key = 1101 0x000d Putting 4 into cache & returning.
Calling D(XXXX, 2)
- Nodes left: XXsX Node =  2.  Comp = AA-A.  Key = 1011 0x000b Will be using recursion.
- Nodes left: sX-X Node =  0.  Comp = -A-A.  Key = 1010 0x000a Will be using recursion.
- Nodes left: -s-X Node =  1.  Comp = ---A.  Key = 1000 0x0008 In Cache: 1
- Nodes left: -X-s Node =  3.  Comp = -A--.  Key = 0010 0x0002 Will be using recursion.
- Nodes left: -s-- Node =  1.  Comp = ----.  Key = 0000 0x0000 Base case: No components left: 1
+ Nodes left: -X-s Node =  3.                Key = 0010 0x0002 Putting 1 into cache & returning.
+ Nodes left: sX-X Node =  0.                Key = 1010 0x000a Putting 2 into cache & returning.
- Nodes left: Xs-X Node =  1.  Comp = A--A.  Key = 1001 0x0009 Will be using recursion.
- Nodes left: s--X Node =  0.  Comp = ---A.  Key = 1000 0x0008 In Cache: 1
- Nodes left: X--s Node =  3.  Comp = A---.  Key = 0001 0x0001 Will be using recursion.
- Nodes left: s--- Node =  0.  Comp = ----.  Key = 0000 0x0000 Base case: No components left: 1
+ Nodes left: X--s Node =  3.                Key = 0001 0x0001 Putting 1 into cache & returning.
+ Nodes left: Xs-X Node =  1.                Key = 1001 0x0009 Putting 2 into cache & returning.
+ Nodes left: XXsX Node =  2.                Key = 1011 0x000b Putting 4 into cache & returning.
Calling D(XXXX, 3)
- Nodes left: XXXs Node =  3.  Comp = AAA-.  Key = 0111 0x0007 Will be using recursion.
- Nodes left: sXX- Node =  0.  Comp = -AA-.  Key = 0110 0x0006 Will be using recursion.
- Nodes left: -sX- Node =  1.  Comp = --A-.  Key = 0100 0x0004 In Cache: 1
- Nodes left: -Xs- Node =  2.  Comp = -A--.  Key = 0010 0x0002 Will be using recursion.
- Nodes left: -s-- Node =  1.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: -Xs- Node =  2.                Key = 0010 0x0002 Putting 1 into cache & returning.
+ Nodes left: sXX- Node =  0.                Key = 0110 0x0006 Putting 2 into cache & returning.
- Nodes left: XsX- Node =  1.  Comp = A-A-.  Key = 0101 0x0005 Will be using recursion.
- Nodes left: s-X- Node =  0.  Comp = --A-.  Key = 0100 0x0004 In Cache: 1
- Nodes left: X-s- Node =  2.  Comp = A---.  Key = 0001 0x0001 Will be using recursion.
- Nodes left: s--- Node =  0.  Comp = ----.  Key = 0000 0x0000 In Cache: 1
+ Nodes left: X-s- Node =  2.                Key = 0001 0x0001 Putting 1 into cache & returning.
+ Nodes left: XsX- Node =  1.                Key = 0101 0x0005 Putting 2 into cache & returning.
+ Nodes left: XXXs Node =  3.                Key = 0111 0x0007 Putting 4 into cache & returning.
16
UNIX> a.out 4
Calling D(X, 0)
- Nodes left: s Node =  0.  Comp = -.  Key = 0 0x0000 Base case: No components left: 1
1
UNIX> 
Of course, this recursive program blows up exponentially, so you have to memoize on the component and the starting node. I first did this by turning the component and starting node into a string, and I had my cache be a map. However, it was too slow. So instead, I used bit arithmetic to represent a component by a number, and I had a vector of caches -- one for every possible starting node. (14 possible starting nodes, and 214 elements in each cache -- that's 229,376 elements in the caches -- no problem). That was fast enough!

I have put the output to example 3 in ex3.txt.

I have also created example 5:

  1-2-3
 /
0-4-5-6
 \
  7-8-9
Its output is in ex5.txt. That might be a good graph to explain this problem if you're in CS494/594.

Running Time

I had a student ask for help in analyzing the running time of this. Here was my response:
Let's simply assume that the graph is connected, so we can dispense
with |V| and |E|, and simply work with n.  |V| = n.  |E| = n^2.  The
connected component analysis is O(n^2), since it is a simple DFS,
visiting each edge (in each direction) once.

Calculating the key is O(n), as is calculating T. So we're still at
O(n^2).

Next, you want to figure out the effect of D(). This is the difficult
part of the analysis.  Since this is dynamic programming, the number
of calls to D() is going to be roughly equal to the size of the
memoization cache.  Consider the case where there is one fully
connected component.  D() can be called on every possible subset of
the nodes.  That is the power set of the nodes, (every possible
binary string of size n) — 2^n.  I kept a separate cache for each
possible starting node — of course, that meant that the bit
corresponding to that node was always the same in the cache string.
So it’s really 2^(n-1) for each starting node.  Overall, that looks
like n * 2^(n-1) * n^2.  That’s one of the reasons why they limited
n to 14.

If you want to test your program for performance — generate fully
connected test graphs, and make two graphs: time, and number of
overall (set, not unset) elements in the memoization caches.