Writing a graph

[Christian Christmann]

Hi,

I need to write a graph which provides at least the
following functions:

1) stores nodes and edges (both store further information which
can be of any type)
2) manipulations on nodes and edges like delete, add ...
3) provides a list of all successors/predecessors for a given node
4) provides a list of all nodes that can be reached from a given
node on an existing path (sequence of edges)
5) provides a list of all nodes that can reach n on a given path
6) check whether the graph is cyclic

The code should be based on Standard Template Libraries (STL).

How would you realize this task e.g. which structures would you
use?

Are there any STL graph classes which already provides the aforementioned
functions?

If you have or know any self-written graph code and would like to share
just let me know

Thank you very much for your help.

Chris

 

[Samee Zahur]

I don't know much about graphs, but did you try boost graph library?
Take a look:

http://www.boost.org/libs/graph/doc/table_of_contents.html

Hey, I do have a nag at learning mathematical concepts - if you'll be
my tutor, you know my email address

Samee

P.S. Please try to avoid postings to which easy answers exist e.g.
googling with C++ graph library gives the boost library as the very
first result! My first post to this group (just a few days back) was a
similar Q about a regex library, and I was immediately notified of
inappropriate postings (these are often considered OT)

 

[Jeff Flinn]

Hi,

I need to write a graph which provides at least the
following functions:

1) stores nodes and edges (both store further information which
can be of any type)
2) manipulations on nodes and edges like delete, add ...
3) provides a list of all successors/predecessors for a given node
4) provides a list of all nodes that can be reached from a given
node on an existing path (sequence of edges)
5) provides a list of all nodes that can reach n on a given path
6) check whether the graph is cyclic

The code should be based on Standard Template Libraries (STL).

How would you realize this task e.g. which structures would you
use?

Are there any STL graph classes which already provides the aforementioned
functions?

If you have or know any self-written graph code and would like to share
just let me know

Take a look at http://www.boost.org/libs/graph/doc/table_of_contents.html

Jeff Flinn