Finding all circles in a graph
I have a directed graph stored in a map data structure where the key is the node id and [value] is the array of node nodes that the node key points to.
Map<String, String[]> map = new HashMap<String, String[]>();
map.put("1", new String[] {"2", "5"});
map.put("2", new String[] {"3"});
map.put("3", new String[] {"4"});
map.put("4", new String[] {"4"});
map.put("5", new String[] {"5", "9"});
map.put("6", new String[] {"5"});
map.put("7", new String[] {"6"});
map.put("8", new String[] {"6"});
map.put("9", new String[] {"10"});
map.put("10", new String[] {"5"});
map.put("11", new String[] {"11"});
I wrote a recursive search algorithm that tries to find a circle in a graph.
Set<String> nodes = map.keySet();
for(String node : nodes) {
List<String> forbiddens = new ArrayList<>(); // This list stores the touched nodes, during the process.
forbiddens.add(node);
recursiveSearch(node, forbiddens);
}
The function is called by the code above.
private void recursiveSearch(String nodeId, List<String> forbiddens) {
String[] neighbours = map.get(nodeId); // The given node neighbours
for(String neighbour : neighbours) {
for(String forbidden : forbiddens) {
if(neighbour.equals(forbidden)) {
ways.add( getClone(forbidden) ); //getClone returns the copy of a given List, "ways" is a List<List<String>> which contains the lists of paths which are leading to a circle in the graph
return;
}
}
forbiddens.add(neighbour);
recursiveSearch(neighbour, forbiddens);
forbiddens.remove(neighbour);
}
}
Some paths contain additional nodes (which are not included in the circle), which I would like to get rid of. I would like to ask for help selecting nodes from lists of "paths" in order to get the actual nodes of the circle.
Can this algorithm find ALL circles in the chart?
source to share
Since a circle in a directed graph is a strongly connected component, you can use any of the algorithms mentioned on the wikipedia page to find strongly connected components https://en.wikipedia.org/wiki/Strongly_connected_component - for example, Tarjan's algorithm based on searching by depth: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
Edit: It is possible that a strongly coupled component contains multiple circles that swap nodes with each other. So, manual checking of each component should be done, but should be easy.
source to share