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 pastchecked 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! :) 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
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 :)
thanx both of you for your answers :)
i started solving the mst, by using the reversedelete 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 :)
thanx again for your answers :)
streamkid
streamkid wrote:
thanx both of you for your answers :)
i started solving the mst, by using the reversedelete 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 :)
thanx again for your answers :)
streamkid
BTW, Wikipedia is your friend. It even has pseudocode! Imagine that! http://en.wikipedia.org/wiki/ReverseDelete_algorithm
On Feb 24, 1:23 am, Piyo <cybermax...@yahoo.comwrote:
streamkid wrote:
thanx both of you for your answers :)
i started solving the mst, by using the reversedelete 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 :)
thanx again for your answers :)
streamkid
BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!
http://en.wikipedia.org/wiki/ReverseDelete_algorithm
yeah, i know, that's my source. i didn't know about that algorithm
before i read wiki ;)
On Feb 24, 1:23 am, Piyo <cybermax...@yahoo.comwrote:
streamkid wrote:
thanx both of you for your answers :)
i started solving the mst, by using the reversedelete 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 :)
thanx again for your answers :)
streamkid
BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!
http://en.wikipedia.org/wiki/ReverseDelete_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++... This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...

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...

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. ...

by: SeongKook 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...

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...

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:
<script...

by: Harry 
last post by:
Hi all,
1)I need your help to solve a problem.
I have a function whose prototype is
int reclen(char *)
This function has to find the length of the string passed to it.But
the conditions...

by: RandomElle 
last post by:
Hi there
I'm hoping someone can help me out with the use of the Eval function. I am using Access2003 under WinXP Pro. I can successfully use the Eval function and get it to call any function with...

by: skanemupp 
last post by:
the 0.409 vs 0.095 is the total times right?
so the imperative function is >4 times faster than the recursive.
or what does tottime stand for?
is this always the case that the recursive function...

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...

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...

by: erikbower65 
last post by:
Here's a concise stepbystep guide for manually installing IntelliJ IDEA:
1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on...

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...

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...

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
...

by: DJRhino1175 
last post by:
When I run this code I get an error, its Runtime 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...

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...

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...

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=()=>{
 