C++

Forum

 
Depth First Search/Breadth First Search - Graph Theory

bgbnbigben (27)
Ok, so here's where I'm at.
Im trying to write a program that will use a DFS algorithm. Minor problem - i cant seem to construct a working one.
I can get as far as the first tree. (I.e untill it gets to the end of the graph) but the algorithm wont backtrack.
Now, technically this isnt homework. Its what i do in my free time. So, bearing that in mind, this is currently the sample data I have.
1
2
3
4
5
6
7
8
9
10
 
9
2 3 3 4 
4 1 5 2 
6 3 7 2 
0 0 0 0 
0 0 0 0
8 1 9 1
0 0 0 0
0 0 0 0
0 0 0 0

where the first line is the number of vertices in the graph, and each other line is in the format a x b y, where a and b are line numbers and x and y is the length from one point to the next (weighted graphs, people)
and again, let me emphasise that this is NOT my homework. I dont even know that they make assigments like this.
(i only added that part because i know someone will say that this is my h/w and they cant help me with it, etc. etc. )
Anyway, this is what ive got so far.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <cstdio> // I USE PRINTF/FPRINTF AND SCANF/FSCANF, NOT SLOW STREAMS
#include <vector>
#include <cstdlib> 
// I THINK I MIGHT NEED TO INCLUDE ALGORITHM SOMEWHERE IN HERE, TOO.
using namespace std;
int main () {
    FILE* in = fopen("sculptin.txt", "r"); //MY INPUT AND OUTPUT FILES
    FILE* out = fopen("sculptout.txt", "w");
    int n; //number of apples.
    fscanf(in,"%d", &n);
    int a, x, b, y;
    int z;
    z = n*4; // n number of vertices, but there are 4 things per line.
    vector<int> applearray(z);
    int f;
    f = 0; 
    for (;f<applearray.size();f = f+4){
    fscanf(in, "%d %d %d %d", &applearray[f], &applearray[f+1], &applearray[f+2], &applearray[f+3]);}   
    int c, d, g;
    int h, t, u; // NOT USED CURRENTLY, I ALREADY KNOW THIS.
    vector<int> treesize(n);
    f = 1; //CURRENTLY ONLY FOR DEBUGGING PURPOSES, THIS WILL BE REPLACED WITH SOMETHING MORE RELAVANT IN THE NEAR FUTURE.
    g = 0; 
    c = 0;
    if (f == 1){ // THIS IF LOOP IS ONLY FOR DEBUG PURPOSES AT THE MOMENT.
         treesize[g] = applearray[f];
         while (applearray[f] != 0){
               c = treesize[g]; // USE BECOMES APPARANT LATER ON.
               f--;
               d = applearray[f]; // THIS IS ONLY USEFULL FOR THE NEXT LINE.
               f = applearray[f]*3 - (4 - d); // THIS IS A WAY OF MOVING FROM ONE LINE TO THE NEXT SPECIFIED LINE - THIS FORMULA WORKS FOR ANY NUMBER AND ANY LINE. BEAR IN MIND THAT THE VECTOR COUNTS FROM 0, NOT 1
               f = g; // I'M USING G SO THAT NEXT TIME THIS LOOP RUNS, IT DOESNT TRACK THE SAME POINT, BUT THATS BECAUSE I DONT KNOW ANYOTHER WAYS TO WRITE DFS ALGORITHMS.
               f++;
               treesize[g] = c + applearray[f];
               printf("%d - size of treesize.", treesize[0]); // GOOD TO GO FOR ONE LINE.
               system("pause"); //ONLY SO I CAN READ THE SIZE OF TREESIZE.
               }
         g++;}         
        
        //now, i know that i currently dont have any output to a file. there is more i need to add, but i first need a bit of advice on a DFS algorithm and its construction.

return 0;    
}


So, i also know what a DFS does. But i dont know how to construct one (entirely).
And there a no good tutorials on the web.
Now, a few digressions before i go on:
1. that code was only included to show what im trying to do. For all you know, this isnt even my code, but i still want to create a DFS on it.
2. THIS ISNT MY HOMEWORK!.
anyway, going on.
Any ideas on how to get the algorithm to backtrack and reach the other tops of the graph, like a DFS should?
Many Thanks,
Ben
Last edited on
Duthomhas (13206)
You've got way too much stuff swimming around there.

First off, you need to back-off from the code a bit first. (Don't feel like I'm talking down to you. This is the very same technique I use both before beginning an algorithm and whenever I get confused writing it. People never believe me that pulling out the construction paper and crayons and drawing stuff makes a difference, but they are always amazed at my results...)

I recommend drawing your graph. You'll notice it is a weighted, directed, acyclic, unconnected graph. (That is, a forest with one-way edges and no loops.)

Next, you might want to take a look at the Wikipedia article:
 
 
http://en.wikipedia.org/wiki/Depth_first_search

(it has both recursive and iterative versions) and review your own texts on graph theory.

When writing your algorithm, start with the basic structure. Decide what data structures best represent each kind of data. For example, a directed tree might best be represented as a list of edges, where an edge is a pair of (source node, target node, length). So far you've got a std::vector or std::list to represent the graph and a struct to represent an edge.

Once you have a solid data structure, make your input file match. Currently, your input file attempts to represent one node per line, with two edges coming from each node. Since you don't actually need to represent individual nodes there actually is no need to worry about line numbers. Just make your input a list of edges:
1
2
3
4
5
6
7
8
9
10
 
9 nodes (starting at 1)
edges as (source, target, length):
1 2 3
1 3 4
2 4 1
2 5 2
3 6 3
3 7 2
6 8 1
6 9 1

This structure makes it very easy to read the list of edges directly in from file. It also removes limitations on the number of edges leaving a given node.

Penultimately, make yourself the necessary functions to manipulate the graph (list of edges) easily: add, find, remove, etc. This uncomplicates the main algorithm, which should be your final effort.


Some comments on your code and commentary:

Your algorithm looks to be an iterative attempt, but you have confused searching for and tracking edges.

Also, watch your indentation. Your outer loop does not appear to be there (to the eye). I know you know it is there, but it will help you to make it obvious what is inside and outside the loop. Also, you need to only document what it is that the code is doing, and what individual variables represent.

For example, your code might have comments along the following lines:
1
2
3
4
5
6
7
8
9
10
 
// 'applearray' represents the data in the nodes of the weighted graph.
// Every four elements are a x b y, where a and b are node numbers and x and y are distances from the indexed node.
// (Remember: node number - 1 = index into vector of node)
vector< int > applearray( n*4 );

// 'f' iterates through all the nodes in the list
// Each iteration we are doing <explain what is happening>
for (int f = 0; f < applearray.size(); f += 4) {
   ...
   }


Lastly, forget about the "standard streams are slow" crap. Whoever told you that doesn't know what he is talking about. There are very few applications where the difference in speed between C and C++ I/O methods is significant. For a program like this, you won't even notice. Using the standard streams makes it easier to code, codes in fewer lines, and improves type safety, error checking, and security.

Hope this helps. Post back once you get further along.
Last edited on
bgbnbigben (27)
Don't feel like I'm talking down to you

No, i wouldnt feel that way. Im quite often told that one, but have never managed to get that specific method to work for me. I usually have to not actually think about the problem for a while and the answer just appears so obvious after that

The commentary wasnt really what i had, i just added it as i added it to this site, so someone else could read it - i generally dont code with that many comments, because they seem to get lost and then i cant find them. That, and i rarely read them anyway.
Yeah, im trying to attempt an iterative attempt of a DFS, however because the edges are already defined in the input file (as x and y) i knew that i could find them at every odd interval in (applearray), i.e 
1
2
 
applearray[1]  // this is an edge
applearray[5] // this is another edge

and shouldnt need to redo the input file. that, and the input file you suggest, although it is good, is just a repackaged version of the current one that ive got, which takes too much effort to redo the input and then the method of input.
that, and im too lazy to recode it anyway :)

Although your advice is great and does actually help me in working out what im trying to achieve, the problem im having is getting the algorithm to backtrack once it reaches the end of part of the graph. I still cant come up with a solution to that.

Ive seen many examples where they change the "colour" of each vertex that has been visited, but im not that adept at programming, so i still dont know how to do that.
I could also manage the vertex to get to the farthest point from node 2 and node 3 (which is great if i only had a 2 tree graph), but it still wont backtrack, and thats the biggest problem that ive got at the moment.

And with the standard streams, they can get slow when you have to input data that ranges up to 25,000 numbers/characters/whatevers, process them with an algorithm and provide output to a file in UNDER 1 second :)
and my compiler doesnt seem to want to accept cout and an ofstream in the same program
i dont know why though, and so it makes using the c++ I/O method too hard to navigate when i also want to debug.

however, ive still made no actual progress on the code itself, so i cant show much for the past few days.
Last edited on
Duthomhas (13206)
OK, now I'm going to talk down just a little (but with no malicious intent):

Only really easy academic stuff for beginners is obvious after sleeping on it. Everything else you have to work for.

First, as for backtracking, I addressed that for you with the reference to Wikipedia and your textbooks. As a further hint, look up "FIFO". You'll need one.

Secondly, I offer advice so that you may improve, not so you can perpetuate being lazy. As an experienced and capable programmer and teacher I can justly boast that I know a little something about programming your brain to work with the computer.

Don't dismiss "repackaging". It makes a tremendous amount of difference.

The "color" of a vertex is just some silly way of visualizing setting a flag somewhere. In other words, each one of your vertices will need a boolean variable in there indicating whether or not it has been touched. That or you will have to keep a separate array of boolean variables --one for each vertex.

Finally, I don't know who is feeding you the anti-STL nonsense, but that's all it is: nonsense. (At least with a proper compiler. What on earth could you be using that won't permit cout and ofstream together? Both are ostreams! Make sure you have a modern compiler: MSVC++, BCB++, GCC, etc.)

The STL is intimidating to a lot of people, especially when they first deal with it, but it has very specific performance characteristics (as part of its specification) and it makes programming I/O much easier and significantly less error-prone. The vast majority of problems assigned to the STL are actually caused by improperly using it (i.e. programmer error).

Most programmer error is caused by sitting down and typing and compiling and retyping (so-called "debugging") and compiling and so on. You can't build a bridge by just showing up with a bunch of materials and jumping into the hammering and sawing. You might be able to cobble together something that looks kind of like a bridge, but it won't ever be right. You have to have a specific plan and a complete understanding of it first.

Alas. I'm not forcing you to change anything. You asked for advice; and this is it: you need to study and get a basic understanding of how the graph traversal algorithms work before you can make the computer do it. There is unfortunately no way around that.
bgbnbigben (27)
Only really easy academic stuff for beginners is obvious after sleeping on it.

i disagree
http://pos-psych.com/news/david-j-pollay/20070502224
Although pulling out the construction paper and crayons may be ONE of the many ways that enhance algorithm design, there is increasing evidence that using the subconscious mind by completely dropping your subject is one of the more efficient ways to go about this.
Finally, I don't know who is feeding you the anti-STL nonsense, but that's all it is: nonsense.

I was using an older version of Borland Turbo, but traded it for Dev C++, which now allows both fstream and iostream.
I ran a little test of my own, too.
Using printf (and this code), i get a time of roughly 2-2.5 minutes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
  FILE* out = fopen("printfout.txt", "w");
  clock_t start;
  double diff;

  start = clock();
  for ( int i = 0; i < 10000000; i++ )
    printf ( "a" );
  diff = ( clock() - start ) / (double)CLOCKS_PER_SEC;

  fprintf(out, "printf: %.12lf", diff);
  fclose(out);
  return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
int main()
{
  ofstream out("cout.txt");
  clock_t start;
  double diff;
  
  cout.sync_with_stdio ( false );

  start = clock();
  for ( int i = 0; i < 10000000; i++ )
    cout<<"a";
  diff = ( clock() - start ) / (double)CLOCKS_PER_SEC;

  out<<"cout:   "<< diff <<'\n';
  return 0;
}

on the other hand, this gets about 11 seconds.
Bearing in mind that this is a 10 million sequence of a's (which can really be changed to whatever you want), i think you're right about the STL
my bad......

As for the DFS, ive decided to go with a BFS. although its not optimal for what im trying to achieve, at the moment, it will have to do.
Plus, its something that i can actually code.

First, as for backtracking, I addressed that for you with the reference to Wikipedia and your textbooks.


Well, wikipedia was my textbook. as well as some of the bibliography references and a little help from google. Im not doing this as part of a school/uni course. Its my own "free-time killer". Although i try to take it much more seriously than that, but because its not a subject that im taught from a textbook, i dont have a textbook. My knowledge is scavenged from free sites on the web, plus that of a few friends. which i probably should cut back on, since one of them was adamant that fprintf/printf was faster than an iostream

I know/knew how graph traversal algorithms work. However, i'm primarily a mathematician, and not a programmer. So i could know how to solve P vs NP, but still not know how to tell the computer to do the same thing
Thats the advantage to me of using the BFS. Using any input file, either with your or my way, i can quite easily get it to track the verticies just with a simple for loop

And i finally realised what you mean about confusing tracking and finding vertices. That also helps a tremendous amount in creating both the DFS and the BFS.

Finally,
You can't build a bridge by just showing up with a bunch of materials and jumping into the hammering and sawing.

nope, you most certainly can
no more than 25 bamboo skewers and a bit of PVA glue, and my systems tech assignment scored me about 45 kilos of weight. Not bad, really ;)

Thanks for all the help,
Ben
Last edited on
awhite1159 (17)
Interesting discussion. Perhaps I initiated this with my previous post on an undirected acyclic graph algorithm? Let me start off by saying I am not a student but instead some nutcase who does this for fun. I can try to describe how it works in plain language but maybe a portion of the code will explain itself. The output below is from an undirected acyclic graph of 9 vertices. I first link the nine vertices with edges all in a row like a bi-directional list. I then connect the 9th to the 7th, and the 9th to the 4th. I can post the code separately if anyone is interested in seeing it.

(IP addresses are used so I can take real world data from a Tivoli Storage Manager Server.)

Network Backup Simulator (BkupSim) (c) 2008 AW Systems Inc. (Just kidding.)

<3> linked to <2>
<4> linked to <3>
<5> linked to <4>
<6> linked to <5>
<7> linked to <6>
<8> linked to <7>
<9> linked to <8>
Less costly route for <9>-Edge to <2> found and substituted.
Less costly route for <9>-Edge to <3> found and substituted.
Less costly route for <9>-Edge to <4> found and substituted.
Less costly route for <9>-Edge to <5> found and substituted.
Less costly route for <9>-Edge to <6> found and substituted.
Less costly route for <9>-Edge to <7> found and substituted.
Less costly route for <2>-Edge to <9> found and substituted.
Less costly route for <3>-Edge to <9> found and substituted.
Less costly route for <4>-Edge to <9> found and substituted.
Less costly route for <5>-Edge to <9> found and substituted.
Less costly route for <6>-Edge to <9> found and substituted.
Less costly route for <7>-Edge to <9> found and substituted.
<9> linked to <7>
Less costly route for <8>-Edge to <2> found and substituted.
Less costly route for <7>-Edge to <2> found and substituted.
Less costly route for <8>-Edge to <2> found and substituted.
Less costly route for <9>-Edge to <2> found and substituted.
Less costly route for <8>-Edge to <3> found and substituted.
Less costly route for <7>-Edge to <3> found and substituted.
Less costly route for <8>-Edge to <3> found and substituted.
Less costly route for <9>-Edge to <3> found and substituted.
Less costly route for <9>-Edge to <5> found and substituted.
Less costly route for <2>-Edge to <7> found and substituted.
Less costly route for <3>-Edge to <7> found and substituted.
Less costly route for <4>-Edge to <7> found and substituted.
Less costly route for <2>-Edge to <8> found and substituted.
Less costly route for <3>-Edge to <8> found and substituted.
Less costly route for <4>-Edge to <8> found and substituted.
Less costly route for <8>-Edge to <4> found and substituted.
Less costly route for <7>-Edge to <4> found and substituted.
Less costly route for <8>-Edge to <4> found and substituted.
Less costly route for <9>-Edge to <4> found and substituted.
Less costly route for <2>-Edge to <9> found and substituted.
Less costly route for <3>-Edge to <9> found and substituted.
Less costly route for <5>-Edge to <9> found and substituted.
Less costly route for <4>-Edge to <9> found and substituted.
<9> linked to <4>
Name......:<2>-Edge
Type......:ROUTER
Node ID...:2
Thruput...:16000000
IP/NM/NET.:192.168.002.000| 192.168.002.000| 192.168.002.000 Locked:0
Routes===========================================================================>
192.168.3.0 via <3> (Hop/Cost=>1)
192.168.4.0 via <3> (Hop/Cost=>2)
192.168.5.0 via <3> (Hop/Cost=>3)
192.168.6.0 via <3> (Hop/Cost=>4)
192.168.7.0 via <3> (Hop/Cost=>4)
192.168.8.0 via <3> (Hop/Cost=>4)
192.168.9.0 via <3> (Hop/Cost=>3)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<3>-Edge
Type......:ROUTER
Node ID...:4
Thruput...:16000000
IP/NM/NET.:192.168.003.000| 192.168.003.000| 192.168.003.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <2> (Hop/Cost=>1)
192.168.4.0 via <4> (Hop/Cost=>1)
192.168.5.0 via <4> (Hop/Cost=>2)
192.168.6.0 via <4> (Hop/Cost=>3)
192.168.7.0 via <4> (Hop/Cost=>3)
192.168.8.0 via <4> (Hop/Cost=>3)
192.168.9.0 via <4> (Hop/Cost=>2)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<4>-Edge
Type......:ROUTER
Node ID...:6
Thruput...:16000000
IP/NM/NET.:192.168.004.000| 192.168.004.000| 192.168.004.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <3> (Hop/Cost=>2)
192.168.3.0 via <3> (Hop/Cost=>1)
192.168.5.0 via <5> (Hop/Cost=>1)
192.168.6.0 via <5> (Hop/Cost=>2)
192.168.7.0 via <9> (Hop/Cost=>2)
192.168.8.0 via <9> (Hop/Cost=>2)
192.168.9.0 via <9> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<5>-Edge
Type......:ROUTER
Node ID...:8
Thruput...:16000000
IP/NM/NET.:192.168.005.000| 192.168.005.000| 192.168.005.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <4> (Hop/Cost=>3)
192.168.3.0 via <4> (Hop/Cost=>2)
192.168.4.0 via <4> (Hop/Cost=>1)
192.168.6.0 via <6> (Hop/Cost=>1)
192.168.7.0 via <6> (Hop/Cost=>2)
192.168.8.0 via <6> (Hop/Cost=>3)
192.168.9.0 via <4> (Hop/Cost=>2)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<6>-Edge
Type......:ROUTER
Node ID...:10
Thruput...:16000000
IP/NM/NET.:192.168.006.000| 192.168.006.000| 192.168.006.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <5> (Hop/Cost=>4)
192.168.3.0 via <5> (Hop/Cost=>3)
192.168.4.0 via <5> (Hop/Cost=>2)
192.168.5.0 via <5> (Hop/Cost=>1)
192.168.7.0 via <7> (Hop/Cost=>1)
192.168.8.0 via <7> (Hop/Cost=>2)
192.168.9.0 via <7> (Hop/Cost=>2)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<7>-Edge
Type......:ROUTER
Node ID...:12
Thruput...:16000000
IP/NM/NET.:192.168.007.000| 192.168.007.000| 192.168.007.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <9> (Hop/Cost=>4)
192.168.3.0 via <9> (Hop/Cost=>3)
192.168.4.0 via <9> (Hop/Cost=>2)
192.168.5.0 via <6> (Hop/Cost=>2)
192.168.6.0 via <6> (Hop/Cost=>1)
192.168.8.0 via <8> (Hop/Cost=>1)
192.168.9.0 via <9> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<8>-Edge
Type......:ROUTER
Node ID...:14
Thruput...:16000000
IP/NM/NET.:192.168.008.000| 192.168.008.000| 192.168.008.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <9> (Hop/Cost=>4)
192.168.3.0 via <9> (Hop/Cost=>3)
192.168.4.0 via <9> (Hop/Cost=>2)
192.168.5.0 via <7> (Hop/Cost=>3)
192.168.6.0 via <7> (Hop/Cost=>2)
192.168.7.0 via <7> (Hop/Cost=>1)
192.168.9.0 via <9> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<9>-Edge
Type......:ROUTER
Node ID...:16
Thruput...:16000000
IP/NM/NET.:192.168.009.000| 192.168.009.000| 192.168.009.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <4> (Hop/Cost=>3)
192.168.3.0 via <4> (Hop/Cost=>2)
192.168.4.0 via <4> (Hop/Cost=>1)
192.168.5.0 via <4> (Hop/Cost=>2)
192.168.6.0 via <7> (Hop/Cost=>2)
192.168.7.0 via <7> (Hop/Cost=>1)
192.168.8.0 via <8> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1



awhite1159 (17)
A portion of the code that builds the undirected acyclic graph:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
// Exchange routes, build return routes, and then link. This code prevents cycles,
// evaluates costs, recursively conducts depth first search via propagateRetRoute()
// Prior to linking, the two vertices being linked are assumed to have predecessors
// and are treated like separate networks.
void NetSuper::linkNetworks(const string& src, const string& dst) { 
	Net net_src(src);
	Net net_dst(dst);
	h_DM& src_h = *(findNetwork(net_src));
	h_DM& dst_h = *(findNetwork(net_dst));
	map<Net, int>::iterator cost;

// Exchange routes making h_DM the link partner. Existing cost of partner must be added
	setCost(0);
	map<Net, h_DM>::iterator dst_edges = dst_h->getOut()->node_list_begin();
	while(dst_edges != dst_h->getOut()->node_list_end()) {
		setCost(dst_h->getOut()->findCost(dst_edges->first));
		NetSuper::propagateRetRoute(dst_edges->first, dst_h, src_h);
		++dst_edges;
	}
	setCost(0);
	map<Net, h_DM>::iterator src_edges = src_h->getOut()->node_list_begin();
	while(src_edges != src_h->getOut()->node_list_end()) {
		setCost(src_h->getOut()->findCost(src_edges->first));
		NetSuper::propagateRetRoute(src_edges->first, src_h, dst_h);
		++src_edges;
	}
	
// Must also add my new neighbor
	setCost(0);
	NetSuper::propagateRetRoute(net_dst, dst_h, src_h);
// Also add myself to my new neighbor
	setCost(0);
	NetSuper::propagateRetRoute(net_src, src_h, dst_h);
	std::cout << src_h->getName() << " linked to " << dst_h->getName() << std::endl;
}


void NetSuper::propagateRetRoute(const Net& net, const h_DM& prev_h,
	const h_DM& current_h) {
	// No need for route to self
	if(net.compare_net(current_h->getNet()))
		return;
	// Cycle protection to prevent recursive calls from backtracking
	if(current_h->getNet().locked())
		return;
	current_h->getNet().lock();
	incCost();
	map<Net, h_DM>::iterator current_edges = current_h->getOut()->node_list_begin();
	while(current_edges != current_h->getOut()->node_list_end()) {
		NetSuper::propagateRetRoute(net, current_h, current_edges->second);
		++current_edges;
	}
	current_h->getOut()->addNode(net, prev_h, getCost());
	current_h->getNet().unlock();
	decCost();
}	

// Add route with its cost to the route list. The map does not allow duplicates so this
// condition forces a check against the cost of the alternate route and if is less costly, 
// it replaces the existing route.
void BkupRouter::addNode(const Net& n, const h_DM& h, int cost) { 
	Net tmp(n);
	pair<map<Net, h_DM>::iterator, bool> r;
	r = route_list.insert(pair<const Net, h_DM>(n, h));
	route_cost.insert(pair<const Net, int>(n, cost));
	if(r.second == false) {
		// Route already exists. If this new route has less cost, replace.
		int oldcost = findCost(n);
		if(cost < oldcost) {
			vector<h_DM>::iterator dst_h = NetSuper::findNetwork(n);
			std::cout << "Less costly route for " << getName() << " to " << (*dst_h)->getName() <<
			" found and substituted." << std::endl;
			map<Net, h_DM>::iterator oldroute_iter = findNode(n);
			map<Net, int>::iterator oldcost_iter = route_cost.find(n);
			route_list.erase(oldroute_iter);
			route_cost.erase(oldcost_iter);
			route_list.insert(pair<const Net, h_DM>(n, h));
			route_cost.insert(pair<const Net, int>(n, cost));
		}
	}
}


bgbnbigben (27)
Interesting discussion. Perhaps I initiated this with my previous post on an undirected acyclic graph algorithm?

nope. It was actually started due to a problem i had coding an informatics solution. Funny, i too am one of those nutjobs.
The problem with your solution, still being a solution, is that its too costly to run as an informatics solution. i was trying to create a simple iterated version of a DFS algorithm, but still couldnt figure out how to backtrack it. Well, i lie. I couldnt ENTIRELY figure out how to back track it. i could go about 2 steps back, but thats still as good as useless.
instead, i just used a BFS, which is easy to get to go anywhere, because its made quite simply when iterated. Duoas was right, its weighted and directed, which makes using a BFS quite simple.
Although far from optimal for what im trying to do.
awhite1159 (17)
Glad to hear you made progress. If you don't mind me asking, what is an informatics solution?
Duthomhas (13206)
Its a software program that analyzes the behavior of a system, and models suggested changes to that system. Basically, it is a management tool.

A simple example would be to study how a city's semaphores affect traffic, and adjust specific areas to have specific characteristics. You want a high-speed route to be timed so that drivers rarely have to stop at the lights. But in an urban environment you may want to stop drivers very often to keep their speed down. Etc.
Last edited on
bgbnbigben (27)
yeah, something like that. Basically, you're given a set of data, and told what it should do with it. a very, very basic example is to get input from a file and add one to it, then output the answer. hmm, when i put it that way, all of these problems sound so simple.
Hence another reason why i couldnt change the input file - it was given in the form a x b y, so i couldnt repackage it. i could have got the program to do that for me, but that starts to get too costly in runtime and stack memory (because they are both also limited).
Topic archived. No new replies allowed.