stachour@sctc.com (Paul Stachour) (11/08/90)
I am using the Booch Ada components to write a program.
This program uses the directed-graph data-structure.
I use the Graph_Directed_Unbounded_Unmanaged generic package
(plus all the packages it transitively withs).
I want to iterate over all the current vertices of the graph,
to see of one of them has a particular value of a charateristic
(for purposes of discussion, having a particular "name").
I instantiate the graph-package with a STRING to contain the name
as the vertex item, and a NATURAL to be a count as the arc attribute.
Now, I have this directed graph partially built,
and I get another name-pair.
I want to find the first-name, and place an arc from that vertex
to the vertex with the second-name, updating the count on the arc
as I do so. [If the second vertex doesn't exist, I want to create
it, and place a count of 1 on the arc.]
I know that since I have a directed-graph, I could traverse all the
vertices from the base-vertex. However, this means that I would
visit some of them more than once (depnding upon the shape of the graph).
And this means I write my own iteration, which is wasteful.
So I think that the built-in interator is the way-to-go.
However, I have some problems in using the iterator as defined:
#1: Each vertex visited is an "in" parameter. That means that
changing it (by adding an arc) is forbidden. Oops!
#2: I have the new-name needed for the checking. But I don't
see an easy-way to pass it to the visiting-interator.
[I'm using a semi-global variable, but I don't consider
that very good style, or very maintainable.] Oops!
#3: If I have to create a new vertex, I'd like it to be an
output of the iterator, but I see that as similar to #2,
but in reverse. Oops!
#4: Even if all I was doing in this interator was counting
vertices whose items had some particular characteristic
(like having an "a" in the name someplace), I'd still need
to get the total out somehow? How?
How would you recommend interacting with this iterator?
I thought about using the MAP component on top of the graph one,
but this would mean that I would not have a back-mapping from
the vertex to its name, which I need also.
Thanks; Danke; Merci. ...Paul
--
Paul Stachour Secure Computing Technology Corp
stachour@sctc.com 1210 W. County Rd E, Suite 100
Arden Hills, MN 55112
[1]-(612) 482-7467MADMATS@ELCGL.EPFL.CH ("", Mats Weber) (11/13/90)
>I want to iterate over all the current vertices of the graph, >to see of one of them has a particular value of a charateristic >(for purposes of discussion, having a particular "name"). > >I instantiate the graph-package with a STRING to contain the name >as the vertex item, and a NATURAL to be a count as the arc attribute.>> > >[...] First, you should not ITERATE if what you want is FIND Second, for good reasons, few components will allow you to modify their structure while you are iterating on them. The graph component already gives you the mapping Vertex -> String What you seem to need is a mapping String -> Vertex, which you may obtain by instantiating a Map component. Then, once you have the name of the vertex you want to modify, search for the corresponding Vertex in your String -> Vertex map, and then modify that vertex accordingly. If you want to do some operation on all vertices, then iterate on the String -> Vertex map and modify the vertices within the graph from within that iterator. (You might have to use a String -> access Vertex mapping if the Map component does not provide a constructive iterator (on that allows you to modify subcomponents of the structure you are manipulating)). Answer to #4: Do not use a global variable, but instantiate the iterator within a procedure: function Number_Of_Vertices (G : in Graph) return Natural is Count : Natural := 0; procedure Count_Vertex (V : in Vertex) is begin Count := Count + 1; end; procedure Count_Vertices is new Iterate_Vertices(Count_Vertex); begin Count_Vertices(G); return Count; end; -- I'm not shure of the names, but you get the idea. Mats Weber Swiss Federal Institute of Technology EPFL DI LGL 1015 Lausanne Switzerland E-mail : madmats@elcgl.epfl.ch phone : +41 21 693 52 92 fax : +41 21 693 39 09