Vocabulary and Definitions
Vertex
A vertex (also called a “node”) is a fundamental part of a graph. It can have a name, which we will call the “key.” A vertex may also have additional information. We will call this additional information the “payload.”
Edge
An edge (also called an “arc”) is another fundamental part of a graph. An edge connects two vertices to show that there is a relationship between them. Edges may be one-way or two-way. If the edges in a graph are all one-way, we say that the graph is a directed graph, or a digraph.
Weight
Edges may be weighted to show that there is a cost to go from one vertex to another. For example in a graph of roads that connect one city to another, the weight on the edge might represent the distance between the two cities.
Path
A path in a graph is a sequence of vertices that are connected by edges.
Cycle
A cycle in a directed graph is a path that starts and ends at the same vertex.
Implementation
An Adjacency Matrix
One of the easiest ways to implement a graph is to use a two-dimensional matrix. In this matrix implementation, each of the rows and columns represent a vertex in the graph. The value that is stored in the cell at the intersection of row v and column w indicates if there is an edge from vertex v to vertex w. When two vertices are connected by an edge, we say that they are adjacent.
The advantage of the adjacency matrix is that it is simple, and for small graphs it is easy to see which nodes are connected to other nodes. However, notice that most of the cells in the matrix are empty. Because most of the cells are empty we say that this matrix is “sparse.” A matrix is not a very efficient way to store sparse data.
An Adjacency List
A more space-efficient way to implement a sparsely connected graph is to use an adjacency list. In an adjacency list implementation we keep a master list of all the vertices in the Graph object and then each vertex object in the graph maintains a list of the other vertices that it is connected to.
The advantage of the adjacency list implementation is that it allows us to compactly represent a sparse graph. The adjacency list also allows us to easily find all the links that are directly connected to a particular vertex.
Basic Graph Operations
Following code represents the implementation of Vertix for a graph in generics.
public class Vertix<V> {
private V value;
private boolean visited;
public Vertix(V value) {
this.visited = false;
this.value = value;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
@Override
public boolean equals(Object that) {
if (that == null) {
return false;
} else if (that instanceof Vertix) {
return (((Vertix<?>) that).getValue().equals(this.getValue()));
}
return false;
}
@Override
public String toString() {
return String.valueOf(this.getValue());
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import uk.ac.soton.ecs.datastructure.queue.Queue;
public class AdjacencyListGraph<V> {
private Map<Vertix<V>, List<Vertix<V>>> adjacencyList;
public AdjacencyListGraph() {
this.adjacencyList = new HashMap<Vertix<V>, List<Vertix<V>>>();
}
}
Adding a Vertex
public Vertix<V> addVertex(V value) {
if (value == null) {
return null;
}
Vertix<V> newVertix = new Vertix<V>(value);
adjacencyList.put(newVertix, new ArrayList<Vertix<V>>());
return newVertix;
}
Getting a Vertex
Provided that the input to this method (value) is unique in the graph. This method returns back the first occurrence of the vertex or null.
public Vertix<V> getVertex(V value) {
if (value == null) {
return null;
}
for (Vertix<V> v : adjacencyList.keySet()) {
if (v.getValue().equals(value)) {
return v;
}
}
return null;
}
Adding an Edge
public int addEdge(Vertix<V> from, Vertix<V> to) {
if (from == null || to == null) {
return -1;
}
if (!adjacencyList.containsKey(from) || !adjacencyList.containsKey(to)) {
return -1;
}
adjacencyList.get(from).add(to);
return 1;
}
Checking if a graph has an edge
public boolean hasEdge(Vertix<V> from, Vertix<V> to) {
if (from == null || to == null) {
return false;
}
if (!adjacencyList.containsKey(from) || !adjacencyList.containsKey(to)) {
return false;
}
for (Vertix<V> t : adjacencyList.get(from)) {
if (t.equals(to)) {
return true;
}
}
return false;
}
Retrieve all out edges from a vertex
public List<Vertix<V>> outEdges(Vertix<V> vertix) {
List<Vertix<V>> edges = new ArrayList<Vertix<V>>();
for (Vertix<V> to : adjacencyList.get(vertix)) {
edges.add(to);
}
return edges;
}
Retrieve all in edges to a vertex
public List<Vertix<V>> inEdges(Vertix<V> vertix) {
Set<Vertix<V>> keys = adjacencyList.keySet();
List<Vertix<V>> edges = new ArrayList<Vertix<V>>();
for (Vertix<V> key : keys) {
if (adjacencyList.get(key).contains(vertix)) {
edges.add(key);
}
}
return edges;
}
Depth First Search from a vertex to another
public List<Vertix<V>> getDFSPath(Vertix<V> from, Vertix<V> to) {
resetVerticesVisibility();
List<Vertix<V>> DFSPath = new ArrayList<Vertix<V>>();
getDFSPath(from, to, DFSPath);
if (DFSPath.isEmpty()) {
return null;
} else {
return DFSPath;
}
}
private void getDFSPath(Vertix<V> from, Vertix<V> to,
List<Vertix<V>> DFSPath) {
DFSPath.add(from);
from.setVisited(true);
if (from.equals(to)) {
return;
}
for (Vertix<V> middle : adjacencyList.get(from)) {
if (!middle.isVisited()) {
getDFSPath(middle, to, DFSPath);
}
if (DFSPath.get(DFSPath.size() - 1).equals(to)) {
return;
}
}
DFSPath.remove(from);
}
Breadth First Search from a vertex to another
public List<Vertix<V>> getBFSPath(Vertix<V> from, Vertix<V> to) {
resetVerticesVisibility();
List<Vertix<V>> BFSPath = new ArrayList<Vertix<V>>();
Queue<Vertix<V>> queue = new Queue<Vertix<V>>();
queue.enqueue(from);
BFSPath.add(from);
from.setVisited(true);
while (!queue.isEmpty()) {
Vertix<V> middle = queue.dequeue();
if (middle.equals(to)) {
break;
}
for (Vertix<V> v : adjacencyList.get(middle)) {
if (!v.isVisited()) {
BFSPath.add(v);
v.setVisited(true);
queue.enqueue(v);
}
}
}
return BFSPath;
}
Evaluation
Complexity Analysis
| Functionality | Complexity (Adjacency list) | Complexity (Adjacency matrix) |
|---|---|---|
| Storage | O(|V|+|E|) | O(|V|^2) |
| Add vertex | O(1) | O(|V|^2) |
| Add edge | O(1) | O(1) |
| Remove vertex | O(|E|) | O(|V|^2) |
| Remove edge | O(|E|) | O(1) |
Advantages
Disadvantages
Source Code
public class Vertix<V> {
private V value;
private boolean visited;
public Vertix(V value) {
this.visited = false;
this.value = value;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
@Override
public boolean equals(Object that) {
if (that == null) {
return false;
} else if (that instanceof Vertix) {
return (((Vertix<?>) that).getValue().equals(this.getValue()));
}
return false;
}
@Override
public String toString() {
return String.valueOf(this.getValue());
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import uk.ac.soton.ecs.datastructure.queue.Queue;
public class AdjacencyListGraph<V> {
private Map<Vertix<V>, List<Vertix<V>>> adjacencyList;
public AdjacencyListGraph() {
this.adjacencyList = new HashMap<Vertix<V>, List<Vertix<V>>>();
}
public Vertix<V> addVertex(V value) {
if (value == null) {
return null;
}
Vertix<V> newVertix = new Vertix<V>(value);
adjacencyList.put(newVertix, new ArrayList<Vertix<V>>());
return newVertix;
}
public int addEdge(Vertix<V> from, Vertix<V> to) {
if (from == null || to == null) {
return -1;
}
if (!adjacencyList.containsKey(from) || !adjacencyList.containsKey(to)) {
return -1;
}
adjacencyList.get(from).add(to);
return 1;
}
public boolean hasEdge(Vertix<V> from, Vertix<V> to) {
if (from == null || to == null) {
return false;
}
if (!adjacencyList.containsKey(from) || !adjacencyList.containsKey(to)) {
return false;
}
for (Vertix<V> t : adjacencyList.get(from)) {
if (t.equals(to)) {
return true;
}
}
return false;
}
public List<Vertix<V>> outEdges(Vertix<V> vertix) {
List<Vertix<V>> edges = new ArrayList<Vertix<V>>();
for (Vertix<V> to : adjacencyList.get(vertix)) {
edges.add(to);
}
return edges;
}
public List<Vertix<V>> inEdges(Vertix<V> vertix) {
Set<Vertix<V>> keys = adjacencyList.keySet();
List<Vertix<V>> edges = new ArrayList<Vertix<V>>();
for (Vertix<V> key : keys) {
if (adjacencyList.get(key).contains(vertix)) {
edges.add(key);
}
}
return edges;
}
public List<Vertix<V>> getDFSPath(Vertix<V> from, Vertix<V> to) {
resetVerticesVisibility();
List<Vertix<V>> DFSPath = new ArrayList<Vertix<V>>();
getDFSPath(from, to, DFSPath);
if (DFSPath.isEmpty()) {
return null;
} else {
return DFSPath;
}
}
public List<Vertix<V>> getBFSPath(Vertix<V> from, Vertix<V> to) {
resetVerticesVisibility();
List<Vertix<V>> BFSPath = new ArrayList<Vertix<V>>();
Queue<Vertix<V>> queue = new Queue<Vertix<V>>();
queue.enqueue(from);
BFSPath.add(from);
from.setVisited(true);
while (!queue.isEmpty()) {
Vertix<V> middle = queue.dequeue();
if (middle.equals(to)) {
break;
}
for (Vertix<V> v : adjacencyList.get(middle)) {
if (!v.isVisited()) {
BFSPath.add(v);
v.setVisited(true);
queue.enqueue(v);
}
}
}
return BFSPath;
}
private void getDFSPath(Vertix<V> from, Vertix<V> to,
List<Vertix<V>> DFSPath) {
DFSPath.add(from);
from.setVisited(true);
if (from.equals(to)) {
return;
}
for (Vertix<V> middle : adjacencyList.get(from)) {
if (!middle.isVisited()) {
getDFSPath(middle, to, DFSPath);
}
if (DFSPath.get(DFSPath.size() - 1).equals(to)) {
return;
}
}
DFSPath.remove(from);
}
private void resetVerticesVisibility() {
for (Vertix<V> vertix : adjacencyList.keySet()) {
vertix.setVisited(false);
}
}
@Override
public String toString() {
Set<Vertix<V>> keys = adjacencyList.keySet();
String str = "";
for (Vertix<V> v : keys) {
str += v.getValue() + ": ";
List<Vertix<V>> edgeList = adjacencyList.get(v);
for (Vertix<V> edge : edgeList) {
str += edge.getValue() + " ";
}
str += "\n";
}
return str;
}
}
JUnit Test
import static org.junit.Assert.assertTrue;
import java.util.List;
import org.junit.Test;
public class AdjacencyListGraphTest {
@Test
public void testAdjacencyListGraph() {
AdjacencyListGraph<String> names = new AdjacencyListGraph<String>();
Vertix<String> v1 = names.addVertex("v1");
Vertix<String> v2 = names.addVertex("v2");
Vertix<String> v3 = names.addVertex("v3");
Vertix<String> v4 = names.addVertex("v4");
Vertix<String> v5 = names.addVertex("v5");
Vertix<String> v6 = names.addVertex("v6");
Vertix<String> v7 = names.addVertex("v7");
names.addEdge(v3, v1);
names.addEdge(v3, v2);
names.addEdge(v4, v1);
names.addEdge(v4, v2);
names.addEdge(v5, v1);
names.addEdge(v5, v2);
names.addEdge(v6, v4);
names.addEdge(v7, v4);
System.out.println("DFS:");
List<Vertix<String>> DFS = names.getDFSPath(v7, v1);
for (Vertix<String> p : DFS) {
System.out.print(p.toString() + "->");
}
System.out.println();
System.out.println("BFS:");
List<Vertix<String>> BFS = names.getBFSPath(v7, v1);
for (Vertix<String> p : BFS) {
System.out.print(p.toString() + "->");
}
System.out.println();
assertTrue(names.hasEdge(v3, v1));
assertTrue(3 == names.inEdges(v1).size());
assertTrue(2 == names.outEdges(v4).size());
System.out.println(names.toString());
}
}
No comments:
Post a Comment