Package edu.uci.ics.jung.graph

Interface Graph<V,​E>

  • All Superinterfaces:
    Hypergraph<V,​E>
    All Known Subinterfaces:
    DirectedGraph<V,​E>, Forest<V,​E>, KPartiteGraph<V,​E>, Tree<V,​E>, UndirectedGraph<V,​E>
    All Known Implementing Classes:
    GraphDecorator, ObservableGraph
    public interface Graph<V,​E>
extends Hypergraph<V,​E>
    A graph consisting of a set of vertices of type V set and a set of edges of type E. Edges of this graph type have exactly two endpoints; whether these endpoints must be distinct depends on the implementation.

    This interface permits, but does not enforce, any of the following common variations of graphs:

    • directed and undirected edges
    • vertices and edges with attributes (for example, weighted edges)
    • vertices and edges of different types (for example, bipartite or multimodal graphs)
    • parallel edges (multiple edges which connect a single set of vertices)
    • representations as matrices or as adjacency lists or adjacency maps
    Extensions or implementations of this interface may enforce or disallow any or all of these variations.

    Definitions (with respect to a given vertex v):

    • incoming edge of v: an edge that can be traversed from a neighbor of v to reach v
    • outgoing edge of v: an edge that can be traversed from v to reach some neighbor of v
    • predecessor of v: a vertex at the other end of an incoming edge of v
    • successor of v: a vertex at the other end of an outgoing edge of v

    • Method Detail

      • getInEdges

        java.util.Collection<E> getInEdges​(V vertex)
        Returns a Collection view of the incoming edges incident to vertex in this graph.
        Specified by:
        getInEdges in interface Hypergraph<V,​E>
        Parameters:
        vertex - the vertex whose incoming edges are to be returned
        Returns:
        a Collection view of the incoming edges incident to vertex in this graph

      • getOutEdges

        java.util.Collection<E> getOutEdges​(V vertex)
        Returns a Collection view of the outgoing edges incident to vertex in this graph.
        Specified by:
        getOutEdges in interface Hypergraph<V,​E>
        Parameters:
        vertex - the vertex whose outgoing edges are to be returned
        Returns:
        a Collection view of the outgoing edges incident to vertex in this graph

      • getPredecessors

        java.util.Collection<V> getPredecessors​(V vertex)
        Returns a Collection view of the predecessors of vertex in this graph. A predecessor of vertex is defined as a vertex v which is connected to vertex by an edge e, where e is an outgoing edge of v and an incoming edge of vertex.
        Specified by:
        getPredecessors in interface Hypergraph<V,​E>
        Parameters:
        vertex - the vertex whose predecessors are to be returned
        Returns:
        a Collection view of the predecessors of vertex in this graph

      • getSuccessors

        java.util.Collection<V> getSuccessors​(V vertex)
        Returns a Collection view of the successors of vertex in this graph. A successor of vertex is defined as a vertex v which is connected to vertex by an edge e, where e is an incoming edge of v and an outgoing edge of vertex.
        Specified by:
        getSuccessors in interface Hypergraph<V,​E>
        Parameters:
        vertex - the vertex whose predecessors are to be returned
        Returns:
        a Collection view of the successors of vertex in this graph

      • inDegree

        int inDegree​(V vertex)
        Returns the number of incoming edges incident to vertex. Equivalent to getInEdges(vertex).size().
        Specified by:
        inDegree in interface Hypergraph<V,​E>
        Parameters:
        vertex - the vertex whose indegree is to be calculated
        Returns:
        the number of incoming edges incident to vertex

      • outDegree

        int outDegree​(V vertex)
        Returns the number of outgoing edges incident to vertex. Equivalent to getOutEdges(vertex).size().
        Specified by:
        outDegree in interface Hypergraph<V,​E>
        Parameters:
        vertex - the vertex whose outdegree is to be calculated
        Returns:
        the number of outgoing edges incident to vertex

      • isPredecessor

        boolean isPredecessor​(V v1,
                      V v2)
        Returns true if v1 is a predecessor of v2 in this graph. Equivalent to v1.getPredecessors().contains(v2).
        Parameters:
        v1 - the first vertex to be queried
        v2 - the second vertex to be queried
        Returns:
        true if v1 is a predecessor of v2, and false otherwise.

      • isSuccessor

        boolean isSuccessor​(V v1,
                    V v2)
        Returns true if v1 is a successor of v2 in this graph. Equivalent to v1.getSuccessors().contains(v2).
        Parameters:
        v1 - the first vertex to be queried
        v2 - the second vertex to be queried
        Returns:
        true if v1 is a successor of v2, and false otherwise.

      • getPredecessorCount

        int getPredecessorCount​(V vertex)
        Returns the number of predecessors that vertex has in this graph. Equivalent to vertex.getPredecessors().size().
        Parameters:
        vertex - the vertex whose predecessor count is to be returned
        Returns:
        the number of predecessors that vertex has in this graph

      • getSuccessorCount

        int getSuccessorCount​(V vertex)
        Returns the number of successors that vertex has in this graph. Equivalent to vertex.getSuccessors().size().
        Parameters:
        vertex - the vertex whose successor count is to be returned
        Returns:
        the number of successors that vertex has in this graph

      • getSource

        V getSource​(E directed_edge)
        If directed_edge is a directed edge in this graph, returns the source; otherwise returns null. The source of a directed edge d is defined to be the vertex for which d is an outgoing edge. directed_edge is guaranteed to be a directed edge if its EdgeType is DIRECTED.
        Specified by:
        getSource in interface Hypergraph<V,​E>
        Parameters:
        directed_edge -
        Returns:
        the source of directed_edge if it is a directed edge in this graph, or null otherwise

      • getDest

        V getDest​(E directed_edge)
        If directed_edge is a directed edge in this graph, returns the destination; otherwise returns null. The destination of a directed edge d is defined to be the vertex incident to d for which d is an incoming edge. directed_edge is guaranteed to be a directed edge if its EdgeType is DIRECTED.
        Specified by:
        getDest in interface Hypergraph<V,​E>
        Parameters:
        directed_edge -
        Returns:
        the destination of directed_edge if it is a directed edge in this graph, or null otherwise

      • isSource

        boolean isSource​(V vertex,
                 E edge)
        Returns true if vertex is the source of edge. Equivalent to getSource(edge).equals(vertex).
        Parameters:
        vertex - the vertex to be queried
        edge - the edge to be queried
        Returns:
        true iff vertex is the source of edge

      • isDest

        boolean isDest​(V vertex,
               E edge)
        Returns true if vertex is the destination of edge. Equivalent to getDest(edge).equals(vertex).
        Parameters:
        vertex - the vertex to be queried
        edge - the edge to be queried
        Returns:
        true iff vertex is the destination of edge

      • addEdge

        boolean addEdge​(E e,
                V v1,
                V v2)
        Adds edge e to this graph such that it connects vertex v1 to v2. Equivalent to addEdge(e, new Pair(v1, v2)). If this graph does not contain v1, v2, or both, implementations may choose to either silently add the vertices to the graph or throw an IllegalArgumentException. If this graph assigns edge types to its edges, the edge type of e will be the default for this graph. See Hypergraph.addEdge() for a listing of possible reasons for failure.
        Parameters:
        e - the edge to be added
        v1 - the first vertex to be connected
        v2 - the second vertex to be connected
        Returns:
        true if the add is successful, false otherwise
        See Also:
        Hypergraph.addEdge(Object, Collection), addEdge(Object, Object, Object, EdgeType)

      • addEdge

        boolean addEdge​(E e,
                V v1,
                V v2,
                EdgeType edgeType)
        Adds edge e to this graph such that it connects vertex v1 to v2. Equivalent to addEdge(e, new Pair(v1, v2)). If this graph does not contain v1, v2, or both, implementations may choose to either silently add the vertices to the graph or throw an IllegalArgumentException. If edgeType is not legal for this graph, this method will throw IllegalArgumentException. See Hypergraph.addEdge() for a listing of possible reasons for failure.
        Parameters:
        e - the edge to be added
        v1 - the first vertex to be connected
        v2 - the second vertex to be connected
        edgeType - the type to be assigned to the edge
        Returns:
        true if the add is successful, false otherwise
        See Also:
        Hypergraph.addEdge(Object, Collection), addEdge(Object, Object, Object)

      • getEndpoints

        Pair<V> getEndpoints​(E edge)
        Returns the endpoints of edge as a Pair.
        Parameters:
        edge - the edge whose endpoints are to be returned
        Returns:
        the endpoints (incident vertices) of edge

      • getOpposite

        V getOpposite​(V vertex,
              E edge)
        Returns the vertex at the other end of edge from vertex. (That is, returns the vertex incident to edge which is not vertex.)
        Parameters:
        vertex - the vertex to be queried
        edge - the edge to be queried
        Returns:
        the vertex at the other end of edge from vertex