• Borneq (92/92) Mar 22 2022 Hi, I search place to discuss about graph algorithms.

Borneq <borucki.andrzej gmail.com> writes:

Hi, I search place to discuss about graph algorithms.
I start creating experimental language with extended smart 
pointers.
Goal: while smart pointers in C++ and pointers in Swift need 
carefully handle with shared and weak pointers and knowing where 
using weak instead shared, here should be language which disabled 
making leaking code by developer; like garbage collector but 
using reference counting and other fields.
Sample program in Smart language:

```csharp
public class Elem {
     internal Elem next;
     string name;
     public Elem(string name)
     {
         this.name = name;
     }
     ~Elem() {
	    Console.Printf("delete %s",name);
     }
}

public static class Program
{	
     static void Main()
     {
         Elem a = new Elem(“Apartment”);
         Elem b = new Elem(“Person”);
         a.next  = b;
         b.next = a;
      }
}
```

This should be translated to C++ code:

```c++
void main() {
     Shadow shadow;
     Elem* a = new Elem("Apartment");
     Elem* b = new Elem("Person");
     link_assign(a,&shadow,(Object**)&a->next, b);
     link_assign(b,&shadow,(Object**)&b->next, a);
     try_release(&shadow,  b);
     try_release(&shadow,  a);
}
```

In C++ is struct Elem which inherits from Object from runtime.
Is defined:
```C++
struct Object {
     int ref_count;
     int weak_count;
     int out_count;
     int link_number;
     Object() {
         ref_count = 1;
         out_count = 0;
         link_number = 0;
     }
     virtual ~Object(){}
};
```
ref_count is number links to object, in some cases finding 
automatic , ref_count will not increment, but for releasing 
purpose is also weak_count.
out_count – umber outgoing objects
link_number- subsequent number in shadow variable, not creating 
by each creating object, but objects which have outgoing links.
In other hand pointers have standard width unlike fat(double) 
smartpointers in C++.

Struct shadow is local variable with substructures for each graph 
defined locally.
For each graph is stored number of cycles.
Naive approach to cycles: each element in graph 1 is marked with 
1, in graph 2 with 2 and so on. If we links from element with 1 
to element with 1 – is cycle.
Has disadvantages: If we have millions objects and link from 
object with 1 to object with 2, this should be replaced all 
millions 2 to 1, And when we remove edge – all in second half 
should be renamed from 1 to 2.
Shadow size is near proportional to number of graphs, not graphs 
size.
Main routine is  link_assign
https://github.com/parstools/smart/blob/7b6b6910dadbb37f1df0b263415d1a1a15b42476/testCpp/dyncycles.cpp#L53

Problems:
- threads, ref_count in shared_ptr in C++ is atomic, but here is 
element from and element to
- shadow with both local elements and field elements, if elements 
will fields, shadow also must be field, but how do if a.next =b , 
one root is point from fields, second from local?

But for all tested examples is good,
**Is possible proof correctness of this algorithm or find leaks?**
for all possible sets of graphs, with cycles or not, and possible 
adding/deleting vertices and edges?