com.nwawsoft.util.datastructures

Class Graph

java.lang.Object

com.nwawsoft.util.datastructures.Graph

public class Graph
extends java.lang.Object

Graph data structure. A Graph can contain none to infinitely many GraphNode objects with or without edges between them, which again can be either weighted ur unweighted.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Graph.GraphNode Defines GraphNode objects as they are used in the Graph class.

Constructor Summary

Constructors

Constructor and Description
Graph() Creates a Graph object with no GraphNode objects.

Method Summary

Modifier and Type	Method and Description
void	addBidirectionalEdge(Graph.GraphNode graphNode1, Graph.GraphNode graphNode2, double weight) Adds an edge from graphNode1 to graphNode2 and from graphNode1 to graphNode2, both with the specified weight.
void	addEdge(Graph.GraphNode graphNode1, Graph.GraphNode graphNode2, double weight) Adds an edge from graphNode1 to graphNode2 with the specified weight.
void	addNode(Graph.GraphNode graphNode) Adds the specified GraphNode object to the Graph.
boolean	allNodesMarked() Returns whether all GraphNode objects in the Graph are marked.
boolean	contains(Graph.GraphNode graphNode) Returns whether a specified GraphNode object is in the Graph.
boolean	contains(java.lang.String nodeName) Returns whether a GraphNode object with the specified name is in the Graph.
double	cumulativeEdgeWeight(Graph.GraphNode graphNode) Returns the summed up edgeWeights of all edges of the specified GraphNode object.
double	edgeWeightSum() Returns the sum of all edgeWeights in the Graph.
double	getEdgeWeight(Graph.GraphNode graphNode1, Graph.GraphNode graphNode2) Returns the weight of the edge from graphNode1 to graphNode2.
List	getNeighbors(Graph.GraphNode graphNode) Returns a new List object containing all GraphNode objects that are neighbors of the specified GraphNode object.
Graph.GraphNode	getNode(java.lang.String nodeName) Returns the GraphNode object with the specified name.
List	getNodes() Returns a new List object containing all GraphNode objects in the Graph.
boolean	hasEdge(Graph.GraphNode graphNode1, Graph.GraphNode graphNode2) Returns whether there is an edge between the specified GraphNode objects in the Graph.
Graph.GraphNode	highestWeight() Returns the GraphNode object with the highest summed up edgeWeights in the Graph.
boolean	isEmpty() Returns true if the Graph contains no GraphNode objects.
void	removeEdge(Graph.GraphNode graphNode1, Graph.GraphNode graphNode2) Removes the edge from graphNode1 to graphNode2 if there was any.
void	removeEdges(Graph.GraphNode graphNode1, Graph.GraphNode graphNode2) Removes both edges between graphNode1 and graphNode2 if there were any.
void	removeMarks() Sets the 'marked' boolean to false for all GraphNode objects in the Graph.
void	removeNode(Graph.GraphNode graphNode) If graphNode !

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Graph

public Graph()

Creates a Graph object with no GraphNode objects.

Method Detail

isEmpty

public boolean isEmpty()

Returns true if the Graph contains no GraphNode objects. Else false.

Returns:

true if the Graph contains no GraphNode objects. Else false.

addNode

public void addNode(Graph.GraphNode graphNode)

Adds the specified GraphNode object to the Graph. If it is null or a GraphNode object with the same name exists in the Graph already it is not added.

Parameters:

graphNode - the GraphNode object to add to the Graph.

contains

public boolean contains(java.lang.String nodeName)

Returns whether a GraphNode object with the specified name is in the Graph.

Parameters:

nodeName - the name of a GraphNode object.

Returns:

true if a GraphNode object with the specified name is in the Graph, else false.

contains

public boolean contains(Graph.GraphNode graphNode)

Returns whether a specified GraphNode object is in the Graph.

Parameters:

graphNode - a GraphNode object.

Returns:

true if the GraphNode is in the Graph, else false.

getNode

public Graph.GraphNode getNode(java.lang.String nodeName)

Returns the GraphNode object with the specified name. Returns null if there is no such GraphNode in the Graph.

Parameters:

nodeName - the name of a GraphNode object.

Returns:

the GraphNode object with the specified name or null if not on the Graph.

removeNode

public void removeNode(Graph.GraphNode graphNode)

If graphNode != null and graphNode is in the Graph, it and all its edges are removed from the Graph. If graphNode == null or not in the Graph nothing happens.

Parameters:

graphNode - the graphNode object to remove from the Graph.

addEdge

public void addEdge(Graph.GraphNode graphNode1,
                    Graph.GraphNode graphNode2,
                    double weight)

Adds an edge from graphNode1 to graphNode2 with the specified weight. If an edge from graphNode1 to graphNode2 already exists only its weight is set to the new weight. If any specified GraphNode object is null or not in the Graph, nothing changes.

Parameters:

graphNode1 - the GraphNode object to create an edge to graphNode2 from.

graphNode2 - the GraphNode object to create an edge from graphNode 1 to.

weight - the weight of the new edge.

addBidirectionalEdge

public void addBidirectionalEdge(Graph.GraphNode graphNode1,
                                 Graph.GraphNode graphNode2,
                                 double weight)

Adds an edge from graphNode1 to graphNode2 and from graphNode1 to graphNode2, both with the specified weight. If edges between graphNode1 and graphNode2 already exist only their weight is set to the new weight. If any specified GraphNode object is null or not in the Graph, nothing changes.

Parameters:

graphNode1 - the GraphNode object to create an edge to and from graphNode2.

graphNode2 - the GraphNode object to create an edge to and from graphNode1.

weight - the weight of the new edges.

hasEdge

public boolean hasEdge(Graph.GraphNode graphNode1,
                       Graph.GraphNode graphNode2)

Returns whether there is an edge between the specified GraphNode objects in the Graph. If any GraphNode object is null or not in the Graph the result is always false.

Parameters:

graphNode1 - a GraphNode object.

graphNode2 - another GraphNode object.

Returns:

true if edge exists, else false.

removeEdge

public void removeEdge(Graph.GraphNode graphNode1,
                       Graph.GraphNode graphNode2)

Removes the edge from graphNode1 to graphNode2 if there was any.

Parameters:

graphNode1 - a GraphNode object in the Graph.

graphNode2 - another GraphNode object in the Graph.

removeEdges

public void removeEdges(Graph.GraphNode graphNode1,
                        Graph.GraphNode graphNode2)

Removes both edges between graphNode1 and graphNode2 if there were any.

Parameters:

graphNode1 - a GraphNode object in the Graph.

graphNode2 - another GraphNode object in the Graph.

getEdgeWeight

public double getEdgeWeight(Graph.GraphNode graphNode1,
                            Graph.GraphNode graphNode2)

Returns the weight of the edge from graphNode1 to graphNode2.

Parameters:

graphNode1 - a GraphNode object.

graphNode2 - another GraphNode object.

Returns:

the weight of the edge or Double.NaN if there is no such edge.

removeMarks

public void removeMarks()

Sets the 'marked' boolean to false for all GraphNode objects in the Graph.

allNodesMarked

public boolean allNodesMarked()

Returns whether all GraphNode objects in the Graph are marked.

Returns:

true if all GraphNode objects in the Graph are marked, else false. Also true if Graph is empty.

getNodes

public List getNodes()

Returns a new List object containing all GraphNode objects in the Graph.

Returns:

a new List object containing all GraphNode objects in the Graph.

getNeighbors

public List getNeighbors(Graph.GraphNode graphNode)

Returns a new List object containing all GraphNode objects that are neighbors of the specified GraphNode object.

Parameters:

graphNode - a GraphNode object which the Graph contains.

Returns:

a new List object containing all GraphNode objects that are neighbors of the specified GraphNode object.

edgeWeightSum

public double edgeWeightSum()

Returns the sum of all edgeWeights in the Graph.

Returns:

all edgeWeights in the Graph summed up.

cumulativeEdgeWeight

public double cumulativeEdgeWeight(Graph.GraphNode graphNode)

Returns the summed up edgeWeights of all edges of the specified GraphNode object.

Parameters:

graphNode - a GraphNode object.

Returns:

the sum of all edgeWeights of the GraphNode (and his neighbors).

highestWeight

public Graph.GraphNode highestWeight()

Returns the GraphNode object with the highest summed up edgeWeights in the Graph.

Returns:

the GraphNode with the highest summed up edgeWeights.