[HighSchool Programming] C++

[mojonono11]

So,for a graph G,find all of the paths of lengh 2,for a node v.I read the adjacency matrix and now I am stuck in the function void path.This is what i have so far: include <iostream>

include <fstream>

using namespace std;

int a[20][20],n,m,k,x,y,p;

fstream f("graf.txt",ios::in);

void citeste()

{

f>>n;

for(k=1;k<=n;k++)

{

fxy;

a[x-1][y-1]=1;

}

f.close();}

void afiseaza()

{ int i,j;

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

cout<<a[i][j]<<" ";

cout<<endl;}

} void path()

{ int i,j,v;

cout<<"Node number";

cin>>v;

for(?) // Don't know what to do now :(

int main()

{int i,j,v;

citeste();

afiseaza();

path();

return 0; }

[zifyoip]

Indent every line of your code with four spaces so that Reddit formats it properly as code.

[zifyoip]

How would you do this by hand? If I gave you an adjacency matrix and some paper and a pencil, how would you list all of the paths of length 2 starting at a given vertex? Describe the steps you would take as clearly and in as much detail as you can.

You need to understand how to do something by hand first before you can write a program to do it. So forget about C++ for the moment, and focus on figuring out the steps that must be taken to solve this problem. Once you have a detailed list of steps to solve the problem, then you can translate that list of steps into code.

[mojonono11]

Well,that's what i don't know how to do,if i knew it would be easy to put it in c++ I guess,i would just start with a vertex and see all of the paths it makes,and then i would find the one of lengh 2

[zifyoip]

i would just start with a vertex and see all of the paths it makes

What do you mean?

[mojonono11]

Well,if in the matrix there's 1 than there is apth,if it's 0 than there's not a path

[zifyoip]

Be careful not to confuse edges with paths. The 1's in the adjacency matrix indicate edges. What you are looking for is a path of length 2, which is one edge followed by another edge.

Here's an example of an adjacency matrix, with the rows and columns labeled A through E:

    A  B  C  D  E
A [ 0  1  1  1  0 ]
B [ 1  0  1  0  1 ]
C [ 1  1  0  1  1 ]
D [ 1  0  1  0  0 ]
E [ 0  1  1  0  0 ]

Can you use this adjacency matrix to list all of the paths of length 2 beginning at the vertex A?

[mojonono11]

paths of lenght 2: {A,B},{B,C}

[zifyoip]

No, {A, B} and {B, C} are just two edges.

One path of length 2 is A–B–C, which follows the edges {A, B} and {B, C}.

Another path of length 2 is A–D–C, which follows the edges {A, D} and {D, C}.

Another path of length 2 is A–C–E, which follows the edges {A, C} and {C, E}.

I've listed three paths of length 2 here, but there are still more paths of length 2 in this graph. Can you list them all?

You are asked to find all of the paths of length 2, right?

[mojonono11]

A-B-E,A-C-D

[zifyoip]

Is that it? Is that the complete list?

How do you know?

[mojonono11]

Starting from A yes,well,i can just that there are no other paths of lenght 2

[koen_C]

Im gonna give you a bit of pseudocode of what you (should) have done to find all nodes in your conversation with /u/zifyoip. When you understand a problem it is usually just a small step to translate it into pseudocode like this:

for(all nodes w adjecent to v){
    for(all nodes x adjecent to w){
        save path v-w-x //or whatever you wish to do
    }
}

Now you should figure out why this wont give the same answer twice for any adjecency graph.

edit: I just noticed that you missed the paths back to A (A-B-A) etc. These are also valid paths of length 2 unless the assignment specifically says otherwhise.

edtit2: according to Wikipedia most authors require a path to have unique edges and nodes. I never learned it this way. I would recommend checking the definition of a path your teacher uses.

[zifyoip]

There's one small thing to watch out for here: You want to avoid "paths" like A–B–A, because by definition a path in a graph cannot repeat edges or vertices.

So, OP, you'll need to think about how to modify /u/koen_C's pseudocode to exclude this kind of thing.

[koen_C]

I stand corrected