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:
AbstractGraph, AbstractTypedGraph, AggregateGraph, DelegateForest, DelegateTree, DirectedOrderedSparseMultigraph, DirectedSparseGraph, DirectedSparseMultigraph, FastRenderingGraph, GraphDecorator, ObservableGraph, OrderedKAryTree, OrderedSparseMultigraph, SortedSparseMultigraph, SparseGraph, SparseMultigraph, UndirectedOrderedSparseMultigraph, UndirectedSparseGraph, UndirectedSparseMultigraph
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
Author:
Joshua O'Madadhain

  • Method Details

    • getInEdges

      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

      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

      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

      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 - the edge whose source is to be returned
      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 - the edge whose destination is to be returned
      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:

    • 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:

    • 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