/*
* Created on Oct 17, 2005
*
* Copyright (c) 2005, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.graph;
import java.util.Collection;
import edu.uci.ics.jung.graph.util.EdgeType;
/**
* A hypergraph, consisting of a set of vertices of type V
* and a set of hyperedges of type E which connect the vertices.
* This is the base interface for all JUNG graph types.
*
* This interface permits, but does not enforce, any of the following
* common variations of graphs:
*
* - hyperedges (edges which connect a set of vertices of any size)
*
- edges (these have have exactly two endpoints, which may or may not be distinct)
*
- self-loops (edges which connect exactly one vertex)
*
- directed and undirected edges
*
- vertices and edges with attributes (for example, weighted edges)
*
- vertices and edges with different constraints or properties (for example, bipartite
* or multimodal graphs)
*
- parallel edges (multiple edges which connect a single set of vertices)
*
- internal 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.
* Notes:
*
* - The collections returned by
Hypergraph instances
* should be treated in general as if read-only. While they are not contractually
* guaranteed (or required) to be immutable,
* this interface does not define the outcome if they are mutated.
* Mutations should be done via {add,remove}{Edge,Vertex}, or
* in the constructor.
* -
*
*
* @author Joshua O'Madadhain
*/
public interface Hypergraph
{
/**
* Returns a view of all edges in this graph. In general, this
* obeys the Collection contract, and therefore makes no guarantees
* about the ordering of the vertices within the set.
* @return a Collection view of all edges in this graph
*/
Collection getEdges();
/**
* Returns a view of all vertices in this graph. In general, this
* obeys the Collection contract, and therefore makes no guarantees
* about the ordering of the vertices within the set.
* @return a Collection view of all vertices in this graph
*/
Collection getVertices();
/**
* Returns true if this graph's vertex collection contains vertex.
* Equivalent to getVertices().contains(vertex).
* @param vertex the vertex whose presence is being queried
* @return true iff this graph contains a vertex vertex
*/
boolean containsVertex(V vertex);
/**
* Returns true if this graph's edge collection contains edge.
* Equivalent to getEdges().contains(edge).
* @param edge the edge whose presence is being queried
* @return true iff this graph contains an edge edge
*/
boolean containsEdge(E edge);
/**
* Returns the number of edges in this graph.
* @return the number of edges in this graph
*/
int getEdgeCount();
/**
* Returns the number of vertices in this graph.
* @return the number of vertices in this graph
*/
int getVertexCount();
/**
* Returns the collection of vertices which are connected to vertex
* via any edges in this graph.
* If vertex is connected to itself with a self-loop, then
* it will be included in the collection returned.
*
* @param vertex the vertex whose neighbors are to be returned
* @return the collection of vertices which are connected to vertex,
* or null if vertex is not present
*/
Collection getNeighbors(V vertex);
/**
* Returns the collection of edges in this graph which are connected to vertex.
*
* @param vertex the vertex whose incident edges are to be returned
* @return the collection of edges which are connected to vertex,
* or null if vertex is not present
*/
Collection getIncidentEdges(V vertex);
/**
* Returns the collection of vertices in this graph which are connected to edge.
* Note that for some graph types there are guarantees about the size of this collection
* (i.e., some graphs contain edges that have exactly two endpoints, which may or may
* not be distinct). Implementations for those graph types may provide alternate methods
* that provide more convenient access to the vertices.
*
* @param edge the edge whose incident vertices are to be returned
* @return the collection of vertices which are connected to edge,
* or null if edge is not present
*/
Collection getIncidentVertices(E edge);
/**
* Returns an edge that connects this vertex to v.
* If this edge is not uniquely
* defined (that is, if the graph contains more than one edge connecting
* v1 to v2), any of these edges
* may be returned. findEdgeSet(v1, v2) may be
* used to return all such edges.
* Returns null if either of the following is true:
*
* v2 is not connected to v1
* - either
v1 or v2 are not present in this graph
*
* Note: for purposes of this method, v1 is only considered to be connected to
* v2 via a given directed edge e if
* v1 == e.getSource() && v2 == e.getDest() evaluates to true.
* (v1 and v2 are connected by an undirected edge u if
* u is incident to both v1 and v2.)
*
* @param v1 the first endpoint of the returned edge
* @param v2 the second endpoint of the returned edge
* @return an edge that connects v1 to v2,
* or null if no such edge exists (or either vertex is not present)
* @see Hypergraph#findEdgeSet(Object, Object)
*/
E findEdge(V v1, V v2);
/**
* Returns all edges that connects this vertex to v.
* If this edge is not uniquely
* defined (that is, if the graph contains more than one edge connecting
* v1 to v2), any of these edges
* may be returned. findEdgeSet(v1, v2) may be
* used to return all such edges.
* Returns null if v2 is not connected to v1.
*
Returns an empty collection if either v1 or v2
* are not present in this graph.
*
*
Note: for purposes of this method, v1 is only considered to be connected to
* v2 via a given directed edge d if
* v1 == d.getSource() && v2 == d.getDest() evaluates to true.
* (v1 and v2 are connected by an undirected edge u if
* u is incident to both v1 and v2.)
*
* @param v1 the first endpoint of the returned edge set
* @param v2 the second endpoint of the returned edge set
* @return a collection containing all edges that connect v1 to v2,
* or null if either vertex is not present
* @see Hypergraph#findEdge(Object, Object)
*/
Collection findEdgeSet(V v1, V v2);
/**
* Adds vertex to this graph.
* Fails if vertex is null or already in the graph.
*
* @param vertex the vertex to add
* @return true if the add is successful, and false otherwise
* @throws IllegalArgumentException if vertex is null
*/
boolean addVertex(V vertex);
/**
* Adds edge to this graph.
* Fails under the following circumstances:
*
* edge is already an element of the graph
* - either
edge or vertices is null
* vertices has the wrong number of vertices for the graph type
* vertices are already connected by another edge in this graph,
* and this graph does not accept parallel edges
*
*
* @param edge the edge to add
* @param vertices the vertices to which the edge will be connected
* @return true if the add is successful, and false otherwise
* @throws IllegalArgumentException if edge or vertices is null,
* or if a different vertex set in this graph is already connected by edge,
* or if vertices are not a legal vertex set for edge
*/
boolean addEdge(E edge, Collection extends V> vertices);
/**
* Adds edge to this graph with type edge_type.
* Fails under the following circumstances:
*
* edge is already an element of the graph
* - either
edge or vertices is null
* vertices has the wrong number of vertices for the graph type
* vertices are already connected by another edge in this graph,
* and this graph does not accept parallel edges
* edge_type is not legal for this graph
*
*
* @param edge edge to add to this graph
* @param vertices vertices which are to be connected by this edge
* @param edge_type type of edge to add
* @return true if the add is successful, and false otherwise
* @throws IllegalArgumentException if edge or vertices is null,
* or if a different vertex set in this graph is already connected by edge,
* or if vertices are not a legal vertex set for edge
*/
boolean addEdge(E edge, Collection extends V> vertices, EdgeType
edge_type);
/**
* Removes vertex from this graph.
* As a side effect, removes any edges e incident to vertex if the
* removal of vertex would cause e to be incident to an illegal
* number of vertices. (Thus, for example, incident hyperedges are not removed, but
* incident edges--which must be connected to a vertex at both endpoints--are removed.)
*
* Fails under the following circumstances:
*
* vertex is not an element of this graph
* vertex is null
*
*
* @param vertex the vertex to remove
* @return true if the removal is successful, false otherwise
*/
boolean removeVertex(V vertex);
/**
* Removes edge from this graph.
* Fails if edge is null, or is otherwise not an element of this graph.
*
* @param edge the edge to remove
* @return true if the removal is successful, false otherwise
*/
boolean removeEdge(E edge);
/**
* Returns true if v1 and v2 share an incident edge.
* Equivalent to getNeighbors(v1).contains(v2).
*
* @param v1 the first vertex to test
* @param v2 the second vertex to test
* @return true if v1 and v2 share an incident edge
*/
boolean isNeighbor(V v1, V v2);
/**
* Returns true if vertex and edge
* are incident to each other.
* Equivalent to getIncidentEdges(vertex).contains(edge) and to
* getIncidentVertices(edge).contains(vertex).
* @param vertex vertex to test
* @param edge edge to test
* @return true if vertex and edge
* are incident to each other
*/
boolean isIncident(V vertex, E edge);
/**
* Returns the number of edges incident to vertex.
* Special cases of interest:
*
* - Incident self-loops are counted once.
*
- If there is only one edge that connects this vertex to
* each of its neighbors (and vice versa), then the value returned
* will also be equal to the number of neighbors that this vertex has
* (that is, the output of
getNeighborCount).
* - If the graph is directed, then the value returned will be
* the sum of this vertex's indegree (the number of edges whose
* destination is this vertex) and its outdegree (the number
* of edges whose source is this vertex), minus the number of
* incident self-loops (to avoid double-counting).
*
* Equivalent to getIncidentEdges(vertex).size().
*
* @param vertex the vertex whose degree is to be returned
* @return the degree of this node
* @see Hypergraph#getNeighborCount(Object)
*/
int degree(V vertex);
/**
* Returns the number of vertices that are adjacent to vertex
* (that is, the number of vertices that are incident to edges in vertex's
* incident edge set).
*
*
Equivalent to getNeighbors(vertex).size().
* @param vertex the vertex whose neighbor count is to be returned
* @return the number of neighboring vertices
*/
int getNeighborCount(V vertex);
/**
* Returns the number of vertices that are incident to edge.
* For hyperedges, this can be any nonnegative integer; for edges this
* must be 2 (or 1 if self-loops are permitted).
*
*
Equivalent to getIncidentVertices(edge).size().
* @param edge the edge whose incident vertex count is to be returned
* @return the number of vertices that are incident to edge.
*/
int getIncidentCount(E edge);
/**
* Returns the edge type of edge in this graph.
* @param edge the edge whose type is to be returned
* @return the EdgeType of edge, or null if edge has no defined type
*/
EdgeType getEdgeType(E edge);
/**
* Returns the default edge type for this graph.
*
* @return the default edge type for this graph
*/
EdgeType getDefaultEdgeType();
/**
* Returns the collection of edges in this graph which are of type edge_type.
* @param edge_type the type of edges to be returned
* @return the collection of edges which are of type edge_type, or
* null if the graph does not accept edges of this type
* @see EdgeType
*/
Collection getEdges(EdgeType edge_type);
/**
* Returns the number of edges of type edge_type in this graph.
* @param edge_type the type of edge for which the count is to be returned
* @return the number of edges of type edge_type in this graph
*/
int getEdgeCount(EdgeType edge_type);
/**
* Returns a Collection view of the incoming edges incident to vertex
* in this graph.
* @param vertex the vertex whose incoming edges are to be returned
* @return a Collection view of the incoming edges incident
* to vertex in this graph
*/
Collection getInEdges(V vertex);
/**
* Returns a Collection view of the outgoing edges incident to vertex
* in this graph.
* @param vertex the vertex whose outgoing edges are to be returned
* @return a Collection view of the outgoing edges incident
* to vertex in this graph
*/
Collection getOutEdges(V vertex);
/**
* Returns the number of incoming edges incident to vertex.
* Equivalent to getInEdges(vertex).size().
* @param vertex the vertex whose indegree is to be calculated
* @return the number of incoming edges incident to vertex
*/
int inDegree(V vertex);
/**
* Returns the number of outgoing edges incident to vertex.
* Equivalent to getOutEdges(vertex).size().
* @param vertex the vertex whose outdegree is to be calculated
* @return the number of outgoing edges incident to vertex
*/
int outDegree(V vertex);
/**
* 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.
* @param directed_edge the edge whose source is to be returned
* @return the source of directed_edge if it is a directed edge in this graph, or null otherwise
*/
V getSource(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.
* @param directed_edge the edge whose destination is to be returned
* @return the destination of directed_edge if it is a directed edge in this graph, or null otherwise
*/
V getDest(E directed_edge);
/**
* 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.
* @param vertex the vertex whose predecessors are to be returned
* @return a Collection view of the predecessors of
* vertex in this graph
*/
Collection getPredecessors(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.
* @param vertex the vertex whose predecessors are to be returned
* @return a Collection view of the successors of
* vertex in this graph
*/
Collection getSuccessors(V vertex);
}
Ads help maintain this website.