Peterson Graph Problem

Algorithm 

We will implement the petersonGraphWalk(S, v) function: 

Step 1: We will take a res variable and initialize it with res:= starting vertex

Step 2: Now for each character c in S except the first one, we will check if there is an edge between v and in the outer graph, if the edge is present then:    

v := c

Step 3: Else if there is an edge present between v and c+5 in the inner graph, then

We will calculate v := c + 5

Step 4: If both conditions are not satisfied, we will return false.

Step 5: Put v into the res variable.

Let us see the implementation of this approach in the next section of this blog.

Implementation in C++

#include <bits/stdc++.h>

using namespace std;
char path[100005]; //path which needs to be checked 
bool adj[10][10]; // adjacency matrix of the path
char res[100005]; // resulted path
bool petersonGraph(char * path, int v) //BFS
{
  res[0] = v + '0';
  for (int i = 1; path[i]; i++) {
    // first traverse the outer graph
    if (adj[v][path[i] - 'A'] || adj[path[i] -
        'A'][v]) {
      v = path[i] - 'A';
    }
    // then traverse the inner graph
    else if (adj[v][path[i] - 'A' + 5] ||
      adj[path[i] - 'A' + 5][v]) {
      v = path[i] - 'A' + 5;
    } else
      return false;

    res[i] = v + '0';
  }
  return true;
}
int main() {
  // representation in adjacency matrix 
    adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] =
    adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] =
    adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] =
    adj[9][6] = adj[6][8] = adj[8][5] = true;
  char path[] = "ABBECCD"; //path which needs to be checked 
  if (petersonGraph(path, path[0] - 'A') ||
    petersonGraph(path, path[0] - 'A' + 5)) {
       cout << res;
  } else {
       cout << "-1";
  }
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The path is: 0169723

Implementation in Java

class Graph {
    static char[] path = new char[100005]; //path which needs to be checked
    static boolean[][] adj = new boolean[10][10]; // adjacency matrix.
    static char[] res = new char[100005]; // resulted path
    static boolean petersonGraph(char[] path, int v) //BFS
    {
        res[0] = (char)(v + '0');
        for (int i = 1; i < (int) path.length; i++) {

            // first traverse the outer graph
            if (adj[v][path[i] - 'A'] ||
                adj[path[i] - 'A'][v]) {
                v = path[i] - 'A';
            }
            // then traverse the inner graph
            else if (adj[v][path[i] - 'A' + 5] ||
                adj[path[i] - 'A' + 5][v]) {
                v = path[i] - 'A' + 5;
            } else
                return false;

            res[i] = (char)(v + '0');
        }
        return true;
    }
    public static void main(String[] args) {
        // representation in adjacency matrix 
        adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] =
            adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] =
            adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] =
            adj[9][6] = adj[6][8] = adj[8][5] = true;

        //path which needs to be checked
        char path[] = "ABBECCD".toCharArray();

        if (petersonGraph(path, path[0] - 'A') ||
            petersonGraph(path, path[0] - 'A' + 5)) {
            System.out.print(res);
        } else {
            System.out.print("-1");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

The path is: 0169723

Implementation in Python

adj = [[False for i in range(10)] for j in range(10)]
result = [0]
# we are applying breadth first search
def findthepath(S, v):
	result[0] = v
	for i in range(1, len(S)):
		if (adj[v][ord(S[i]) - ord('A')] or
			adj[ord(S[i]) - ord('A')][v]):
			v = ord(S[i]) - ord('A')
		else if (adj[v][ord(S[i]) - ord('A') + 5] or
			adj[ord(S[i]) - ord('A') + 5][v]):
			v = ord(S[i]) - ord('A') + 5
		else:
			return False
		result.append(v)
	return True
# adjacency matrix to make connections between the connected nodes
adj[0][1] = adj[1][2] = adj[2][3] = \
adj[3][4] = adj[4][0] = adj[0][5] = \
adj[1][6] = adj[2][7] = adj[3][8] = \
adj[4][9] = adj[5][7] = adj[7][9] = \
adj[9][6] = adj[6][8] = adj[8][5] = True
# path to be checked
S= "ABBECCD"
S=list(S)
print("The path is: ")
if (findthepath(S, ord(S[0]) - ord('A')) or
	findthepath(S, ord(S[0]) - ord('A') + 5)):
	print(*result, sep = "")
else:
	print("-1")

You can also try this code with Online Python Compiler

Run Code

Output

The path is: 0169723

Let us analyze the time and complexity of this approach.

Complexity analysis

Time complexity

This approach will take O(V+E) times where V is vertices and E is the number of edges.  

Frequently Asked Questions

What are graphs?

A graph is a popular data structure made up of a limited number of nodes (also known as vertices) and a limited number of connected edges. An edge is a pair (x,y) that indicates that the x vertex is connected to the y vertex.

What is directed and undirected graphs?

Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.

What are cyclic and acyclic graphs?

If a network has a cycle—a continuous set of nodes without any repeating nodes or edges that connects back to itself—then it is said to be cyclic. Acyclic graphs are those without cycles.

Conclusion

In this blog, we discussed the Peterson graph problem. We understood this problem with the help of an example. Then we discussed its algorithm. After that, we discussed its implementations in other languages like C++ and java. In the end, we saw the complexity analysis of the approach.  

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself.

Recommended Problems:

• Graph Bridge
• Longest Path In Graph
• Graph Valid Tree
  
  Related Articles:
• Detect cycle in an undirected graph
   

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!