Find nodes which are not part of any cycle in a directed graph
In a directed graph, a cycle is a path that starts and ends at the same node. Therefore, nodes that are not part of any cycle in a directed graph are those that do not belong to any path that starts and ends at the same node.
If a node has no incoming edges, then it is a candidate for being part of a cycle since it cannot be reached from any other node.
Program Solution
// 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
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