StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POClique problem algorithm design
text
Body
copied!<p>One of the assignments in my algorithms class is to design an exhaustive search algorithm to solve the clique problem. That is, given a graph of size <em>n</em>, the algorithm is supposed to determine if there is a complete sub-graph of size <em>k</em>. I think I've gotten the answer, but I can't help but think it could be improved. Here's what I have:</p> <h1>Version 1</h1> <p><strong>input</strong>: A graph represented by an array A[0,...<em>n</em>-1], the size <em>k</em> of the subgraph to find.</p> <p><strong>output</strong>: True if a subgraph exists, False otherwise</p> <p><strong>Algorithm</strong> (in python-like pseudocode):</p> <pre><code>def clique(A, k): P = A x A x A //Cartesian product for tuple in P: if connected(tuple): return true return false def connected(tuple): unconnected = tuple for vertex in tuple: for test_vertex in unconnected: if vertex is linked to test_vertex: remove test_vertex from unconnected if unconnected is empty: return true else: return false </code></pre> <h1>Version 2</h1> <p><strong>input</strong>: An adjacency matrix of size n by n, and k the size of the subgraph to find</p> <p><strong>output</strong>: All complete subgraphs in A of size k.</p> <p><strong>Algorithm</strong> (this time in functional/Python pseudocode):</p> <pre><code>//Base case: return all vertices in a list since each //one is a 1-clique def clique(A, 1): S = new list for i in range(0 to n-1): add i to S return S //Get a tuple representing all the cliques where //k = k - 1, then find any cliques for k def clique(A,k): C = clique(A, k-1) S = new list for tuple in C: for i in range(0 to n-1): //make sure the ith vertex is linked to each //vertex in tuple for j in tuple: if A[i,j] != 1: break //This means that vertex i makes a clique if j is the last element: newtuple = (i | tuple) //make a new tuple with i added add newtuple to S //Return the list of k-cliques return S </code></pre> <p>Does anybody have any thoughts, comments, or suggestions? This includes bugs I might have missed as well as ways to make this more readable (I'm not used to using much pseudocode).</p> <h1>Version 3</h1> <p>Fortunately, I talked to my professor before submitting the assignment. When I showed him the pseudo-code I had written, he smiled and told me that I did <em>way</em> too much work. For one, I didn't have to submit pseudo-code; I just had to demonstrate that I understood the problem. And two, he <em>was</em> wanting the brute force solution. So what I turned in looked something like this:</p> <p><strong>input</strong>: A graph G = (V,E), the size of the clique to find <em>k</em></p> <p><strong>output</strong>: True if a clique does exist, false otherwise</p> <p><strong>Algorithm</strong>:</p> <ol> <li>Find the Cartesian Product V<sup>k</sup>.</li> <li>For each tuple in the result, test whether each vertex is connected to every other. If all are connected, return true and exit.</li> <li>Return false and exit.</li> </ol> <p><strong>UPDATE</strong>: Added second version. I think this is getting better although I haven't added any fancy dynamic programming (that I know of).</p> <p><strong>UPDATE 2</strong>: Added some more commenting and documentation to make version 2 more readable. This will probably be the version I turn in today. Thanks for everyone's help! I wish I could accept more than one answer, but I accepted the answer by the person that's helped me out the most. I'll let you guys know what my professor thinks.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload