Class Graph<V>

java.lang.Object
com.phasmidsoftware.gryphon.java.Graph<V>
Type Parameters:
V - the vertex type. Must implement equals and hashCode.
Direct Known Subclasses:
WeightedGraph

public class Graph<V> extends Object
A mutable, lazily-materialised façade over Gryphon's purely functional graph types.

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 Type
    Method
    Description
    void
    addEdge(Edge<V> edge)
    Adds an edge to this graph.
    void
    addEdge(V from, V to)
    Adds an unweighted edge between from and to.
    void
    addVertex(V vertex)
    Adds an isolated vertex to this graph.
    bfs(V start)
    Performs a breadth-first search from start.
    bfs(V start, Function<V,Iterable<V>> neighbours)
    Performs a breadth-first search from start using a custom neighbour function.
    bfsUntil(V start, Predicate<V> goal)
    Performs a breadth-first search from start, stopping as soon as goal holds for a discovered vertex.
    int
    degree(V vertex)
    Returns the degree of vertex: the number of edges incident to it.
    dfs(V start)
    Performs a depth-first search from start.
    dfs(V start, Function<V,Iterable<V>> neighbours)
    Performs a depth-first search from start using a custom neighbour function.
    Performs a depth-first search over every component of the graph.
    static <V> Graph<V>
    Creates an empty directed graph.
    Returns all edges in this graph.
    edgesFrom(V vertex)
    Returns the edges incident from vertex.
    int
    inDegree(V vertex)
    Returns the in-degree of vertex: the number of edges arriving at it.
    boolean
    Returns whether the vertices can be two-coloured so that no edge joins two vertices of the same colour.
    boolean
    Returns whether every vertex is reachable from every other.
    boolean
    Returns whether this graph contains a cycle.
    boolean
    Returns whether this graph is directed.
    int
    Returns the largest degree of any vertex.
    double
    Returns the mean degree, 2M/N.
    neighbours(V vertex)
    Returns the neighbours of vertex.
    int
    Returns the number of self-loops: edges whose endpoints are the same vertex.
    int
    Returns the number of vertices — N in Sedgewick's notation.
    int
    outDegree(V vertex)
    Returns the out-degree of vertex: the number of edges leaving it.
    Returns a new directed graph with all edge directions reversed.
    int
    Returns the number of edges — M in Sedgewick's notation.
     
    static <V> Graph<V>
    Creates an empty undirected graph.
    Returns all vertices in this graph as an unmodifiable set.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Method Details

    • directed

      public static <V> Graph<V> directed()
      Creates an empty directed graph.

      In a directed graph, addEdge(u, v) adds only the arc u → v. The reverse arc v → u is not implied.

      Type Parameters:
      V - the vertex type.
      Returns:
      a new empty directed Graph.
    • undirected

      public static <V> Graph<V> undirected()
      Creates an empty undirected graph.

      In an undirected graph, addEdge(u, v) implicitly adds both u → v and v → u in the underlying representation.

      Type Parameters:
      V - the vertex type.
      Returns:
      a new empty undirected Graph.
    • addVertex

      public void addVertex(V vertex)
      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

      public void addEdge(Edge<V> edge)
      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

      public void addEdge(V from, V to)
      Adds an unweighted edge between from and to.

      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:
      true if directed, false if undirected.
    • vertices

      public Set<V> vertices()
      Returns all vertices in this graph as an unmodifiable set.
      Returns:
      the vertex set.
    • edges

      public List<Edge<V>> 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

      public Iterable<V> neighbours(V vertex)
      Returns the neighbours of vertex.
      Parameters:
      vertex - the query vertex.
      Returns:
      an iterable of neighbouring vertices.
      Throws:
      NoSuchElementException - if vertex is not in the graph.
    • edgesFrom

      public Iterable<Edge<V>> edgesFrom(V vertex)
      Returns the edges incident from vertex.
      Parameters:
      vertex - the query vertex.
      Returns:
      an iterable of edges from vertex.
      Throws:
      NoSuchElementException - if vertex is not in the graph.
    • order

      public int order()
      Returns the number of vertices — N in Sedgewick's notation.
      Returns:
      the vertex count.
    • size

      public int size()
      Returns the number of edges — M in Sedgewick's notation.
      Returns:
      the edge count.
    • degree

      public int degree(V vertex)
      Returns the degree of vertex: 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) and outDegree(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

      public int inDegree(V vertex)
      Returns the in-degree of vertex: 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

      public int outDegree(V vertex)
      Returns the out-degree of vertex: the number of edges leaving it. See inDegree(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:
      true if 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 ConnectedComponents for weak connectivity, treating edges as undirected, or StronglyConnectedComponents.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:
      true if 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:
      true if the graph is bipartite.
      Throws:
      com.phasmidsoftware.gryphon.core.GraphException - if this graph is directed.
    • bfs

      public Map<V,V> bfs(V start)
      Performs a breadth-first search from start.

      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

      public Map<V,V> dfs(V start)
      Performs a depth-first search from start.

      Returns a came-from map; start vertex absent.

      Parameters:
      start - the source vertex.
      Returns:
      the DFS came-from map.
    • dfsAll

      public Map<V,V> 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

      public Map<V,V> bfsUntil(V start, Predicate<V> goal)
      Performs a breadth-first search from start, stopping as soon as goal holds 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 bfsUntil rather than overloading bfs, because a lambda argument could not then be resolved against the Function<V, Iterable<V>> overload.

      Parameters:
      start - the source vertex.
      goal - the stopping condition.
      Returns:
      the partial BFS came-from map.
    • bfs

      public Map<V,V> bfs(V start, Function<V,Iterable<V>> neighbours)
      Performs a breadth-first search from start using 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

      public Map<V,V> dfs(V start, Function<V,Iterable<V>> neighbours)
      Performs a depth-first search from start using 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

      public Graph<V> reverse()
      Returns a new directed graph with all edge directions reversed.

      For every edge u → v in this graph, the returned graph contains v → 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

      public String toString()
      Overrides:
      toString in class Object