472,805 Members | 1,528 Online

# recursive calls to function. how should i do it?

hello..
i have the following problem to solve, which is part of mst problem.
i have some nodes (ie cities if you like), and each city is connected
with some other. we don't know which city is connected with what other
city, except for the 1st level (direct connections from city to city).
i want to build the complete map of what is connected to what.

let's say that i have:
city A, connected to: D, F
city B, connected to: A, C,
city C, connected to: D,

starting from city D, i find out that it's connected to C.
C is also connected to B and directly. We set also true that D is
connected to B.
Since B is connected To A, D must know that it's also connected to
whichother cities A is connected with.
And So on..

As you can see, there is a recursive "thing" in this process.
I 'm wondering how to implement it.. I thought of building a function
that would recursively calls its self, and does what i described with
words above.
And for each step deeper it will go, it won't check if the current
node is also connected with past-checked nodes..

I hope you get what i mean.. Can't describe it better :|

If you think that it could be done better/easier with another way,
tell me! :)

Feb 23 '07 #1
6 1721
On Feb 23, 12:58 pm, "streamkid" <stream...@gmail.comwrote:
i have some nodes (ie cities if you like), and each city is connected
with some other. we don't know which city is connected with what other
city, except for the 1st level (direct connections from city to city).
i want to build the complete map of what is connected to what.

let's say that i have:
city A, connected to: D, F
city B, connected to: A, C,
city C, connected to: D,

starting from city D, i find out that it's connected to C.
C is also connected to B and directly. We set also true that D is
connected to B.
Since B is connected To A, D must know that it's also connected to
whichother cities A is connected with.
And So on..

If you think that it could be done better/easier with another way,
tell me! :)
Common ways to solve this are Dijkstra's algorithm, and the Floyd-
Warshall algorithm. Both are covered in Wikipedia.

Michael
Feb 23 '07 #2
streamkid wrote:
If you think that it could be done better/easier with another way,
tell me! :)
BTW, this is not really a C++ question but hey, its an interesting
problem. So here is how I would approach this:
- write a recursive (or not) depth first traversal given a node
and returns all reachable nodes from that node. The signature
might look like:
{set of all reachable nodes from a and including a} dft( node a );

- then I would approach the problem by first initializing all nodes
marked as unreachable. Then pick any unreachable node and call dft
on it.

- this returns a set of nodes that are accesssible to and from each
other. Mark your nodes properly. eg. given {a, b, c} then
a can go to b and c
b can go to a and c
c can go to a and b

- rinse and repeat for the remaining unreachable nodes

Good Luck with your project :)

Feb 23 '07 #3

i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)

streamkid

Feb 23 '07 #4
streamkid wrote:

i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)

streamkid
BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!

http://en.wikipedia.org/wiki/Reverse-Delete_algorithm
Feb 23 '07 #5
On Feb 24, 1:23 am, Piyo <cybermax...@yahoo.comwrote:
streamkid wrote:
i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"
the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)
streamkid

BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!

http://en.wikipedia.org/wiki/Reverse-Delete_algorithm
yeah, i know, that's my source. i didn't know about that algorithm

Feb 24 '07 #6
On Feb 24, 1:23 am, Piyo <cybermax...@yahoo.comwrote:
streamkid wrote:
i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"
the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)
streamkid

BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!

http://en.wikipedia.org/wiki/Reverse-Delete_algorithm
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"
which i pasted before is from wiki, but my problem is to implement 3rd
step (* Check if deleting current edge will further disconnect graph.)
in c++...

Feb 24 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 2 by: | last post by: OK: Purpose: Using user's input and 3 recursive functions, construct an hour glass figure. Main can only have user input, loops and function calls. Recursive function 1 takes input and displays... 7 by: aurora | last post by: I love generator and I use it a lot. Lately I've been writing some recursive generator to traverse tree structures. After taking closer look I have some concern on its performance. Let's take... 4 by: Victor | last post by: Hello, I've got a situation in which the number of (valid) recursive calls I make will cause stack overflow. I can use getrlimit (and setrlimit) to test (and set) my current stack size. ... 5 by: Seong-Kook Shin | last post by: Hi, I'm reading Steve's "C Programming FAQs" in book version, and have two question regarding to Q11.16 ... Also, a `return' from `main' cannot be expected to work if data local to main might be... 11 by: randomtalk | last post by: hi, i have the following recursive function (simplified to demonstrate the problem): >>> def reTest(bool): .... result = .... if not bool: .... reTest(True) .... else: .... print... 9 by: Csaba Gabor | last post by: Inside a function, I'd like to know the call stack. By this I mean that I'd like to know the function that called this one, that one's caller and so on. So I thought to do: 4 times faster than the recursive. or what does tottime stand for? is this always the case that the recursive function... 3 by: from.future.import | last post by: Hi, I encountered garbage collection behaviour that I didn't expect when using a recursive function inside another function: the definition of the inner function seems to contain a circular... 0 by: linyimin | last post by: Spring Startup Analyzer generates an interactive Spring application startup report that lets you understand what contributes to the application startup time and helps to optimize it. Support for... 0 by: erikbower65 | last post by: Here's a concise step-by-step guide for manually installing IntelliJ IDEA: 1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on... 0 by: kcodez | last post by: As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 6 Sept 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 0 by: Taofi | last post by: I try to insert a new record but the error message says the number of query names and destination fields are not the same This are my field names ID, Budgeted, Actual, Status and Differences ... 14 by: DJRhino1175 | last post by: When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this - If... 0 by: Rina0 | last post by: I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in... 5 by: DJRhino | last post by: Private Sub CboDrawingID_BeforeUpdate(Cancel As Integer) If = 310029923 Or 310030138 Or 310030152 Or 310030346 Or 310030348 Or _ 310030356 Or 310030359 Or 310030362 Or... 0 by: lllomh | last post by: Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{