Skip to main content

Find nodes which are not part of any cycle in a directed graph

Non cycle node in graph

Here given code implementation process.

// C program for 
// Find nodes which are not part of any cycle in a directed graph
#include <stdio.h>

#include <stdlib.h>

// Define edge of graph node
struct AjlistNode
{
    int id; // Vertices id
    struct AjlistNode *next;
};
// Define node of graph 
struct GraphNode
{
    int data; // node key value
    struct AjlistNode *edge;
};
// Define structure of graph
struct MyGraph
{
    int size; // Number of graph nodes
    struct GraphNode *node;
};
// This are return a new graph with given number of nodes
struct MyGraph *newGraph(int size)
{
    if (size < 0)
    {
        printf("\n Invalid size of nodes %d \n", size);
        return NULL;
    }
    // Create a graph
    struct MyGraph *graph = (struct MyGraph *) malloc(sizeof(struct MyGraph));
    if (graph != NULL)
    {
        // Set node size
        graph->size = size;
        // Allocate memory to graph node
        graph->node = (struct GraphNode *) malloc(sizeof(struct GraphNode) *size);
        // Loop controlling variable
        int i = 0;
        // Set graph node level and e
        for (i = 0; i < graph->size; i++)
        {
            // Set node level (0...size-1)
            graph->node[i].data = i;
            // Set the node [i] have no edge
            graph->node[i].edge = NULL;
        }
    }
    else
    {
        printf("\n Graph of nodes %d is not created (memory overflow problem)\n", size);
    }
    return graph;
}
//This function are connect nodes with one edge 
void connectEdge(struct MyGraph *graph, int a, int b)
{
    if (graph->node == NULL)
    {
        printf("\n Graph have no nodes \n");
        return;
    }
    // Create Adjacency node
    struct AjlistNode *newEdge = (struct AjlistNode *) malloc(sizeof(struct AjlistNode));
    if (newEdge != NULL)
    {
        newEdge->next = NULL;
        newEdge->id = b;
        // Get first edge of [i] node
        struct AjlistNode *edge = graph->node[a].edge;
        if (edge == NULL)
        {
            // Whe no edge of graph node [i] then
            // Add a first edge of a [i] node
            graph->node[a].edge = newEdge;
        }
        else
        {
            //Find last location to add new edge
            while (edge->next != NULL)
            {
                edge = edge->next;
            }
            // Add edge at last position
            edge->next = newEdge;
        }
    }
    else
    {
        printf("\nMemory overflow, when connect a new \
            edge from ( %d to %d ) nodes.\n", a, b);
    }
}
// This function is add new edge
void addEdge(struct MyGraph *graph, int a, int b)
{
    if (a < graph->size && b < graph->size)
    {
        // connect edge
        // a---->b
        connectEdge(graph, a, b);
    }
    else
    {
        //not valid Vertices
        printf("Invalid Node Vertices %d  %d", a, b);
    }
}
//Display Adjacency list of vertex
void printGraph(struct MyGraph *graph)
{
    if (graph->node != NULL)
    {
        struct AjlistNode *temp = NULL;
        // Loop controlling variable
        int i = 0;
        for (i = 0; i < graph->size; i++)
        {
            printf("\n Adjacency list of vertex %d  :", i);
            // Get first edge of [i] node
            temp = graph->node[i].edge;
            while (temp != NULL)
            {
                //temp->id is graph node vertices
                //in this case temp->id is same as 
                //node[temp->id].data
                printf("  %d", graph->node[temp->id].data);
                temp = temp->next;
            }
        }
    }
    else
    {
        printf("Empty GraphNode");
    }
}
void resetDefault(int visit[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        visit[i] = 0;
    }
}
// This function are detect loop in given source code
int isCyclic(struct MyGraph *graph, int visit[], int source, int current)
{
    if (source == current && visit[current] == 1)
    {
        // When loop exist
        return 1;
    }
    else if (visit[current] == 1)
    {
        // When intermediate node contains loop
        // back to previous process
        return 0;
    }
    struct AjlistNode *temp = graph->node[current].edge;
    // Active the visiting node status
    visit[current] = 1;
    // iterating the nodes edges
    while (temp != NULL)
    {
        if (isCyclic(graph, visit, source, temp->id) == 1)
        {
            // When source node contains cycle
            return 1;
        }
        // Visit to next edge
        temp = temp->next;
    }
    // Deactivate the current visiting node status
    visit[current] = 0;
    return 0;
}
void nonCyclicNode(struct MyGraph *graph)
{
    if (graph->size > 0)
    {
        int visit[graph->size];
        int cycle[graph->size];
        // Set that initial have no cyclic node
        resetDefault(cycle, graph->size);
        for (int i = 0; i < graph->size; ++i)
        {
            if (cycle[i] == 0)
            {
                resetDefault(visit, graph->size);
                // Check that
                if (isCyclic(graph, visit, i, i))
                {
                    // When i contain cycle 
                    // Then collect the cycle node 
                    for (int j = 0; j < graph->size; ++j)
                    {
                        if (visit[j] == 1)
                        {
                            // contain cycle
                            cycle[j] = 1;
                        }
                    }
                }
            }
        }
        // result counter
        int count = 0;
        printf("\n Result : ");
        // Print resultant node
        for (int j = 0; j < graph->size; ++j)
        {
            if (cycle[j] == 0)
            {
                // Count the number of resultant nodes
                count++;
                printf("  %d", j);
            }
        }
        if (count == 0)
        {
            // In case no result
            printf("\n None \n");
        }
    }
}
int main(int argc, char const *argv[])
{
    struct MyGraph *graph = newGraph(8);
    //Connected two node with Edges
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 4);
    addEdge(graph, 2, 7);
    addEdge(graph, 3, 2);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);
    addEdge(graph, 4, 2);
    addEdge(graph, 6, 2);
    addEdge(graph, 6, 4);
    addEdge(graph, 7, 0);
    printGraph(graph);
    nonCyclicNode(graph);
    return 0;
}

input

 Adjacency list of vertex 0  :  1
 Adjacency list of vertex 1  :  2
 Adjacency list of vertex 2  :  4  7
 Adjacency list of vertex 3  :  2  4  5
 Adjacency list of vertex 4  :  2
 Adjacency list of vertex 5  :
 Adjacency list of vertex 6  :  2  4
 Adjacency list of vertex 7  :  0
 Result :   3  5  6
/*
  Java Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode
{
	//Vertices id
	public int id;
	public AjlistNode next;
	public AjlistNode(int id)
	{
		this.id = id;
		this.next = null;
	}
}
// Define node of graph 
class GraphNode
{
	//node key value
	public int data;
	public AjlistNode edge;
	public GraphNode(int data)
	{
		this.data = data;
		this.edge = null;
	}
}
// Define structure of graph
public class MyGraph
{
	// Number of graph nodes
	public int size;
	public GraphNode[] node;
	public MyGraph(int size)
	{
		if (size < 0)
		{
			System.out.print("\n Invalid size of nodes " + size + " \n");
		}
		else
		{
			this.size = size;
			this.node = new GraphNode[this.size];
			int i = 0;
			// Set graph node level and e
			for (i = 0; i < this.size; i++)
			{
				this.node[i] = new GraphNode(i);
			}
		}
	}
	//This function are connect nodes with one edge 
	public void connectEdge(int a, int b)
	{
		if (this.size <= 0)
		{
			System.out.print("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		AjlistNode newEdge = new AjlistNode(b);
		if (newEdge != null)
		{
			// Get first edge of [i] node
			AjlistNode edge = this.node[a].edge;
			if (edge == null)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this.node[a].edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				// Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			System.out.print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes. \n");
		}
	}
	// This function is add new edge
	public void addEdge(int a, int b)
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			// connect edge
			// a---->b
			connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			System.out.print("Invalid Node Vertices " + a + " " + b);
		}
	}
	//Display Adjacency list of vertex
	public void printGraph()
	{
		if (this.size > 0)
		{
			AjlistNode temp = null;
			// Loop controlling variable
			int i = 0;
			for (i = 0; i < this.size; i++)
			{
				System.out.print("\n Adjacency list of vertex " + i + " :");
				// Get first edge of [i] node
				temp = this.node[i].edge;
				while (temp != null)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					System.out.print("  " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
		else
		{
			System.out.print("Empty Graph Node");
		}
	}
	public void resetDefault(boolean[] visit, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			visit[i] = false;
		}
	}
	// This function are detect loop in given source code
	public boolean isCyclic(boolean[] visit, int source, int current)
	{
		if (source == current && visit[current] == true)
		{
			// When loop exist
			return true;
		}
		else if (visit[current] == true)
		{
			// When intermediate node contains loop
			// back to previous process
			return false;
		}
		AjlistNode temp = this.node[current].edge;
		// Active the visiting node status
		visit[current] = true;
		// iterating the nodes edges
		while (temp != null)
		{
			if (isCyclic(visit, source, temp.id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp.next;
		}
		// Deactivate the current visiting node status
		visit[current] = false;
		return false;
	}
	public void nonCyclicNode()
	{
		if (this.size > 0)
		{
			boolean[] visit = new boolean[this.size];
			boolean[] cycle = new boolean[this.size];
			// Set that initial have no cyclic node
			resetDefault(cycle, this.size);
			for (int i = 0; i < this.size; ++i)
			{
				if (cycle[i] == false)
				{
					resetDefault(visit, this.size);
					// Check that cycle
					if (isCyclic(visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						for (int j = 0; j < this.size; ++j)
						{
							if (visit[j] == true)
							{
								// contain cycle
								cycle[j] = true;
							}
						}
					}
				}
			}
			// result counter
			int count = 0;
			System.out.print("\n Result : ");
			// Print resultant node
			for (int j = 0; j < this.size; ++j)
			{
				if (cycle[j] == false)
				{
					// Count the number of resultant nodes
					count++;
					System.out.print(" " + j);
				}
			}
			if (count == 0)
			{
				// In case no result
				System.out.print("\n None \n");
			}
		}
	}
	public static void main(String[] args)
	{
		// 8 is number of nodes
		MyGraph graph = new MyGraph(8);
		//Connected two node with Edges
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(2, 4);
		graph.addEdge(2, 7);
		graph.addEdge(3, 2);
		graph.addEdge(3, 4);
		graph.addEdge(3, 5);
		graph.addEdge(4, 2);
		graph.addEdge(6, 2);
		graph.addEdge(6, 4);
		graph.addEdge(7, 0);
		graph.printGraph();
		graph.nonCyclicNode();
	}
}

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode
{
	public:
	// Vertices id
	int id;
	AjlistNode *next;
	AjlistNode(int id)
	{
		this->id = id;
		this->next = NULL;
	}
};
// Define node of graph
class GraphNode
{
	public:
	// node key value
	int data;
	AjlistNode *edge;
	GraphNode()
	{
		this->data = 0;
		this->edge = NULL;
	}
	GraphNode(int data)
	{
		this->data = data;
		this->edge = NULL;
	}
};
// Define structure of graph
class MyGraph
{
	public:
	// Number of graph nodes
	int size;
	GraphNode *node;
	MyGraph(int size)
	{
		if (size < 0)
		{
			cout << "\n Invalid size of nodes " << size << " \n";
		}
		else
		{
			this->size = size;
			this->node = new GraphNode[this->size];
			int i = 0;
			//   Set graph node level and e
			i = 0;
			while (i < this->size)
			{
				this->node[i].data = i;
				this->node[i].edge = NULL;
				i++;
			}
		}
	}
	//This function are connect nodes with one edge 
	void connectEdge(int a, int b)
	{
		if (this->size <= 0)
		{
			cout << "\n Graph have no nodes \n";
			return;
		}
		// Create Adjacency node
		AjlistNode *newEdge = new AjlistNode(b);
		if (newEdge != NULL)
		{
			// Get first edge of [i] node
			AjlistNode *edge = this->node[a].edge;
			if (edge == NULL)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this->node[a].edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge->next != NULL)
				{
					edge = edge->next;
				}
				// Add edge at last position
				edge->next = newEdge;
			}
		}
		else
		{
			cout << "\nMemory overflow, when connect a new edge from ( " << a << " to " << b << " ) nodes. \n";
		}
	}
	// This function is add new edge
	void addEdge(int a, int b)
	{
		if (this->size > 0 && a < this->size && b < this->size)
		{
			// connect edge
			// a---->b
			this->connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			cout << "Invalid Node Vertices " << a << " " << b;
		}
	}
	//Display Adjacency list of vertex
	void printGraph()
	{
		if (this->size > 0)
		{
			AjlistNode *temp = NULL;
			// Loop controlling variable
			int i = 0;
			for (i = 0; i < this->size; i++)
			{
				cout << "\n Adjacency list of vertex " << i << " :";
				// Get first edge of [i] node
				temp = this->node[i].edge;
				while (temp != NULL)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					cout << "  " << this->node[temp->id].data;
					temp = temp->next;
				}
			}
		}
		else
		{
			cout << "Empty Graph Node";
		}
	}
	void resetDefault(bool visit[], int n)
	{
		for (int i = 0; i < n; ++i)
		{
			visit[i] = false;
		}
	}
	// This function are detect loop in given source code
	bool isCyclic(bool visit[], int source, int current)
	{
		if (source == current && visit[current] == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if (visit[current] == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		AjlistNode *temp = this->node[current].edge;
		// Active the visiting node status
		visit[current] = true;
		// iterating the nodes edges
		while (temp != NULL)
		{
			if (this->isCyclic(visit, source, temp->id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp->next;
		}
		// Deactivate the current visiting node status
		visit[current] = false;
		return false;
	}
	void nonCyclicNode()
	{
		if (this->size > 0)
		{
			bool visit[this->size];
			bool cycle[this->size];
			// Set that initial have no cyclic node
			this->resetDefault(cycle, this->size);
			for (int i = 0; i < this->size; ++i)
			{
				if (cycle[i] == false)
				{
					this->resetDefault(visit, this->size);
					// Check that cycle
					if (this->isCyclic(visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						for (int j = 0; j < this->size; ++j)
						{
							if (visit[j] == true)
							{
								// contain cycle
								cycle[j] = true;
							}
						}
					}
				}
			}
			// result counter
			int count = 0;
			cout << "\n Result : ";
			// Print resultant node
			for (int j = 0; j < this->size; ++j)
			{
				if (cycle[j] == false)
				{
					// Count the number of resultant nodes
					count++;
					cout << " " << j;
				}
			}
			if (count == 0)
			{
				// In case no result
				cout << "\n None \n";
			}
		}
	}
};
int main()
{
	// 8 is number of nodes
	MyGraph *graph = new MyGraph(8);
	//Connected two node with Edges
	graph->addEdge(0, 1);
	graph->addEdge(1, 2);
	graph->addEdge(2, 4);
	graph->addEdge(2, 7);
	graph->addEdge(3, 2);
	graph->addEdge(3, 4);
	graph->addEdge(3, 5);
	graph->addEdge(4, 2);
	graph->addEdge(6, 2);
	graph->addEdge(6, 4);
	graph->addEdge(7, 0);
	graph->printGraph();
	graph->nonCyclicNode();
	return 0;
}

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
// Include namespace system
using System;
/*
  Csharp Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
public class AjlistNode
{
	// Vertices id
	public int id;
	public AjlistNode next;
	public AjlistNode(int id)
	{
		this.id = id;
		this.next = null;
	}
}
// Define node of graph 
public class GraphNode
{
	// node key value
	public int data;
	public AjlistNode edge;
	public GraphNode(int data)
	{
		this.data = data;
		this.edge = null;
	}
}
// Define structure of graph
public class MyGraph
{
	// Number of graph nodes
	public int size;
	public GraphNode[] node;
	public MyGraph(int size)
	{
		if (size < 0)
		{
			Console.Write("\n Invalid size of nodes " + size + " \n");
		}
		else
		{
			this.size = size;
			this.node = new GraphNode[this.size];
			int i = 0;
			// Set graph node level and e
			for (i = 0; i < this.size; i++)
			{
				this.node[i] = new GraphNode(i);
			}
		}
	}
	//This function are connect nodes with one edge 
	public void connectEdge(int a, int b)
	{
		if (this.size <= 0)
		{
			Console.Write("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		AjlistNode newEdge = new AjlistNode(b);
		if (newEdge != null)
		{
			// Get first edge of [i] node
			AjlistNode edge = this.node[a].edge;
			if (edge == null)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this.node[a].edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				// Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			Console.Write("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes. \n");
		}
	}
	// This function is add new edge
	public void addEdge(int a, int b)
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			// connect edge
			// a---->b
			this.connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			Console.Write("Invalid Node Vertices " + a + " " + b);
		}
	}
	//Display Adjacency list of vertex
	public void printGraph()
	{
		if (this.size > 0)
		{
			AjlistNode temp = null;
			// Loop controlling variable
			int i = 0;
			for (i = 0; i < this.size; i++)
			{
				Console.Write("\n Adjacency list of vertex " + i + " :");
				// Get first edge of [i] node
				temp = this.node[i].edge;
				while (temp != null)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					Console.Write("  " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
		else
		{
			Console.Write("Empty Graph Node");
		}
	}
	public void resetDefault(Boolean[] visit, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			visit[i] = false;
		}
	}
	// This function are detect loop in given source code
	public Boolean isCyclic(Boolean[] visit, int source, int current)
	{
		if (source == current && visit[current] == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if (visit[current] == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		AjlistNode temp = this.node[current].edge;
		// Active the visiting node status
		visit[current] = true;
		// iterating the nodes edges
		while (temp != null)
		{
			if (this.isCyclic(visit, source, temp.id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp.next;
		}
		// Deactivate the current visiting node status
		visit[current] = false;
		return false;
	}
	public void nonCyclicNode()
	{
		if (this.size > 0)
		{
			Boolean[] visit = new Boolean[this.size];
			Boolean[] cycle = new Boolean[this.size];
			// Set that initial have no cyclic node
			this.resetDefault(cycle, this.size);
			for (int i = 0; i < this.size; ++i)
			{
				if (cycle[i] == false)
				{
					this.resetDefault(visit, this.size);
					// Check that cycle
					if (this.isCyclic(visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						for (int j = 0; j < this.size; ++j)
						{
							if (visit[j] == true)
							{
								// contain cycle
								cycle[j] = true;
							}
						}
					}
				}
			}
			// result counter
			int count = 0;
			Console.Write("\n Result : ");
			// Print resultant node
			for (int j = 0; j < this.size; ++j)
			{
				if (cycle[j] == false)
				{
					// Count the number of resultant nodes
					count++;
					Console.Write(" " + j);
				}
			}
			if (count == 0)
			{
				// In case no result
				Console.Write("\n None \n");
			}
		}
	}
	public static void Main(String[] args)
	{
		// 8 is number of nodes
		MyGraph graph = new MyGraph(8);
		//Connected two node with Edges
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(2, 4);
		graph.addEdge(2, 7);
		graph.addEdge(3, 2);
		graph.addEdge(3, 4);
		graph.addEdge(3, 5);
		graph.addEdge(4, 2);
		graph.addEdge(6, 2);
		graph.addEdge(6, 4);
		graph.addEdge(7, 0);
		graph.printGraph();
		graph.nonCyclicNode();
	}
}

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
<?php
/*
  Php Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode
{
	// Vertices id
	public $id;
	public $next;
	public	function __construct($id)
	{
		$this->id = $id;
		$this->next = NULL;
	}
}
// Define node of graph 
class GraphNode
{
	// node key value
	public $data;
	public $edge;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->edge = NULL;
	}
}
// Define structure of graph
class MyGraph
{
	// Number of graph nodes
	public $size;
	public $node;
	public	function __construct($size)
	{
		if ($size < 0)
		{
			echo("\n Invalid size of nodes ".$size." \n");
		}
		else
		{
			$this->size = $size;
			$this->node = array_fill(0, $this->size, NULL);
			$i = 0;
			// Set graph node level and e
			for ($i = 0; $i < $this->size; $i++)
			{
				$this->node[$i] = new GraphNode($i);
			}
		}
	}
	//This function are connect nodes with one edge 
	public	function connectEdge($a, $b)
	{
		if ($this->size <= 0)
		{
			echo("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		$newEdge = new AjlistNode($b);
		if ($newEdge != NULL)
		{
			// Get first edge of [i] node
			$edge = $this->node[$a]->edge;
			if ($edge == NULL)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				$this->node[$a]->edge = $newEdge;
			}
			else
			{
				//Find last location to add new edge
				while ($edge->next != NULL)
				{
					$edge = $edge->next;
				}
				// Add edge at last position
				$edge->next = $newEdge;
			}
		}
		else
		{
			echo("\nMemory overflow, when connect a new edge from ( ".$a.
				" to ".$b.
				" ) nodes. \n");
		}
	}
	// This function is add new edge
	public	function addEdge($a, $b)
	{
		if ($this->size > 0 && $a < $this->size && $b < $this->size)
		{
			// connect edge
			// a---->b
			$this->connectEdge($a, $b);
		}
		else
		{
			//not valid Vertices
			echo("Invalid Node Vertices ".$a.
				" ".$b);
		}
	}
	//Display Adjacency list of vertex
	public	function printGraph()
	{
		if ($this->size > 0)
		{
			$temp = NULL;
			
			for ($i = 0; $i < $this->size; $i++)
			{
				echo("\n Adjacency list of vertex ".$i.
					" :");
				// Get first edge of [i] node
				$temp = $this->node[$i]->edge;
				while ($temp != NULL)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					echo("  ".$this->node[$temp->id]->data);
					$temp = $temp->next;
				}
			}
		}
		else
		{
			echo("Empty Graph Node");
		}
	}
	public	function resetDefault(&$visit, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			$visit[$i] = false;
		}
	}
	// This function are detect loop in given source code
	public	function isCyclic(&$visit, $source, $current)
	{
		if ($source == $current && $visit[$current] == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if ($visit[$current] == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		$temp = $this->node[$current]->edge;
		// Active the visiting node status
		$visit[$current] = true;
		// iterating the nodes edges
		while ($temp != NULL)
		{
			if ($this->isCyclic($visit, $source, $temp->id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			$temp = $temp->next;
		}
		// Deactivate the current visiting node status
		$visit[$current] = false;
		return false;
	}
	public	function nonCyclicNode()
	{
		if ($this->size > 0)
		{
			$visit = array_fill(0, $this->size, false);
			$cycle = array_fill(0, $this->size, false);
			// Set that initial have no cyclic node
			$this->resetDefault($cycle, $this->size);
			for ($i = 0; $i < $this->size; ++$i)
			{
				if ($cycle[$i] == false)
				{
					$this->resetDefault($visit, $this->size);
					// Check that cycle
					if ($this->isCyclic($visit, $i, $i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						for ($j = 0; $j < $this->size; ++$j)
						{
							if ($visit[$j] == true)
							{
								// contain cycle
								$cycle[$j] = true;
							}
						}
					}
				}
			}
			// result counter
			$count = 0;
			echo("\n Result : ");
			// Print resultant node
			for ($j = 0; $j < $this->size; ++$j)
			{
				if ($cycle[$j] == false)
				{
					// Count the number of resultant nodes
					$count++;
					echo(" ".$j);
				}
			}
			if ($count == 0)
			{
				// In case no result
				echo("\n None \n");
			}
		}
	}
}

function main()
{
	// 8 is number of nodes
	$graph = new MyGraph(8);
	//Connected two node with Edges
	$graph->addEdge(0, 1);
	$graph->addEdge(1, 2);
	$graph->addEdge(2, 4);
	$graph->addEdge(2, 7);
	$graph->addEdge(3, 2);
	$graph->addEdge(3, 4);
	$graph->addEdge(3, 5);
	$graph->addEdge(4, 2);
	$graph->addEdge(6, 2);
	$graph->addEdge(6, 4);
	$graph->addEdge(7, 0);
	$graph->printGraph();
	$graph->nonCyclicNode();
}
main();

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
/*
  Node JS Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode
{
	constructor(id)
	{
		this.id = id;
		this.next = null;
	}
}
// Define node of graph 
class GraphNode
{
	constructor(data)
	{
		this.data = data;
		this.edge = null;
	}
}
// Define structure of graph
class MyGraph
{
	constructor(size)
	{
		if (size < 0)
		{
			process.stdout.write("\n Invalid size of nodes " + size + " \n");
		}
		else
		{
			this.size = size;
			this.node = Array(this.size).fill(null);
			var i = 0;
			// Set graph node level and e
			for (i = 0; i < this.size; i++)
			{
				this.node[i] = new GraphNode(i);
			}
		}
	}
	//This function are connect nodes with one edge 
	connectEdge(a, b)
	{
		if (this.size <= 0)
		{
			process.stdout.write("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		var newEdge = new AjlistNode(b);
		if (newEdge != null)
		{
			// Get first edge of [i] node
			var edge = this.node[a].edge;
			if (edge == null)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this.node[a].edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				// Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			process.stdout.write("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes. \n");
		}
	}
	// This function is add new edge
	addEdge(a, b)
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			// connect edge
			// a---->b
			this.connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			process.stdout.write("Invalid Node Vertices " + a + " " + b);
		}
	}
	//Display Adjacency list of vertex
	printGraph()
	{
		if (this.size > 0)
		{
			var temp = null;
			// Loop controlling variable
			var i = 0;
			for (i = 0; i < this.size; i++)
			{
				process.stdout.write("\n Adjacency list of vertex " + i + " :");
				// Get first edge of [i] node
				temp = this.node[i].edge;
				while (temp != null)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					process.stdout.write("  " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
		else
		{
			process.stdout.write("Empty Graph Node");
		}
	}
	resetDefault(visit, n)
	{
		for (var i = 0; i < n; ++i)
		{
			visit[i] = false;
		}
	}
	// This function are detect loop in given source code
	isCyclic(visit, source, current)
	{
		if (source == current && visit[current] == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if (visit[current] == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		var temp = this.node[current].edge;
		// Active the visiting node status
		visit[current] = true;
		// iterating the nodes edges
		while (temp != null)
		{
			if (this.isCyclic(visit, source, temp.id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp.next;
		}
		// Deactivate the current visiting node status
		visit[current] = false;
		return false;
	}
	nonCyclicNode()
	{
		if (this.size > 0)
		{
			var visit = Array(this.size).fill(false);
			var cycle = Array(this.size).fill(false);
			// Set that initial have no cyclic node
			this.resetDefault(cycle, this.size);
			for (var i = 0; i < this.size; ++i)
			{
				if (cycle[i] == false)
				{
					this.resetDefault(visit, this.size);
					// Check that cycle
					if (this.isCyclic(visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						for (var j = 0; j < this.size; ++j)
						{
							if (visit[j] == true)
							{
								// contain cycle
								cycle[j] = true;
							}
						}
					}
				}
			}
			// result counter
			var count = 0;
			process.stdout.write("\n Result : ");
			// Print resultant node
			for (var j = 0; j < this.size; ++j)
			{
				if (cycle[j] == false)
				{
					// Count the number of resultant nodes
					count++;
					process.stdout.write(" " + j);
				}
			}
			if (count == 0)
			{
				// In case no result
				process.stdout.write("\n None \n");
			}
		}
	}
}

function main()
{
	// 8 is number of nodes
	var graph = new MyGraph(8);
	//Connected two node with Edges
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(2, 4);
	graph.addEdge(2, 7);
	graph.addEdge(3, 2);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(4, 2);
	graph.addEdge(6, 2);
	graph.addEdge(6, 4);
	graph.addEdge(7, 0);
	graph.printGraph();
	graph.nonCyclicNode();
}
main();

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
#  Python 3 Program
#  Find nodes which are not part of any cycle in a directed graph

#  Define edge of graph node
class AjlistNode :
	#  Vertices id
	def __init__(self, id) :
		self.id = id
		self.next = None
	

#  Define node of graph 
class GraphNode :
	#  node key value
	def __init__(self, data) :
		self.data = data
		self.edge = None
	

#  Define structure of graph
class MyGraph :
	#  Number of graph nodes
	def __init__(self, size) :
		if (size < 0) :
			print("\n Invalid size of nodes ", size ," ")
		else :
			self.size = size
			self.node = [None] * (self.size)
			i = 0
			#  Set graph node level and e
			while (i < self.size) :
				self.node[i] = GraphNode(i)
				i += 1
			
		
	
	# This function are connect nodes with one edge 
	def connectEdge(self, a, b) :
		if (self.size <= 0) :
			print("\n Graph have no nodes ")
			return
		
		#  Create Adjacency node
		newEdge = AjlistNode(b)
		if (newEdge != None) :
			#  Get first edge of [i] node
			edge = self.node[a].edge
			if (edge == None) :
				#  Whe no edge of graph node [i] then
				#  Add a first edge of a [i] node
				self.node[a].edge = newEdge
			else :
				# Find last location to add new edge
				while (edge.next != None) :
					edge = edge.next
				
				#  Add edge at last position
				edge.next = newEdge
			
		else :
			print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes. ")
		
	
	#  This function is add new edge
	def addEdge(self, a, b) :
		if (self.size > 0 and a < self.size and b < self.size) :
			#  connect edge
			#  a---->b
			self.connectEdge(a, b)
		else :
			# not valid Vertices
			print("Invalid Node Vertices ", a ," ", b, end = "")
		
	
	# Display Adjacency list of vertex
	def printGraph(self) :
		if (self.size > 0) :
			temp = None
			#  Loop controlling variable
			i = 0
			i = 0
			while (i < self.size) :
				print("\n Adjacency list of vertex ", i ," :", end = "")
				#  Get first edge of [i] node
				temp = self.node[i].edge
				while (temp != None) :
					# temp->id is graph node vertices
					# in this case temp->id is same as 
					# node[temp->id].data
					print("  ", self.node[temp.id].data, end = "")
					temp = temp.next
				
				i += 1
			
		else :
			print("Empty Graph Node", end = "")
		
	
	def resetDefault(self, visit, n) :
		i = 0
		while (i < n) :
			visit[i] = False
			i += 1
		
	
	#  This function are detect loop in given source code
	def isCyclic(self, visit, source, current) :
		if (source == current and visit[current] == True) :
			#  When loop exist
			return True
		else :
			if (visit[current] == True) :
				#  When intermediate node contains loop
				#  back to previous process
				return False
			
		
		temp = self.node[current].edge
		#  Active the visiting node status
		visit[current] = True
		#  iterating the nodes edges
		while (temp != None) :
			if (self.isCyclic(visit, source, temp.id) == True) :
				#  When source node contains cycle
				return True
			
			#  Visit to next edge
			temp = temp.next
		
		#  Deactivate the current visiting node status
		visit[current] = False
		return False
	
	def nonCyclicNode(self) :
		if (self.size > 0) :
			visit = [False] * (self.size)
			cycle = [False] * (self.size)
			#  Set that initial have no cyclic node
			self.resetDefault(cycle, self.size)
			i = 0
			while (i < self.size) :
				if (cycle[i] == False) :
					self.resetDefault(visit, self.size)
					#  Check that cycle
					if (self.isCyclic(visit, i, i) == True) :
						#  When i contain cycle 
						#  Then collect the cycle node 
						j = 0
						while (j < self.size) :
							if (visit[j] == True) :
								#  contain cycle
								cycle[j] = True
							
							j += 1
						
					
				
				i += 1
			
			#  result counter
			count = 0
			print("\n Result : ", end = "")
			#  Print resultant node
			j = 0
			while (j < self.size) :
				if (cycle[j] == False) :
					#  Count the number of resultant nodes
					count += 1
					print(" ", j, end = "")
				
				j += 1
			
			if (count == 0) :
				#  In case no result
				print("\n None ")
			
		
	

def main() :
	#  8 is number of nodes
	graph = MyGraph(8)
	# Connected two node with Edges
	graph.addEdge(0, 1)
	graph.addEdge(1, 2)
	graph.addEdge(2, 4)
	graph.addEdge(2, 7)
	graph.addEdge(3, 2)
	graph.addEdge(3, 4)
	graph.addEdge(3, 5)
	graph.addEdge(4, 2)
	graph.addEdge(6, 2)
	graph.addEdge(6, 4)
	graph.addEdge(7, 0)
	graph.printGraph()
	graph.nonCyclicNode()

if __name__ == "__main__": main()

input

 Adjacency list of vertex  0  :   1
 Adjacency list of vertex  1  :   2
 Adjacency list of vertex  2  :   4   7
 Adjacency list of vertex  3  :   2   4   5
 Adjacency list of vertex  4  :   2
 Adjacency list of vertex  5  :
 Adjacency list of vertex  6  :   2   4
 Adjacency list of vertex  7  :   0
 Result :   3  5  6
#  Ruby Program
#  Find nodes which are not part of any cycle in a directed graph

#  Define edge of graph node
class AjlistNode 
	# Define the accessor and reader of class AjlistNode
	attr_reader :id, :next
	attr_accessor :id, :next
	#  Vertices id
	def initialize(id) 
		self.id = id
		self.next = nil
	end

end

#  Define node of graph 
class GraphNode 
	# Define the accessor and reader of class GraphNode
	attr_reader :data, :edge
	attr_accessor :data, :edge
	#  node key value
	def initialize(data) 
		self.data = data
		self.edge = nil
	end

end

#  Define structure of graph
class MyGraph 
	# Define the accessor and reader of class MyGraph
	attr_reader :size, :node
	attr_accessor :size, :node
	#  Number of graph nodes
	def initialize(size) 
		if (size < 0) 
			print("\n Invalid size of nodes ", size ," \n")
		else 
			self.size = size
			self.node = Array.new(self.size) {nil}
			i = 0
			#  Set graph node level and edge
			while (i < self.size) 
				self.node[i] = GraphNode.new(i)
				i += 1
			end

		end

	end

	# This function are connect nodes with one edge 
	def connectEdge(a, b) 
		if (self.size <= 0) 
			print("\n Graph have no nodes \n")
			return
		end

		#  Create Adjacency node
		newEdge = AjlistNode.new(b)
		if (newEdge != nil) 
			#  Get first edge of [i] node
			edge = self.node[a].edge
			if (edge == nil) 
				#  Whe no edge of graph node [i] then
				#  Add a first edge of a [i] node
				self.node[a].edge = newEdge
			else 
				# Find last location to add new edge
				while (edge.next != nil) 
					edge = edge.next
				end

				#  Add edge at last position
				edge.next = newEdge
			end

		else 
			print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes. \n")
		end

	end

	#  This function is add new edge
	def addEdge(a, b) 
		if (self.size > 0 && a < self.size && b < self.size) 
			#  connect edge
			#  a---->b
			self.connectEdge(a, b)
		else 
			# not valid Vertices
			print("Invalid Node Vertices ", a ," ", b)
		end

	end

	# Display Adjacency list of vertex
	def printGraph() 
		if (self.size > 0) 
			temp = nil
			#  Loop controlling variable
			i = 0
			i = 0
			while (i < self.size) 
				print("\n Adjacency list of vertex ", i ," :")
				#  Get first edge of [i] node
				temp = self.node[i].edge
				while (temp != nil) 
					# temp->id is graph node vertices
					# in this case temp->id is same as 
					# node[temp->id].data
					print("  ", self.node[temp.id].data)
					temp = temp.next
				end
				i += 1
			end

		else 
			print("Empty Graph Node")
		end

	end

	def resetDefault(visit, n) 
		i = 0
		while (i < n) 
			visit[i] = false
			i += 1
		end

	end

	#  This function are detect loop in given source code
	def isCyclic(visit, source, current) 
		if (source == current && visit[current] == true) 
			#  When loop exist
			return true
		else 
			if (visit[current] == true) 
				#  When intermediate node contains loop
				#  back to previous process
				return false
			end

		end

		temp = self.node[current].edge
		#  Active the visiting node status
		visit[current] = true
		#  iterating the nodes edges
		while (temp != nil) 
			if (self.isCyclic(visit, source, temp.id) == true) 
				#  When source node contains cycle
				return true
			end

			#  Visit to next edge
			temp = temp.next
		end

		#  Deactivate the current visiting node status
		visit[current] = false
		return false
	end

	def nonCyclicNode() 
		if (self.size > 0) 
			visit = Array.new(self.size) {false}
			cycle = Array.new(self.size) {false}
			#  Set that initial have no cyclic node
			self.resetDefault(cycle, self.size)
			i = 0
			while (i < self.size) 
				if (cycle[i] == false) 
					self.resetDefault(visit, self.size)
					#  Check that cycle
					if (self.isCyclic(visit, i, i) == true) 
						#  When i contain cycle 
						#  Then collect the cycle node 
						j = 0
						while (j < self.size) 
							if (visit[j] == true) 
								#  contain cycle
								cycle[j] = true
							end

							j += 1
						end

					end

				end

				i += 1
			end

			#  result counter
			count = 0
			print("\n Result : ")
			#  Print resultant node
			j = 0
			while (j < self.size) 
				if (cycle[j] == false) 
					#  Count the number of resultant nodes
					count += 1
					print(" ", j)
				end

				j += 1
			end

			if (count == 0) 
				#  In case no result
				print("\n None \n")
			end

		end

	end

end

def main() 
	#  8 is number of nodes
	graph = MyGraph.new(8)
	# Connected two node with Edges
	graph.addEdge(0, 1)
	graph.addEdge(1, 2)
	graph.addEdge(2, 4)
	graph.addEdge(2, 7)
	graph.addEdge(3, 2)
	graph.addEdge(3, 4)
	graph.addEdge(3, 5)
	graph.addEdge(4, 2)
	graph.addEdge(6, 2)
	graph.addEdge(6, 4)
	graph.addEdge(7, 0)
	graph.printGraph()
	graph.nonCyclicNode()
end

main()

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
/*
  Scala Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode(var id: Int , var next: AjlistNode)
{
	def this(id: Int)
	{
		this(id, null);
	}
}
// Define node of graph
class GraphNode(var data: Int , var edge: AjlistNode)
{
	def this(data: Int)
	{
		this(data, null);
	}
}
class MyGraph(var size: Int , var node: Array[GraphNode])
{
   def this(size: Int)
    {
        this(size, Array.fill[GraphNode](size)(null));

        if (size > 0)
        {
            var i: Int = 0;
            //  Set graph node level and e
            while (i < this.size)
            {
                this.node(i) = new GraphNode(i);
                i += 1;
            }
        }
    }
	//This function are connect nodes with one edge 
	def connectEdge(a: Int, b: Int): Unit = {
		if (this.size <= 0)
		{
			print("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		var newEdge: AjlistNode = new AjlistNode(b);
		if (newEdge != null)
		{
			// Get first edge of [i] node
			var edge: AjlistNode = this.node(a).edge;
			if (edge == null)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this.node(a).edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				// Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes. \n");
		}
	}
	// This function is add new edge
	def addEdge(a: Int, b: Int): Unit = {
		if (this.size > 0 && a < this.size && b < this.size)
		{
			// connect edge
			// a---->b
			connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			print("Invalid Node Vertices " + a + " " + b);
		}
	}
	//Display Adjacency list of vertex
	def printGraph(): Unit = {
		if (this.size > 0)
		{
			var temp: AjlistNode = null;
			// Loop controlling variable
			var i: Int = 0;
			while (i < this.size)
			{
				print("\n Adjacency list of vertex " + i + " :");
				// Get first edge of [i] node
				temp = this.node(i).edge;
				while (temp != null)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					print("  " + this.node(temp.id).data);
					temp = temp.next;
				}
				i += 1;
			}
		}
		else
		{
			print("Empty Graph Node");
		}
	}
	def resetDefault(visit: Array[Boolean], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			visit(i) = false;
			i += 1;
		}
	}
	// This function are detect loop in given source code
	def isCyclic(visit: Array[Boolean], source: Int, current: Int): Boolean = {
		if (source == current && visit(current) == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if (visit(current) == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		var temp: AjlistNode = this.node(current).edge;
		// Active the visiting node status
		visit(current) = true;
		// iterating the nodes edges
		while (temp != null)
		{
			if (isCyclic(visit, source, temp.id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp.next;
		}
		// Deactivate the current visiting node status
		visit(current) = false;
		return false;
	}
	def nonCyclicNode(): Unit = {
		if (this.size > 0)
		{
			var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
          	// Set that initial have no cyclic node
			var cycle: Array[Boolean] = Array.fill[Boolean](this.size)(false);
			var i: Int = 0;
			while (i < this.size)
			{
				if (cycle(i) == false)
				{
					resetDefault(visit, this.size);
					// Check that cycle
					if (isCyclic(visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						var j: Int = 0;
						while (j < this.size)
						{
							if (visit(j) == true)
							{
								// contain cycle
								cycle(j) = true;
							}
							j += 1;
						}
					}
				}
				i += 1;
			}
			// result counter
			var count: Int = 0;
			print("\n Result : ");
			// Print resultant node
			var j: Int = 0;
			while (j < this.size)
			{
				if (cycle(j) == false)
				{
					// Count the number of resultant nodes
					count += 1;
					print(" " + j);
				}
				j += 1;
			}
			if (count == 0)
			{
				// In case no result
				print("\n None \n");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// 8 is number of nodes
		var graph: MyGraph = new MyGraph(8);
		//Connected two node with Edges
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(2, 4);
		graph.addEdge(2, 7);
		graph.addEdge(3, 2);
		graph.addEdge(3, 4);
		graph.addEdge(3, 5);
		graph.addEdge(4, 2);
		graph.addEdge(6, 2);
		graph.addEdge(6, 4);
		graph.addEdge(7, 0);
		graph.printGraph();
		graph.nonCyclicNode();
	}
}

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
/*
  Swift 4 Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode
{
	//Vertices id
	var id: Int;
	var next: AjlistNode? ;
	init(_ id: Int)
	{
		self.id = id;
		self.next = nil;
	}
}
// Define node of graph
class GraphNode
{
	//node key value
	var data: Int;
	var edge: AjlistNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.edge = nil;
	}
}
class MyGraph
{
	// Number of graph nodes
	var size: Int;
	var node: [GraphNode? ];
	init(_ size: Int)
	{
		if (size < 0)
		{
			print("\n Invalid size of nodes ", size, " ");
			self.size = 0;
			self.node = Array(repeating: nil, count: 1);
		}
		else
		{
			self.size = size;
			self.node = Array(repeating: nil, count: self.size);
			var i: Int = 0;
			//   Set graph node level and e
			i = 0;
			while (i < self.size)
			{
				self.node[i] = GraphNode(i);
				i += 1;
			}
		}
	}
	//This function are connect nodes with one edge
	func connectEdge(_ a: Int, _ b: Int)
	{
		if (self.size <= 0)
		{
			print("\n Graph have no nodes ");
			return;
		}
		// Create Adjacency node
		let newEdge: AjlistNode? = AjlistNode(b);
		if (newEdge  != nil)
		{
			// Get first edge of [i] node
			var edge: AjlistNode? = self.node[a]!.edge;
			if (edge == nil)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				self.node[a]!.edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge!.next  != nil)
				{
					edge = edge!.next;
				}
				// Add edge at last position
				edge!.next = newEdge;
			}
		}
		else
		{
			print("\nMemory overflow, when connect a new edge from ( ", a, " to ", b, " ) nodes.");
		}
	}
	// This function is add new edge
	func addEdge(_ a: Int, _ b: Int)
	{
		if (self.size > 0 && a < self.size && b < self.size)
		{
			// connect edge
			// a---->b
			self.connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			print("Invalid Node Vertices ", a, " ", b, terminator: "");
		}
	}
	//Display Adjacency list of vertex
	func printGraph()
	{
		if (self.size > 0)
		{
			var temp: AjlistNode? = nil;
			// Loop controlling variable
			var i: Int = 0;
			i = 0;
			while (i < self.size)
			{
				print("\n Adjacency list of vertex ", i, " :", terminator: "");
				// Get first edge of [i] node
				temp = self.node[i]!.edge;
				while (temp  != nil)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					print("  ", self.node[temp!.id]!.data, terminator: "");
					temp = temp!.next;
				}
				i += 1;
			}
		}
		else
		{
			print("Empty Graph Node", terminator: "");
		}
	}
	func resetDefault(_ visit: inout[Bool], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			visit[i] = false;
			i += 1;
		}
	}
	// This function are detect loop in given source code
	func isCyclic(_ visit: inout[Bool], _ source: Int, _ current: Int)->Bool
	{
		if (source == current && visit[current] == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if (visit[current] == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		var temp: AjlistNode? = self.node[current]!.edge;
		// Active the visiting node status
		visit[current] = true;
		// iterating the nodes edges
		while (temp  != nil)
		{
			if (self.isCyclic(&visit, source, temp!.id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp!.next;
		}
		// Deactivate the current visiting node status
		visit[current] = false;
		return false;
	}
	func nonCyclicNode()
	{
		if (self.size > 0)
		{
			var visit: [Bool] = Array(repeating: false, count: self.size);
          	// Set that initial have no cyclic node
			var cycle: [Bool] = Array(repeating: false, count: self.size);
		
	
			var i: Int = 0;
			while (i < self.size)
			{
				if (cycle[i] == false)
				{
					self.resetDefault(&visit, self.size);
					// Check that cycle
					if (self.isCyclic(&visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						var j: Int = 0;
						while (j < self.size)
						{
							if (visit[j] == true)
							{
								// contain cycle
								cycle[j] = true;
							}
							j += 1;
						}
					}
				}
				i += 1;
			}
			// result counter
			var count: Int = 0;
			print("\n Result : ", terminator: "");
			// Print resultant node
			var j: Int = 0;
			while (j < self.size)
			{
				if (cycle[j] == false)
				{
					// Count the number of resultant nodes
					count += 1;
					print(" ", j, terminator: "");
				}
				j += 1;
			}
			if (count == 0)
			{
				// In case no result
				print("\n None ");
			}
		}
	}
}
func main()
{
	// 8 is number of nodes
	let graph: MyGraph = MyGraph(8);
	//Connected two node with Edges
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(2, 4);
	graph.addEdge(2, 7);
	graph.addEdge(3, 2);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(4, 2);
	graph.addEdge(6, 2);
	graph.addEdge(6, 4);
	graph.addEdge(7, 0);
	graph.printGraph();
	graph.nonCyclicNode();
}
main();

input

 Adjacency list of vertex  0  :   1
 Adjacency list of vertex  1  :   2
 Adjacency list of vertex  2  :   4   7
 Adjacency list of vertex  3  :   2   4   5
 Adjacency list of vertex  4  :   2
 Adjacency list of vertex  5  :
 Adjacency list of vertex  6  :   2   4
 Adjacency list of vertex  7  :   0
 Result :   3  5  6
/*
  Kotlin Program
  Find nodes which are not part of any cycle in a directed graph
*/
// Define edge of graph node
class AjlistNode
{
	// Vertices id
	var id: Int;
	var next: AjlistNode ? ;
	constructor(id: Int)
	{
		this.id = id;
		this.next = null;
	}
}
// Define node of graph 
class GraphNode
{
	// node key value
	var data: Int;
	var edge: AjlistNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.edge = null;
	}
}
class MyGraph
{
    var size: Int;
    var node: Array<GraphNode?>;
    constructor(size: Int)
    {
        if (size < 0)
        {
            print("\n Invalid size of nodes " + size + " \n");
            this.size = 0;
            this.node = Array(1)
            {
                null
            };
        }
        else
        {
            this.size = size;
            this.node = Array(this.size)
            {
                null
            };
            var i: Int = 0;
            //   Set graph node level and e
            while (i<this.size)
            {
                this.node[i] = GraphNode(i);
                i += 1;
            }
        }
    }
	//This function are connect nodes with one edge
	fun connectEdge(a: Int, b: Int): Unit
	{
		if (this.size <= 0)
		{
			print("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		var newEdge: AjlistNode ? = AjlistNode(b);
		if (newEdge != null)
		{
			// Get first edge of [i] node
			var edge: AjlistNode ? = this.node[a]?.edge;
			if (edge == null)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this.node[a]?.edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge?.next != null)
				{
					edge = edge.next;
				}
				// Add edge at last position
				edge?.next = newEdge;
			}
		}
		else
		{
			print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
		}
	}
	// This is handles the request of connecting Edges between given node a to b
	fun addEdge(a: Int, b: Int): Unit
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			// connect edge
			// a---->b
			this.connectEdge(a, b);
		}
		else
		{
			//not valid Vertices
			print("Invalid Node Vertices " + a + " " + b);
		}
	}
	//Display Adjacency list of vertex
	fun printGraph(): Unit
	{
		if (this.size > 0)
		{
			var temp: AjlistNode ? ;
			// Loop controlling variable
			var i: Int = 0;
			while (i < this.size)
			{
				print("\n Adjacency list of vertex " + i + " :");
				// Get first edge of [i] node
				temp = this.node[i]?.edge;
				while (temp != null)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as
					//node[temp->id].data
					print("  " + this.node[temp.id]?.data);
					temp = temp.next;
				}
				i += 1;
			}
		}
		else
		{
			print("Empty Graph Node");
		}
	}
	fun resetDefault(visit: Array < Boolean > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			visit[i] = false;
			i += 1;
		}
	}
	// This function are detect loop in given source code
	fun isCyclic(visit: Array < Boolean > , source: Int, current: Int): Boolean
	{
		if (source == current && visit[current] == true)
		{
			// When loop exist
			return true;
		}
		else
		{
			if (visit[current] == true)
			{
				// When intermediate node contains loop
				// back to previous process
				return false;
			}
		}
		var temp: AjlistNode ? = this.node[current]?.edge;
		// Active the visiting node status
		visit[current] = true;
		// iterating the nodes edges
		while (temp != null)
		{
			if (this.isCyclic(visit, source, temp.id) == true)
			{
				// When source node contains cycle
				return true;
			}
			// Visit to next edge
			temp = temp.next;
		}
		// Deactivate the current visiting node status
		visit[current] = false;
		return false;
	}
	fun nonCyclicNode(): Unit
	{
		if (this.size > 0)
		{
			val visit: Array < Boolean > = Array(this.size)
			{
				false
			};
          	// Set that initial have no cyclic node
			val cycle: Array < Boolean > = Array(this.size)
			{
				false
			};
			
			
			var i: Int = 0;
			while (i < this.size)
			{
				if (cycle[i] == false)
				{
					this.resetDefault(visit, this.size);
					// Check that cycle
					if (this.isCyclic(visit, i, i) == true)
					{
						// When i contain cycle 
						// Then collect the cycle node 
						var j: Int = 0;
						while (j < this.size)
						{
							if (visit[j] == true)
							{
								// contain cycle
								cycle[j] = true;
							}
							j += 1;
						}
					}
				}
				i += 1;
			}
			// result counter
			var count: Int = 0;
			print("\n Result : ");
			// Print resultant node
			var j: Int = 0;
			while (j < this.size)
			{
				if (cycle[j] == false)
				{
					// Count the number of resultant nodes
					count += 1;
					print(" " + j);
				}
				j += 1;
			}
			if (count == 0)
			{
				// In case no result
				print("\n None \n");
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// 8 is number of nodes
	val graph: MyGraph = MyGraph(8);
	//Connected two node with Edges
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(2, 4);
	graph.addEdge(2, 7);
	graph.addEdge(3, 2);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(4, 2);
	graph.addEdge(6, 2);
	graph.addEdge(6, 4);
	graph.addEdge(7, 0);
	graph.printGraph();
	graph.nonCyclicNode();
}

input

 Adjacency list of vertex 0 :  1
 Adjacency list of vertex 1 :  2
 Adjacency list of vertex 2 :  4  7
 Adjacency list of vertex 3 :  2  4  5
 Adjacency list of vertex 4 :  2
 Adjacency list of vertex 5 :
 Adjacency list of vertex 6 :  2  4
 Adjacency list of vertex 7 :  0
 Result :  3 5 6
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment