Class Graph<V>
- Type Parameters:
V- the vertex type. Must implementequalsandhashCode.
- Direct Known Subclasses:
WeightedGraph
Graph<V> accumulates vertices and edges in ordinary Java collections.
When any algorithm is requested, it materialises an immutable Scala graph from
those collections, caches it, and delegates to Gryphon's Scala engine. The cache
is invalidated whenever the graph is mutated (addEdge(com.phasmidsoftware.gryphon.java.Edge<V>), addVertex(V)),
so the Scala graph is always consistent with the Java state.
All BFS and DFS traversals — both Option 1 and Option 3 — delegate to the
Scala Visitor engine via JavaFacadeBridge and return a came-from
map: for each discovered vertex v, result.get(v) is the
vertex from which v was first discovered. The start vertex is absent
from the map — it has no predecessor. This is consistent with all other
algorithm façades in Gryphon (Dijkstra SPT, Prim/Kruskal MST, Kosaraju SCC).
Path reconstruction:
Map<String, String> tree = g.bfs("A");
List<String> path = new ArrayList<>();
String v = "D";
path.add(v);
while (tree.containsKey(v)) { v = tree.get(v); path.add(0, v); }
// path == ["A", "B", "C", "D"]
-
Method Summary
Modifier and TypeMethodDescriptionvoidAdds an edge to this graph.voidAdds an unweighted edge betweenfromandto.voidAdds an isolated vertex to this graph.Performs a breadth-first search fromstart.Performs a breadth-first search fromstartusing a custom neighbour function.Performs a breadth-first search fromstart, stopping as soon asgoalholds for a discovered vertex.intReturns the degree ofvertex: the number of edges incident to it.Performs a depth-first search fromstart.Performs a depth-first search fromstartusing a custom neighbour function.dfsAll()Performs a depth-first search over every component of the graph.static <V> Graph<V> directed()Creates an empty directed graph.edges()Returns all edges in this graph.Returns the edges incident fromvertex.intReturns the in-degree ofvertex: the number of edges arriving at it.booleanReturns whether the vertices can be two-coloured so that no edge joins two vertices of the same colour.booleanReturns whether every vertex is reachable from every other.booleanisCyclic()Returns whether this graph contains a cycle.booleanReturns whether this graph is directed.intReturns the largest degree of any vertex.doubleReturns the mean degree,2M/N.neighbours(V vertex) Returns the neighbours ofvertex.intReturns the number of self-loops: edges whose endpoints are the same vertex.intorder()Returns the number of vertices —Nin Sedgewick's notation.intReturns the out-degree ofvertex: the number of edges leaving it.reverse()Returns a new directed graph with all edge directions reversed.intsize()Returns the number of edges —Min Sedgewick's notation.toString()static <V> Graph<V> Creates an empty undirected graph.vertices()Returns all vertices in this graph as an unmodifiable set.
-
Method Details
-
directed
Creates an empty directed graph.In a directed graph,
addEdge(u, v)adds only the arcu → v. The reverse arcv → uis not implied.- Type Parameters:
V- the vertex type.- Returns:
- a new empty directed
Graph.
-
undirected
Creates an empty undirected graph.In an undirected graph,
addEdge(u, v)implicitly adds bothu → vandv → uin the underlying representation.- Type Parameters:
V- the vertex type.- Returns:
- a new empty undirected
Graph.
-
addVertex
Adds an isolated vertex to this graph.If the vertex is already present this method has no effect.
- Parameters:
vertex- the vertex to add.
-
addEdge
Adds an edge to this graph.Both endpoint vertices are added automatically if not already present. For undirected graphs the reverse edge is also added.
- Parameters:
edge- the edge to add.
-
addEdge
Adds an unweighted edge betweenfromandto.Convenience overload — equivalent to
addEdge(new Edge<>(from, to)).- Parameters:
from- the source vertex.to- the target vertex.
-
isDirected
public boolean isDirected()Returns whether this graph is directed.- Returns:
trueif directed,falseif undirected.
-
vertices
Returns all vertices in this graph as an unmodifiable set.- Returns:
- the vertex set.
-
edges
Returns all edges in this graph.For undirected graphs both directions are stored internally; this method returns only the canonical direction (each edge once, as originally added via
addEdge(com.phasmidsoftware.gryphon.java.Edge<V>)).- Returns:
- an unmodifiable list of edges.
-
neighbours
Returns the neighbours ofvertex.- Parameters:
vertex- the query vertex.- Returns:
- an iterable of neighbouring vertices.
- Throws:
NoSuchElementException- ifvertexis not in the graph.
-
edgesFrom
Returns the edges incident fromvertex.- Parameters:
vertex- the query vertex.- Returns:
- an iterable of edges from
vertex. - Throws:
NoSuchElementException- ifvertexis not in the graph.
-
order
public int order()Returns the number of vertices —Nin Sedgewick's notation.- Returns:
- the vertex count.
-
size
public int size()Returns the number of edges —Min Sedgewick's notation.- Returns:
- the edge count.
-
degree
Returns the degree ofvertex: the number of edges incident to it.Undirected graphs only. A vertex of a directed graph has an in-degree and an out-degree, not a single degree — use
inDegree(Object)andoutDegree(Object).- Parameters:
vertex- the query vertex.- Returns:
- the degree.
- Throws:
com.phasmidsoftware.gryphon.core.GraphException- if this graph is directed.
-
maxDegree
public int maxDegree()Returns the largest degree of any vertex. Undirected graphs only.- Returns:
- the maximum degree.
- Throws:
com.phasmidsoftware.gryphon.core.GraphException- if this graph is directed.
-
meanDegree
public double meanDegree()Returns the mean degree,2M/N. Undirected graphs only.- Returns:
- the average degree.
- Throws:
com.phasmidsoftware.gryphon.core.GraphException- if this graph is directed.
-
inDegree
Returns the in-degree ofvertex: the number of edges arriving at it.Unlike
degree(Object), this works on both kinds of graph. In an undirected graph every edge can be traversed both ways, so the in-degree, the out-degree and the degree are the same number. A self-loop counts once towards each of the in- and out-degrees.- Parameters:
vertex- the query vertex.- Returns:
- the number of edges arriving at
vertex.
-
outDegree
Returns the out-degree ofvertex: the number of edges leaving it. SeeinDegree(Object)for how this behaves on an undirected graph.- Parameters:
vertex- the query vertex.- Returns:
- the number of edges leaving
vertex.
-
numberOfSelfLoops
public int numberOfSelfLoops()Returns the number of self-loops: edges whose endpoints are the same vertex.- Returns:
- the self-loop count.
-
isCyclic
public boolean isCyclic()Returns whether this graph contains a cycle.For a directed graph this is the negation of
TopologicalSort.isDAG(Graph).- Returns:
trueif a cycle exists.
-
isConnected
public boolean isConnected()Returns whether every vertex is reachable from every other.Undirected graphs only, because connectivity of a directed graph has two distinct meanings and neither is assumed: use
ConnectedComponentsfor weak connectivity, treating edges as undirected, orStronglyConnectedComponents.kosaraju(Graph)for strong.In Scala this is not declared on a directed graph, so the compiler rejects it. Java cannot express that, so the façade checks and throws instead.
- Returns:
trueif the graph is connected.- Throws:
com.phasmidsoftware.gryphon.core.GraphException- if this graph is directed.
-
isBipartite
public boolean isBipartite()Returns whether the vertices can be two-coloured so that no edge joins two vertices of the same colour.Undirected graphs only; see
isConnected()for why, and for why Scala callers get a compile error where Java callers get an exception.- Returns:
trueif the graph is bipartite.- Throws:
com.phasmidsoftware.gryphon.core.GraphException- if this graph is directed.
-
bfs
Performs a breadth-first search fromstart.Returns a came-from map; start vertex absent.
Path reconstruction: walk
result.get(v)until the key is absent — that vertex is the start.- Parameters:
start- the source vertex.- Returns:
- the BFS came-from map.
-
dfs
Performs a depth-first search fromstart.Returns a came-from map; start vertex absent.
- Parameters:
start- the source vertex.- Returns:
- the DFS came-from map.
-
dfsAll
Performs a depth-first search over every component of the graph.dfs(Object)explores only the component containing its start vertex. This method restarts from each vertex not yet discovered, so the came-from map covers the whole graph — a depth-first forest. Each component's root is absent from the map, just as the start vertex is for a single DFS, so the number of absent vertices is the number of components.- Returns:
- the came-from map over all components.
-
bfsUntil
Performs a breadth-first search fromstart, stopping as soon asgoalholds for a discovered vertex.Use this to find a shortest path to a known target without exploring the rest of the graph. The came-from map covers only what was discovered before stopping, so a vertex beyond the goal will be absent.
Named
bfsUntilrather than overloadingbfs, because a lambda argument could not then be resolved against theFunction<V, Iterable<V>>overload.- Parameters:
start- the source vertex.goal- the stopping condition.- Returns:
- the partial BFS came-from map.
-
bfs
Performs a breadth-first search fromstartusing a custom neighbour function.The neighbour function is wrapped into a Scala
Neighbours[V,V]given instance and passed to the Visitor engine, ensuring consistent behaviour with Option 1. Returns a came-from map; start vertex absent.- Parameters:
start- the source vertex.neighbours- a function mapping each vertex to its neighbours.- Returns:
- the BFS came-from map.
-
dfs
Performs a depth-first search fromstartusing a custom neighbour function.The neighbour function is wrapped into a Scala
Neighbours[V,V]given instance and passed to the Visitor engine, ensuring consistent behaviour with Option 1. Returns a came-from map; start vertex absent.- Parameters:
start- the source vertex.neighbours- a function mapping each vertex to its neighbours.- Returns:
- the DFS came-from map.
-
reverse
Returns a new directed graph with all edge directions reversed.For every edge
u → vin this graph, the returned graph containsv → u. The vertex set is preserved. This operation is the first step in Kosaraju's SCC algorithm and is useful for reachability queries in the reverse direction.- Returns:
- a new
Graph<V>with all edges reversed. - Throws:
IllegalStateException- if this graph is undirected.
-
toString
-