blob: 2c7ba08820739be44f70472ac65cae211022bfdc (
plain)
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
|
package bjc.utils.graph;
import java.util.*;
/**
* A basic implementation of a directed algebraic graph.
*
* @author bjcul
*
* @param <Vertex> The type of the vertices
*/
public class SimpleAlgGraph<Vertex> implements AlgGraph<Vertex, SimpleAlgGraph<?>> {
// TODO: consider if some function for labeling edges would make sense
private Set<Vertex> vertices;
private Map<Vertex, Vertex> edges;
/**
* Create a new empty graph.
*/
public SimpleAlgGraph() {
vertices = new HashSet<>();
edges = new HashMap<>();
}
/**
* Create a new graph with the given vertices, but no edges.
*
* @param vertexes The vertices for the graph.
*/
@SafeVarargs
public SimpleAlgGraph(Vertex... vertexes) {
this();
for (Vertex vertex : vertexes)
vertices.add(vertex);
}
@Override
public <B> SimpleAlgGraph<B> empty() {
return new SimpleAlgGraph<>();
}
@Override
public <B> SimpleAlgGraph<B> vertex(B val) {
return new SimpleAlgGraph<>();
}
/**
* Overlay a graph onto this one, adding its vertices and edges.
*
* @param other The graph to overlay
*/
@Override
public void overlay(AlgGraph<Vertex, SimpleAlgGraph<?>> other) {
SimpleAlgGraph<Vertex> graph = (SimpleAlgGraph<Vertex>) other;
vertices.addAll(graph.vertices);
edges.putAll(graph.edges);
}
/**
* Connect a graph to this one, adding its vertices and edges; as well as
* establishing an edge from each node in this graph, to each node in the other
* graph.
*
* @param other The graph to connect
*/
@Override
public void connect(AlgGraph<Vertex, SimpleAlgGraph<?>> other) {
SimpleAlgGraph<Vertex> graph = (SimpleAlgGraph<Vertex>) other;
// note: this could be inefficent for large graphs
for (Vertex left : vertices) {
for (Vertex right : graph.vertices) {
edges.put(left, right);
}
}
overlay(other);
}
}
|
