edu.ucla.sspace.graph

Interface Multigraph<T,E extends TypedEdge<T>>

All Superinterfaces:

Graph<E>

All Known Implementing Classes:

DirectedMultigraph, UndirectedMultigraph, WeightedDirectedMultigraph

public interface Multigraph<T,E extends TypedEdge<T>>
extends Graph<E>

An interface specification for interacting with MultiGraph objects. A multigraph contains a set of vertices and a list of edges between vertices, where multiple, parallel edges may exist between two vertices.

The edge type parameter for a multigraph is used to distinguish between different edges between the same two nodes. For example, a multigraph may represents cities with edges indicating the different types of transportation (e.g. car, train, bus) between two cities. Edge type may additionally have their own subtypes (e.g., airline carrier, bus company, etc.). This multigraph class only considers the value of the edge type to determine if two edges are equal, i.e. two edges between the same nodes are equal if for their edge types t1 and t2, t1.equals(t2).

Author:

David Jurgens

Method Summary

Methods

Modifier and Type	Method and Description
void	clearEdges(T edgeType) Removes all the edges in the graph with the specified edge type.
boolean	contains(int vertex1, int vertex2, T edgeType) Returns true if there exists an edge between vertex1 and vertex2 of the specified type.
Multigraph<T,E>	copy(Set<Integer> vertices) Creates a copy of this graph containing only the specified number of vertices and all edges between those vertices.
Set<E>	edges() Returns the set of typed edges in the graph
Set<E>	edges(T type) Returns the set of edges with the corresponding type or the empty set if no edges of that exist.
Set<T>	edgeTypes() Returns the set of edge types currently present in this graph.
Set<E>	getAdjacencyList(int vertex) Returns the set of typed edges connected to the vertex.
Set<E>	getEdges(int vertex1, int vertex2) Returns the set of TypedEdge instances that connect the two vertices.
Multigraph<T,E>	subgraph(Set<Integer> vertices) Returns a view of this graph containing only the specified vertices where the returned graph's vertinces are renamed (0, ..., n).
Multigraph<T,E>	subgraph(Set<Integer> vertices, Set<T> edgeTypes) Returns a subgraph of this graph containing only the specified vertices and edges of the specified types.

Methods inherited from interface edu.ucla.sspace.graph.Graph

add, add, clear, clearEdges, contains, contains, contains, degree, getNeighbors, hasCycles, order, remove, remove, size, vertices

Method Detail

clearEdges

void clearEdges(T edgeType)

Removes all the edges in the graph with the specified edge type.

contains

boolean contains(int vertex1,
               int vertex2,
               T edgeType)

Returns true if there exists an edge between vertex1 and vertex2 of the specified type.

copy

Multigraph<T,E> copy(Set<Integer> vertices)

Creates a copy of this graph containing only the specified number of vertices and all edges between those vertices. If vertices is empty a new, empty graph of this instance's type is returned. Any changes made to this graph will not be reflected in returned copy or vice-versa.

Specified by:

copy in interface Graph<E extends TypedEdge<T>>

edges

Set<E> edges()

Returns the set of typed edges in the graph

Specified by:

edges in interface Graph<E extends TypedEdge<T>>

edges

Set<E> edges(T type)

Returns the set of edges with the corresponding type or the empty set if no edges of that exist.

edgeTypes

Set<T> edgeTypes()

Returns the set of edge types currently present in this graph.

getAdjacencyList

Set<E> getAdjacencyList(int vertex)

Returns the set of typed edges connected to the vertex.

Specified by:

getAdjacencyList in interface Graph<E extends TypedEdge<T>>

getEdges

Set<E> getEdges(int vertex1,
              int vertex2)

Returns the set of TypedEdge instances that connect the two vertices. If no edges connect the vertices, the set will be empty but non-null.

Specified by:

getEdges in interface Graph<E extends TypedEdge<T>>

subgraph

Multigraph<T,E> subgraph(Set<Integer> vertices)

Returns a view of this graph containing only the specified vertices where the returned graph's vertinces are renamed (0, ..., n). This renaming is to ensure a conceptual distance between the "new" returned graph and the backing graph in terms of vertex labeling; for example, adding vertex n to the subgraph may not necessarily correspond to vertex n in the backing graph.

Only edges connecting two vertices in the provided set will be viewable in the subgraph. Any changes to the subgraph will be reflected in this graph and vice versa.

This view allows for direct manipulation of a part of the graph. For example, clearing this subgraph will remove all of its corresponding vertices and edges from the backing graph.

Specified by:

subgraph in interface Graph<E extends TypedEdge<T>>

Parameters:

vertices - the vertices to include in the subgraph

subgraph

Multigraph<T,E> subgraph(Set<Integer> vertices,
                       Set<T> edgeTypes)

Returns a subgraph of this graph containing only the specified vertices and edges of the specified types. Note that if all of the vertices are specified, this method can be used to extract edge-type-specific versions of this multigraph. Any attempt subsequent attempt to add an edge of a type other than the specified types to this subgraph will fail. Implementations are free to specify whether this will be an exception