T
- The type of the node.public class DefaultGraph<T extends Node> extends java.lang.Object implements Graph<T>
Modifier and Type | Field and Description |
---|---|
private java.util.Set<Edge<T>> |
edges
The set of edges
|
private java.util.Set<T> |
nodes
The set of nodes
|
IGNORE_SELFLOOPS, INVERT_SELFLOOPS, REMOVE_SELFLOOPS
Constructor and Description |
---|
DefaultGraph()
Creates an empty graph.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(Edge<T> edge)
Adds the given edge to this graph.
|
boolean |
add(T node)
Adds the given node to this graph.
|
boolean |
areAdjacent(T a,
T b)
Returns "true" iff the two nodes are connected by a directed edge
from a to b or an undirected edge.
|
boolean |
contains(java.lang.Object obj)
Returns "true" when this graph contains the given
node or edge.
|
static <S extends Node> |
existsDirectedPath(Graph<S> g,
S node1,
S node2)
Checks whether there is a (directed) path from node1 to node2 in the given graph.
|
boolean |
existsDirectedPath(T node1,
T node2)
Checks whether there is a (directed) path from node1 to node2.
|
Matrix |
getAdjancyMatrix()
Returns the adjacency matrix of this graph (the order
of the nodes is the same as returned by "iterator()").
|
java.util.Collection<T> |
getChildren(Node node)
Returns the set of children (node connected via an undirected edge or a directed edge
where the given node is the parent) of the given node.
|
Graph<T> |
getComplementGraph(int selfloops)
Returns the complement graph of this graph, i.e.
|
Edge<T> |
getEdge(T a,
T b)
Returns the corresponding edge (a,b) if a and b are adjacent.
|
java.util.Collection<Edge<T>> |
getEdges()
Returns the edges of this graph.
|
java.util.Collection<T> |
getNeighbors(T node)
Returns the set of neighbors of the given node.
|
java.util.Collection<T> |
getNodes()
Returns the nodes of this graph.
|
int |
getNumberOfNodes()
Returns the number of nodes in this graph.
|
java.util.Collection<T> |
getParents(Node node)
Returns the set of parents (node connected via an undirected edge or a directed edge
where the given node is the child) of the given node.
|
DefaultGraph<T> |
getRestriction(java.util.Collection<T> nodes)
Returns copy of this graph consisting only of the given
nodes and all corresponding edges.
|
java.util.Collection<java.util.Collection<T>> |
getStronglyConnectedComponents()
Returns the strongly connected components of this graph.
|
static <S extends Node> |
getStronglyConnectedComponents(Graph<S> g)
Returns the strongly connected components of the given graph.
|
private static <S extends Node> |
getStronglyConnectedComponentsRec(int idx,
S v,
java.util.Stack<S> stack,
java.util.Collection<java.util.Collection<S>> sccs,
Graph<S> g,
java.util.Map<S,java.lang.Integer> index,
java.util.Map<S,java.lang.Integer> lowlink)
Main method for computing the strongly connected components using
Tarjan's algorithm.
|
java.util.Collection<Graph<T>> |
getSubgraphs()
Returns the set of sub graphs of this graph.
|
static <S extends Node> |
getSubgraphs(Graph<S> g)
Returns the set of sub graphs of the given graph.
|
boolean |
hasSelfLoops()
Returns "true" iff the graph has a self loop (an edge from a node to itself).
|
boolean |
isWeightedGraph()
Checks whether this graph only contains weighted edges.
|
java.util.Iterator<T> |
iterator() |
java.lang.String |
toString() |
public boolean add(T node)
Graph
public boolean add(Edge<T> edge)
Graph
public java.util.Collection<T> getNodes()
Graph
public int getNumberOfNodes()
Graph
getNumberOfNodes
in interface Graph<T extends Node>
public java.util.Collection<Edge<T>> getEdges()
Graph
public java.util.Iterator<T> iterator()
public boolean contains(java.lang.Object obj)
Graph
public java.util.Collection<T> getNeighbors(T node)
Graph
getNeighbors
in interface Graph<T extends Node>
node
- some node (must be in the graph).public java.util.Collection<T> getChildren(Node node)
Graph
getChildren
in interface Graph<T extends Node>
node
- some node (must be in the graph).public java.util.Collection<T> getParents(Node node)
Graph
getParents
in interface Graph<T extends Node>
node
- some node (must be in the graph).public boolean areAdjacent(T a, T b)
Graph
areAdjacent
in interface Graph<T extends Node>
a
- some nodeb
- some nodepublic Edge<T> getEdge(T a, T b)
Graph
public boolean existsDirectedPath(T node1, T node2)
Graph
existsDirectedPath
in interface Graph<T extends Node>
node1
- some node.node2
- some node.public Matrix getAdjancyMatrix()
Graph
getAdjancyMatrix
in interface Graph<T extends Node>
public java.lang.String toString()
public Graph<T> getComplementGraph(int selfloops)
Graph
getComplementGraph
in interface Graph<T extends Node>
selfloops
- Indicates how to deal with selfloops:public boolean hasSelfLoops()
Graph
hasSelfLoops
in interface Graph<T extends Node>
public boolean isWeightedGraph()
Graph
isWeightedGraph
in interface Graph<T extends Node>
public java.util.Collection<java.util.Collection<T>> getStronglyConnectedComponents()
Graph
getStronglyConnectedComponents
in interface Graph<T extends Node>
private static <S extends Node> int getStronglyConnectedComponentsRec(int idx, S v, java.util.Stack<S> stack, java.util.Collection<java.util.Collection<S>> sccs, Graph<S> g, java.util.Map<S,java.lang.Integer> index, java.util.Map<S,java.lang.Integer> lowlink)
idx
- the current node indexv
- the current nodestack
- the stack of nodes that need to be visitedsccs
- the set of SCCs that is computedg
- the graphindex
- an index map for the verticeslowlink
- the lowlink map for the verticespublic static <S extends Node> java.util.Collection<java.util.Collection<S>> getStronglyConnectedComponents(Graph<S> g)
g
- some graphpublic java.util.Collection<Graph<T>> getSubgraphs()
Graph
getSubgraphs
in interface Graph<T extends Node>
public static <S extends Node> java.util.Collection<Graph<S>> getSubgraphs(Graph<S> g)
public DefaultGraph<T> getRestriction(java.util.Collection<T> nodes)
Graph
getRestriction
in interface Graph<T extends Node>
nodes
- a set of nodespublic static <S extends Node> boolean existsDirectedPath(Graph<S> g, S node1, S node2)
g
- some graph.node1
- some node.node2
- some node.