-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathSinkOfGraph.java
More file actions
executable file
·61 lines (51 loc) · 1.95 KB
/
SinkOfGraph.java
File metadata and controls
executable file
·61 lines (51 loc) · 1.95 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* Author: Kevin Richardson <[email protected]>
* Date: 11/17/11
* Time: 7:21 AM
*
* Methods for determining the sink of a graph. This class assumes each graph has exactly one sync and that
* all other nodes point to the sink.
*/
import java.util.Scanner;
public class SinkOfGraph
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Create a new unweighted, directed graph based off specified input file.
System.out.print("Name of unweighted, directed graph file: ");
UnweightedMatrixGraph graph = new UnweightedMatrixGraph(scanner.nextLine());
// Find the sink of the graph.
System.out.println("Sink of this graph: " + findSink(graph));
}
// Returns the sink of the specified graph.
public static int findSink(UnweightedMatrixGraph graph)
{
// If we only have one node, it must be the sink.
if(graph.table.length == 1){ return 0; }
// Store the last node in the table (so we know when to stop examining).
int lastNode = graph.table.length - 1;
// The nodes to initially examine (first and second).
int origin = 0;
int destination = 1;
// Examine nodes until the sink is found.
while(true)
{
// Final possibilities for sink:
// originNode == lastNode (lastNode is the sink)
// destination > lastNode (origin is the sink)
if(origin == lastNode){ return lastNode; }
else if(destination > lastNode){ return origin; }
// Does origin connect to destination? If so, it is not the sink.
if(graph.table[origin][destination] == 1)
{
origin++;
}
// If it does not, destination is not the sink.
else
{
destination++;
}
}
}
}