how to commute values of vectors

cpit · #1 22-Jun-2006, 03:48

Hi friends, I need help to this problem

I have an array of vectors<int>

path[0]={}
path[1]={}
path[2]={}
path[3]={1,2}
path[4]={1,2}
path[5]={3,4}

The path[?] represent a node in a graph and the {?,?} represents a direct path to path[?].

I need to print all possible paths.

5 <- 3 <- 1 <- 0
5 <- 3 <- 2 <- 0
5 <- 4 <- 1 <- 0
5 <- 4 <- 2 <- 0

The follow code was I have did.

CPP / C++ / C Code:

caminho=5;

while (path[caminho].size()!=0){

        cout << path[caminho][0]; <-- I need to iterate this.
        caminho=path[caminho][0]; <--

        if(path[caminho].size()!=0){
          cout << " <- " ;
        }else {
            cout << " <- " << s <<endl; //to print the source node
            }

}

regards,

CPIT

davekw7x · #2 22-Jun-2006, 08:41

Quote:

Originally Posted by cpit

I need to print all possible paths.

5 <- 3 <- 1 <- 0
5 <- 3 <- 2 <- 0
5 <- 4 <- 1 <- 0
5 <- 4 <- 2 <- 0

I'll print them first-to-last. You can do it the other-way-first or whatever:

CPP / C++ / C Code:

#include <iostream>
#include <vector>

typedef std::vector<int> vInt;

using namespace std;

int main()
{

    void printIVec(vInt v);

    const int numPaths = 6;
    vInt paths[numPaths]; // an array of six paths, all empty

    paths[1].push_back(0);
    paths[2].push_back(1);
    paths[2].push_back(2);
    paths[3].push_back(3);
    paths[3].push_back(4);
    paths[4].push_back(5);
    paths[4].push_back(6);
    paths[4].push_back(7);

    for (int i = 0; i < numPaths; i++) {
        cout << "Path " << i << ": <";
        printIVec(paths[i]);
        cout << ">" << endl;
    }

    return 0;
}

void printIVec(vInt v)
{

    for (unsigned i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i < v.size() - 1) {
            cout << " -> ";
        }
    }
}

Output

Code:

Path 0: <>
Path 1: <0>
Path 2: <1 -> 2>
Path 3: <3 -> 4>
Path 4: <5 -> 6 -> 7>
Path 5: <>

For debug purposes I put angle brackets arount them <> and put the print routine itself in a function.

Regards,

Dave

cpit · #3 22-Jun-2006, 09:29

Thank you for your attention friend,

but I need other output...

Suppose I have this graph, where 1 there is a direct link.

Adjacence matrix
0 1 1 0 0 0
1 0 1 1 1 0
1 1 0 1 1 0
0 1 1 0 1 1
0 1 1 1 0 1
0 0 0 1 1 0

After I perform an algorithm to find out the shortest paths (all edges have weight=1), I have obtained this

CPP / C++ / C Code:

    path[3].push_back(1);
    path[3].push_back(2);
    path[4].push_back(1);
    path[4].push_back(2);
    path[5].push_back(3);
    path[5].push_back(4);

Or be, if we see the first element of path[5], it is pointing to node 3, then, we need to jump to position
path[3], the first element of path[3] is 1, then, we need to jump to position 1, then, as the position path[1]
is blank, it means that we arrived on the last node of the path. (5-3-1)

After, we need to see the second element of path[5], it is pointing to node 4, then we need to jump to position
path[4] and so on...

And commuting all possibilities, the output I need is

5 <- 3 <- 1 <- 0
5 <- 3 <- 2 <- 0
5 <- 4 <- 1 <- 0
5 <- 4 <- 2 <- 0

or

0 -> 1 -> 3 -> 5
...

I try a little change in the code, but I only obtain 2 paths...

CPP / C++ / C Code:


caminho=5;
t=5;

for(int i=0;i<path[t].size();i++){
 while (path[caminho].size()!=0){

        cout << path[caminho][i]; 
        caminho=path[caminho][i];

        if(path[caminho].size()!=0){
          cout << " <- " ;
        }else {
            cout << " <- " << s <<endl;
            }

 }
 caminho=t;
 cout << t << " <- "; 
}

davekw7x · #4 22-Jun-2006, 10:10

Quote:

Originally Posted by cpit

I have obtained this

CPP / C++ / C Code:

    path[3].push_back(1);
    path[3].push_back(2);
    path[4].push_back(1);
    path[4].push_back(2);
    path[5].push_back(3);
    path[5].push_back(4);

When I put this into my test program (changing my array name to path), I get this:

Code:

Path 0: <>
Path 1: <>
Path 2: <>
Path 3: <1 -> 2>
Path 4: <1 -> 2>
Path 5: <3 -> 4>

What do you get? (The purpose of my example was to illustrate a way of printing out a vector, which was, I thought, the point of your original question, although I now see that the topic is about commuting vectors, not printing vectors.) If it worked for you, then you have a tool to put into your program to show vectors at whatever stage of program execution that you might want to use it.

Now if this is what the paths are supposed to be, (that is, is what you had in mind when you designed the program), you have to figure out how to use tha value of any element of a vector to select another vector (using the overloaded [] operator for the std::vector class is a good way, I'm thinking).

Then all your program has to do is follow the links.

I perceive that the hard part (so far) was converting the adjacency matrix to path vectors and finding shortest paths.

Now that you have the shortest paths (and they are what you expected them to be) you have to "commute all possibilities" (whatever that means --- and I really don't know). How do you do that?

Now, instead of just firing back a post with a detailed explanation of "commute the possibilities", I'm thinking along the following lines:

Given the correct paths, my suggestion would be: Back away from the keyboard; sit down with pencil and paper (yes --- pencil and paper); and perform the steps required to get the expected output for these specific vectors. Then see if those steps make any sense in the context of a general program (write down ---yes write down--- the pseudo code).

If you understand "commuting all possibilities", then the little exercise that I just recommended might help you get to a point where you can use it in a project. If you are a little fuzzy on the details, then working with a specific example: your example, for which you know the right answer, can, maybe, help you nail it.

If you need help with some non-program-related characteristics, then maybe someone who understands the principles will jump right in and give us all a lesson (I wasn't kidding when I indicated that I don't know what that term implies in this context).

If you get stuck, you can always ask, but I'm thinking you have done a lot of work up to this point, and you may be able to punch through to the finish.

Regards,

Dave

cpit · #5 23-Jun-2006, 08:27

Thank you friend, I already spent a lot of time with a paper and a pencil, but my mind is betraying me!!!

I we want to obtain the path between source=0 and target=5, (which are the intermediate nodes?)

CPP / C++ / C Code:

    path[4].push_back(1);
    path[5].push_back(4); // path[node].push_back(next node on the path)

Then, doing backtracking we have:

1) take the value of path[target][0] - for our case is "4"
It means that the next hop for our path is the node 4.
then, now we need to jump the target to node 4 "target=path[target][0]"

2) take the value of path[target][0] - now, for our case is "1"
It means that the next hop for our path is the node 1.
then, now we need to jump the target to node 1 "target=path[target][0]"

3) take the value of path[target][0] - now, for our case is "{}"
It means that the path is complete.

Then, the intermediate nodes are 4 and 1, but if we print target + intermediates + source
we obtain a complete path (5<-4<-1<-0).

When we have only one element in each patch[target], we can easily to obtain this with:

CPP / C++ / C Code:

 int caminho = target;

    cout << target << " <- ";

    while (caminho != s)
    {
        cout << path[caminho]);
        caminho = path[caminho];

        if (caminho != s)
            cout << " <- ";
    }

But I am really with difficulties to extract the paths when there are several elements on path.

Having this:

CPP / C++ / C Code:

    path[3].push_back(1);
    path[3].push_back(2);
    path[4].push_back(1);
    path[4].push_back(2);
    path[5].push_back(3);
    path[5].push_back(4);

the output of intermediates should be. (with target=5 and source=0)

3 <- 1
3 <- 2
4 <- 1
4 <- 2

The first element of path[5] is 3 ( path[5].push_back(3)), then,the node 3 is the next hop and we need to jump to path[3],
which first element is 1 (path[3].push_back(1)) , jumping to path[1], the path[1].size()==0, then, we dont need to
continue, because the intermediates nodes (for the first path) are find.

But, in this case, there are 4 paths, then, the program needs "to combine" the intermediate nodes.

first element of path[5] + first element of path[3]
first element of path[5] + second element of path[3]

second element of path[5] + first element of path[4]
second element of path[5] + second element of path[4]

note that we may have a variable number of intermediate nodes!

My program bellow only print 3 <- 1 and 4<-2!!!

CPP / C++ / C Code:

int caminho = target;

cout << target << " <- "; //imprime o destino



for(int i=0;i<path[target].size();i++){
 while (path[caminho].size()!=0){  //intermediary nodes !!!

        cout << path[caminho][i]; 
        caminho=path[caminho][i];

        if(path[caminho].size()!=0){
          cout << " <- " ;
        }else {
            cout << " <- " << s <<endl; // only to print the source node
            }

 }
 caminho=target;
 cout << target << " <- "; // to print a target node.
}

regards,

CPIT

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Grabbing radiobutton values in a session variable	Saru	.NET Forum	1	16-Feb-2006 11:51
C programming not giving correct values	fadedg2	C Programming Language	5	12-Sep-2005 07:45
store values	skyloon	MySQL / PHP Forum	6	23-Jul-2005 03:29
vectors of references	mirizar	C++ Forum	1	12-Apr-2005 02:02
Declaring a vector of vectors?	Lethal411	C++ Forum	2	20-Mar-2004 09:02

how to commute values of vectors

Re: how to commute values of vectors

Re: how to commute values of vectors

Re: how to commute values of vectors

Re: how to commute values of vectors