GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Java/Data Structures/Graphs/Graphs.java at master · fishinhouse/Java

Expand file tree

/

Graphs.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
129 lines (117 loc) · 3.98 KB
/

Graphs.java

Copy path

File metadata and controls

129 lines (117 loc) · 3.98 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.ArrayList;
import java.lang.StringBuilder;
class AdjacencyListGraph<E extends Comparable<E>> {
ArrayList<Vertex> verticies;
public AdjacencyListGraph() {
verticies = new ArrayList<>();
}
private class Vertex {
E data;
ArrayList<Vertex> adjacentVerticies;
public Vertex(E data) {
adjacentVerticies = new ArrayList<>();
this.data = data;
}
public boolean addAdjacentVertex(Vertex to) {
for (Vertex v: adjacentVerticies) {
if (v.data.compareTo(to.data) == 0) {
return false; // the edge already exists
}
}
return adjacentVerticies.add(to); // this will return true;
}
public boolean removeAdjacentVertex(E to) {
// use indexes here so it is possible to
// remove easily without implementing
// equals method that ArrayList.remove(Object o) uses
for (int i = 0; i < adjacentVerticies.size(); i++) {
if (adjacentVerticies.get(i).data.compareTo(to) == 0) {
adjacentVerticies.remove(i);
return true;
}
}
return false;
}
}
/**
* this method removes an edge from the graph between two specified
* verticies
*
* @param from the data of the vertex the edge is from
* @param to the data of the vertex the edge is going to
* @return returns false if the edge doesn't exist, returns true if the edge exists and is removed
*/
public boolean removeEdge(E from, E to) {
Vertex fromV = null;
for (Vertex v: verticies) {
if (from.compareTo(v.data) == 0) {
fromV = v;
break;
}
}
if (fromV == null) return false;
return fromV.removeAdjacentVertex(to);
}
/**
* this method adds an edge to the graph between two specified
* verticies
*
* @param from the data of the vertex the edge is from
* @param to the data of the vertex the edge is going to
* @return returns true if the edge did not exist, return false if it already did
*/
public boolean addEdge(E from, E to) {
Vertex fromV = null, toV = null;
for (Vertex v: verticies) {
if (from.compareTo(v.data) == 0) { // see if from vertex already exists
fromV = v;
} else if (to.compareTo(v.data) == 0) { // see if to vertex already exists
toV = v;
}
if (fromV != null && toV != null) break; // both nodes exist so stop searching
}
if (fromV == null) {
fromV = new Vertex(from);
verticies.add(fromV);
}
if (toV == null) {
toV = new Vertex(to);
verticies.add(toV);
}
return fromV.addAdjacentVertex(toV);
}
/**
* this gives a list of verticies in the graph and their adjacencies
*
* @return returns a string describing this graph
*/
public String toString() {
StringBuilder sb = new StringBuilder();
for (Vertex v: verticies) {
sb.append("Vertex: ");
sb.append(v.data);
sb.append("\n");
sb.append("Adjacent verticies: ");
for (Vertex v2: v.adjacentVerticies) {
sb.append(v2.data);
sb.append(" ");
}
sb.append("\n");
}
return sb.toString();
}
}
public class Graphs {
public static void main(String args[]) {
AdjacencyListGraph<Integer> graph = new AdjacencyListGraph<>();
assert graph.addEdge(1, 2);
assert graph.addEdge(1, 5);
assert graph.addEdge(2, 5);
assert !graph.addEdge(1, 2);
assert graph.addEdge(2, 3);
assert graph.addEdge(3, 4);
assert graph.addEdge(4, 1);
assert !graph.addEdge(2, 3);
System.out.println(graph);
}
}
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.