|
|
In many Graph applications, it is necessary to know whether a Vertex has been processed by an algorithm which is traversing or ``visiting'' Vertices for some purpose (such as changing the value in a user-defined data member). Examples of such traversals are the dfs and bfs algorithms that are included in the accompanying Graph Algorithms package (discussed in detail in the section, ``Traversals''. Often, though, you will need to create Vertex-processing algorithms that are specific to your application.
Two kinds of ``marks'' are defined to indicate whether a Vertex has been processed. One mark simply indicates that the Vertex has been processed: this mark is known in the Graph package as a ``visited'' mark. The other mark leaves an integer value at the Vertex: this mark is known as a ``val'' mark.
When only one such algorithm takes place at a given time, then the following Vertex member functions are defined for both the generic and user-derived Vertex types to change the value of these marks:
int set_visited();
// sets the visited mark at this Vertex to 1
int reset_visited();
// resets the visited mark at this Vertex to 0
int set_val(int value);
// sets the val mark at this Vertex to the
// given value
and to test the value of these marks:
int visited();
// tests whether this Vertex has been visited
// (initially 0)
int val();
// returns the val mark associated with this
// Vertex (initially 0)
Then, for a given Vertex v, these functions could be used in the following way:
.
.
.
/* a user-defined Vertex processing algorithm that
identifies Vertices with in edges */
void my_alg(Mygraph& g) {
Set_of_piter<Myvertex> si (g.vertices());
Myvertex* v;
while (v = si.next())
if (v.in_edges().size()) //v has in edges
v.set_val(1);
}
.
.
.
//later in the code
v.in_edges().remove_all();
// we have to remove the in edges
// for some reason
.
.
.
if (v.val()) ... ; // if this v used to have in
// edges ...
.
.
.
Note that in this case, although we could have used set_visited instead of set_val to mark each myvertex that used to have in edges, a visit mark traditionally indicates that a Vertex has been ``touched'', while a val mark has no such prior meaning. Thus, here it is more appropriate to use val.
After an algorithm has terminated, two non-member functions are defined in the Graph package to assist in zeroing out the visited and val marks:
reset_visited(Set_of_p<Vertex>& vset);
reset_val(Set_of_p<Vertex>& vset);
to be used with the set of Vertices, vset, which had undergone processing.
Now, let's consider the case when more than one algorithm may be processing Vertices concurrently. For instance, the dfs and bfs algorithms both take an optional function pointer: the called function may in turn be another Vertex-processing algorithm!
The Graph package defines versions of the above member (and non-member) functions which take a Ticket as a parameter. Each Ticket is unique, and is allocated a unique place in the Vertex for marking. Thus, when using different Tickets, the marks from different algorithms will not collide.
Two kinds of Tickets for a Vertex are defined: a Vis_v_ticket, which can be used in giving a visit mark to a Vertex; and a Val_v_ticket, which can be used in giving a val mark to a Vertex.
A Ticket is obtained by invoking either of
Vis_v_ticket vis_v_t = Vertex::get_vis_v_ticket();
Val_v_ticket val_v_t = Vertex::get_val_v_ticket();
depending on which kind of mark the algorithm will use, visited or val. Note that these member functions are not specific to a Vertex, since the pool of Tickets must be common to all Vertices (to ensure the elimination of collisions). A continuous supply of Tickets is available until memory is exhausted.
Once the Ticket is obtained, it can be used in versions of the member and non-member functions described above which expect a Ticket parameter:
int set_visited(const Vis_v_ticket& vis_v_t);
int reset_visited(const Vis_v_ticket& vis_v_t);
int visited(const Vis_v_ticket& vis_v_t);
int set_val(const Val_v_ticket& val_v_t, int value);
int val(const Val_v_ticket& val_v_t);
reset_visited(const Vis_v_ticket& vis_v_t,
Set_of_p<Vertex>& vset);
reset_val(const Val_v_ticket& val_v_t,
Set_of_p<Vertex>& vset);
When an algorithm has finished processing, its Ticket should be returned to its respective pool using one of the following two functions:
Vertex::free_vis_v_ticket(Vis_v_ticket& vis_v_t);
// for Vis_v_tickets
Vertex::free_val_v_ticket(Val_v_ticket& val_v_t);
// for Val_v_tickets
Here is an example of their use, given Vertex v:
Vis_v_ticket vvt = Vertex::get_vis_v_ticket();
.
.
.
v.set_visited(vvt);
if (v.visited(vvt)) ... ;
.
.
.
Vertex::free_vis_v_ticket(vvt);
Edges have all the same traversal support capabilities, with both Ticket and non-Ticket versions.