galois.objects.graph
Interface Graph<N extends GObject>

Type Parameters:

N - the type of the data contained in a node

All Superinterfaces:

GObject, Mappable<GNode<N>>

All Known Subinterfaces:

DoubleGraph<N>, FloatGraph<N>, IndexedGraph<N>, IntGraph<N>, LongGraph<N>, ObjectGraph<N,E>

All Known Implementing Classes:

ArrayIndexedTree, LocalComputationGraph, VoidGraphToObjectGraphAdapter

public interface Graph<N extends GObject>
extends Mappable<GNode<N>>, GObject

Root interface in the graph hierarchy. A graph is a set of nodes connected by edges. Two nodes can be connected by at most one edge (i.e., this graph is not a multigraph), but self edges are allowed.
This interface supports the storage of data in the nodes of the graph, but not in the edges. Use ObjectGraph if you need to store values on the edges too.

Method Summary

boolean	add(GNode<N> n) Adds a node to the graph.
boolean	add(GNode<N> n, byte flags) Adds a node to the graph.
boolean	addNeighbor(GNode<N> src, GNode<N> dst) Adds an edge between the two nodes.
boolean	addNeighbor(GNode<N> src, GNode<N> dst, byte flags) Adds an edge between the two nodes.
boolean	contains(GNode<N> n) Checks if a node is in the graph All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.
boolean	contains(GNode<N> n, byte flags) Checks if a node is in the graph
GNode<N>	createNode(N n) Creates a new node holding the indicated data.
GNode<N>	createNode(N n, byte flags) Creates a new node holding the indicated data.
boolean	hasNeighbor(GNode<N> src, GNode<N> dst) Checks if there is an edge between the two nodes in this graph.
boolean	hasNeighbor(GNode<N> src, GNode<N> dst, byte flags) Checks if there is an edge between the two nodes in this graph.
int	inNeighborsSize(GNode<N> src) Computes the number of in neighbors of the node, i.e., the number of different vertices that have an outgoing edge that ends at the indicated node.
int	inNeighborsSize(GNode<N> src, byte flags) Computes the number of in neighbors of the node, i.e., the number of different vertices that have an outgoing edge that ends at the indicated node.
boolean	isDirected() Tests if the current graph is directed.
void	mapInNeighbors(GNode<N> src, LambdaVoid<GNode<N>> body) Applies the function passed as parameter to every in neighbor of the given node exactly once.
void	mapInNeighbors(GNode<N> src, LambdaVoid<GNode<N>> body, byte flags) Applies the function passed as parameter to every in neighbor of the given node exactly once.
int	outNeighborsSize(GNode<N> src) Computes the number of out neighbors of the node, i.e., the number of different vertices that have an incoming edge that starts at the indicated node.
int	outNeighborsSize(GNode<N> src, byte flags) Computes the number of out neighbors of the node, i.e., the number of different vertices that have an incoming edge that starts at the indicated node.
boolean	remove(GNode<N> n) Removes a node from the graph along with all its outgoing/incoming edges.
boolean	remove(GNode<N> n, byte flags) Removes a node from the graph along with all its outgoing/incoming edges.
boolean	removeNeighbor(GNode<N> src, GNode<N> dst) Removes the edge between the two nodes from this graph.
boolean	removeNeighbor(GNode<N> src, GNode<N> dst, byte flags) Removes the edge between the two nodes from this graph.
int	size() Returns the number of nodes in this graph.
int	size(byte flags) Returns the number of nodes in this graph.

Methods inherited from interface galois.objects.Mappable

map, map, map, map, map, map, mapInternal, mapInternal, mapInternal, mapInternalDone

Methods inherited from interface galois.objects.GObject

access

Method Detail

createNode

GNode<N> createNode(N n)

Creates a new node holding the indicated data. The new node is not automatically added to the graph (use add(GNode, byte)),

Parameters:

n - data contained in the new node.

Returns:

the newly created node.

createNode

GNode<N> createNode(N n,
                    byte flags)

Creates a new node holding the indicated data. The new node is not automatically added to the graph (use add(GNode, byte)),

Parameters:

n - data contained in the new node.

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

the newly created node.

add

boolean add(GNode<N> n)

Adds a node to the graph. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

n - node created by the current graph

Returns:

true if the node was not already in the graph

Throws:

IllegalArgumentException - if the node has been created by another graph

add

boolean add(GNode<N> n,
            byte flags)

Adds a node to the graph.

Parameters:

n - node created by the current graph

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

true if the node was not already in the graph

Throws:

IllegalArgumentException - if the node has been created by another graph

remove

boolean remove(GNode<N> n)

Removes a node from the graph along with all its outgoing/incoming edges. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

n - node to be removed

Returns:

true if the node was removed from the graph

remove

boolean remove(GNode<N> n,
               byte flags)

Removes a node from the graph along with all its outgoing/incoming edges.

Parameters:

n - node to be removed

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

true if the node was removed from the graph

contains

boolean contains(GNode<N> n)

Checks if a node is in the graph All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

n - the node to check for

Returns:

true if the node is part of this graph

contains

boolean contains(GNode<N> n,
                 byte flags)

Checks if a node is in the graph

Parameters:

n - the node to check for

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

true if the node is part of this graph

size

int size()

Returns the number of nodes in this graph. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Returns:

the number of nodes (vertices) in this graph

size

int size(byte flags)

Returns the number of nodes in this graph.

Parameters:

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

the number of nodes (vertices) in this graph

addNeighbor

boolean addNeighbor(GNode<N> src,
                    GNode<N> dst)

Adds an edge between the two nodes. If the graph is directed, the first node is interpreted to be the source of the edge. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

src - the source of the edge

dst - the destination of the edge

Returns:

true if the edge was not already in the graph

addNeighbor

boolean addNeighbor(GNode<N> src,
                    GNode<N> dst,
                    byte flags)

Adds an edge between the two nodes. If the graph is directed, the first node is interpreted to be the source of the edge.

Parameters:

src - the source of the edge

dst - the destination of the edge

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

true if the edge was not already in the graph

removeNeighbor

boolean removeNeighbor(GNode<N> src,
                       GNode<N> dst)

Removes the edge between the two nodes from this graph. If the graph is directed, the first node is interpreted to be the source of the edge. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

src - the source of the edge

dst - the target of the edge

Returns:

true if the edge was removed from this graph

removeNeighbor

boolean removeNeighbor(GNode<N> src,
                       GNode<N> dst,
                       byte flags)

Removes the edge between the two nodes from this graph. If the graph is directed, the first node is interpreted to be the source of the edge.

Parameters:

src - the source of the edge

dst - the target of the edge

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

true if the edge was removed from this graph

hasNeighbor

boolean hasNeighbor(GNode<N> src,
                    GNode<N> dst)

Checks if there is an edge between the two nodes in this graph. If the graph is directed, the first node is interpreted to be the source of the edge. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

src - the source of the edge

dst - the target of the edge

Returns:

true if the two nodes are neighbors in this graph

hasNeighbor

boolean hasNeighbor(GNode<N> src,
                    GNode<N> dst,
                    byte flags)

Checks if there is an edge between the two nodes in this graph. If the graph is directed, the first node is interpreted to be the source of the edge.

Parameters:

src - the source of the edge

dst - the target of the edge

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

true if the two nodes are neighbors in this graph

mapInNeighbors

void mapInNeighbors(GNode<N> src,
                    LambdaVoid<GNode<N>> body)

Applies the function passed as parameter to every in neighbor of the given node exactly once. For example, if we assume that each node contains an integer and we want to print the integer contained in each incoming neighbor of node in graph

   graph.mapInNeighbors(node, new LambdaVoid<GNode<Integer>>() {
      public void call(GNode<Integer> inNeighbor) {
        System.out.println(inNeighbor.getData());
     }
   }
 

If you wish to apply a function to the out neighbors, please use GNode#map All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

src - a node in the graph

body - the function to be applied once to each incoming neighbor

Throws:

ConcurrentModificationException - if the function modifies the set of in neighbors of the node

See Also:

Mappable.map(util.fn.LambdaVoid)

mapInNeighbors

void mapInNeighbors(GNode<N> src,
                    LambdaVoid<GNode<N>> body,
                    byte flags)

Applies the function passed as parameter to every in neighbor of the given node exactly once. For example, if we assume that each node contains an integer and we want to print the integer contained in each incoming neighbor of node in graph

   graph.mapInNeighbors(node, new LambdaVoid<GNode<Integer>>() {
      public void call(GNode<Integer> inNeighbor) {
        System.out.println(inNeighbor.getData());
     }
   }
 

If you wish to apply a function to the out neighbors, please use GNode#map

Parameters:

src - a node in the graph

body - the function to be applied once to each incoming neighbor

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Throws:

ConcurrentModificationException - if the function modifies the set of in neighbors of the node

See Also:

Mappable.map(util.fn.LambdaVoid)

inNeighborsSize

int inNeighborsSize(GNode<N> src)

Computes the number of in neighbors of the node, i.e., the number of different vertices that have an outgoing edge that ends at the indicated node. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

src - a node in the graph

Returns:

the number of incoming neighbors

inNeighborsSize

int inNeighborsSize(GNode<N> src,
                    byte flags)

Computes the number of in neighbors of the node, i.e., the number of different vertices that have an outgoing edge that ends at the indicated node.

Parameters:

src - a node in the graph

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

the number of incoming neighbors

outNeighborsSize

int outNeighborsSize(GNode<N> src)

Computes the number of out neighbors of the node, i.e., the number of different vertices that have an incoming edge that starts at the indicated node. All the Galois runtime actions (e.g., conflict detection) will be performed when the method is executed.

Parameters:

src - a node in the graph

Returns:

the number of outgoing neighbors

outNeighborsSize

int outNeighborsSize(GNode<N> src,
                     byte flags)

Computes the number of out neighbors of the node, i.e., the number of different vertices that have an incoming edge that starts at the indicated node.

Parameters:

src - a node in the graph

flags - Galois runtime actions (e.g., conflict detection) that need to be executed upon invocation of this method. See MethodFlag

Returns:

the number of outgoing neighbors

isDirected

boolean isDirected()

Tests if the current graph is directed.

Returns:

true if the graph uses directed edges