• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Return all paths of length <n in graph

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey everyone, I'm having trouble finding all paths of length < n in a graph.
I am working with a small graph at the moment to find out how to do this. Here's a representation of it.

If I take the node Ben as my starting point, I want to return all paths with less than 5 or more nodes.
This gives :
[Ben, Steven, John]
[Ben, Steven, Mary, Jane]
[Ben, Steven, Mary, Paul]
[Ben, Chris]
[Ben, Cian, Una]
[Ben, Cian, Robert]

I don't want the paths :
[Ben, Steven, Mary, Paul, Lisa]
[Ben, Steven, Mary, Paul, Rich]
...because these have 5 or more nodes in them.

I'm a bit lost on how to do this. I've seen things like Dijkstra's Algorithm mentioned alot when I search for help on this, but I don't really understand it for one,
and secondly it appears to find the shortest path from a node to a search point in a weighted graph, which is not quite what I want to do.

Logically, when I think about how I myself would go about doing this, I start at the root node (Ben), and follow any path. I stop when I get to a node with no children, or if n is 5. (John)
I write that down as a path and go to the last visted node where I haven't visited all the children. (Steven) I continue to follow this method for this node. When each child of the root node has been visited, I stop, because all paths have been found.

A problem I'm running into is how to go to the last visted node where I haven't visited all the children. Because my graph is single direction, a node does not know its parent node. I'm thinking perhaps every time I reach a node, I should create a stack of all its children and then pop them off as I visit. This seems like it would work better than my last idea, which was to recursively call

on everything. I managed to iterate through the graph with it, but couldn't get it to return paths successfully.

I've written a lot of text now, so I'll stop here. Hopefully somebody can point me in the right direction with regards to using a stack, how my recursive method should be written etc.
 
Author
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Think about the recursive thing again... then think about the stack thing again... then tell us what's different between doing something recursively and keeping a stack... then tell us what happens when a recursive algorithm reaches one of its terminating conditions.
 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm promoting this to "past beginner" status, off we go to Java in General...
 
reply
    Bookmark Topic Watch Topic
  • New Topic