Graph

[Asteris]

Hello!
Please help me.
How to create a function that tells you if there is a tip in a particular graph?

#include<iostream>

using namespace std;
const int n = 10;

struct link {
	char key;
	link *next;
}
*g[n];

int m[n];

void init()  
{
	for (int i = 0;i < n;i++)
		g[i] = NULL;
}

int srch_node(link *g[n], char c) 
{
	int flag = 0;
	for (int i = 0;i < n;i++)
	{
		if (g[i])
		{
			if (g[i]->key == c)
				flag = 1;
		}
	}
	return flag;
}


int srch_arc(link *g[n], char C1, char C2)
{
	int flag = 0;
	if (srch_node(g, C1) && srch_node(g, C2))
	{
		int i = 0;
		while ((g[i]->key) != C1)
			i++;
		link *p = g[i];

		while ((p->key != C2) && (p->next))
			p = p->next;
		if (p->key == C2)
			flag = 1;
	}
	return flag;
}

void add_node(link *g[n], char C)
{
	if (srch_node(g, C))
	{
		cout << "\n ";
	}
	else
	{

		int j = 0;
		while (g[j] && j < n)
			j++;
		if (g[j] == NULL)
		{
			g[j] = new link;
			g[j]->key = C;
			g[j]->next = NULL;
		}

		else
			cout << "\nOverflow";
	}
}

void add_arc(link *g[n], char C1, char C2)
{
	if (srch_arc(g, C1, C2))
	{
		cout << "\nThe arc: ";
	}
	else
	{
		if (!srch_node(g, C1))
			add_node(g, C1);
		if (!srch_node(g, C2))
			add_node(g, C2);
		int i = 0;
		while (g[i]->key != C1)
			i++;
		link *p = new link;
		p->key = C2;
		p->next = g[i]->next;
		g[i]->next = p;
	}
}


void print(link *g[n])
{
	for (int i = 0;i < n;i++)
	{
		if (g[i])
		{
			link *p = g[i];
			cout << endl;
			while (p)
			{
				cout << p->key << "\t";
				p = p->next;
			}
		}
	}
}

int convert(char k, link *g[n])
{
	int i = 0;
	while (g[i]->key != k)
		i++;
	return i;
}


void dfs(char k, link *g[n])
{
	cout << k << "\t";
	int j = convert(k, g);
	m[j] = 1;
	link *t = g[j]->next;
	while (t)
	{
		if (m[convert(t->key, g)] == 0)
			dfs(t->key, g);
		t = t->next;
	}
}


void print_dfs(link *g[n])
{
	for (int i = 0;i < n;i++)
		if (g[i] && (m[i] == 0))
			dfs(g[i]->key, g);
}



void bfs(link *g[n])
{
	int i;
	link *p;
	for (i = 0;i < n;i++)
	{
		if (m[i] == 0)
		{
			p = g[i];
			while (p)
			{
				cout << p->key << "\t";
				m[convert(p->key, g)] = 1;
				p = p->next;
			}
		}
	}
}


void main()
{

	char A, B[20], C[20];
	int e, d;

	cout << "\n How many elements:";
	cin >> e;

	for (int i = 0;i < e;i++)
	{
		cout << "\n Element:";
		cin >> A;
		add_node(G, A);
	}

	cout << "\n Number of arcs:";
	cin >> d;

	cout << "\n Number of elements cunect with arc";

	for (int i = 0;i < d;i++)
	{
		cout << "\n Element 1:";
		cin >> B[i];
		cout << "\n Element 2:";
		cin >> C[i];
		cout << endl;

		add_arc(G, B[i], C[i]);
	}
	cout << "\n Struct:\n";
	print(G);

	cout << endl;

	cout << "\nDFS:" << endl << endl;

	print_dfs(G);

	cout << endl;

	int FLAG = 0;

	int m = 1;
	for (int o = 0;o < d;o++)
	{

		int m = o + 1;

		char ctrl = B[o];

		for (m;m < d;m++)
		{
			if (ctrl == B[m]) FLAG++;
		}
	}

	if (FLAG != 0) cout << "\n There is top";
	else cout << "\n There isn't a top";

	cout << endl;

}

[MikeStgt]

www.cpp.sh shows errors and warnings:

170:11: error: '::main' must return 'int'
 In function 'int main()':
183:12: error: 'G' was not declared in this scope
199:11: error: 'G' was not declared in this scope
202:8: error: 'G' was not declared in this scope
222:9: warning: statement has no effect [-Wunused-value]
214:6: warning: unused variable 'm' [-Wunused-variable] 

How to find a tip of a graph? Solve first derivative = 0 and look at the sign of the second derivative at that point, if < 0 it is a tip, else it is a sink.
(For such tasks I use REDUCE https://reduce-algebra.sourceforge.io or similar.)

[Duthomhas]

I have no idea how a non-C++ symbolic algebra system relates to this.


@Asteris
Alas, I am unsure what you mean by “tip”. Your source code leads me to think you might be asking about a loop: https://en.wikipedia.org/wiki/Loop_(graph_theory)

You are correct that a DFS can be used to find loops. If an edge leads to the current node, you have found one.

If you wish to find any cyclic characteristic in a graph, you will need additional data for that, either:
  • an additional field for every vertex that indicates whether or not the node has already been “visited” by the DFS
  • a set (such as std::unordered_set) that tracks which nodes the DFS has already visited

In either case, if you can detect that you have arrived at a node that has already been visited, then you have detected a cycle.

A loop is a cycle where the parent and child node are the same; it is a loop of length one (one edge traversed == one node visited).

Hope this helps.