Check for Cycles in Undirected Graphs: O(|V|) Algorithm

[0rthodontist]

I'm just posting a random graph algorithm problem for discussion fodder, since another interesting graph algorithm post was removed due to a threatening-sounding title and lead-up. This is from Cormen, Leiserson, Rivest, & Stein, 22.4-3 (not a homework problem of any kind, just for fun--I had algorithms a year ago). It should be pretty accessible to all audiences:

Give an O(|V|) algorithm that determines whether or not an undirected graph G = (V, E) contains a cycle.

Hint (highlight): if the graph has at least |V| edges you know it's cyclic
If you answer this, why not post your own interesting mathematical CS question! (don't post homework)

 

[-Job-]

The following may seem like overkill, but basically we check each edge one by one until we see at most |V| edges, at which point we have a cycle and return.

Begin
Declare TotalEdges
For Each Node x In V
    For Each Edge y Of Node x
         IF IsNotMarked(y) Then
               Mark(y)
               TotalEdges++
               IF TotalEdges = |V| RETURN "HAS CYCLE"
         End IF
    End For
End For
RETURN "NO CYCLE"
End

My question is one i thought of recently, so I'm not guaranteed to have the best solution.
Consider two graphs G1 and G2. Define G1 and G2 as "equivalent" if G1's nodes can be reordered such that G1 becomes identical to G2.
1. How many unique graphs of n nodes are there?
2. Give your best algorithm for determining if two graphs G1 and G2 are equivalent.

EDIT: This is known as the Graph isomorphism problem apparently. http://en.wikipedia.org/wiki/Graph_isomorphism_problem
You're excused if you can't find a polynomial time algorithm, but if you have an algorithm why not post it.

 

[Sane]

P.S. I think I may have sorted out the problem, about my topic, with the moderators. After three posts, and two deleted threads, it is back up. The problem was, some moderators were under the impression that the solution to the question actually provided a way to launch a network attack! Hahaha! So check that thread out, for my "contribution" to this thread.​

Give an O(|V|) algorithm that determines whether or not an undirected graph G = (V, E) contains a cycle.

You can not count edges, as your hint describes, because what if you have different subsections of nodes? Those edgeless nodes will make one more node able to have an additional edge. Potentially creating a cycle. Counting edges will only work for a continuous graph.

http://img174.imageshack.us/img174/5788/dagtestta7.jpg​

[/URL]

I assume this question is checking if G is a "Directed Acyclic Graph", or DAG, for short. If it is a DAG, then it is linear and does not contain a cycle.

In which case, this is very easy. We just look for a backedge, since that denotes a cycle. This is O(|V|) (linear) time!

Note : The following code would need to used for each subsection, by checking the visited nodes array when you're done, and recursing again until no more nodes exist.

function dfs
    input: parent node, current node, visited nodes (global), adjacency matrix for graph G
    output: dag or not
    
    result = "Graph G Is A Dag"
    for adjacent node in adjacency matrix
        if adjacent node is a visited node
            if its not the parent node
                return "Graph G Is Not A Dag"
        else
            mark the adjacent node as visited
            tempResult = dfs (current node, adjacent node, visited nodes, adjacency matrix for graph G)
            if tempResult is "Graph G Is Not A Dag"
                result = tempResult
    
    return "Graph G Is A Dag"

 

[0rthodontist]

Job, that's similar to what I had in mind though you also need to check if you run into a marked node other than the parent node. Sane, your method works except you should return "tempResult" in place of your line "result = tempResult." Also you should use an adjacency list, not an adjacency matrix since an adjacency matrix always requires n steps to determine the nodes adjacent to a given one. (The hint was just to put an upper bound on your algorithm's complexity--I wasn't suggesting that counting the edges was a complete algorithm)

Graph isomorphism...
There are 2^(C(n, 2)) ways to choose the edges of a graph with n vertices. There are n! ways to reorder the vertices. However many of these orderings will yield graphs that are identical, not just isomorphic. I don't know, it looks like you might count them using Burnside's lemma, but I don't see a good way. Give an easier problem.

 

[Sane]

Adjacency list is the terminology I meant to use. And, yes, I suppose you don't need to search the rest of the tree once the first back-edge is found. I wrote that in a rush.

 

[-Job-]

Anyway, to a say little about the graph isomorphism problem. Your estimate of 2^(C(n, 2))/n! is what i had in mind. It's ok if some of the orderings are identical. A graph of n nodes has at most n(n-1)/2 edges. So we can represent any graph of n nodes with n(n-1) bits and it's clear that we can have at most 2^(n(n-1)) different graphs. Of these graphs many are different "perspectives" of the same graph. For each unique graph there are n! different perspectives. So there should be 2^(n(n-1))/n! unique graphs right?

As for an algorithm, it would be nice to have a function that returns the same value for a graph, independently of perspective. But suppose we have such a value, then that is the perspective-less representation of the graph. It's an absolute representation of the graph. If instead of graphs we have objects then we might be able to assign an absolute value to every object.

Anyway i don't have a "solvable" graph problem to post yet, if somebody has one, don't wait for me.

 

[Hurkyl]

It's ok if some of the orderings are identical.

It's not the orderings he meant: it's the graphs themselves. For example, the graph

* ----- *

has exactly one "perspective", not 2.

 

[0rthodontist]

A little judicious googling turns up this programmatic approach to counting isomorphic graphs on n vertices:
http://www.polyomino.f2s.com/david/haskell/polyacounting2.html

 

[-Job-]

Yeah, it's not exactly 2^[n(n-1)/2)]/n!, any complete graph of n nodes takes up only one of the 2^(n(n-1)/2) representations, not n!.
Nevermind.

 

[-Job-]

Ok, the following problem is from parallel computation:

Produce an algorithm that, given an array of n bits, identifies the index of the first bit in the array whose value is 1, in O(1) time using at most n processors. You can assume the processors can read and write concurrently if it helps.

If you're new to parallel computation, the idea is to take advantage of the capability to perform computations in parallel as much as possible, everything else is the same.

TIP - (select text to view)Divide the processors into groups of size SquareRoot(n).

 

[0rthodontist]

I don't see how any divide and conquer could work because the number of layers in the tree would have to increase as n increases. I assume that the processors can only read or write a constant number of bits in any constant time interval.

 

[-Job-]

I should probably mention that the solution doesn't involve a graph since we've been posting graph related problems, to avoid confusion.

The solution is a three step process. You should think about how you would solve this problem if you had n^2 processors instead of n. You can allocate arrays if you like, or anything else just as in a regular sequential algorithm, just make sure you stay within O(1).

Let me give an example of an easy parallel problem and solution, to outline the format:
Example Problem: Produce an algorithm that, given an array of n elements, determines if there is at least one non-zero element in the array, in O(1) using n processors.

Example Solution:
Step 1: Allocate an Output bit, initialized to 0.
Step 2: Processor i looks at the ith element of the input array. If the ith element is a 1 then processor i writes a 1 to the Output bit, otherwise it does nothing.
Step 3: Return the value in the Output bit.

 

[Hurkyl]

Details...

I'm assuming that the processors are synchronized: they all perform one operation per "tick".

If multiple processors write to the same location in memory, they must all write the same value. Otherwise, it's considered an error.

If a processor reads from a memory location during the same tick in which another processor writes to a memory location, it's considered an error.

Processors can only communicate through memory.

Processors can only act on one bit at a time.

(This last one is key, I think. Are you requiring this, or can a processor write an entire number in one tick?)

 

[0rthodontist]

I was already thinking along those lines but I don't see how to extend it to finding the first bit. For example, you can't have each processor X write the index of the bit it is responsible for to an output register only if the output register is greater than the index of the bit and at the same time the bit that X is responsible for is 1. That would lead to synchronization problems where many registers try to write their indices at the same time, and no way to resolve those problems without using $$\Omega(n)$$ time.

I don't see how your first problem could be done with any number of processors. How do you do it with n^2?

 

[Hurkyl]

Notationally, I'm going to assume the array and processors are two-dimensional. That is, the indices in the array are:

(0, 0) - (0, 1) - (0, 2) - ... - (0, n-1) - (1, 0) - (1, 1) - ... - (n-1, n-1)

(so the array is of length n²)

The following directions are the program for processor (a, b). The first 1 happens to be at location (x, y)

Let A and B be arrays of length n, initialized to zero.

(1) if (array[a, b] = 1) then A[a] := 1
(2) if (a < b) and (A[a] = 1), then A := 0
(3) if (A[a] = 1) then write the b-th bit of a to the output as the b-th bit of the first index

(note that A[k] = 1 iff k = x)

(4) if (array[a, b] = 1) and (A[a] = 1) then B := 1
(5) if (a < b) and (B[a] = 1), then B := 0
(6) if (B[a] = 1) then write the b-th bit of a to the output as the b-th bit of the second index

(note that B[k] = 1 iff k = y)

 

[-Job-]

Hurkyll the details you mentioned are safe to assume, although if two processors write different values at the same time generally one wins over the other one, such as the one with the highest index. For this problem this shouldn't be an issue. Processors can write an entire number in one tick and you can access a memory location in one tick as well (random access memory). Try to explain the general idea of the algorithm, rather than just the process to make it easier to read.

Here's a solution to the problem using n^2 processors, Hurkyll i'll look at your answer and get back to you.

Step 1: Allocate space for an output integer between 0 and n.
Step 2: Divide the n^2 processors into n groups of n processors.
Step 3: For each group allocate a Flag bit, initialized to 0.
Step 4: Group i will be responsible for determining if the ith element is the first element whose value is 1 in the array.
Step 5: If element i is 0, then group i does nothing for the rest of the algorithm, since element i is definitely not the first element of value 1 in the array.
Step 6: If element i is a 1 then, in order to determine if the element i is the first 1 in the array, Group i needs to look at the (i-1) elements that come before element i. Group i uses (i-1) of its n processors to look at the first (i-1) elements of the array, in parallel. Each of these processors looks at one one of the first (i-1) elements of the array, and, if that element is a 1, writes a 1 to the group's Flag bit, otherwise the processor does nothing.
Step 7: At this time the first processor of group i looks at its flag bit. The flag bits tell us whether there is a 1 before element i. If the flag is 1, then there is at least one element before element i whose value is 1. Therefore, if the Flag bit is a 0, the first processor of group i writes i to the Output integer, otherwise it does nothing.
Step 8: Return the output integer.

 

[-Job-]

Your algorithm seems to work Hurkyl, the main idea is there. You split the elements into SquareRoot(n) columns of SquareRoot(n) elements. You first identify the column containing the first 1, then you determine the first 1 in that column. Well done.

The solution i had in mind is similar. In my previous post i gave an algorithm that determines the index of the first element whose value is 1 in an array of n elements, in O(1), using n^2 processors, call it GET_FIRST1_N2.
The idea is to split the processors into groups of SquareRoot(n) processors. Each group is assigned SquareRoot(n) elements.
We allocate an array, k[], of SquareRoot(n) elements, initialized to 0.
Group i looks at its SquareRoot(n) elements to determine if there is at least one 1 among its elements. If there is then it writes a 1 to k.
What we end up with is an array k[] of SquareRoot(n) elements where k is 1 if there is at least one 1 in the ith group of SquareRoot(n) elements.
Naturally the first group containing at least one 1 is the one containing the first 1.
We are therefore interested in determining the index of the first 1 in k[]. Notice that k has SquareRoot(n) elements, and we have n processors, so we can use GET_FIRST1_N2 to determine the first element in k whose value is 1, in O(1).
Once we have the desired index we know what group of SquareRoot(n) elements contains the first 1. The first 1 in this group is the absolute first 1 in the original array. Again we have an array of SquareRoot(n) elements and n processors, so we can use GET_FIRST1_N2 again to determine the index of the first 1.

 

[0rthodontist]

Well, I don't understand your algorithm, Hurkyl. I wrote a program that I believe does what I think you meant:

import random
import math

array = ['000000','001011','110000','000000', '000000','000001']
A = '000000'
B = '000000'
output = [0, 0]

class processor:
	a, b = 0, 0
	def step1(self):
		if(array[self.a][self.b] == '1'): A[self.a] = '1'
	def step2(self):
		if(self.a < self.b and A[self.a] == '1'): A[self.b] = '0'
	def step3(self):
		if(A[self.a] == '1'):
			output[0] = output[0] | (self.a & int(math.pow(2, self.b)))
			
	def step4(self):
		if(array[self.a][self.b] == '1' and A[self.a] == '1'): B[self.b] = '1'
	def step5(self):
		if(self.a < self.b and B[self.a] == '1'): B[self.b] = '0'
	def step6(self):
		if(B[self.a] == '1'):
			output[1] = output[1] | (self.a & int(math.pow(2, self.b)))
			
	steps = [step1, step2, step3, step4, step5, step6]
			
def perm(str):
	perm = []
	for i in range(0, len(str)):
		r = random.randint(0, len(str)-1)
		perm.append(str[r])
		str = str[:r] + str[r+1:]
	return perm

ps = []
str = []
for x in range(0, 6):
	ps.append([])
	for y in range(0, 6):
		p = processor()
		p.a = x
		p.b = y
		ps[x].append(processor())
		str.append((x, y))

for i in range(0, 6):
	str = perm(str)
	for x, y in str:
		cp = ps[x][y]
		cp.steps[i](cp) # execute step i

print output

Notationally, I'm going to assume the array and processors are two-dimensional. That is, the indices in the array are:

(0, 0) - (0, 1) - (0, 2) - ... - (0, n-1) - (1, 0) - (1, 1) - ... - (n-1, n-1)

(so the array is of length n²)

The following directions are the program for processor (a, b). The first 1 happens to be at location (x, y)

Let A and B be arrays of length n, initialized to zero.

(1) if (array[a, b] = 1) then A[a] := 1
(2) if (a < b) and (A[a] = 1), then A := 0
(3) if (A[a] = 1) then write the b-th bit of a to the output as the b-th bit of the first index

(note that A[k] = 1 iff k = x)

(4) if (array[a, b] = 1) and (A[a] = 1) then B := 1
(5) if (a < b) and (B[a] = 1), then B := 0
(6) if (B[a] = 1) then write the b-th bit of a to the output as the b-th bit of the second index

(note that B[k] = 1 iff k = y)

Have I misrepresented you? This outputs [0,0]

 

[Hurkyl]

You have steps (3) and (6) wrong. The "b-th bit of a" means "the b-th digit in the binary representation of the integer a".

(3) and (6) are my scheme to be able to write the index when I'm counting bit writes. If you allow the processors to write entire integers at a time, then you can replace with:

(3') If A[a] = 1 then output a as the first index
(6') If B[a] = 1 then output a as the second index

(And you can add the condition that b = 1, if you want to write only once to the output)

 

[0rthodontist]

OK, I think I fixed 3 and 6 but it still outputs [0, 0]. Does it have anything to do with the ordering of the steps? I assumed that for every step, every processor completes that step, and the order in which the 36 processors complete the step is random, and so on for all 6 steps.

 

[Hurkyl]

Somethings going wrong in the initialization. I added the line

print self.a, self.b​

to the body of step1, and each time it printed

0 0​

edit: Ah, there it is. You append processor() to ps[x], instead of appending p

 

[0rthodontist]

Ah, ok I fixed that and something else with A and B and now it outputs [1, 2] (which is correct).

import random
import math

array = ['000000','001011','110000','000000', '000000','000001']
A = ['0','0','0','0','0','0']
B = ['0','0','0','0','0','0']
output = [0, 0]

class processor:
	a, b = 0, 0
	def step1(self):
		if(array[self.a][self.b] == '1'): A[self.a] = '1'
	def step2(self):
		if(self.a < self.b and A[self.a] == '1'): A[self.b] = '0'
	def step3(self):
		if(A[self.a] == '1'):
			output[0] = output[0] | (self.a & int(math.pow(2, self.b)))
			
	def step4(self):
		if(array[self.a][self.b] == '1' and A[self.a] == '1'): B[self.b] = '1'
	def step5(self):
		if(self.a < self.b and B[self.a] == '1'): B[self.b] = '0'
	def step6(self):
		if(B[self.a] == '1'):
			output[1] = output[1] | (self.a & int(math.pow(2, self.b)))
			
	steps = [step1, step2, step3, step4, step5, step6]
			
def perm(str):
	perm = []
	for i in range(0, len(str)):
		r = random.randint(0, len(str)-1)
		perm.append(str[r])
		str = str[:r] + str[r+1:]
	return perm

ps = []
str = []
for x in range(0, 6):
	ps.append([])
	for y in range(0, 6):
		p = processor()
		p.a = x
		p.b = y
		ps[x].append(p)
		str.append((x, y))

for i in range(0, 6):
	str = perm(str)
	for x, y in str:
		cp = ps[x][y]
		cp.steps[i](cp) # execute step i

print output

 

[-Job-]

What language are you guys using there? I haven't come across it before.

 

[Hurkyl]

python. Happily, I thought to grab it with my cygwin installation.

 

[0rthodontist]

Python /* 88 */
Edit: whoa the comments aren't working any more?
Edit: huh, I guess they are. I had just typed / * 88 * / to fill 10char and it was viewable in my browser for some reason.

 

[-Job-]

That's what i thought, python seems popular around here.