-
Notifications
You must be signed in to change notification settings - Fork 56
Class Graph
Ori Roth edited this page Apr 2, 2017
·
3 revisions
public class Graph<Data> implements Checkable {
/*
* Type (4)
*/
final Vertex<Data>[] vertices;
final Edge<Data>[] edges;
void invariant();
void reset();
/*
* Nested types (3)
*/
static class Edge<Data> implements Checkable, Comparable<Edge<Data>> { ... }
static class Vertex<Data> implements Comparable<Vertex<Data>> { ... }
static class Builder<Data> { ... }
} Output types*: Comparable<Data>, Edge<Data>, Vertex<Data>.
public static class Graph.Edge<Data> implements Checkable, Comparable<Edge<Data>> {
/*
* Type (4)
*/
final Vertex<Data> from;
final Vertex<Data> to;
void invariant();
int compareTo(Edge<Data> o);
} Input types: Comparable<Data>.
Output types: Comparable<Data>, Vertex<Data>.
public static class Graph.Vertex<Data> implements Comparable<Vertex<Data>> {
/*
* Type (9)
*/
final Vertex<Data>[] to;
final Vertex<Data>[] from;
final Data data;
final int i;
void reset();
void visit();
boolean isVisited();
String toString();
final int compareTo(Vertex<Data> o);
}*Input types: Comparable<Data>.
Output types: Comparable<Data>.
public static class Graph.Builder<Data> {
/*
* Forge (1)
*/
Builder();
/*
* Type (3)
*/
void newEdge(Data from, Data to);
void newVertex(Data d);
Graph<Data> build();
} Input types: Comparable<Data>.
Output types: Comparable<Data>, Graph<Data>.
private static class Graph.Builder.Pair<Data> {
/*
* Forge (1)
*/
Pair(Data first, Data second);
/*
* Type (2)
*/
int hashCode();
boolean equals(Object o);
} // SSDLPedia
package il.ac.technion.cs.cs236700.graph;
import static il.ac.technion.cs.ssdl.utils.DBC.*;
import il.ac.technion.cs.ssdl.stereotypes.Classical;
import il.ac.technion.cs.ssdl.stereotypes.Immutable;
import il.ac.technion.cs.ssdl.stereotypes.Instantiable;
import il.ac.technion.cs.ssdl.utils.All;
import il.ac.technion.cs.ssdl.utils.DBC.Checkable;
import java.util.*;
/**
* Class Graph: a class representing an immutable directed graph with
* arbitrary data contained in its nodes. The design supports graph visitation,
* with a facility to mark (and unmark) vertices as visited.
*
* <Data> Kind of elements stored in each of the graph vertices. This
* data type must implement correctly both #equals(Object)
* and Comparable#compareTo(Object).
* Author: Yossi Gil
* See: 20/06/2007
*/
@Instantiable @Immutable @Classical public class Graph<Data extends Comparable<Data>> implements Checkable {
/**
* An immutable array of all vertices of this graph
*/
public final Vertex<Data>[] vertices;
/**
* An immutable array of all edges of this graph
*/
public final Edge<Data>[] edges;
public void invariant() {
nonnull(vertices);
nonnull(edges);
sure(All.notNull(vertices));
sure(All.notNull(edges));
for (final Vertex<Data> v : vertices) {
nonnull(v);
sure(vertices[v.i] == v);
for (final Vertex<Data> u : v.from) {
nonnull(u);
sure(Arrays.binarySearch(vertices, u) >= 0);
sure(Arrays.binarySearch(u.to, v) >= 0);
}
for (final Vertex<Data> u : v.to) {
nonnull(u);
sure(Arrays.binarySearch(vertices, u) >= 0);
sure(Arrays.binarySearch(u.from, v) >= 0);
}
}
for (final Edge<Data> e : edges) {
nonnull(e);
nonnull(e.from);
nonnull(e.to);
sure(Arrays.binarySearch(vertices, e.from) >= 0);
sure(Arrays.binarySearch(vertices, e.to) >= 0);
}
}
/**
* Mark all vertices of this graph unvisited
*/
public void reset() {
for (final Vertex<Data> v : vertices)
v.reset();
}
private Graph(final Vertex<Data>[] vertices, final Edge<Data>[] edges) {
nonnull(vertices);
nonnull(edges);
require(All.notNull(vertices));
require(All.notNull(edges));
this.vertices = vertices;
this.edges = edges;
}
protected Graph(final Graph<Data> other) {
this(other.vertices, other.edges);
}
/**
* Class Graph.Edge: Represents an edge in a Graph.
*
* <Data> the type of information stored in a graph node
* Author: Yossi Gil
* See: 28/06/2007
*/
public static class Edge<Data extends Comparable<Data>> implements Checkable, Comparable<Edge<Data>> {
/**
* where this edge starts
*/
public final Vertex<Data> from;
/**
* where this edge ends
*/
public final Vertex<Data> to;
public void invariant() {
nonnull(from);
nonnull(to);
}
private Edge(final Vertex<Data> from, final Vertex<Data> to) {
this.from = from;
this.to = to;
}
public int compareTo(final Edge<Data> o) {
final int $ = from.compareTo(o.from);
return $ != 0 ? $ : to.compareTo(o.to);
}
}
/**
* Class Graph.Vertex: an immutable class representing a vertex in a
* Graph
*
* <Data> the type of information stored in each vertex.
* Author: Yossi Gil
* See: 28/06/2007
*/
public static class Vertex<Data extends Comparable<Data>> implements Comparable<Vertex<Data>> {
/**
* Vertices to which there is an edge from this vertex.
*/
public final Vertex<Data> to[];
/**
* Vertices from which there is an edge leading to this vertex.
*/
public final Vertex<Data> from[];
/**
* The data stored in this node.
*/
public final Data data;
/**
* The ordinal number of this node in its containing graph.
*/
public final int i;
/**
* Was this node visited?
*/
private boolean visited;
private Vertex(final Vertex<Data>[] from, final Vertex<Data>[] to, final Data attributes, final int i) {
this.from = from;
this.to = to;
this.data = attributes;
this.i = i;
}
/**
* Reset this vertex. That is, the visited flag is set to
* false.
*/
public void reset() {
visited = false;
}
/**
* Marks this instance as visited. That is, the visited flag becomes
* true.
*/
public void visit() {
visited = true;
}
/**
* check the visitation status.
*
* Return: true if this vertex was visited.
*/
public boolean isVisited() {
return visited;
}
/**
* Returns toString() of the attributes and the number of
* incoming and outgoing arcs.
*/
@Override public String toString() {
String $ = data == null ? super.toString() : data.toString();
$ += " [" + from.length + " in, ";
$ += to.length + " out]";
return $;
}
public final int compareTo(final Vertex<Data> o) {
nonnull(data);
nonnull(o);
nonnull(o.data);
return data.compareTo(o.data);
}
}
/**
* Class Graph.Builder: A class to create a Graph from a
* bunch of associations. The associations are added incrementally, with
* function {@link #newEdge(Comparable, Comparable)} called for each
* association, then function #build() is invoked to actually create
* the graph. Vertices are created implicitly, i.e., the graph has only
* vertices which participated in an association.
*
* Author: Yossi Gil
* See: 20/06/2007
* <Data> Kind of information stored in graph vertices
*/
public static class Builder<Data extends Comparable<Data>> {
private final HashSet<Pair<Data>> edges = new HashSet<Pair<Data>>();
/**
* Record an association between two data elements- later to be shown as
* a graph edge.
*
* from association starts here
* to association ends here
*/
public void newEdge(final Data from, final Data to) {
nonnull(from);
nonnull(to);
newVertex(from);
newVertex(to);
edges.add(new Pair<Data>(from, to));
}
public void newVertex(final Data d) {
nonnull(d);
vertices.put(d, emptyPair());
}
private final TreeMap<Data, Pair<HashSet<Data>>> vertices = new TreeMap<Data, Pair<HashSet<Data>>>();
/**
* The actual function to create the graph, defined by all associations
* recorded so far.
*
* Return: th Graph objects odefined by the associations.
*/
@SuppressWarnings("synthetic-access")//
public Graph<Data> build() {
// Phase I: Determine vertex set, and record mappings.
for (final Pair<Data> edge : edges) {
final Data from = edge.first;
final Data to = edge.second;
vertices.get(from).second.add(to);
vertices.get(to).first.add(from);
}
// Phase II: create vertex array.
final Graph.Vertex<Data>[] vs = newVertexArray(vertices.size());
{
int i = 0;
for (final Data d : vertices.keySet()) {
final Graph.Vertex<Data>[] from = newVertexArray(vertices.get(d).first.size());
final Graph.Vertex<Data>[] to = newVertexArray(vertices.get(d).second.size());
vs[i] = new Graph.Vertex<Data>(from, to, d, i);
record(d, vs[i]);
i++;
}
}
// Phase III: fill vertex array.
for (final Data d : vertices.keySet()) {
final Graph.Vertex<Data> v = find(d);
fill(v.from, vertices.get(d).first);
fill(v.to, vertices.get(d).second);
}
// Phase IV: create and fill edges array
final Graph.Edge<Data>[] es = newEdgeArray(edges.size());
{
int i = 0;
for (final Pair<Data> p : edges)
es[i++] = new Graph.Edge<Data>(find(p.first), find(p.second));
}
Arrays.sort(es);
ensure(es.length == edges.size());
return new Graph<Data>(vs, es);
}
private void fill(final Graph.Vertex<Data> a[], final Collection<Data> ds) {
require(a.length == ds.size());
int i = 0;
for (final Data d : ds)
a[i++] = find(d);
Arrays.sort(a);
}
@SuppressWarnings("unchecked")//
private Graph.Vertex<Data>[] newVertexArray(final int n) {
return new Graph.Vertex[n];
}
@SuppressWarnings("unchecked")//
private Graph.Edge<Data>[] newEdgeArray(final int n) {
return new Graph.Edge[n];
}
private Pair<HashSet<Data>> emptyPair() {
return new Pair<HashSet<Data>>(emptySet(), emptySet());
}
private HashSet<Data> emptySet() {
return new HashSet<Data>();
}
private final HashMap<Data, Graph.Vertex<Data>> data2vertex = new HashMap<Data, Graph.Vertex<Data>>();
private void record(final Data d, final Graph.Vertex<Data> v) {
data2vertex.put(d, v);
}
private Graph.Vertex<Data> find(final Data d) {
return data2vertex.get(d);
}
private static class Pair<Data> {
Data first;
Data second;
public Pair(final Data first, final Data second) {
nonnull(first);
nonnull(second);
this.first = first;
this.second = second;
}
@Override public int hashCode() {
return first.hashCode() >>> 1 ^ second.hashCode();
}
@Override public boolean equals(final Object o) {
nonnull(o);
require(o instanceof Pair);
nonnull(first);
nonnull(second);
@SuppressWarnings("unchecked") final Pair<Data> other = (Pair<Data>) o;
nonnull(other.first);
nonnull(other.second);
return first.equals(other.first) && second.equals(other.second);
}
}
}
}| Metric | Value | Acronym | Explanation |
|---|---|---|---|
| LOC | 343 | Lines Of Code | Total number of lines in the code |
| SCC | 118 | SemiColons Count | Total number of semicolon tokens found in the code. |
| NOT | 1764 | Number Of Tokens | Comments, whitespace and text which cannot be made into a token not included. |
| VCC | 7417 | Visible Characters Count | The total number of non-white (i.e., not space, tab, newline, carriage return, form feed) characters. |
| CCC | 5085 | Code Characters Count | Total number of non-white characters in tokens. White space characters in string and character literals are not counted. |
| UIC | 87 | Unique Identifiers Count | The number of different identifiers found in the code |
| WHC | 7 | Weighted Horizontal Complexity | A heuritistic on horizontal complexity |
| Statitic | Value |
|---|---|
| Average token length | 2.9 |
| Tokens/line | 5.1 |
| Visible characters/line | 22 |
| Code characters/line | 15 |
| Semicolons/tokens | 6% |
| Comment text percentage | 31% |
| Token Kind | Occurrences |
|---|---|
| KEYWORD | 195 |
| OPERATOR | 187 |
| LITERAL | 18 |
| ID | 633 |
| PUNCTUATION | 731 |
| COMMENT | 28 |
| OTHER | 682 |