Package edu.claflin.finder.logic

# Class Graph

java.lang.Object
edu.claflin.finder.logic.Graph

Direct Known Subclasses:
  `ConditionedGraph`

public class Graph extends Object
Used to represent a graph in memory. Migrated from matrix form, the graph is now kept track of via a list of edges and nodes. All the previous methods remain in existence but the underlying implementation has changed.

Version:
  3.4 February 2, 2016
Author:
  Charles Allen Schultz II

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `private final ArrayList<Edge>`
  `edgeList`
  The list of edges added to the graph.
  `private final String`
  `graphName`
  The name of the Graph provided by the user.
  `private final ArrayList<Node>`
  `nodeList`
  The list of the nodes added to the graph.
  `protected boolean`
  `suppressLog`
  Used to suppress logging.
  `private double`
  `weight`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `Graph(String graphName)`
  Initializes the graph.
  `Graph(String graphName, List<Node> nodeList, List<Edge> edgeList)`
  Private constructor used by subGraph method.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `boolean`
  `addEdge(int node1Index, int node2Index, Double edgeData)`
  Deprecated.
  Outdated since v3.
  `boolean`
  `addEdge(Edge edge)`
  Adds an edge to the Graph.
  `boolean`
  `addEdge(String node1, String node2, Double edgeData)`
  Deprecated.
  Outdated since v3.
  `boolean`
  `addEdges(List<Edge> edges)`
  Adds a list of Edges to the graph.
  `boolean`
  `addNewNode(String node)`
  Deprecated.
  Outdated since v3.
  `boolean`
  `addNode(Node node)`
  Adds a node to the graph.
  `boolean`
  `addNodes(List<Node> nodes)`
  Adds a list of nodes to the graph.
  `boolean`
  `addPartialGraph(List<Node> nodes, List<Edge> edges)`
  Adds a partial graph to this graph.
  `private void`
  `checkNode(Node node)`
  Verifies that the node is NOT in the graph.
  `private void`
  `checkNodeIndex(int nodeIndex)`
  Deprecated.
  No replacement.
  `boolean`
  `containsNode(Node node)`
  Checks if the graph contains the given node.
  `Graph`
  `copy()`
  Copies this Graph object using the getSubGraph() method.
  `Graph`
  `crosstalk(Graph subgraph1, Graph subgraph2)`
  Crosstalk of 2 subgraphs of this Graph.
  `Graph`
  `difference(Graph that)`
  Difference of this Graph with a provided Graph.
  `List<Node>`
  `getAdjacencyList(Node node)`
  Obtains an adjacency list for the supplied node based on the Graph.
  `Object`
  `getEdge(int node1Index, int node2Index)`
  Deprecated.
  Outdated since v3.
  `Edge`
  `getEdge(Node source, Node destination)`
  Locates an Edge object in the edgeList and returns it.
  `Object`
  `getEdge(String node1, String node2)`
  Deprecated.
  Outdated since v3.
  `int`
  `getEdgeCount()`
  Get the number of Edges in the Graph
  `List<Edge>`
  `getEdgeList()`
  Returns the list of edges in the graph.
  `List<Edge>`
  `getEdgesBack(List<Node> nodes)`
  Gets the list edges of this Graph that involve the nodes in the given list
  `double`
  `getGraphWeight()`
  Get the Graph's total weight (sum of all edge weights)
  `String`
  `getName()`
  Gets the name of the graph.
  `Node`
  `getNode(String NodeName)`
  Gets a node based on its name.
  `int`
  `getNodeCount()`
  Gets the number of nodes in the graph.
  `List<Edge>`
  `getNodeEdges(Node n)`
  Get the list of Edges in which the given Node participates.
  `int`
  `getNodeIndex(Node node)`
  Gets the index of a Node object in memory.
  `int`
  `getNodeIndex(String node)`
  Deprecated.
  Outdated since v3.
  `List<Node>`
  `getNodeList()`
  Returns the list of nodes in the graph.
  `String`
  `getNodeName(int nodeIndex)`
  Deprecated.
  Outdated since v3.
  `ArrayList<ArrayList<Node>>`
  `getPartiteSets()`
  Divides the given graph into two bipartite sets.
  `Graph`
  `getSubGraph(int startNode, int stopNode, String nameQualifier)`
  Deprecated.
  Outdated since v3.
  `Graph`
  `getSubGraph(ArrayList<String> subStringSet, String nameQualifier)`
  Deprecated.
  Outdated since v3.
  `Graph`
  `getSubGraph(List<Node> nodes, String nameQualifier)`
  Returns a subGraph of this graph.
  `Graph`
  `intersect(Graph that)`
  Intersects this Graph with a provided Graph.
  `boolean`
  `isBipartite()`
  Determines whether the Graph is Bipartite.
  `private boolean`
  `isBipartite(Node current, Set<Node> addSet, Set<Node> compareSet)`
  Private method for stepping through the adjacency lists and determining if the graph is bipartite.
  `boolean`
  `isClique()`
  Determines whether the Graph is a Clique.
  `void`
  `removeEdge(Edge e)`
  `private void`
  `removeEdgesInvolving(Node n)`
  Remove all the edges in which the given Node participates.
  `void`
  `removeNode(Node node)`
  Removes a node from the set.
  `String`
  `toString()`
  Returns a String representation of the Graph.
  `String`
  `toStringNameless()`
  `void`
  `transpose(int node1Index, int node2Index)`
  Transposes the specified nodes.
  `void`
  `transpose(Node node1, Node node2)`
  Transposes the specified nodes.
  `void`
  `transpose(String node1, String node2)`
  Deprecated.
  Outdated since v3.
  `Graph`
  `union(Graph that)`
  Union this Graph with a provided Graph.
  `Graph`
  `uniqueCopy()`
  Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects.
  `Graph`
  `uniqueCopy(String gName)`

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### graphName

    private final String graphName
    The name of the Graph provided by the user. This value is used by the program to name output files unless specified otherwise.

  - ### nodeList

    private final ArrayList<Node> nodeList
    The list of the nodes added to the graph. Used by the program to keep track of the associations within the matrix. It may be re-ordered dynamically at runtime.

  - ### edgeList

    private final ArrayList<Edge> edgeList
    The list of edges added to the graph. The graph is, by default, a directed graph. As such, two edges must be added to force the graph to be bidirectional.

  - ### weight

    private double weight

  - ### suppressLog

    protected boolean suppressLog
    Used to suppress logging.

- ## Constructor Details

  - ### Graph

    public Graph(String graphName)
    Initializes the graph. Merely initializes fields. It does not set any data. Also sets the Logging Utility object. If null, the class will not log data.
    Parameters:
      `graphName` - the String which represents the name of the Graph.

  - ### Graph

    public Graph(String graphName, List<Node> nodeList, List<Edge> edgeList)
    Private constructor used by subGraph method.
    Parameters:
      `graphName` - the String which represents the name of the Graph.
      `nodeList` - the ArrayList of Node objects.
      `edgeList` - the ArrayList of Edge objects.

- ## Method Details

  - ### getName

    public String getName()
    Gets the name of the graph.
    Returns:
      The graph name.

  - ### addPartialGraph

    public boolean addPartialGraph(List<Node> nodes, List<Edge> edges)
    Adds a partial graph to this graph. Specifically adds a set of nodes and a set of edges to the graph. It should be noted that nodes or edges in the graph already that attempt to be added again may cause exceptions to occur. Additionally, Nodes are added before Edges so any Edges that depend on Nodes in the add list may be safely added simultaneously. This method is the backbone structure for adding any component to the graph as all other addition methods filter through here.
    Parameters:
      `nodes` - the List<Node> containing the nodes to add.
      `edges` - the List<Edge> containing the edges to add.
    Returns:
      true, always. Allows overriding in subclasses which wish to change base implementation.

  - ### getSubGraph

    @Deprecated public Graph getSubGraph(int startNode, int stopNode, String nameQualifier)
    Deprecated.
    Outdated since v3. Replaced by `getSubGraph(java.util.List, java.lang.String)`
    Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.
    Parameters:
      `startNode` - the integer pointing to the start node.
      `stopNode` - the integer pointing to the stop node.
      `nameQualifier` - the String representing an additional qualifier to prepend the name of the new Graph object with.
    Returns:
      the Graph object representing a subgraph of the original.

  - ### getSubGraph

    @Deprecated public Graph getSubGraph(ArrayList<String> subStringSet, String nameQualifier)
    Deprecated.
    Outdated since v3. Replaced by `getSubGraph(java.util.List, java.lang.String)`
    Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.
    Parameters:
      `subStringSet` - an ArrayList containing the String names of the desired nodes.
      `nameQualifier` - the String representing an additional qualifier to prepend the name of the new Graph object with.
    Returns:
      the Graph object representing a subgraph of the original.

  - ### getSubGraph

    public Graph getSubGraph(List<Node> nodes, String nameQualifier)
    Returns a subGraph of this graph. Isolates and extracts a subgraph based on a user supplied node list. The new Graph is a quasi-separate Graph. Each node utilized is directly related between the two graphs and, as such, changes to the properties of one node in the subgraph will be reflected in the super graph. To obtain an independent graph
    Parameters:
      `nodes` - the List<Node> containing the Node references.
      `nameQualifier` - the String to differentiate the Graph names.
    Returns:
      the Graph representing the subgraph.

  - ### transpose

    public void transpose(int node1Index, int node2Index)
    Transposes the specified nodes. Swaps the location of the nodes in memory. Specifically swaps the nodes in the nodeList as the Edge data has been uncoupled from the Node data. Newer implementation is dependent upon the int based method for performance.
    Parameters:
      `node1Index` - the integer index of the first node.
      `node2Index` - the integer index of the second node.

  - ### transpose

    @Deprecated public void transpose(String node1, String node2)
    Deprecated.
    Outdated since v3. Replaced by {}
    Transposes the specified nodes. Swaps the location of the nodes in memory. This is a convenience method for transposing the nodes based on the Sting representation of the nodes.
    Parameters:
      `node1` - the String name of the first node.
      `node2` - the String name of the second node.

  - ### transpose

    public void transpose(Node node1, Node node2)
    Transposes the specified nodes. Relies on the integer based method for carrying out the operation.
    Parameters:
      `node1` - the Node object in the first position.
      `node2` - the Node object in the second position.

  - ### getGraphWeight

    public double getGraphWeight()
    Get the Graph's total weight (sum of all edge weights)
    Returns:
      the Graph's total weight

  - ### copy

    public Graph copy()
    Copies this Graph object using the getSubGraph() method.
    Returns:
      a Graph object identical to the original.

  - ### uniqueCopy

    public Graph uniqueCopy()
    Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects. I.e. there are no shared nodes or edges between the two graphs. Mathematically speaking: `x.getNodeList().get(0) != y.getNodeList().get(0)` under any circumstances. The Nodes and Edges may remain equivalent via the equals() implementation. Further, Edge data shall remain entangled due to implementation details.
    Returns:
      a unique copy of the graph object.

  - ### uniqueCopy

    public Graph uniqueCopy(String gName)

  - ### union

    public Graph union(Graph that)
    Union this Graph with a provided Graph.
    Parameters:
      `that` - the Graph to union with
    Returns:
      the Graph that is the union of the two Graphs

  - ### intersect

    public Graph intersect(Graph that)
    Intersects this Graph with a provided Graph.
    Parameters:
      `that` - the Graph to intersect with
    Returns:
      the Graph that is the intersection of the two Graphs

  - ### difference

    public Graph difference(Graph that)
    Difference of this Graph with a provided Graph.
    Parameters:
      `that` - the Graph to difference with
    Returns:
      the Graph that is the difference of the two Graphs

  - ### crosstalk

    public Graph crosstalk(Graph subgraph1, Graph subgraph2)
    Crosstalk of 2 subgraphs of this Graph. It is the edges of the 2 subgraphs and the edges that connect the subgraphs. The subgraphs must be disjoint.
    Parameters:
      `subgraph1` - subgraph 1
      `subgraph2` - subgraph 2
    Returns:
      the crosstalk or empty graph if the subgraphs are not disjoint

  - ### toString

    public String toString()
    Returns a String representation of the Graph.
    Overrides:
      `toString` in class `Object`
    Returns:
      the String representation of the Graph.

  - ### toStringNameless

    public String toStringNameless()

  - ### getNodeCount

    public int getNodeCount()
    Gets the number of nodes in the graph.
    Returns:
      the integer representing the total number of nodes in the graph.

  - ### getNodeList

    public List<Node> getNodeList()
    Returns the list of nodes in the graph.
    Returns:
      the List<Node> containing the list of nodes in the graph.

  - ### containsNode

    public boolean containsNode(Node node)
    Checks if the graph contains the given node.
    Parameters:
      `node` - the node to check for
    Returns:
      whether or not node is in this graph

  - ### addNewNode

    @Deprecated public boolean addNewNode(String node)
    Deprecated.
    Outdated since v3. Replaced by {}
    Adds a node to the graph. Adds the specified node name to the nodeList by creating and adding a new node and then calling the addNode(Node) method.
    Parameters:
      `node` - the String which denotes the name of the node to add.
    Returns:
      true if the addition was successful.

  - ### addNode

    public boolean addNode(Node node)
    Adds a node to the graph. Adds a Node object to the graph.
    Parameters:
      `node` - the Node object to add.
    Returns:
      true if the addition was successful.

  - ### removeNode

    public void removeNode(Node node)
    Removes a node from the set. Only used with the Bron-Kerbosch algorithm right now, hopefully doesn't break anything Does NOT affect edges!!!!!!! At time of writing may cause issues if you rely on it to do so
    Parameters:
      `node` - the node to remove

  - ### addNodes

    public boolean addNodes(List<Node> nodes)
    Adds a list of nodes to the graph.
    Parameters:
      `nodes` - the List<Node> containing the nodes to add.
    Returns:
      true if the addition was successful.

  - ### getNodeIndex

    @Deprecated public int getNodeIndex(String node)
    Deprecated.
    Outdated since v3. Replaced by {}
    Gets the index of a node based on its name. Maintained with the new implementation to preserve existing uses. Will not match nodes which may have additional properties attached in future implementations.
    Parameters:
      `node` - the String representing the node to search for.
    Returns:
      the index of the node or -1 if the node was not found.

  - ### getNodeIndex

    public int getNodeIndex(Node node)
    Gets the index of a Node object in memory. Retained for older API compatibility. The ordering of the nodes is not guaranteed and may change during the program's runtime.
    Parameters:
      `node` - the Node object to search for.
    Returns:
      the index of the node or -1 if the node was not found.

  - ### getNodeName

    @Deprecated public String getNodeName(int nodeIndex)
    Deprecated.
    Outdated since v3. No replacement. Obtain the Node data via the `Node` object.
    Gets the name of the node at the specified nodeIndex. Ensures that the provided integer is within the range of available indices.
    Parameters:
      `nodeIndex` - the integer representing the index to get from the headerList.
    Returns:
      the String representing the name of the node.

  - ### getNode

    public Node getNode(String NodeName)
    Gets a node based on its name.
    Parameters:
      `NodeName` - the String representing the node to search for.
    Returns:
      the node or null if the node was not found.

  - ### getAdjacencyList

    public List<Node> getAdjacencyList(Node node)
    Obtains an adjacency list for the supplied node based on the Graph. Very inefficient, try to use the neighbors variable in the Node class instead.
    Parameters:
      `node` - the Node to obtain the adjacency list for.
    Returns:
      the List of Nodes containing the adjacent Nodes.

  - ### checkNode

    private void checkNode(Node node)
    Verifies that the node is NOT in the graph. Checks to see if the provided node name is in the headerList and, hence, the dataMatrix. This is an internal method used to ensure that the algorithm is operating correctly.
    Parameters:
      `node` - the Node to check for.

  - ### checkNodeIndex

    @Deprecated private void checkNodeIndex(int nodeIndex)
    Deprecated.
    No replacement. Further operations shall utilize {)}
    Verifies that the nodeIndex is valid. Ensures that the node does not fall out of bounds. This is an internal method used to ensure that the algorithm is operating correctly.
    Parameters:
      `nodeIndex` - the integer of the node to check for.

  - ### getEdgeCount

    public int getEdgeCount()
    Get the number of Edges in the Graph
    Returns:
      the number of Edges in the Graph

  - ### getEdgeList

    public List<Edge> getEdgeList()
    Returns the list of edges in the graph.
    Returns:
      the List<Edge> containing the list of edges in the graph.

  - ### addEdge

    @Deprecated public boolean addEdge(int node1Index, int node2Index, Double edgeData)
    Deprecated.
    Outdated since v3. Replaced by {}
    Adds an edge connecting the specified nodes in the Graph. Sets the object data for the edge dependent upon the supplied parameter.
    Parameters:
      `node1Index` - the integer value indicating the first node.
      `node2Index` - the integer value indicating the second node.
      `edgeData` - the Object that represents unique edge data (i.e. weight or edge relationship).
    Returns:
      true if the addition was successful.

  - ### addEdge

    @Deprecated public boolean addEdge(String node1, String node2, Double edgeData)
    Deprecated.
    Outdated since v3. Replaced by {
    Adds an edge connecting the specified nodes to the Graph. This is a convenience method for adding an edge using node names. Graphs are undirected so the order of the parameters does not matter.
    Parameters:
      `node1` - the String indicating the first node.
      `node2` - the String indicating the second node.
      `edgeData` - the Object that represents unique edge data (i.e. weight or edge relationship).
    Returns:
      true if the addition was successful.

  - ### addEdge

    public boolean addEdge(Edge edge)
    Adds an edge to the Graph. If any edge already exists within the Graph connecting the two supplied nodes or either of the two nodes is not in the nodeList, then the edge is not added.
    Parameters:
      `edge` - the Edge object to add to the graph.
    Returns:
      true if the addition was successful.

  - ### addEdges

    public boolean addEdges(List<Edge> edges)
    Adds a list of Edges to the graph.
    Parameters:
      `edges` - the List<Edge> containing the edges to add.
    Returns:
      true if the addition was successful.

  - ### getEdge

    @Deprecated public Object getEdge(int node1Index, int node2Index)
    Deprecated.
    Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
    Gets the value of the edge between the specified nodes.
    Parameters:
      `node1Index` - the integer value of the first node.
      `node2Index` - the integer value of the second node.
    Returns:
      the Object representing the edge relationship.

  - ### getEdge

    @Deprecated public Object getEdge(String node1, String node2)
    Deprecated.
    Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
    Gets the value of the edge between the specified nodes. This is a convenience method for getting the edge using the node's String name.
    Parameters:
      `node1` - the String of the first node.
      `node2` - the String of the second node.
    Returns:
      the Object representing the edge relationship.

  - ### getEdge

    public Edge getEdge(Node source, Node destination)
    Locates an Edge object in the edgeList and returns it. Note that it will also return an edge with the provided source and destination parameters swapped IF AN ONLY IF said edge is undirected.
    Parameters:
      `source` - the source Node of the edge.
      `destination` - the destination Node of the edge.
    Returns:
      the Edge object or null if not found.

  - ### getNodeEdges

    public List<Edge> getNodeEdges(Node n)
    Get the list of Edges in which the given Node participates.
    Parameters:
      `n` - the Node to find edges
    Returns:
      the edges the node participates in

  - ### removeEdge

    public void removeEdge(Edge e)

  - ### removeEdgesInvolving

    private void removeEdgesInvolving(Node n)
    Remove all the edges in which the given Node participates.
    Parameters:
      `n` - the participating Node

  - ### getEdgesBack

    public List<Edge> getEdgesBack(List<Node> nodes)
    Gets the list edges of this Graph that involve the nodes in the given list
    Parameters:
      `nodes` - the list of nodes to found the edges from
    Returns:
      the list edges of this Graph that involve the nodes in the given list

  - ### isClique

    public boolean isClique()
    Determines whether the Graph is a Clique.
    Returns:
      true if the Graph is a Clique

  - ### isBipartite

    public boolean isBipartite()
    Determines whether the Graph is Bipartite.
    Returns:
      true if the Graph is Bipartite

  - ### getPartiteSets

    public ArrayList<ArrayList<Node>> getPartiteSets()
    Divides the given graph into two bipartite sets.
    Returns:
      two lists of nodes, each representing a bipartite set. Both lists are empty if the graph is not a valid bipartite graph.

  - ### isBipartite

    private boolean isBipartite(Node current, Set<Node> addSet, Set<Node> compareSet)
    Private method for stepping through the adjacency lists and determining if the graph is bipartite. Specifically, it uses a Depth-First model for exploring the node tree and sorting the nodes into two groups. If it successfully sorts the nodes into two groups with no invalidating edges, it returns true.
    Parameters:
      `addSet` - the current set to add a node to based on the previous.
      `compareSet` - the current set to add adjacent nodes to.
      `current` - the current Node being compared.
    Returns:
      true if the structure could be bipartite.