org.nongnu.multigraph

Interface Graph<N,E>

All Superinterfaces:

java.util.Collection<N>, java.lang.Iterable<N>, java.util.Set<N>

All Known Implementing Classes:

MultiDiGraph, MultiGraph, PartitionGraph, SimpleDiGraph, SimpleGraph, SyncGraph

public interface Graph<N,E>
extends java.util.Set<N>

General Graph interface, for graphs of N-typed nodes, each having 0 or more edges to other nodes, labeled L.

Edges may optionally be weighted, otherwise they are assigned a default weight of 1. Weights of edges may be revised.

This interface does not specify how many edges are allowed between nodes and does specify whether a node may have an edge to itself, or not. A graph which explicitly allows both these cases is called a "multi-graph", a graph which does not allow either condition is called a "simple-graph".

This interface does not restrict whether edges are directed or not. Where edges are directed, then the presence of an edge out from one node to another does not imply that the other node has a corresponding edge back. Where edges are undirected, then the presence of an edge at one node must imply the presence of a similar edge at the other node.

This interface does not allow for "hyper-graphs", where 1 edge may connect to multiple nodes, however hyper-graphs can be supported by using a node to act as hyper-edge.

Author:

Paul Jakma

Method Summary

Modifier and Type	Method and Description
boolean	add(N node) Add the given node to the graph, sans edges
void	addObserver(java.util.Observer o)
float	avg_nodal_degree()
void	clear_all_edges() Clear all edges from the graph.
int	countObservers()
void	deleteObserver(java.util.Observer o)
void	deleteObservers()
int	edge_outdegree(N node) The out-degree for a give node.
Edge<N,E>	edge(N from, N to) Find the first edge from a node to another node.
Edge<N,E>	edge(N from, N to, E label) Find the edge with the given label, from the one node to another node, if it exists.
java.util.Set<Edge<N,E>>	edges(N from)
java.util.Collection<Edge<N,E>>	edges(N from, N to) Find the edges going from one node to another node.
boolean	hasChanged()
boolean	is_directed()
boolean	is_linked(N from, N to) Determine if there is a link from one node to another.
boolean	is_simple()
long	link_count()
int	max_nodal_degree()
int	nodal_outdegree(N node)
void	notifyObservers()
void	notifyObservers(java.lang.Object arg)
void	plugObservable() "Plug" delivery of Observable events to observers, so that any such events are instead queued up internally, and potentially coalesced, rather than delivered to Observers.
java.lang.Iterable<Edge<N,E>>	random_edge_iterable(N n) Provide a random-access Iterable over the <Edge<N,E>>-edges from the given node.
java.lang.Iterable<N>	random_node_iterable() Provide a random-access Iterable over the <N>-nodes in the graph.
boolean	remove(N from, N to) Remove all edges that go from one node to another
boolean	remove(N from, N to, E label) Remove 1 specific edge, given by the label, from between two nodes.
void	set(N from, N to, E label) Set an edge from one node to another with the given label.
void	set(N from, N to, E label, int weight) Set an edge from one node to another with the given label and weight.
java.util.Set<N>	successors(N from)
void	unplugObservable() Unplug the delivery of Observable events.

Methods inherited from interface java.util.Set

addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, spliterator, toArray, toArray

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Method Detail

is_directed

boolean is_directed()

Returns:

Whether the graph is directed or not, i.e. whether edges have a direction.

is_simple

boolean is_simple()

Returns:

Whether the graph is simple or not. A simple graph allows only single edges between nodes.

set

void set(N from,
         N to,
         E label)

Set an edge from one node to another with the given label. Weight defaults to 1. Nodes are automatically added to graph, as needs be. If a given edge for <from,to,label> }already exists, then the weight is updated.

Parameters:

from - Node from which the edge originates.

to - Node to which the edges goes.

label - The user's label for this edge.

set

void set(N from,
         N to,
         E label,
         int weight)

Set an edge from one node to another with the given label and weight.

Parameters:

weight - a user-specified metric or weight for the edge

See Also:

set(Object, Object, Object)

add

boolean add(N node)

Add the given node to the graph, sans edges

Specified by:

add in interface java.util.Collection<N>

Specified by:

add in interface java.util.Set<N>

remove

boolean remove(N from,
               N to,
               E label)

Remove 1 specific edge, given by the label, from between two nodes.

Returns:

Whether an edge was removed

remove

boolean remove(N from,
               N to)

Remove all edges that go from one node to another

Returns:

Whether an edge was removed

See Also:

set(Object, Object, Object), add(Object)

clear_all_edges

void clear_all_edges()

Clear all edges from the graph. This can NOT be done by iterating over the sets of edges from each node, as that will raise a concurrent modification exception.

edge_outdegree

int edge_outdegree(N node)

The out-degree for a give node. I.e. the number of edges leaving the node.

nodal_outdegree

int nodal_outdegree(N node)

Parameters:

node -

Returns:

The number of distinct nodes to which this node has edges.

avg_nodal_degree

float avg_nodal_degree()

Returns:

The average nodal out-degree.

link_count

long link_count()

Returns:

The number of edges in the graph

max_nodal_degree

int max_nodal_degree()

Returns:

The maximum degree of any node in the graph

successors

java.util.Set<N> successors(N from)

Parameters:

node - The given node, which is to be queried.

Returns:

The set of nodes that succeed the given node. I.e. those nodes to which the given node has an edge. The returned set is read-only and may not be modified. The returned set will be null if the node does not exist, and will be the empty set if the node exists but has no successors.

edges

java.util.Set<Edge<N,E>> edges(N from)

Parameters:

node - The given node, which is to be queried.

Returns:

The set of edges that go out from this node. The returned set is read-only and may not be modified. The set will be null if the node does not exist, and an empty set if the node exists but has no edges.

edges

java.util.Collection<Edge<N,E>> edges(N from,
                                      N to)

Find the edges going from one node to another node.

Parameters:

from - Which node we want to query edges from.

to - The node to which we're looking for an edge.

Returns:

An immutable Collection of edges going from

See Also:

edges(Object)

edge

Edge<N,E> edge(N from,
               N to)

Find the first edge from a node to another node.

Parameters:

from - Which node we want to query edges from.

to - The node to which we're looking for an edge.

Returns:

An edge going from from->to if any exist, or null otherwise.

is_linked

boolean is_linked(N from,
                  N to)

Determine if there is a link from one node to another.

Returns:

True if an edge exists from -> to

edge

Edge<N,E> edge(N from,
               N to,
               E label)

Find the edge with the given label, from the one node to another node, if it exists.

Parameters:

from - Which node we want to query edges from.

to - The node to which we're looking for an edge.

label - The label of the edge we're interested in.

Returns:

The edge going from from->to specified by the given label, if it exists, or null otherwise.

random_node_iterable

java.lang.Iterable<N> random_node_iterable()

Provide a random-access Iterable over the <N>-nodes in the graph.

random_edge_iterable

java.lang.Iterable<Edge<N,E>> random_edge_iterable(N n)

Provide a random-access Iterable over the <Edge<N,E>>-edges from the given node.

addObserver

void addObserver(java.util.Observer o)

See Also:

Observable

countObservers

int countObservers()

See Also:

Observable

deleteObserver

void deleteObserver(java.util.Observer o)

See Also:

Observable

deleteObservers

void deleteObservers()

See Also:

Observable

hasChanged

boolean hasChanged()

See Also:

Observable

notifyObservers

void notifyObservers()

See Also:

Observable

notifyObservers

void notifyObservers(java.lang.Object arg)

See Also:

Observable

plugObservable

void plugObservable()

"Plug" delivery of Observable events to observers, so that any such events are instead queued up internally, and potentially coalesced, rather than delivered to Observers. This potentially allows bulk updates to be made to the graph more efficiently.

unplugObservable

void unplugObservable()

Unplug the delivery of Observable events. Stored events will be delivered, though potentially coalesced, so that multiple events for the same object are collapsed into one. Further, a general "notifyObservers" event will coalesce with and subsume *all* events for specific objects.