Description:
Consider the following values for con_data:
1 1 0 1 0
1 1 0 0 0
0 0 1 1 1
1 0 1 1 0
0 0 1 0 1
Look at row 2 (corresponding to object 2). There is a 1 in column 1.
This means object 2 is connected to object 1. Now look at row 1
(corresponding to object 1). There is a 1 in column 4. This means
that object 1 is connected to object 4. Since object 2 is connected
to object 1, this also means object 2 is connected to object 4. Now
look at row 4 (corresponding to object 4). There is a 1 in column 3
so object 4 is connected to object 3 and, as before, objects 1 and 2
are also connected to object 3. Finally, look at row 3. There is a 1
in column 5 so object 3 is connected to object 5 and so are objects
1,2, and 4. Because all objects are connected, we say that this
matrix represents a connected set of objects. On the other hand the
matrix
1 1 0 0 0
1 1 0 0 0
0 0 1 1 1
0 0 1 1 0
0 0 1 0 1
does not represent a connected set of objects.
Problem: Write a Matlab function, call it prob3, that takes as input a 0-1 square matrix con_data and returns 1 if the matrix represents a connected set of objects and 0 if it doesn't. Solution description: Start at one object, say object 1, and call it current. Mark current visited. Repeat the following until no more objects can be marked visited: for each object connected to current (as indicated by a 1 in the row of con_data corresponding to current) that has not yet been visited (not yet marked), call it current and mark it visited. If some object remains unmarked (that is, unvisited), then the objects are not connected so return 0, otherwise all objects are connected so return 1. Alternative Solution (not for the faint at heart): Let n=length(con_data), and c=con_data. Repeat the following line n times: c=(c*con_data) & ones(n,n);. If the number of 1s in c is n2 then return 1 otherwise return 0. Can you figure out why this works? |