Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Finding paths between two nodes in an undirected graph

Reply
Thread Tools

Finding paths between two nodes in an undirected graph

 
 
axcytz@gmail.com
Guest
Posts: n/a
 
      07-29-2013
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
 
Reply With Quote
 
 
 
 
Öö Tiib
Guest
Posts: n/a
 
      07-29-2013
On Monday, 29 July 2013 11:07:52 UTC+3, (E-Mail Removed) wrote:
> 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.
 
Reply With Quote
 
 
 
 
axcytz@gmail.com
Guest
Posts: n/a
 
      07-29-2013
On Monday, July 29, 2013 3:50:45 AM UTC-5, Öö Tiib wrote:
> On Monday, 29 July 2013 11:07:52 UTC+3, (E-Mail Removed) wrote:
>
> > 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.


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?
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      07-29-2013
On Monday, 29 July 2013 12:05:17 UTC+3, (E-Mail Removed) wrote:
> On Monday, July 29, 2013 3:50:45 AM UTC-5, Öö Tiib wrote:
> > On Monday, 29 July 2013 11:07:52 UTC+3, (E-Mail Removed) wrote:
> > > 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.

>
> 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...doc/index.html
There is even a book:
http://www.informit.com/store/boost-...-9780201729146
It is header-only library so if you have downloaded the needed include
files then it should already work.
 
Reply With Quote
 
axcytz@gmail.com
Guest
Posts: n/a
 
      07-29-2013
On Monday, July 29, 2013 4:49:32 AM UTC-5, Öö Tiib wrote:
> On Monday, 29 July 2013 12:05:17 UTC+3, (E-Mail Removed) wrote:
>
> > On Monday, July 29, 2013 3:50:45 AM UTC-5, Öö Tiib wrote:

>
> > > On Monday, 29 July 2013 11:07:52 UTC+3, (E-Mail Removed) wrote:

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

>
> >

>
> > 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...doc/index.html
>
> There is even a book:
>
> http://www.informit.com/store/boost-...-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?
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      07-29-2013
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

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

--
Ian Collins
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      07-29-2013
On Monday, 29 July 2013 13:12:59 UTC+3, (E-Mail Removed) wrote:
>
> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Finding all cycles within an undirected graph (disappearedng) disappearedng Python 0 07-22-2009 02:16 PM
Finding all cycles within an undirected graph disappearedng Python 0 07-22-2009 01:04 PM
Finding all paths between 2 nodes undirected multigraph nick C++ 1 09-12-2008 05:28 AM
undirected graph representation and Kruskal's algorithm Gregor Rot C Programming 1 05-11-2004 09:11 AM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM



Advertisments