Finding paths between two nodes in an undirected graph

Discussion in 'C++' started by axcytz@gmail.com, Jul 29, 2013.

  1. Guest

    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
     
    , Jul 29, 2013
    #1
    1. Advertising

  2. Öö Tiib Guest

    On Monday, 29 July 2013 11:07:52 UTC+3, 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.
     
    Öö Tiib, Jul 29, 2013
    #2
    1. Advertising

  3. Guest

    On Monday, July 29, 2013 3:50:45 AM UTC-5, Öö Tiib wrote:
    > On Monday, 29 July 2013 11:07:52 UTC+3, 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?
     
    , Jul 29, 2013
    #3
  4. Öö Tiib Guest

    On Monday, 29 July 2013 12:05:17 UTC+3, wrote:
    > On Monday, July 29, 2013 3:50:45 AM UTC-5, Öö Tiib wrote:
    > > On Monday, 29 July 2013 11:07:52 UTC+3, 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/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.
     
    Öö Tiib, Jul 29, 2013
    #4
  5. Guest

    On Monday, July 29, 2013 4:49:32 AM UTC-5, Öö Tiib wrote:
    > On Monday, 29 July 2013 12:05:17 UTC+3, wrote:
    >
    > > On Monday, July 29, 2013 3:50:45 AM UTC-5, Öö Tiib wrote:

    >
    > > > On Monday, 29 July 2013 11:07:52 UTC+3, 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/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?
     
    , Jul 29, 2013
    #5
  6. Ian Collins Guest

    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
     
    Ian Collins, Jul 29, 2013
    #6
  7. Öö Tiib Guest

    On Monday, 29 July 2013 13:12:59 UTC+3, 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.
     
    Öö Tiib, Jul 29, 2013
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Daniele
    Replies:
    8
    Views:
    9,327
    Victor Bazarov
    Aug 3, 2004
  2. Gregor Rot
    Replies:
    1
    Views:
    510
    those who know me have no need of my name
    May 11, 2004
  3. nick
    Replies:
    1
    Views:
    500
    Le Chaud Lapin
    Sep 12, 2008
  4. disappearedng
    Replies:
    0
    Views:
    385
    disappearedng
    Jul 22, 2009
  5. disappearedng
    Replies:
    0
    Views:
    1,490
    disappearedng
    Jul 22, 2009
Loading...

Share This Page