Re: Simple Components (Generic_Directed_Graph)

[Victor Porton <porton@narod.ru>]

You can look my code in

https://github.com/vporton/xml-boiler/blob/master/src/boiler-global.ads
https://github.com/vporton/xml-boiler/blob/master/src/boiler-global.adb

I think it works (not yet tested just compiled). But it is probably not 
quite intended use of your directed graph.

Dmitry A. Kazakov wrote:
> On 2017-10-30 19:30, Victor Porton wrote:
> 
>> Oh, I've finally realized that Node_Type and Node are not the same type.
>> Now your logic seems clear.
>> 
>> But how to solve my particular problem?
>> 
>> I have two objects (URI1 and URI2) of URI_Type type each (or for
>> simplicity both could be two strings). I need to check if there exists a
>> path from URI1 to URI2. How to do this?
> 
>     URI1 : Node := new String'("http://foo.html");
>     URI2 : Node := new String'("http://bar.html");
>     URI3 : Node := new String'("http://baz.html");
> begin
>     Connect (URI1, URI2);
>     Connect (URI2, URI3);
>     --
>     -- The graph is now:
>     --
>     -- "http://foo.html" -> "http://bar.html" -> "http://baz.html"
>     --
>     if Is_Ancestor (URI1, URI2) then
>        -- There is a path in the graph

The issue here that equal strings should get equal access values. That is 
the same string should be never in more than one node.

Thus I use a map from URIs (or they could be strings) to node access values.

Again, the complete code is referred above.

>> My current idea is to use Ada standard "map" container which could map
>> from "access URI_Type" to "URI_Type" (for all URIs in the considered
>> finite set) before asking your generic package for existence of a path.
> 
> If you are concerned about performance in the case when same tests
> frequently repeat, you can keep a map (Node,Node)-> Boolean in order to
> cache once evaluated results.
> 
>> The same problem appears when I insert new edges: An edge should be
>> identified by two values of type URI_Type but you require two accesses to
>> URI_Type instead. Should I convert URI_Type to "access URI_Type" using a
>> standard map before inserting into the graph?
> 
> You cannot convert it, node objects are allocated in a special storage
> pool backed by the pool passed as the package parameter. The graph
> structure is stored in that pool as well.

See above. I "convert" them through a Map from accesses to URIs.

-- 
Victor Porton - http://portonvictor.org