Open In App

A Peterson Graph Problem

The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:

Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters ‘A’ – ‘E’ is realized by walking W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.

For example, S = ‘ABBECCD’ is realized by W = (0, 1, 6, 9, 7, 2, 3). Determine whether there is a walk W that realizes a given string S in graph G and if so then find the lexicographically least such walk. The only line of input contains one string S. If there is no walk W which realizes S, then output -1 otherwise, you should output the least lexicographical walk W which realizes S.

Example of a Petersen Graph

Examples:

```Input : s = 'ABB'
Output: 016
Explanation: As we can see in the graph
the path from ABB is 016.
Input : s = 'AABE'
Output :-1
Explanation: As there is no path that
exists, hence output is -1.```

Algorithm for a Peterson Graph Problem:

petersonGraphWalk(S, v):

begin
res := starting vertex
for each character c in S except the first one, do
if there is an edge between v and c in outer graph, then
v := c
else if there is an edge between v and c+5 in inner graph, then
v := c + 5
else
return false
end if
put v into res
done
return true
end

Below is the implementation of the above algorithm:

C++

 `// C++ program to find the``// path in Peterson graph``#include ``using` `namespace` `std;` `// path to be checked``char` `S[100005];` `// adjacency matrix.``bool` `adj[10][10];` `// resulted path - way``char` `result[100005];` `// we are applying breadth first search``// here``bool` `findthepath(``char``* S, ``int` `v)``{``    ``result[0] = v + ``'0'``;``    ``for` `(``int` `i = 1; S[i]; i++) {``        ` `        ``// first traverse the outer graph``        ``if` `(adj[v][S[i] - ``'A'``] || adj[S[i] -``                              ``'A'``][v]) {``            ``v = S[i] - ``'A'``;``        ``}` `        ``// then traverse the inner graph``        ``else` `if` `(adj[v][S[i] - ``'A'` `+ 5] ||``                 ``adj[S[i] - ``'A'` `+ 5][v]) {``            ``v = S[i] - ``'A'` `+ 5;``        ``}` `        ``// if the condition failed to satisfy``        ``// return false``        ``else``            ``return` `false``;` `        ``result[i] = v + ``'0'``;``    ``}` `    ``return` `true``;``}` `// driver code``int` `main()``{``    ``// here we have used 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``    ``char` `S[] = ``"ABB"``;``    ` `    ``if` `(findthepath(S, S[0] - ``'A'``) ||``        ``findthepath(S, S[0] - ``'A'` `+ 5)) {``        ``cout << result;``    ``} ``else` `{``        ``cout << ``"-1"``;``    ``}``    ``return` `0;``}`

Java

 `// Java program to find the``// path in Peterson graph``class` `GFG``{` `    ``// path to be checked``    ``static` `char` `[]S = ``new` `char``[``100005``];` `    ``// adjacency matrix.``    ``static` `boolean` `[][]adj = ``new` `boolean``[``10``][``10``];``    ` `    ``// resulted path - way``    ``static` `char``[] result = ``new` `char``[``100005``];``    ` `    ``// we are applying breadth first search``    ``// here``    ``static` `boolean` `findthepath(``char``[] S, ``int` `v)``    ``{``        ``result[``0``] = (``char``) (v + ``'0'``);``        ``for` `(``int` `i = ``1``; i<(``int``)S.length; i++)``        ``{``            ` `            ``// first traverse the outer graph``            ``if` `(adj[v][S[i] - ``'A'``] ||``                ``adj[S[i] - ``'A'``][v])``            ``{``                ``v = S[i] - ``'A'``;``            ``}``    ` `            ``// then traverse the inner graph``            ``else` `if` `(adj[v][S[i] - ``'A'` `+ ``5``] ||``                    ``adj[S[i] - ``'A'` `+ ``5``][v])``            ``{``                ``v = S[i] - ``'A'` `+ ``5``;``            ``}``    ` `            ``// if the condition failed to satisfy``            ``// return false``            ``else``                ``return` `false``;``    ` `            ``result[i] = (``char``) (v + ``'0'``);``        ``}``        ``return` `true``;``    ``}``    ` `    ``// Driver code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``// here we have used 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``        ``char` `S[] = ``"ABB"``.toCharArray();``        ` `        ``if` `(findthepath(S, S[``0``] - ``'A'``) ||``            ``findthepath(S, S[``0``] - ``'A'` `+ ``5``))``        ``{``            ``System.out.print(result);``        ``}``        ``else``        ``{``            ``System.out.print(``"-1"``);``        ``}``    ``}``}` `// This code is contributed by Rajput-Ji`

Python3

 `# Python3 program to find the``# path in Peterson graph``# path to be checked` `# adjacency matrix.``adj ``=` `[[``False` `for` `i ``in` `range``(``10``)] ``for` `j ``in` `range``(``10``)]` `# resulted path - way``result ``=` `[``0``]` `# we are applying breadth first search``# here``def` `findthepath(S, v):``    ``result[``0``] ``=` `v``    ``for` `i ``in` `range``(``1``, ``len``(S)):``        ` `        ``# first traverse the outer graph``        ``if` `(adj[v][``ord``(S[i]) ``-` `ord``(``'A'``)] ``or``            ``adj[``ord``(S[i]) ``-` `ord``(``'A'``)][v]):``            ``v ``=` `ord``(S[i]) ``-` `ord``(``'A'``)``            ` `        ``# then traverse the inner graph``        ``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``        ` `        ``# if the condition failed to satisfy``        ``# return false``        ``else``:``            ``return` `False``        ` `        ``result.append(v)``        ` `    ``return` `True` `# driver code``# here we have used 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``=` `"ABB"``S``=``list``(S)``if` `(findthepath(S, ``ord``(S[``0``]) ``-` `ord``(``'A'``)) ``or``    ``findthepath(S, ``ord``(S[``0``]) ``-` `ord``(``'A'``) ``+` `5``)):``    ``print``(``*``result, sep ``=` `"")``else``:``    ``print``(``"-1"``)``    ` `# This code is contributed by SHUBHAMSINGH10`

C#

 `// C# program to find the``// path in Peterson graph``using` `System;``public` `class` `GFG``{` `  ``// adjacency matrix.``  ``static` `bool` `[,]adj = ``new` `bool``[10, 10];` `  ``// resulted path - way``  ``static` `char``[] result = ``new` `char``[100005];` `  ``// we are applying breadth first search``  ``// here``  ``static` `bool` `findthepath(String S, ``int` `v)``  ``{``    ``result[0] = (``char``) (v + ``'0'``);``    ``for` `(``int` `i = 1; i < S.Length; i++)``    ``{` `      ``// first traverse the outer graph``      ``if` `(adj[v,S[i] - ``'A'``] ||``          ``adj[S[i] - ``'A'``,v])``      ``{``        ``v = S[i] - ``'A'``;``      ``}` `      ``// then traverse the inner graph``      ``else` `if` `(adj[v,S[i] - ``'A'` `+ 5] ||``               ``adj[S[i] - ``'A'` `+ 5,v])``      ``{``        ``v = S[i] - ``'A'` `+ 5;``      ``}` `      ``// if the condition failed to satisfy``      ``// return false``      ``else``        ``return` `false``;` `      ``result[i] = (``char``) (v + ``'0'``);``    ``}``    ``return` `true``;``  ``}` `  ``// Driver code``  ``public` `static` `void` `Main(String[] args)``  ``{` `    ``// here we have used 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``    ``String S = ``"ABB"``;``    ``if` `(findthepath(S, S[0] - ``'A'``) ||  findthepath(S, S[0] - ``'A'` `+ 5))``    ``{``      ``Console.WriteLine(result);``    ``}``    ``else``    ``{``      ``Console.Write(``"-1"``);``    ``}``  ``}``}` `// This code is contributed by aashish1995`

Javascript

 ``

Output

`016`

Time complexity: O(N)

The time complexity of the above program is O(N), where N is the length of the given string S. We are applying Breadth First Search here, which runs in linear time.

Space complexity: O(N)

The space complexity of the above program is O(N), where N is the length of the given string S. We are using two auxiliary arrays – result[] and S[] to store the path and the given string, respectively. Both of them require linear space.

This article is contributed by Sunidhi Chaudhary. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}