algorithm to use to return a specific range of nodes in a directed graph

Question

I have a class Graph with two lists types 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 (the level) as the range. The algorithm should be able to accommodate large number of nodes and large ranges.

Atop this, should I use a similar function

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

I want to be able to search outwards from it, to the number of nodes outwards (range) specified.

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

The other function, if I pass the nodes as in the graph with a range of 1 and it starts at node 5, I want it to return the list of nodes that satisfy this criteria (placed in the orange box)

Answer 1

What you need seems to be simply a depth-limited breadth-first search or depth-first search, with an option of ignoring edge directionality.

---

Here's a recursive definition that may help you:

• I'm the only one of range 1 from myself.
• I know who my immediate neighbors are.
• If N > 1, then those of range N from myself are
  • The union of all that is of range N-1 from my neighbors

Answer 2

It should be a recursive function, that finds neighbours of the selected, then finds neighbours of each neighbour until range is 0. DFS search something like that:

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 they are possible. This code is for tree structure.

Answer 3

// 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 modified your requirements somewhat to return a Set rather than a List.

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

Note: This has not been tested in any way.