Simple Components (Generic_Directed_Graph)

Simple Components (Generic_Directed_Graph)

[Victor Porton]

Dear Dmitry,

I do not understand your logic in Generic_Directed_Graph:

The procedures like

procedure Disconnect (Parent : Node; Child : Node);

do not take "Graph" argument.

Does it mean that there exists just one graph (per instantiation)?

This looks wrong for me. First it is using global variables.

Please explain your logic.

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

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

Victor Porton wrote:

> Dear Dmitry,
> 
> I do not understand your logic in Generic_Directed_Graph:
> 
> The procedures like
> 
> procedure Disconnect (Parent : Node; Child : Node);
> 
> do not take "Graph" argument.
> 
> Does it mean that there exists just one graph (per instantiation)?
> 
> This looks wrong for me. First it is using global variables.
> 
> Please explain your logic.

It is in principle possible to represent an object as an internal state of a 
package. But this isn't the intended usage. And actually it is not suitable 
in some situations, such as dynamic memory allocation or an array of graphs.

So why did you do this? Shouldn't you rethink your design?

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

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-30 12:04, Victor Porton wrote:

> It is in principle possible to represent an object as an internal state of a
> package.

If object supposed to have a type, then no, Ada packages have no types.

> But this isn't the intended usage. And actually it is not suitable
> in some situations, such as dynamic memory allocation or an array of graphs.

Node = graph. Node type is scalar. You can allocate it, have arrays of, 
whatever you like keeping in mind that it is an access type.

Compare it to Ada task or file types. You can allocate tasks, you can 
have arrays of tasks, but remember that these are only proxy objects to 
some other entities.

> So why did you do this? Shouldn't you rethink your design?

That depends on the use case you have in mind.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-30 11:41, Victor Porton wrote:

> I do not understand your logic in Generic_Directed_Graph:
> 
> The procedures like
> 
> procedure Disconnect (Parent : Node; Child : Node);
> 
> do not take "Graph" argument.

A graph consists of connected nodes. Each node is in and a graph.

> Does it mean that there exists just one graph (per instantiation)?

No. If two nodes are mutually unreachable you have two graphs.

> This looks wrong for me. First it is using global variables.

It uses referential semantics. Node is an access type to the type you 
pass to the package when you instantiate it. E.g. if you want a graph of 
Strings you instantiate the package with String. Then Node is a pointer 
to string.

The notion of scope does not really applied to the structures like 
graph. You can scope the pool you pass to the instance. You can scope 
nodes with some logic attached when a node leaves its scope. But 
otherwise it makes little sense to talk about the scope of a graph.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-30 11:41, Victor Porton wrote:
> 
>> I do not understand your logic in Generic_Directed_Graph:
>> 
>> The procedures like
>> 
>> procedure Disconnect (Parent : Node; Child : Node);
>> 
>> do not take "Graph" argument.
> 
> A graph consists of connected nodes. Each node is in and a graph.
> 
>> Does it mean that there exists just one graph (per instantiation)?
> 
> No. If two nodes are mutually unreachable you have two graphs.
> 
>> This looks wrong for me. First it is using global variables.
> 
> It uses referential semantics. Node is an access type to the type you
> pass to the package when you instantiate it. E.g. if you want a graph of
> Strings you instantiate the package with String. Then Node is a pointer
> to string.
> 
> The notion of scope does not really applied to the structures like
> graph. You can scope the pool you pass to the instance. You can scope
> nodes with some logic attached when a node leaves its scope. But
> otherwise it makes little sense to talk about the scope of a graph.

What's about having multiple graphs for the situation if when A and B are of 
type T then A=B implies A'Access=B'Access?

It seems in this situation we cannot have multiple graphs of nodes of type 
T.

It yet seems bad for me, but may I mistake.

Maybe it's worth to create an alternative graph type (with every graph being 
a full-fledged object)? However I do not quite understand your logic, maybe 
you are right after all and this is not necessary.

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

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-30 15:58, Victor Porton wrote:

> What's about having multiple graphs for the situation if when A and B are of
> type T then A=B implies A'Access=B'Access?

I don't see how you could create such thing in Ada.

> Maybe it's worth to create an alternative graph type (with every graph being
> a full-fledged object)? However I do not quite understand your logic, maybe
> you are right after all and this is not necessary.

In practical applications where graphs might be useful:

1. There is no graph-wide operations or else they are impossibly 
inefficient.

2. Nodes are normally limited, updated in-place, never copied or moved.

3. Subgraphs are actively used without making copies of the whole graph.

4. Graph structure gets modified (e.g. rotation etc).

In short graphs are not containers, the picture you have in mind.

Consider graphs in the same league as doubly-linked lists.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Dennis Lee Bieber]

On Mon, 30 Oct 2017 16:46:32 +0100, "Dmitry A. Kazakov"
<mailbox@dmitry-kazakov.de> declaimed the following:

>
>Consider graphs in the same league as doubly-linked lists.

	<ouch> Except for simple one-in, one-out situations this comes across
as an overly simplified view.

	Presuming bidirectionality is required, I'd probably end up with a
structure where each node has a linked list of "IN" references, and a
linked list of "OUT" references. Granted, of one's requirements provide a
limit to the number of IN and OUT links, one might be able to use a fixed
array of references for each.
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-30 18:46, Dennis Lee Bieber wrote:

> 	Presuming bidirectionality is required, I'd probably end up with a
> structure where each node has a linked list of "IN" references, and a
> linked list of "OUT" references.

Right. The structure is allocated in the pool for each node. The package 
has the parameters for the sizes of the IN and OUT neighbor sets.

> Granted, of one's requirements provide a limit to the number of IN
> and OUT links, one might be able to use a fixed array of references
> for each.
IN and OUT sets are enlarged to n*Increment/100, where n is the current 
set size. Increment is the package parameter too.

In most cases graph connectivity and topology allows reasonable guessing 
the IN and OUT sizes.

P.S. Surely there is no optimal graph implementation for all cases.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-30 11:41, Victor Porton wrote:
> 
>> I do not understand your logic in Generic_Directed_Graph:
>> 
>> The procedures like
>> 
>> procedure Disconnect (Parent : Node; Child : Node);
>> 
>> do not take "Graph" argument.
> 
> A graph consists of connected nodes. Each node is in and a graph.
> 
>> Does it mean that there exists just one graph (per instantiation)?
> 
> No. If two nodes are mutually unreachable you have two graphs.
> 
>> This looks wrong for me. First it is using global variables.
> 
> It uses referential semantics. Node is an access type to the type you
> pass to the package when you instantiate it. E.g. if you want a graph of
> Strings you instantiate the package with String. Then Node is a pointer
> to string.

I also do not understand, when nodes are finalized. Please explain.

> The notion of scope does not really applied to the structures like
> graph. You can scope the pool you pass to the instance. You can scope
> nodes with some logic attached when a node leaves its scope. But
> otherwise it makes little sense to talk about the scope of a graph.
> 
-- 
Victor Porton - http://portonvictor.org

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-30 16:13, Victor Porton wrote:

> I also do not understand, when nodes are finalized. Please explain.

As usual in Ada, when an object is freed, it gets finalized right before 
its memory returns to the pool.

Nodes are allocated using new-allocator. Nodes are freed by operations 
like Delete and Free.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-30 11:41, Victor Porton wrote:
> 
>> I do not understand your logic in Generic_Directed_Graph:
>> 
>> The procedures like
>> 
>> procedure Disconnect (Parent : Node; Child : Node);
>> 
>> do not take "Graph" argument.
> 
> A graph consists of connected nodes. Each node is in and a graph.
> 
>> Does it mean that there exists just one graph (per instantiation)?
> 
> No. If two nodes are mutually unreachable you have two graphs.
> 
>> This looks wrong for me. First it is using global variables.
> 
> It uses referential semantics. Node is an access type to the type you
> pass to the package when you instantiate it. E.g. if you want a graph of
> Strings you instantiate the package with String. Then Node is a pointer
> to string.
> 
> The notion of scope does not really applied to the structures like
> graph. You can scope the pool you pass to the instance. You can scope
> nodes with some logic attached when a node leaves its scope. But
> otherwise it makes little sense to talk about the scope of a graph.

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?

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.

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?

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

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

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

> 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.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

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

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-30 22:20, Victor Porton wrote:

> 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.

Use a set of general constant access type instead. I don't know it goes 
with Ada containers, but normally you should be able to define a set 
with custom < and = defined on that access:

    function "=" (Left, Right : Pointer) return Boolean is
    begin
       return Left = Right or else
              (Left /= null and then Left.all = Right.all);
    end "=";

    function "<" (Left, Right : Pointer) return Boolean is
    begin
       return Right /= null and then
              (Left = null or else Left.all < Right.all);
    end "<";

If you put each node into the set taking Node.all'Unchecked_Access. You 
could test a given aliased string by taking its 'Unchecked_Access. No 
copies.

Alternatively you can use a set of Node with order operations defined as 
above and allocate a copy of the tested string in the test. You then 
free that string if it is already in the set and use one in the set 
instead. If duplicated strings are rather exception a few allocations 
should be no problem.

An finally you can have a set of access to String and a graph of that 
access to String nodes. I.e. Node would be an access to access to 
String. You can use a handle to reference counted String instead of the 
plain access to String.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Simon Wright]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>    function "=" (Left, Right : Pointer) return Boolean is
>    begin
>       return Left = Right or else
>              (Left /= null and then Left.all = Right.all);

Should there be a test Right /= null in there?

>    end "=";

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-31 08:36, Simon Wright wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>>     function "=" (Left, Right : Pointer) return Boolean is
>>     begin
>>        return Left = Right or else
>>               (Left /= null and then Left.all = Right.all);
> 
> Should there be a test Right /= null in there?

Yes.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-30 22:20, Victor Porton wrote:
> 
>> 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.
> 
> Use a set of general constant access type instead. I don't know it goes
> with Ada containers, but normally you should be able to define a set
> with custom < and = defined on that access:
> 
>     function "=" (Left, Right : Pointer) return Boolean is
>     begin
>        return Left = Right or else
>               (Left /= null and then Left.all = Right.all);
>     end "=";
> 
>     function "<" (Left, Right : Pointer) return Boolean is
>     begin
>        return Right /= null and then
>               (Left = null or else Left.all < Right.all);
>     end "<";
> 
> If you put each node into the set taking Node.all'Unchecked_Access. You
> could test a given aliased string by taking its 'Unchecked_Access. No
> copies.

Why Node.all'Unchecked_Access? Isn't it the same as Node?

Why no copies? Because of so defined "<"?

> Alternatively you can use a set of Node with order operations defined as
> above and allocate a copy of the tested string in the test. You then
> free that string if it is already in the set and use one in the set
> instead. If duplicated strings are rather exception a few allocations
> should be no problem.

Duplicated strings is NOT an exception.

What should I do?

> An finally you can have a set of access to String and a graph of that
> access to String nodes. I.e. Node would be an access to access to
> String. You can use a handle to reference counted String instead of the
> plain access to String.

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

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-31 12:12, Victor Porton wrote:

> Why Node.all'Unchecked_Access? Isn't it the same as Node?

No. Node is pool-specific.

And anyway different access types are different types. Ada is strongly 
typed.

It is one of great advantages of Ada typing system that pointer types 
have no structure-equivalence. In particular the solution I proposed is 
based on that. You can have different kinds of pointers to the same 
target type with operations like "<" and "=" defined differently on 
them. Thus having differently indexed structures of targets without 
copying the targets. In your case it is a set of strings and a graph of 
strings.

> Why no copies? Because of so defined "<"?

Because the set's element is access-to-String rather than String.

>> Alternatively you can use a set of Node with order operations defined as
>> above and allocate a copy of the tested string in the test. You then
>> free that string if it is already in the set and use one in the set
>> instead. If duplicated strings are rather exception a few allocations
>> should be no problem.
> 
> Duplicated strings is NOT an exception.

URIs do not repeat frequently. But I don't understand what are you doing 
anyway because the same URI can be resolved to different targets and 
conversely same target can have different URIs. And why they should have 
to be in a graph is a mystery to me.

> What should I do?

It is your choice. I merely pointed out that you can easily avoid having 
the same string kept twice.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simple Components (Generic_Directed_Graph)

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-31 12:12, Victor Porton wrote:
> 
>> Why Node.all'Unchecked_Access? Isn't it the same as Node?
> 
> No. Node is pool-specific.
> 
> And anyway different access types are different types. Ada is strongly
> typed.
> 
> It is one of great advantages of Ada typing system that pointer types
> have no structure-equivalence. In particular the solution I proposed is
> based on that. You can have different kinds of pointers to the same
> target type with operations like "<" and "=" defined differently on
> them. Thus having differently indexed structures of targets without
> copying the targets. In your case it is a set of strings and a graph of
> strings.
> 
>> Why no copies? Because of so defined "<"?
> 
> Because the set's element is access-to-String rather than String.
> 
>>> Alternatively you can use a set of Node with order operations defined as
>>> above and allocate a copy of the tested string in the test. You then
>>> free that string if it is already in the set and use one in the set
>>> instead. If duplicated strings are rather exception a few allocations
>>> should be no problem.
>> 
>> Duplicated strings is NOT an exception.
> 
> URIs do not repeat frequently. But I don't understand what are you doing
> anyway because the same URI can be resolved to different targets and
> conversely same target can have different URIs. And why they should have
> to be in a graph is a mystery to me.

I consider an RDF file. RDF files contain so called "triples" (subject-
predicate-object). Each of the three can be an URI.

I consider a digraph whose arcs are subject-object (with predicate 
expressing the relation "is-subclass-of"). This graph is to store all known 
sub-class relations between URIs. It is specifically is there is a path of 
"is-subclass-of" relations between any two given URIs.

Certainly an RDF file can have a subject or object more than once (and even 
many times).

RDF is a mean to store logical (semantic) relations online in a portable 
way. A URI may be not a page of the Web, but an abstract object representing 
any concept (for example, we can have an URI whose meaning is "cursive font" 
or "revolution in Ukraine" or "computer science", just arbitrary, this is 
the power of RDF).

>> What should I do?
> 
> It is your choice. I merely pointed out that you can easily avoid having
> the same string kept twice.

Is my solution to use Map to map URIs (you can think of them as strings) to 
accesses to empty records (representing graph vertices) a good programming 
style?

I do not need to map a graph vertex into a string, but I need to map a 
string into a graph vertex.

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

Re: Simple Components (Generic_Directed_Graph)

[Dmitry A. Kazakov]

On 2017-10-31 16:07, Victor Porton wrote:
> Dmitry A. Kazakov wrote:
> 
> I consider an RDF file. RDF files contain so called "triples" (subject-
> predicate-object). Each of the three can be an URI.
> 
> I consider a digraph whose arcs are subject-object (with predicate
> expressing the relation "is-subclass-of"). This graph is to store all known
> sub-class relations between URIs. It is specifically is there is a path of
> "is-subclass-of" relations between any two given URIs.

OK, that is a decision tree, a crisp tree in your case. Though usually 
weighted graphs are used, e.g. in probabilistic and fuzzy, 
intuitionistic fuzzy trees. In real-life applications such relations are 
rarely crisp. It is an inference that usually yields a probability or 
confidence measure of A in B. [In intuitionistic inference it is also 
other three outcomes A in not B, not A in B, not A in not B.]

> Certainly an RDF file can have a subject or object more than once (and even
> many times).
> 
> RDF is a mean to store logical (semantic) relations online in a portable
> way. A URI may be not a page of the Web, but an abstract object representing
> any concept (for example, we can have an URI whose meaning is "cursive font"
> or "revolution in Ukraine" or "computer science", just arbitrary, this is
> the power of RDF).

No, this is weakness. Any = nothing.

> Is my solution to use Map to map URIs (you can think of them as strings) to
> accesses to empty records (representing graph vertices) a good programming
> style?

Rather a poor choice. There is no advantage in having copies. One could 
have them in order to gain something, e.g. performance or design clarity.

> I do not need to map a graph vertex into a string, but I need to map a
> string into a graph vertex.

No, it is a set of vertices implemented as a map because you have 
trouble using a string for searching the set.


-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de