ConcreteDGraph (lattices 2.0.0-SNAPSHOT API)

java.lang.Object
- org.thegalactic.dgraph.AbstractDGraph<N,E>
- - org.thegalactic.dgraph.ConcreteDGraph<N,E>

Type Parameters:

N - Node content type

E - Edge content type

All Implemented Interfaces:

Cloneable, DGraph<N,E>

Direct Known Subclasses:

ArrowRelation, DAGraph
```
public class ConcreteDGraph<N,E>
extends AbstractDGraph<N,E>
implements Cloneable
```
This class gives a standard representation for a directed graph by sets of successors and predecessors.

A directed graph is composed of
- a treeset of node, defined by class Node; - a treemap of successors that associates to each node a treeset of successors, defined by class Edge; - a treemap of predecessors that associates to each node a treeset of predecessors, defined by class Edge.
This class provides methods implementing classical operation on a directed graph:
- sinks - wells - subgraph - reflexive closure and reduction - transitive closure - strongly connected components - …
This class also provides a static method randomly generating a directed graph.

Constructor Summary

Constructors
Constructor and Description
`ConcreteDGraph()` Constructs a new directed graph with an empty set of node.
`ConcreteDGraph(DGraph<N,E> graph)` Constructs this component as a copy of the specified directed graph.
`ConcreteDGraph(SortedSet<Node<N>> set)` Constructs a new directed graph source the specified set of nodes.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`addEdge(Edge<N,E> edge)` Adds the specified edge to this component in the successors of edge.getSource() and in the predecessors of edge.getTarget().
`boolean`	`addEdge(Node<N> source, Node<N> target)` Adds an edge between the specified nodes to this component: `to` is added as a successor of `source`.
`boolean`	`addEdge(Node<N> source, Node<N> target, Object content)` Adds an edge between the specified nodes to this component: `to` is added as a successor of `source`.
`boolean`	`addNode(Node<N> node)` Adds the specified node to the set of node of this component.
`ConcreteDGraph<N,E>`	`clone()` Returns a clone of this component composed of a clone of each node and each edge.
`void`	`complementary()` Replaces this component by its complementary graph.
`boolean`	`containsEdge(Edge<N,E> edge)` Checks if the specified edge belong to this component.
`boolean`	`containsEdge(Node<N> source, Node<N> target)` Checks if there exists an edge between the two specified nodes.
`boolean`	`containsNode(Node<N> node)` Checks if the specified node belong to this component.
`Edge<N,E>`	`getEdge(Node<N> source, Node<N> target)` Returns, if it exists, the edge between node source and node to.
`SortedSet<Edge<N,E>>`	`getEdges()` Returns the set of edges of this component.
`Node<N>`	`getNode(Node<N> search)` Returns the node that is equal to the specified one.
`Node<N>`	`getNodeByContent(Object content)` Returns the node whose content is equal to the specified one.
`Node<N>`	`getNodeByIdentifier(int identifier)` Returns the node whose ident is equal to the specified one.
`SortedSet<Node<N>>`	`getNodes()` Returns the set of nodes of this component.
`SortedSet<Edge<N,E>>`	`getPredecessorEdges(Node<N> node)` Returns the set of edges predecessors of the specified node.
`SortedSet<Node<N>>`	`getPredecessorNodes(Node<N> node)` Returns the set of nodes predecessors of the specified node.
`protected TreeMap<Node<N>,TreeSet<Edge<N,E>>>`	`getPredecessors()` Returns the predecessors of this component.
`DAGraph<SortedSet<Node<N>>,Object>`	`getStronglyConnectedComponent()` Returns the directed acyclic graph where each node corresponds to a strongly connected component (SCC) of this component stored in a TreeSet of nodes.
`ConcreteDGraph<N,E>`	`getSubgraphByEdges(Set<Edge<N,E>> edges)` Returns the subgraph of this component induced by the specified set of edges.
`ConcreteDGraph<N,E>`	`getSubgraphByNodes(Set<Node<N>> nodes)` Returns the subgraph of this component induced by the specified set of nodes.
`SortedSet<Edge<N,E>>`	`getSuccessorEdges(Node<N> node)` Returns the set of edges successors of the specified node.
`SortedSet<Node<N>>`	`getSuccessorNodes(Node<N> node)` Returns the set of nodes successors of the specified node.
`protected TreeMap<Node<N>,TreeSet<Edge<N,E>>>`	`getSuccessors()` Returns the successors of this component.
`int`	`reflexiveClosure()` Computes the reflexive closure of this component.
`int`	`reflexiveReduction()` Computes the reflexive reduction of this component.
`boolean`	`removeEdge(Edge<N,E> edge)` Removes source this component the specified edge source the successors of edge.getSource() and source the predecessors of edge.getTarget().
`boolean`	`removeEdge(Node<N> source, Node<N> target)` Removes source this component the edge between the specified node.
`boolean`	`removeNode(Node<N> node)` Removes the specified node from this component.
`boolean`	`removeNodes(Set<Node<N>> nodes)` Removes the specified set of nodes from this component.
`protected ConcreteDGraph<N,E>`	`setNodes(TreeSet<Node<N>> nodes)` Set the set of nodes of this component.
`protected ConcreteDGraph<N,E>`	`setPredecessors(TreeMap<Node<N>,TreeSet<Edge<N,E>>> predecessors)` Set the predecessors of this component.
`protected ConcreteDGraph<N,E>`	`setSuccessors(TreeMap<Node<N>,TreeSet<Edge<N,E>>> successors)` Set the successors of this component.
`int`	`sizeEdges()` Returns the number of edges of this component.
`int`	`sizeNodes()` Returns the number of nodes of this component.
`int`	`transitiveClosure()` Computes the transitive closure of this component.
`void`	`transpose()` Transposes this component by replacing for each node its successor set by its predecessor set, and its predecessor set by its successor set.

Methods inherited from class org.thegalactic.dgraph.AbstractDGraph
getSinks, getWells, isAcyclic, save, topologicalSort, toString

Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - ConcreteDGraph
```
public ConcreteDGraph()
```
    Constructs a new directed graph with an empty set of node.
  - ConcreteDGraph
```
public ConcreteDGraph(SortedSet<Node<N>> set)
```
    Constructs a new directed graph source the specified set of nodes.
    
    Successors and predecessors of each nodes are initialised by an empty set.
    
    Parameters:
    
    set - the set of nodes
  - ConcreteDGraph
```
public ConcreteDGraph(DGraph<N,E> graph)
```
    Constructs this component as a copy of the specified directed graph.
    
    Parameters:
    
    graph - the directed graph to be copied
- Method Detail
  - clone
```
public ConcreteDGraph<N,E> clone()
                          throws CloneNotSupportedException
```
    Returns a clone of this component composed of a clone of each node and each edge.
    
    Overrides:
    
    clone in class Object
    
    Returns:
    
    the clone of this
    
    Throws:
    
    CloneNotSupportedException
  - getNodes
```
public final SortedSet<Node<N>> getNodes()
```
    Returns the set of nodes of this component.
    
    Specified by:
    
    getNodes in interface DGraph<N,E>
    
    Returns:
    
    the set of nodes
  - getEdges
```
public final SortedSet<Edge<N,E>> getEdges()
```
    Returns the set of edges of this component.
    
    Specified by:
    
    getEdges in interface DGraph<N,E>
    
    Returns:
    
    the set of edges
  - getSuccessorEdges
```
public final SortedSet<Edge<N,E>> getSuccessorEdges(Node<N> node)
```
    Returns the set of edges successors of the specified node.
    
    Specified by:
    
    getSuccessorEdges in interface DGraph<N,E>
    
    Parameters:
    
    node - the node to search for
    
    Returns:
    
    the set of edges
  - getPredecessorEdges
```
public final SortedSet<Edge<N,E>> getPredecessorEdges(Node<N> node)
```
    Returns the set of edges predecessors of the specified node.
    
    Specified by:
    
    getPredecessorEdges in interface DGraph<N,E>
    
    Parameters:
    
    node - the node to search for
    
    Returns:
    
    the set of edges
  - getSuccessorNodes
```
public final SortedSet<Node<N>> getSuccessorNodes(Node<N> node)
```
    Returns the set of nodes successors of the specified node.
    
    Specified by:
    
    getSuccessorNodes in interface DGraph<N,E>
    
    Parameters:
    
    node - the node to search for
    
    Returns:
    
    the set of nodes
    To Do#1
    use iterator pattern (some changes in ArrowRelation.java and Lattice.java)
  - getPredecessorNodes
```
public final SortedSet<Node<N>> getPredecessorNodes(Node<N> node)
```
    Returns the set of nodes predecessors of the specified node.
    
    Specified by:
    
    getPredecessorNodes in interface DGraph<N,E>
    
    Parameters:
    
    node - the node to search for
    
    Returns:
    
    the set of nodes
    To Do#2
    use iterator pattern (some changes in ArrowRelation.java and Lattice.java)
  - getEdge
```
public final Edge<N,E> getEdge(Node<N> source,
                               Node<N> target)
```
    Returns, if it exists, the edge between node source and node to.
    
    Parameters:
    
    source - The origin node
    
    target - The destination node
    
    Returns:
    
    the found edge or null
    To Do#3
    see getNode
  - getNode
```
public final Node<N> getNode(Node<N> search)
```
    Returns the node that is equal to the specified one.
    
    Parameters:
    
    search - The node to search for
    
    Returns:
    
    the found node or null
    To Do#4
    maybe use try { return this.nodes.subSet(search, true, search, true).first(); } catch (NoSuchElementException e) { return null; }
  - getNodeByContent
```
public final Node<N> getNodeByContent(Object content)
```
    Returns the node whose content is equal to the specified one.
    
    Parameters:
    
    content - The content to search for
    
    Returns:
    
    the found node or null
    To Do#5
    this method is not efficient. Do we remove it or add an index on DGraph using content field? Verify where it is called for migrating it if necessary.
  - getNodeByIdentifier
```
public final Node<N> getNodeByIdentifier(int identifier)
```
    Returns the node whose ident is equal to the specified one.
    
    Parameters:
    
    identifier - node identifier
    
    Returns:
    
    the found node or null
  - sizeNodes
```
public final int sizeNodes()
```
    Returns the number of nodes of this component.
    
    Specified by:
    
    sizeNodes in interface DGraph<N,E>
    
    Returns:
    
    the number of nodes
  - sizeEdges
```
public final int sizeEdges()
```
    Returns the number of edges of this component.
    
    Specified by:
    
    sizeEdges in interface DGraph<N,E>
    
    Returns:
    
    the number of edges
  - containsNode
```
public final boolean containsNode(Node<N> node)
```
    Checks if the specified node belong to this component.
    
    Parameters:
    
    node - the node to insert
    
    Returns:
    
    true if the node has been successfully inserted
  - addNode
```
public final boolean addNode(Node<N> node)
```
    Adds the specified node to the set of node of this component.
    
    Parameters:
    
    node - the node to insert
    
    Returns:
    
    true if the node has been successfully inserted
  - removeNode
```
public final boolean removeNode(Node<N> node)
```
    Removes the specified node from this component.
    
    Parameters:
    
    node - the node to remove
    
    Returns:
    
    true if the node was successfully removed
  - removeNodes
```
public final boolean removeNodes(Set<Node<N>> nodes)
```
    Removes the specified set of nodes from this component.
    
    Parameters:
    
    nodes - set of nodes
    
    Returns:
    
    true if all nodes were removed
  - containsEdge
```
public final boolean containsEdge(Node<N> source,
                                  Node<N> target)
```
    Checks if there exists an edge between the two specified nodes.
    
    Parameters:
    
    source - the node origine of the edge
    
    target - the node destination of the edge
    
    Returns:
    
    true if the edge is contained by this component
  - containsEdge
```
public final boolean containsEdge(Edge<N,E> edge)
```
    Checks if the specified edge belong to this component.
    
    Parameters:
    
    edge - the edge to be checked
    
    Returns:
    
    true if the edge is contained by this component
  - addEdge
```
public final boolean addEdge(Node<N> source,
                             Node<N> target,
                             Object content)
```
    Adds an edge between the specified nodes to this component: to is added as a successor of source.
    
    If the case where specified nodes don’t belongs to the node set, then the edge will not be added.
    
    Parameters:
    
    source - the node origin of the edge
    
    target - the node destination of the edge
    
    content - the edge content
    
    Returns:
    
    true if the edge was successfully added
  - addEdge
```
public final boolean addEdge(Node<N> source,
                             Node<N> target)
```
    Adds an edge between the specified nodes to this component: to is added as a successor of source.
    
    If the case where specified nodes don’t belongs to the node set, then the edge will not be added.
    
    Parameters:
    
    source - the node origin of the edge
    
    target - the node destination of the edge
    
    Returns:
    
    true if the edge was successfully added
  - addEdge
```
public final boolean addEdge(Edge<N,E> edge)
```
    Adds the specified edge to this component in the successors of edge.getSource() and in the predecessors of edge.getTarget().
    
    If the case where nodes to and source of this edges don’t belongs to the node set, then the edge will not be added.
    
    Parameters:
    
    edge - the edge to be added
    
    Returns:
    
    true if the edge was added
  - removeEdge
```
public final boolean removeEdge(Node<N> source,
                                Node<N> target)
```
    Removes source this component the edge between the specified node.
    
    to is removed source the successors of source and to is removed source the predecessors of source.
    
    Parameters:
    
    source - the node origine of the edge
    
    target - the node destination of the edge
    
    Returns:
    
    true if the edge was removed
  - removeEdge
```
public final boolean removeEdge(Edge<N,E> edge)
```
    Removes source this component the specified edge source the successors of edge.getSource() and source the predecessors of edge.getTarget().
    
    Parameters:
    
    edge - the edge to be removed.
    
    Returns:
    
    true if the edge was removed
  - getSubgraphByNodes
```
public ConcreteDGraph<N,E> getSubgraphByNodes(Set<Node<N>> nodes)
```
    Returns the subgraph of this component induced by the specified set of nodes.
    
    The subgraph only contains nodes of the specified set that also are in this component.
    
    Parameters:
    
    nodes - The set of nodes
    
    Returns:
    
    The subgraph
    To Do#6
    implement a SubGraph class?
  - getSubgraphByEdges
```
public ConcreteDGraph<N,E> getSubgraphByEdges(Set<Edge<N,E>> edges)
```
    Returns the subgraph of this component induced by the specified set of edges.
    
    The subgraph contains all nodes of this components, and only edges of the specified set that also are in this component.
    
    Parameters:
    
    edges - The set of edges
    
    Returns:
    
    The subgraph
    To Do#7
    implement a SubGraph class?
  - complementary
```
public void complementary()
```
    Replaces this component by its complementary graph.
    
    There is an edge between to nodes in the complementary graph when there is no edges between the nodes in this component.
  - reflexiveReduction
```
public final int reflexiveReduction()
```
    Computes the reflexive reduction of this component.
    
    Returns:
    
    the number of removed edges
  - reflexiveClosure
```
public final int reflexiveClosure()
```
    Computes the reflexive closure of this component.
    
    Returns:
    
    the number of added edges
  - transitiveClosure
```
public int transitiveClosure()
```
    Computes the transitive closure of this component.
    
    This treatment is performed in $O(nm+m_c)$, where $n$ corresponds to the number of nodes, $m$ to the number of edges, and $m_c$ to the number of edges in the closure. This treatment improves the Roy-Warshall algorithm that directly implements the definition in $O(log(m) n^3)$.
    
    This treatment is overridden in class DAGraph with a more efficient algorithm dedicated to directed acyclic graph.
    
    Returns:
    
    the number of added edges
  - transpose
```
public final void transpose()
```
    Transposes this component by replacing for each node its successor set by its predecessor set, and its predecessor set by its successor set.
  - getStronglyConnectedComponent
```
public DAGraph<SortedSet<Node<N>>,Object> getStronglyConnectedComponent()
```
    Returns the directed acyclic graph where each node corresponds to a strongly connected component (SCC) of this component stored in a TreeSet of nodes.
    
    When two nodes in two different SCC are in relation, the same is for the SCC they belongs to.
    
    Returns:
    
    The directed acyclic graph
  - setNodes
```
protected ConcreteDGraph<N,E> setNodes(TreeSet<Node<N>> nodes)
```
    Set the set of nodes of this component.
    
    Parameters:
    
    nodes - The nodes
    
    Returns:
    
    this for chaining
  - getSuccessors
```
protected TreeMap<Node<N>,TreeSet<Edge<N,E>>> getSuccessors()
```
    Returns the successors of this component.
    
    Returns:
    
    the map
  - setSuccessors
```
protected ConcreteDGraph<N,E> setSuccessors(TreeMap<Node<N>,TreeSet<Edge<N,E>>> successors)
```
    Set the successors of this component.
    
    Parameters:
    
    successors - The successors
    
    Returns:
    
    this for chaining
  - getPredecessors
```
protected TreeMap<Node<N>,TreeSet<Edge<N,E>>> getPredecessors()
```
    Returns the predecessors of this component.
    
    Returns:
    
    the map
  - setPredecessors
```
protected ConcreteDGraph<N,E> setPredecessors(TreeMap<Node<N>,TreeSet<Edge<N,E>>> predecessors)
```
    Set the predecessors of this component.
    
    Parameters:
    
    predecessors - The predecessors
    
    Returns:
    
    this for chaining

Class ConcreteDGraph<N,E>

Constructor Summary

Method Summary

Methods inherited from class org.thegalactic.dgraph.AbstractDGraph

Methods inherited from class java.lang.Object

Constructor Detail

ConcreteDGraph

ConcreteDGraph

ConcreteDGraph

Method Detail

clone

getNodes

getEdges

getSuccessorEdges

getPredecessorEdges

getSuccessorNodes

getPredecessorNodes

getEdge

getNode

getNodeByContent

getNodeByIdentifier

sizeNodes

sizeEdges

containsNode

addNode

removeNode

removeNodes

containsEdge

containsEdge

addEdge

addEdge

addEdge

removeEdge

removeEdge

getSubgraphByNodes

getSubgraphByEdges

complementary

reflexiveReduction

reflexiveClosure

transitiveClosure

transpose

getStronglyConnectedComponent

setNodes

getSuccessors

setSuccessors

getPredecessors

setPredecessors