Geek Answers Handbook

Algorithm used to return a specific range of nodes in a directed graph

I have a Graph class with two types of lists, namely: nodes and edges

I have a function

List<int> GetNodesInRange(Graph graph, int Range)

when I get these parameters, I need an algorithm that will go through the graph and return the list of nodes only as deep (level) as a range. The algorithm should be able to accommodate a large number of nodes and large ranges.

A similar function should be used.

 List<int> GetNodesInRange(Graph graph, int Range, int selected)

I want to be able to look outside of it, to the number of nodes out of range (range).

alt text http://www.freeimagehosting.net/uploads/b110ccba58.png

So, in the first function, I have to pass the nodes and require the say 2 range, I expect the results to return the nodes shown in the blue box.

Another function, if I pass nodes, as in a graph with a range of 1, and starts with node 5, I want it to return a list of nodes that satisfy these criteria (fits in an orange frame)

+7
algorithm graph
source share
3 answers

It should be a recursive function that finds the neighbors of the selected one and then finds the neighbors of each neighbor until the range is 0. DFS is looking for something like this:

 List<int> GetNodesInRange(Graph graph, int Range, int selected){ var result = new List<int>(); result.Add( selected ); if (Range > 0){ foreach ( int neighbour in GetNeighbours( graph, selected ) ){ result.AddRange( GetNodesInRange(graph, Range-1, neighbour) ); } } return result; }

You should also check for cycles if possible. This code is for a tree structure.

0
source share

What you need is just a depth-limited breadth -first search or depth-deep search with the ability to ignore directional direction.

Here's a recursive definition that may help you:

  • I am the only one from range 1 on my own.
  • I know who my closest neighbors are.
  • If N > 1 , then from the range N from me will be
    • Combining everything that has an N-1 range from my neighbors
+2
source share
 // get all the nodes that are within Range distance of the root node of graph Set<int> GetNodesInRange(Graph graph, int Range) { Set<int> out = new Set<int>(); GetNodesInRange(graph.root, int Range, out); return out; } // get all the nodes that are within Range successor distance of node // accepted nodes are placed in out void GetNodesInRange(Node node, int Range, Set<int> out) { boolean alreadyVisited = out.add(node.value); if (alreadyVisited) return; if (Range == 0) return; // for each successor node { GetNodesInRange(successor, Range-1, out); } } // get all the nodes that are within Range distance of selected node in graph Set<int> GetNodesInRange(Graph graph, int Range, int selected) { Set<int> out = new Set<int>(); GetNodesInRange(graph, Range, selected, out); return out; } // get all the nodes that are successors of node and within Range distance // of selected node // accepted nodes are placed in out // returns distance to selected node int GetNodesInRange(Node node, int Range, int selected, Set<int> out) { if (node.value == selected) { GetNodesInRange(node, Range-1, out); return 1; } else { int shortestDistance = Range + 1; // for each successor node { int distance = GetNodesInRange(successor, Range, selected, out); if (distance < shortestDistance) shortestDistance = distance; } if (shortestDistance <= Range) { out.add(node.value); } return shortestDistance + 1; } }

I changed your requirements a bit to return Set , not List .

The GetNodesInRange(Graph, int, int) method will not process graphs containing loops. This can be overcome by maintaining a collection of nodes that have already been visited. The GetNodesInRange(Graph, int) method GetNodesInRange(Graph, int) advantage of the fact that the out set is the set of visited nodes to overcome cycles.

Note. This has not been tested in any way.

0
source share

More articles:


All Articles