Algorithms

21-Mar-22 9:24

Reference counting enable automated releasing memory if no cycles. Users who use smartpointers in C++ or Swift language must be carefully and proper use weak pointers.
I think about extend smartpointers to manage cycles and start new language which can use this algorithm.
I don’t know if algorithm is correct for all possible graphs and graph forest (set) and all possible adding, removing edges in runtime.
Preview this algorithm
Block must have:
- standard ref count (use count)
- weak count
- outgoing count
- link_number
In other hand pointers have standard with unlike fat(double) smartpointers in C++.
For further info, current version biggest method
https://github.com/parstools/smart/blob/86ca62e9bc6c4dc2e5a2de2408594bedb430140e/testCpp/dyncycles.cpp#L53

main is https://github.com/parstools/smart/blob/86ca62e9bc6c4dc2e5a2de2408594bedb430140e/testCpp/main.cpp#L287

Is possible proof correctness this algorithm or find leaks?

Re: Very smart pointers

Greg Utas26-Mar-22 10:14

Greg Utas

26-Mar-22 10:14

If you want to try this, I would suggest implementing it in C++ instead of designing a new language around it, which is a much bigger undertaking.

My view is that I don't want to rely on a garbage collector. They tend to periodically monopolize the CPU time in a system with a lot of objects. But because memory leaks do occur, I favor object pools with a background garbage collector that recovers the memory for an object that was not properly deleted. You can read about it in this article[^].

Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.

Re: Very smart pointers

Member 146609423-May-22 4:13

Member 14660942

3-May-22 4:13

You can do a test with a circular reference.

A => B => C => A

So, if I have an initial pointer to A object, because of the construct, it is going to have a count of 2 (because of C). The need for the Garbage Collector is that if you remove the initial pointer to A (either in the Stack or Heap), A's reference count only decreases to 1, and because of C it never goes to 0. Is your code prepared to deal with that?

The problem here with reference counting is that one above; it doesn't count how many "access paths" you have to an object, just the number of references you have to it.

Re: Very smart pointers

Andy Oct20213-May-22 22:21

Maximum Sum of Value of Positions Along a Path

3-May-22 22:21

Yes,even more complicated but no proof that all.

Jj2093884218-Mar-22 13:30

18-Mar-22 13:30

I'm practicing my dynamic programming skills and am having trouble coming up with a solution to this problem: Suppose there is a path with n positions. Consider the set S = 1. This is solved.

modified 19-Mar-22 19:40pm.

Richard Andrew x6418-Mar-22 14:11

Richard Andrew x64

18-Mar-22 14:11

What real world problem are you trying to solve?

The difficult we do right away...
...the impossible takes slightly longer.

Jj2093884218-Mar-22 14:21

18-Mar-22 14:21

There's no real-world problem, it's just a problem haha. Any ideas on what a correct dynamic programming approach would look like?

Richard Andrew x6418-Mar-22 14:25

Richard Andrew x64

18-Mar-22 14:25

I have some ideas, but your professor might not like me giving you the answer.

The difficult we do right away...
...the impossible takes slightly longer.

Jj2093884218-Mar-22 18:40

18-Mar-22 18:40

Oh, this isn't actually for school/homework. Given this, would you be willing to share your ideas?

Gerry Schmitz19-Mar-22 5:33

19-Mar-22 5:33

"Dynamic programming" does not preclude you from iterating over every possible solution (which is limited in this case) in coming up with the best solution. Turning "big problems" into smaller ones to tackle.

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

Jj2093884219-Mar-22 5:49

19-Mar-22 5:49

Right, but in this case, aren't there a lot of possible solutions? For example, if we had S1 = {A,C}, S2={A, B}, S3={A,B,C}, S4={A,C}, S5={A,B,C} then there would be 2*2*3*2*3=72 possible solutions, and this grows quickly as the number of subsets grows. I figure you're imagining a different approach. In what ways can I limit the possible solutions that I consider?

Gerry Schmitz19-Mar-22 6:12

19-Mar-22 6:12

72 iterations is trivial. Even thousands ... that's the "dynamic" part.

You haven't "bounded the problem". You can't go through life with "Yeah, but ...".

Incomplete specs lead to incomplete solutions. And, most of the time, you benchmark first; then ask the question: is it good enough?

Jj2093884219-Mar-22 6:21

19-Mar-22 6:21

Sorry, I realize that I should have given an explicit bound for the problem (I have edited the original post to reflect this now). This problem can be done in polynomial time as a function of n, whereas permuting through all possible solutions would be O(3^n). Given this constraint, do you have any advice?

Gerry Schmitz19-Mar-22 6:57

19-Mar-22 6:57

In other words, in polynomial time without an apparent way to get there; whereas with iteration, you're able to get your head around it and it may even be "fast enough" for the practical case.

(Iteration doesn't imply redoing / not using previous calculations).

A quantum computer could probably test all paths at the same time, but I'm not sure how many qbits it would need. Probably "depends".

modified 19-Mar-22 13:19pm.

Jj2093884219-Mar-22 7:41

Special minimum spanning tree

19-Mar-22 7:41

Well, yeah, but iteration is O(n*3^n). This algorithm can be done in polynomial time (given in the problem statement), so I am trying to get a solution that does this. So let's please assume O(n*3^n) isn't fast enough in this context.

Andy Oct202116-Mar-22 10:35

Re: Special minimum spanning tree

16-Mar-22 10:35

All algorithms for MST I meet, uses indirect graph and search minimum weight.
I need a bit other: my graph is directed, weights are unimportant, all are = 1.
Is not necessary find minimal tree, but ANY tree without cycles, although tree with minimal number of edges will be nice.
Most important is - graph must be directed.

Andy Oct202116-Mar-22 15:58

Re: Special minimum spanning tree

16-Mar-22 15:58

Problem is with directed graph, because is possible many vertex links to one. It is reverse tree. This means,that is impossible leaving spanning tree.
Question is another: how detect cycles and remove all cycles?

akratirawat30-Jun-22 19:38

akratirawat

30-Jun-22 19:38

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]= {
	0
}
,min,mincost=0,cost[10][10];
void main() {
	clrscr();
	printf("\n Enter the number of nodes:");
	scanf("%d",&n);
	printf("\n Enter the adjacency matrix:\n");
	for (i=1;i<=n;i++)
	  for (j=1;j<=n;j++) {
		scanf("%d",&cost[i][j]);
		if(cost[i][j]==0)
		    cost[i][j]=999;
	}
	visited[1]=1;
	printf("\n");
	while(ne<n) {
		for (i=1,min=999;i<=n;i++)
		   for (j=1;j<=n;j++)
		    if(cost[i][j]<min)
		     if(visited[i]!=0) {
			min=cost[i][j];
			a=u=i;
			b=v=j;
		}
		if(visited[u]==0 || visited[v]==0) {
			printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
			mincost+=min;
			visited[b]=1;
		}
		cost[a][b]=cost[b][a]=999;
	}
	printf("\n Minimun cost=%d",mincost);
	getch();
}

Triangulation inside a contour

Member 1505866510-Mar-22 1:44

Member 15058665

10-Mar-22 1:44

Hello

I have a home-made program that generates 4 BMP files (top inside, top outside, back inside, back outside) with contour lines for my luthier activity as a hobbyist from another BMP with the contour of the arch and the center line, and the height of the arch. It perfectly works, I crafted 3 violins and 3 cellos with original shapes, they work perfectly.

Now, as the program computes the altitude of each point, I would like to generate 3D models from the results.
At first, I look from a 2D point of view:
I make a list of consecutive 2D vertices (separated at a quite constant distance) that draws the contour of the instrument. I'd like a simple triangulation of the whole instrument, ie. make a 2D mesh inside the contour. I know there are algorithms like Delaunay, but I wanted to know if there is a simple way to do that.

See this picture:
https://i.servimg.com/u/f88/17/72/22/03/triang10.png

- the blue line is the contour I want to fill
- the black grid is a grid whose square size depends on the precision I want - I would triangulate the inner part of the instrument with squares (made of 2 triangles) like the green ones
- the red line show the case when the 3 vertices of a triangle would be inside the contour but should'nt be drawn as part of it is outside of the contour

Now I have 2 questions:
- Is there an easy way to detect these triangles that are partly outside of the contour, but have their summit inside?
- Is there an easy way to triangulate the remaining parts between the contour and the fully inside squares without using a complicated algorithm like Delaunay?

Thank you
David

Gerry Schmitz10-Mar-22 16:27

10-Mar-22 16:27

I have some large scale digital maps I "transform" (uniform colors; removing noise). I can sample and rewrite 100,000,000 pixels in "no time at all". You (just) need to get some hits on different colors in your polygons.

You also have an (apparent) "adjacency rule" happening.

modified 10-Mar-22 22:33pm.

Member 1505866510-Mar-22 20:43

Member 15058665

10-Mar-22 20:43

Sorry, was it an answer for me about triangulation?

Gerry Schmitz11-Mar-22 4:05

11-Mar-22 4:05

Yeah ... dots inside your triangles.

You wanted "simple".