FilesExpand file tree

 master

/

Graphs.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

133 lines (119 loc) · 4.04 KB

 master

/

Graphs.java

Top

File metadata and controls

• Code
• Blame

133 lines (119 loc) · 4.04 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

130

131

132

133

package DataStructures.Graphs;

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

*/

@Override

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);

}

}