CODEWITHSUNDEEP
javaparsinggraph
Sweaver
Sweaver

Reputation: 63

Parsing an Input Regarding a Directed Graph

I am working on a problem where I have run into a slight delay. I am working with directed graphs and trying to determine if within a certain input, if the route to get there exists. Now my issue is that I have to enter the input in one string, but it has to be parsed the way it is to pull out important information. For example:

you have a problem instance of where G is a directed graph with a path from s to t (nodes)

And my input string would be: (1,2,3,4,5),((1,2),(1,3),(2,3),(2,4),(3,2),(3,5),(4,3),(5,2)),1,5

The first set of parentheses represents the nodes, the second set represents the make up of the graph and routes, where as the number 1 would represent s and 5 would represent t (last two numbers at the end).

I have to implement a program to determine whether or not the path exists. The problem lies with the parsing though. I need to extract the list of nodes (first parentheses), list of edges (second set), the starting node(1) and ending node(5).

Can anyone offer me some insight on how to parse these and break them up in such a way where I can extract and print out these? I am not looking for a full out written working program by any means, just clarification and maybe code snippets to point me in the right direction. Any help would be greatly appreciated.

Upvotes: 1

Views: 998

Answers (1)

Xline
Xline

Reputation: 812

If we assume the input would strictly follow the format you provided, then this is simply a parsing problem. Here is how you get the three big blocks (vertices, edges and st). 

 String input=" (1,2,3,4,5),((1,2),(1,3),(2,3),(2,4),(3,2),(3,5),(4,3),(5,2)),1,5";

String nodes=input.substring(0, input.indexOf("((")-1).trim();
String edges=input.substring(input.indexOf("((")+1, input.indexOf("))")+1).trim();
String st=input.substring(input.indexOf("))")+3).trim();

You can then parse every block alone and get its values. One thing: the list of edges is enough for defining the graph (you really do not need the first block).

EDIT: You can simply initialize a boolean array visited[] with size equal to the number of vertices. Initially, all vertices are not visited.

Upvotes: 1

Related Questions