Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Sample Example
3.
Algorithm 
4.
Implementation in C++
5.
Implementation in Java
6.
Implementation in Python
6.1.
Complexity analysis
7.
Frequently Asked Questions
7.1.
What are graphs?
7.2.
What is directed and undirected graphs?
7.3.
What are cyclic and acyclic graphs?
8.
Conclusion
Last Updated: Mar 27, 2024

Peterson Graph Problem

Author Shivani Singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Here in this blog, we are asked to describe the Peterson graph problem. The Petersen graph is an undirected graph in the study of graph theory that has 10 vertices and 15 edges. It is a short graph that may be used as both a counterexample and an example for a variety of graph theory issues. Julius Petersen built the Petersen graph in 1898 with the goal of making it the smallest bridgeless cubic graph without three-edge coloring. In the Peterson graph problem, graph G known as a Petersen graph is given to us, and its vertices are numbered from 0 to 9. The vertices of G will also receive some letter assignments. Let us understand this with a proper example. 

Peterson graph

Sample Example

 

PETERSON PROBLEM

Consider the graph given above as G. The graph given is the Peterson graph. The vertex numbers range from 1 to 10. Letters will be present on each vertex. Let's take a look at one walk W in the graph with L vertices. When the letter sequences in W and S are the same, the walk W realizes a string S with L letters. The vertices are accessible many times. For instance, the walk method reveals that one string S is similar to "ABBECCD" (0, 1, 6, 9, 7, 2, 3). Finding such a walk is our task, followed by finding the lexicographically least such walk if it already exists. Return -1 if there is no suck walk. 

Suppose if we take S= ”ABB”, then the output will b 016. Because we can clearly see in the graph that the path from ABB is 016.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm 

meme on Peterson graph problem

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;
}

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");
        }
    }
}

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")

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:

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

Happy Learning!

Thankyou
Previous article
Bridges in a Graph
Next article
Smallest Binary Digit Multiple of given Number
Live masterclass