Boost logo

Boost :

From: jsiek_at_[hidden]
Date: 1999-12-08 04:49:06


Hi,

Here's an attempt at a compromise on the graph structure interface.
Basically, I can live with the graph objects, but iterators have to be
iterators :) (and input iterator or some new tag derived from input
iterator will do)

First, a suggestion for some names. Instead of "node_pointer" I
suggest "node_descriptor". Similarly for edge.

Also, I've moved the graph object from being the "this" object, to
being in the paramter list. I've found that it's easier to extend and
adapt in the presense of global functions than with member functions.

In addition, I've replaces the pairs of functions that end in "_begin"
and "_end" with a single function that instead returns literally a pair of
iterators. The begin(p) and end(p) functions below just return the
first and second element of the pair.

v is a NodeDescriptor
e is an EdgeDescriptor
g is a Graph
alit is an adjacency list iterator
elit is an edge list iterator
nit is a node iterator
eit is an edge iterator

struct graph_traits {
   typedef ... node_descriptor;
   typedef ... edge_descriptor;
   typedef ... adjacency_iterator;
   typedef ... edgelist_iterator;
   typedef ... node_iterator;
   typedef ... edge_iterator;
};

alit = begin(adj(v,g)) // iterate through the nodes adjacent to node v
alit = end(adj(v,g))

v = *alit // obtain a node descriptor from the adjacency list iterator

elit = begin(out_edges(v,g)) // iterate through the out-edges of node v
elit = begin(out_edges(v,g))

e = *elit // obtain an edge descriptor from the edge list iterator

nit = begin(vertices(g)) // iterate through the "list" for all the nodes
nit = end(vertices(g))

v = *nit // obtain a node descriptor from the node iterator

eit = begin(edges(g)) // iterate through the "list" for all the edges
eit = begin(edges(g))

e = *eit // obtain an edge descriptor from the edge iterator

v = source(e) // I don't see a need for the graph object on this one
v = target(e)

Cheers,

Jeremy

----------------------------------------------------------------------
 Jeremy Siek
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (650) 933-8724
 and cell phone: (415) 377-5814
 C++ Library & Compiler Group fax: (650) 932-0127
 SGI www: http://www.lsc.nd.edu/~jsiek/
----------------------------------------------------------------------


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk