Finding paths between two nodes in an undirected graph

[axcytz]

Hi all,

I have an undirected graph. The edges are 1-2, 1-3, 2-4, 3-4. I should find the paths between node 1 and 4. I will have roughly 50 of the nodes, so I need an efficient algorithm. Is there a sample code (c++) or any suggestions to use?

Thanks

 

[Öö Tiib]

I have an undirected graph. The edges are 1-2, 1-3, 2-4, 3-4.
I should find the paths between node 1 and 4. I will have roughly
50 of the nodes, so I need an efficient algorithm. Is there a sample
code (c++) or any suggestions to use?

C++ standard library does not contain graphs. On the other hand internet
is full of various (more or less problem-oriented) graph implementations.
Most work with millions of edges and vertices nicely.

Boost.Graph library is perhaps most generic. It is so generic that it
may take some time to declare all the details. It has piles of graph
algorithms in it.

50 vertices sounds a bit like homework. If so then better roll your own,
your professor won't buy that you wrote Boost.Graph. If you meet
some particular issue then come back and ask.

 

[axcytz]

C++ standard library does not contain graphs. On the other hand internet

is full of various (more or less problem-oriented) graph implementations.

Most work with millions of edges and vertices nicely.



Boost.Graph library is perhaps most generic. It is so generic that it

may take some time to declare all the details. It has piles of graph

algorithms in it.



50 vertices sounds a bit like homework. If so then better roll your own,

your professor won't buy that you wrote Boost.Graph. If you meet

some particular issue then come back and ask.

No, it is not a homework, it is just to test my other code. I will integrate two codes to run my overall problem. Do you mean it is not possible to doit with c++? What is boost? I haven't used it before, how can I learn about that?

 

[Öö Tiib]

No, it is not a homework, it is just to test my other code. I will
integrate two codes to run my overall problem. Do you mean it is not
possible to do it with c++?

What? No. I have not seen software that can't be as well implemented
using C++.

What is boost? I haven't used it before, how can I learn about that?

Boost is popular collection of open source C++ libraries. Home of it and
its documentation and links is: http://www.boost.org

Boost.Graph is one of those libraries. Some documentation is online.
http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/index.html
There is even a book:
http://www.informit.com/store/boost-graph-library-user-guide-and-reference-manual-9780201729146
It is header-only library so if you have downloaded the needed include
files then it should already work.

 

[axcytz]

What? No. I have not seen software that can't be as well implemented

using C++.






Boost is popular collection of open source C++ libraries. Home of it and

its documentation and links is: http://www.boost.org



Boost.Graph is one of those libraries. Some documentation is online.

http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/index.html

There is even a book:

http://www.informit.com/store/boost-graph-library-user-guide-and-reference-manual-9780201729146

It is header-only library so if you have downloaded the needed include

files then it should already work.

So, how can we include those .hpp files? Should i add them as header file, source, or what? Is there any example regarding this?

 

[Ian Collins]

So, how can we include those .hpp files? Should i add them as header
file, source, or what? Is there any example regarding this?

Read the links supplied.

 

[Öö Tiib]

So, how can we include those .hpp files?

In C++ there is preprocessor directive '#include' for including
header files. Who are "we"?

Should i add them as header file, source, or what? Is there any
example regarding this?

The tutorials and examples are in the boost graph documentation.