Package com.qfs.graph

Interface IDirectedGraph<K,V,E>

Type Parameters:

K - the type of the keys for the vertices

V - the type of the content for the vertices

E - the type of the edges

Edge convention: a null value for an edge between two nodes is interpreted as the absence of edges between these two nodes.

All Superinterfaces:

Map<K,V>

All Known Subinterfaces:

IConcurrentDirectedGraph<K,V,E>, IDirectedMultiGraph<K,V,E>, IQueryStoreTree, ITree<K,V,E>

All Known Implementing Classes:

ConcurrentDirectedGraph, DirectedGraph, DirectedMultiGraph, QueryStoreTree, Tree, UnmodifiableDirectedMultiGraph, UserStoreGraph

public interface IDirectedGraph<K,V,E>
extends Map<K,V>

Represent a mutable directed graph.

Author:

ActiveViam

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

Method Summary

Modifier and Type	Method	Description
void	addNode(K key, V value)	Adds a node to the graph.
IDirectedGraph<K,V,E>	filterEdges(Predicate<E> filter)	Creates a directed graph with the same vertices but only the edges selected by a filter.
default void	forEachNode(BiConsumer<K,V> consumer)
E	getEdge(K from, K to)	Retrieves the edge linking a node to another.
Collection<E>	getEdges()	Retrieves the (unordered) list of all edges in the graph.
Map<K,E>	getEdgesFrom(K from)	Retrieves all edges starting from a node and returns them along with the node they reach.
Map<K,E>	getEdgesTo(K to)	A lot slower than getEdgesFrom(Object) since edges are indexed by their from node.
default Collection<Map.Entry<K,V>>	getNodes()
Set<K>	getReached(Set<K> included)	Returns all the nodes that can be reached from at least one of the included nodes.
Set<K>	getReachers(Set<K> included)	Returns all the nodes that have at least one of their edges ending in a node included in the given set.
K	getTo(K from, E edge)	Finds the node reachable from a given node and a given edge.
boolean	hasEdge(K from, K to)	Checks the existence of an edge between two nodes.
boolean	isAcyclic()	Checks whether or not this graph has cycles.
void	moveKey(K from, K to)	Replaces a key by another.
void	removeEdge(K from, K to)	Removes the edge between two nodes.
default V	removeNode(K key)	Removes a node from the graph.
E	setEdge(K from, K to, E edge)	Changes the edge between two nodes.
default V	setNode(K key, V value)

Methods inherited from interface java.util.Map

clear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, entrySet, equals, forEach, get, getOrDefault, hashCode, isEmpty, keySet, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size, values

Method Detail

addNode

void addNode(K key,
             V value)

Adds a node to the graph. If a node already exists with the same key it is overridden and all edges are now connected to the new node.

Parameters:

key - the key of the node to add

value - the value of the node to add

setNode

default V setNode(K key,
                  V value)

removeNode

default V removeNode(K key)

Removes a node from the graph.

Returns:

the value associated with the node

getNodes

default Collection<Map.Entry<K,V>> getNodes()

forEachNode

default void forEachNode(BiConsumer<K,V> consumer)

setEdge

E setEdge(K from,
          K to,
          E edge)

Changes the edge between two nodes.

Parameters:

from - the node from which the edge should start

to - the node to which this edge should go

edge - the new value for the edge, a null value will be interpreted as a removal of the previous edge (if any)

Returns:

the previous edge between from and to

removeEdge

void removeEdge(K from,
                K to)

Removes the edge between two nodes.

Parameters:

from - the node from which this edge starts

to - the node to which this edge goes

getEdge

E getEdge(K from,
          K to)

Retrieves the edge linking a node to another.

Parameters:

from - the node from which this edge starts

to - the node to which this edge goes

Returns:

null if from and to are not linked by convention

getEdges

Collection<E> getEdges()

Retrieves the (unordered) list of all edges in the graph.

Returns:

a non null but possibly empty collection of edges

getTo

K getTo(K from,
        E edge)

Finds the node reachable from a given node and a given edge.

If two Object.equals(Object) edges connect K to different nodes A and B, A or B will be returned non deterministically.

Parameters:

from - the node from which the edge starts

edge - the edge to use

Returns:

the node to which from is connected via edge, or null if there is no such edge starting from from

getEdgesFrom

Map<K,E> getEdgesFrom(K from)

Retrieves all edges starting from a node and returns them along with the node they reach.

If from is not contained in the graph, an empty map will be returned.

Parameters:

from - the node from which the edges start

Returns:

the edges (and the vertices' keys) that leave from

getEdgesTo

Map<K,E> getEdgesTo(K to)

A lot slower than getEdgesFrom(Object) since edges are indexed by their from node.

Parameters:

to - the node to which the edge go

Returns:

the vertices' keys and the edges that reach to

getReachers

Set<K> getReachers(Set<K> included)

Returns all the nodes that have at least one of their edges ending in a node included in the given set.

Parameters:

included - the nodes to be included

Returns:

the set containing all nodes that can reach one of the included nodes by following edges multiple times, it includes all the given nodes

getReached

Set<K> getReached(Set<K> included)

Returns all the nodes that can be reached from at least one of the included nodes.

Parameters:

included - the nodes to be included.

Returns:

the set containing all nodes that can be reached from one of the included nodes by following edges multiple times

hasEdge

boolean hasEdge(K from,
                K to)

Checks the existence of an edge between two nodes.

Convention: an edge exist if getEdge(Object, Object) returns a non null value.

Parameters:

from - the node from which the edge should start

to - the node to which this edge connects

Returns:

true if there is an edge between the 2 nodes, false otherwise

moveKey

void moveKey(K from,
             K to)

Replaces a key by another.

Moves the value and all edges from and to the previous key to the new key.

Parameters:

from - the original value

to - the destination value

filterEdges

IDirectedGraph<K,V,E> filterEdges(Predicate<E> filter)

Creates a directed graph with the same vertices but only the edges selected by a filter.

Parameters:

filter - tells for each edge if it should be copied in the new graph or not

Returns:

the new graph, it has less edges but the contained vertices and edges are the same objects than in the original graph

isAcyclic

boolean isAcyclic()

Checks whether or not this graph has cycles.

Returns:

true if the graph has no cycle (is acyclic), false otherwise