CODEWITHSUNDEEP
recursiongraphdirected-graph
Blagch
Blagch

Reputation: 95

How to find all equivalent vertices in graph?

Equivalent vertices are those that have the same 'ingoing' and 'outgoing' vertex.

in this case **a** and **c**

Can somebody help me how to approach the algorithm?

I was thinking something like that: to search for two vertices in the same time and if I find equal ingoing and outgoing vertices to print them .. and so on, so it will be actual bruteforce, but how to do this for example with recursion ? What is the best solution?

Upvotes: 4

Views: 656

Answers (2)

errorist
errorist

Reputation: 251

Here's a recursive solution that I come up with.

Imagine that we remove all of the vertices except for two (doesn't matter which two).

In your example, assume that we removed all vertices except for a and b. Notice that a and b are equivalent if and only if there is an edge from a to b, and there is an edge from b to a. This is our base case.

Imagine that we add missing vertices one by one (the order doesn't matter). There are two cases that we need to consider. i) We need to check if any set of vertices became equivalent when we add the vertex. ii) We need to check if any set of vertices that were equivalent, are still equivalent.

Case 1.

In your example, assume that we added c, (recall that we had started with vertices a and b). We know for sure that a and b are stil not equivalent. Why? Because, a has an outgoing vertex that b is missing, and that outgoing vertex is not c, because c was not on the graph earlier. Therefore, we only need to check if there are any vertex that equivalent to c. We can do it efficiently simply by checking ingoing vertices of outgoing vertices of c, and outgoing vertices of ingoing vertices of c. Then, we find out that a and c are equivalent.

Note: I use = symbol to denote the equility of vertices in the remainder of the post.

To be more general, whenever we add a new vertex, (let's say z) to the graph, we know for a fact that there does not exist a pair of vertices, (let's say x and y), such that x != y before we add z, and x = y after we add z. This is because:

Assume that x has an outgoing or ingoing vertex w that y doesn't have without loss of generality. We know that w != z because we did not add z yet. Then, after we add z, y still misses vertex w. Therefore, x != y after we add vertex z. So we need to only check if there are any vertices that are equivalent to z.

Case 2

This case is much simpler. In your example, assume that we finally add d, (recall that we added vertices a, b and c earlier). We had computed that a and c were equivalent, and we need to check if they are still equivalent after we add d. Notice that all we need to do is to check if both a and c have d as an outgoing or ingoing vertex. And compare them.

So, in conclusion, we start with two arbitrary vertices, and check whether they are equivalent. Thereafter, we add each vertex one by one and we check case 1 and case 2 as I have described above.

So, let's say you have a recursive function EQ(n) that returns the all equivalent vertices. Then, given a graph with n vertices you call EQ(n-1), i.e., with one vertex missing (let's say z). And you check case 1 and case 2 to see how z effects the overall solution. And in your base case you have n = 2, as I've mention at the beginning.

So the running time of the algorithm is given as this recurrence T(2) = O(1) and T(n) = T(n - 1) + O(n). Therefore, the running time is O(n^2).

Upvotes: 1

D. Law.
D. Law.

Reputation: 244

One approach would be to add lists to each vertex, one for ingoing vertices, List ingoingVertices, and one for outgoing vertices, List outgoingVertices. Then traverse the edges for each vertex adding the visited vertex to the List outgoingVertices within the first vertex, and every time you take an edge out of the first vertex add the first vertex to the List ingoingEdges of the visited vertex. Then just iterate through the vertices checking if the lists are the same between two vertices to find their equivalence.

Recursively visiting each vertex and then doing that vertex will be about the same as iterating through each vertex. Brute forcing to compare only two vertices at one time will work, but it will take more effort to code and more time during runtime.

Upvotes: 1

Related Questions