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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
package bjc.utils.graph;
import java.util.*;
import java.util.function.Function;
import bjc.data.Pair;
import bjc.esodata.*;
import bjc.funcdata.Freezable;
import bjc.funcdata.ObjectFrozen;
import bjc.functypes.Unit;
public class ASGraph<Node, Value, Label> implements Freezable<ASGraph<Node, Value, Label>> {
private Set<Node> nodes;
private Function<Node, Value> nodeValuer;
private PairMap<Node, Node, Label> arcMap;
// Used for implementation efficiency
private Multimap<Node, Value> nodeToValue;
private Multimap<Value, Node> valueToNode;
private boolean frozen;
private boolean deepFrozen;
public ASGraph(Function<Node, Value> valuer) {
this.nodes = new HashSet<>();
this.nodeValuer = valuer;
this.arcMap = new PairMap<>();
this.nodeToValue = new TSetMultimap<>();
this.valueToNode = new TSetMultimap<>();
}
/**
* Retrieve a read-only view of the nodes
*
* @return A read-only set of the nodes.
*/
public Set<Node> getNodes() {
return Collections.unmodifiableSet(nodes);
}
/**
* Get the value for a node in the graph.
*
* @param nd The node to check.
*
* @return The value for that node.
*/
public Value getValue(Node nd) {
return nodeValuer.apply(nd);
}
/**
* Add a node to the graph.
*
* @param nd The node to add.
*/
public void addNode(Node nd) {
if (deepFrozen)
throw new ObjectFrozen();
this.nodes.add(nd);
Value v = nodeValuer.apply(nd);
this.nodeToValue.add(nd, v);
this.valueToNode.add(v, nd);
}
/**
* Remove a node from the graph.
*
* @param nd The node to remove
*/
public void removeNode(Node nd) {
if (deepFrozen)
throw new ObjectFrozen();
this.nodes.remove(nd);
Value v = nodeValuer.apply(nd);
this.nodeToValue.remove(nd);
this.valueToNode.remove(v, nd);
}
/**
* Add an arc to the graph.
*
* Note that badness can happen if you add a arc that refers to nodes not in the
* graph.
*
* @param nd1 The source node for the arc.
* @param nd2 The destination node for the arc.
* @param lab The label for the arc.
*/
public void addArc(Node nd1, Node nd2, Label lab) {
if (deepFrozen)
throw new ObjectFrozen();
arcMap.put(Pair.pair(nd1, nd2), lab);
}
/**
* Remove an arc from the graph.
*
* @param nd1 The source node for the arc.
* @param nd2 The destination node for the arc.
* @param lab The label for the arc.
*/
public void removeArc(Node nd1, Node nd2, Label lab) {
if (deepFrozen)
throw new ObjectFrozen();
arcMap.remove(Pair.pair(nd1, nd2), lab);
}
/**
* Check if this graph is partitioned by the given graphs.
*
* <ol>
* <li>Every node in nodes is contained in exactly one partition</li>
* <li>For every node in nodes, the value the partition assigns it is equal to
* the value from nodeValuer</li>
* <li>Every arc in a partition is also in arcMap</li>
* </ol>
*
* @param partitions The graphs to check partitioning for.
*
* @return Whether this graph is partitioned by the given nodes.
*/
public boolean partitionedBy(@SuppressWarnings("unchecked") ASGraph<Node, Value, Label>... partitions) {
// TODO: Implement me
return false;
}
/**
* Create a graph representing a given string
*
* Note that because of the way the value function is implemented, modifying the
* graph will not work well.
*
* @param strang The string to represent.
*
* @return The graph representing the string.
*/
public static ASGraph<Integer, Character, Unit> fromString(String strang) {
ASGraph<Integer, Character, Unit> ret = new ASGraph<>(strang::charAt);
for (int i = 0; i < strang.length(); i++) {
ret.addNode(i);
if (i != 0)
ret.addArc(i - 1, i, Unit.UNIT);
}
return ret;
}
@Override
public boolean freeze() {
frozen = true;
return true;
}
@Override
public boolean thaw() {
if (deepFrozen)
return false;
return false;
}
@Override
public boolean deepFreeze() {
deepFrozen = true;
frozen = true;
return true;
}
@Override
public boolean isFrozen() {
return frozen;
}
}
|
