org.nongnu.multigraph

Class MultiDiGraph<N,E>

java.lang.Object

java.util.Observable

org.nongnu.multigraph.MultiDiGraph<N,E>

All Implemented Interfaces:

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

Direct Known Subclasses:

MultiGraph, SimpleDiGraph

public class MultiDiGraph<N,E>
extends java.util.Observable
implements Graph<N,E>

A multi-edge, directed graph implementation of the Graph interface.

This implementation allows for multiple, directed edges between any nodes, including between the same node.

XXX: As SimpleDiGraph inherits from this, this class probably should not be public. We don't really want different restrictions of the Graph to be type-compatible.

Constructor Summary

Constructors

Constructor and Description
MultiDiGraph()

Method Summary

Modifier and Type	Method and Description
protected boolean	_remove(N from, N to, E label) The core, central edge removal method.
protected void	_set(N from, N to, int weight, E label) The core, central set method.
boolean	add(N node) Add the given node to the graph, sans edges
boolean	addAll(java.util.Collection<? extends N> c)
float	avg_nodal_degree()
void	clear_all_edges() Clear all edges from the graph.
void	clear()
boolean	contains(java.lang.Object o)
boolean	containsAll(java.util.Collection<?> c)
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	equals(java.lang.Object o)
int	hashCode()
boolean	is_directed()
boolean	is_linked(N from, N to) Determine if there is a link from one node to another.
boolean	is_simple()
boolean	isEmpty()
java.util.Iterator<N>	iterator()
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.
boolean	remove(java.lang.Object o)
boolean	removeAll(java.util.Collection<?> c)
boolean	retainAll(java.util.Collection<?> c)
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.
int	size()
java.util.Set<N>	successors(N node)
java.lang.Object[]	toArray()
<N> N[]	toArray(N[] a)
java.lang.String	toString()
void	unplugObservable() Unplug the delivery of Observable events.

Methods inherited from class java.util.Observable

addObserver, clearChanged, countObservers, deleteObserver, deleteObservers, hasChanged, setChanged

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.nongnu.multigraph.Graph

addObserver, countObservers, deleteObserver, deleteObservers, hasChanged

Methods inherited from interface java.util.Set

spliterator

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

MultiDiGraph

public MultiDiGraph()

Method Detail

_set

protected void _set(N from,
                    N to,
                    int weight,
                    E label)

The core, central set method. All other set methods are filters for this method, meant to check invariants, apply various requirements. etc. Exported to package so that other types of graph may be subclassed from this

Parameters:

from - The N-typed node from which to set the new edge

to - The N-typed node to which the edge should be set

weight - The weight of the node, unweighted edges should just be set to 1.

label - The E-typed edge label object for the graph edge.

set

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

Description copied from interface: Graph

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.

Specified by:

set in interface Graph<N,E>

Parameters:

from - Node from which the edge originates.

to - Node to which the edges goes.

label - The user's label for this edge.

set

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

Description copied from interface: Graph

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

Specified by:

set in interface Graph<N,E>

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

See Also:

Graph.set(Object, Object, Object)

_remove

protected boolean _remove(N from,
                          N to,
                          E label)

The core, central edge removal method. All other remove methods are filters for this method, meant to check invariants, apply various requirements. etc. Exported to package so that other types of graph may be subclassed from this

Parameters:

from - The N-typed node from which the edge is to be removed

to - The N-typed node to which the edge is to be removed

label - The E-typed edge label object for the edge which is to be removed. If specified, only edges matching the label will be removed. If not specified, all edges will be removed.

remove

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

Description copied from interface: Graph

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

Specified by:

remove in interface Graph<N,E>

Returns:

Whether an edge was removed

remove

public boolean remove(N from,
                      N to)

Description copied from interface: Graph

Remove all edges that go from one node to another

Specified by:

remove in interface Graph<N,E>

Returns:

Whether an edge was removed

See Also:

Graph.set(Object, Object, Object), Graph.add(Object)

edges

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

Specified by:

edges in interface Graph<N,E>

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

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

Description copied from interface: Graph

Find the edges going from one node to another node.

Specified by:

edges in interface Graph<N,E>

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:

Graph.edges(Object)

edge

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

Description copied from interface: Graph

Find the first edge from a node to another node.

Specified by:

edge in interface Graph<N,E>

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.

edge

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

Description copied from interface: Graph

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

Specified by:

edge in interface Graph<N,E>

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.

successors

public java.util.Set<N> successors(N node)

Specified by:

successors in interface Graph<N,E>

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.

edge_outdegree

public int edge_outdegree(N node)

Description copied from interface: Graph

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

Specified by:

edge_outdegree in interface Graph<N,E>

nodal_outdegree

public int nodal_outdegree(N node)

Specified by:

nodal_outdegree in interface Graph<N,E>

Returns:

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

avg_nodal_degree

public float avg_nodal_degree()

Specified by:

avg_nodal_degree in interface Graph<N,E>

Returns:

The average nodal out-degree.

link_count

public long link_count()

Specified by:

link_count in interface Graph<N,E>

Returns:

The number of edges in the graph

max_nodal_degree

public int max_nodal_degree()

Specified by:

max_nodal_degree in interface Graph<N,E>

Returns:

The maximum degree of any node in the graph

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

random_node_iterable

public java.lang.Iterable<N> random_node_iterable()

Description copied from interface: Graph

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

Specified by:

random_node_iterable in interface Graph<N,E>

random_edge_iterable

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

Description copied from interface: Graph

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

Specified by:

random_edge_iterable in interface Graph<N,E>

add

public boolean add(N node)

Description copied from interface: Graph

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>

Specified by:

add in interface Graph<N,E>

addAll

public boolean addAll(java.util.Collection<? extends N> c)

Specified by:

addAll in interface java.util.Collection<N>

Specified by:

addAll in interface java.util.Set<N>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<N>

Specified by:

clear in interface java.util.Set<N>

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection<N>

Specified by:

contains in interface java.util.Set<N>

containsAll

public boolean containsAll(java.util.Collection<?> c)

Specified by:

containsAll in interface java.util.Collection<N>

Specified by:

containsAll in interface java.util.Set<N>

equals

public boolean equals(java.lang.Object o)

Specified by:

equals in interface java.util.Collection<N>

Specified by:

equals in interface java.util.Set<N>

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Collection<N>

Specified by:

hashCode in interface java.util.Set<N>

Overrides:

hashCode in class java.lang.Object

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection<N>

Specified by:

isEmpty in interface java.util.Set<N>

size

public int size()

Specified by:

size in interface java.util.Collection<N>

Specified by:

size in interface java.util.Set<N>

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection<N>

Specified by:

toArray in interface java.util.Set<N>

toArray

public <N> N[] toArray(N[] a)

Specified by:

toArray in interface java.util.Collection<N>

Specified by:

toArray in interface java.util.Set<N>

iterator

public java.util.Iterator<N> iterator()

Specified by:

iterator in interface java.lang.Iterable<N>

Specified by:

iterator in interface java.util.Collection<N>

Specified by:

iterator in interface java.util.Set<N>

clear_all_edges

public void clear_all_edges()

Description copied from interface: Graph

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.

Specified by:

clear_all_edges in interface Graph<N,E>

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection<N>

Specified by:

remove in interface java.util.Set<N>

removeAll

public boolean removeAll(java.util.Collection<?> c)

Specified by:

removeAll in interface java.util.Collection<N>

Specified by:

removeAll in interface java.util.Set<N>

retainAll

public boolean retainAll(java.util.Collection<?> c)

Specified by:

retainAll in interface java.util.Collection<N>

Specified by:

retainAll in interface java.util.Set<N>

plugObservable

public void plugObservable()

Description copied from interface: Graph

"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.

Specified by:

plugObservable in interface Graph<N,E>

unplugObservable

public void unplugObservable()

Description copied from interface: Graph

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.

Specified by:

unplugObservable in interface Graph<N,E>

notifyObservers

public void notifyObservers()

Specified by:

notifyObservers in interface Graph<N,E>

Overrides:

notifyObservers in class java.util.Observable

See Also:

Observable

notifyObservers

public void notifyObservers(java.lang.Object arg)

Specified by:

notifyObservers in interface Graph<N,E>

Overrides:

notifyObservers in class java.util.Observable

See Also:

Observable

is_directed

public boolean is_directed()

Specified by:

is_directed in interface Graph<N,E>

Returns:

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

is_simple

public boolean is_simple()

Specified by:

is_simple in interface Graph<N,E>

Returns:

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

is_linked

public boolean is_linked(N from,
                         N to)

Description copied from interface: Graph

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

Specified by:

is_linked in interface Graph<N,E>

Returns:

True if an edge exists from -> to