Package net.sf.tweety.graphs
Class DefaultGraph<T extends Node>
- java.lang.Object
-
- net.sf.tweety.graphs.DefaultGraph<T>
-
- Type Parameters:
T
- The type of the node.
- All Implemented Interfaces:
java.lang.Iterable<T>
,Graph<T>
- Direct Known Subclasses:
ArgumentTree
,Compilation
public class DefaultGraph<T extends Node> extends java.lang.Object implements Graph<T>
Instance of this class represent graphs with nodes of type T- Author:
- Matthias Thimm
-
-
Field Summary
-
Fields inherited from interface net.sf.tweety.graphs.Graph
IGNORE_SELFLOOPS, INVERT_SELFLOOPS, REMOVE_SELFLOOPS
-
-
Constructor Summary
Constructors Constructor Description DefaultGraph()
Creates an empty graph.
-
Method Summary
Modifier and Type Method 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>
booleancontainsBackEdge(Node parent, java.util.Map<Node,java.lang.Integer> states, Graph<S> g)
Helper method for detecting cycles using depth-first search.static <S extends Node>
booleancontainsCycle(Graph<S> g)
Checks whether there is at least one cycle in the given graph.static <S extends Node>
booleanexistsDirectedPath(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
getAdjacencyMatrix()
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.static <S extends Node>
java.util.Collection<Graph<S>>getComponents(Graph<S> g)
Finds all components of a graph.static <S extends Node>
java.util.Set<java.util.Stack<S>>getCyclesExcludingSelfLoops(Graph<S> g)
Finds the cycles of an graph order-sensitively, excluding self-loops (cycles of length one).static <S extends Node>
java.util.Set<java.util.Stack<S>>getCyclesIncludingSelfLoops(Graph<S> g)
Finds the cycles of an graph order-sensitively, including self-loops (cycles of length one).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.static <S extends Node>
java.util.Collection<Graph<S>>getInducedSubgraphs(Graph<S> g)
Finds all induced subgraphs.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>
java.util.Collection<java.util.Collection<S>>getStronglyConnectedComponents(Graph<S> g)
Returns the strongly connected components of the given graph.java.util.Collection<Graph<T>>
getSubgraphs()
Returns the set of sub graphs of this graph.static <S extends Node>
java.util.Collection<Graph<S>>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()
-
-
-
Method Detail
-
add
public boolean add(T node)
Description copied from interface:Graph
Adds the given node to this graph.
-
add
public boolean add(Edge<T> edge)
Description copied from interface:Graph
Adds the given edge to this graph. If at least one of the nodes the given edge connects is not in the graph, an illegal argument exception is thrown.
-
getNodes
public java.util.Collection<T> getNodes()
Description copied from interface:Graph
Returns the nodes of this graph.
-
getNumberOfNodes
public int getNumberOfNodes()
Description copied from interface:Graph
Returns the number of nodes in this graph.- Specified by:
getNumberOfNodes
in interfaceGraph<T extends Node>
- Returns:
- the number of nodes in this graph.
-
getEdges
public java.util.Collection<Edge<T>> getEdges()
Description copied from interface:Graph
Returns the edges of this graph.
-
iterator
public java.util.Iterator<T> iterator()
-
contains
public boolean contains(java.lang.Object obj)
Description copied from interface:Graph
Returns "true" when this graph contains the given node or edge.
-
getNeighbors
public java.util.Collection<T> getNeighbors(T node)
Description copied from interface:Graph
Returns the set of neighbors of the given node.- Specified by:
getNeighbors
in interfaceGraph<T extends Node>
- Parameters:
node
- some node (must be in the graph).- Returns:
- the set of neighbors of the given node.
-
getChildren
public java.util.Collection<T> getChildren(Node node)
Description copied from interface:Graph
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.- Specified by:
getChildren
in interfaceGraph<T extends Node>
- Parameters:
node
- some node (must be in the graph).- Returns:
- the set of children of the given node.
-
getParents
public java.util.Collection<T> getParents(Node node)
Description copied from interface:Graph
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.- Specified by:
getParents
in interfaceGraph<T extends Node>
- Parameters:
node
- some node (must be in the graph).- Returns:
- the set of parents of the given node.
-
areAdjacent
public boolean areAdjacent(T a, T b)
Description copied from interface:Graph
Returns "true" iff the two nodes are connected by a directed edge from a to b or an undirected edge.- Specified by:
areAdjacent
in interfaceGraph<T extends Node>
- Parameters:
a
- some nodeb
- some node- Returns:
- "true" iff the two nodes are connected by a directed edge from a to b or an undirected edge.
-
getEdge
public Edge<T> getEdge(T a, T b)
Description copied from interface:Graph
Returns the corresponding edge (a,b) if a and b are adjacent. Otherwise it returns null.
-
existsDirectedPath
public boolean existsDirectedPath(T node1, T node2)
Description copied from interface:Graph
Checks whether there is a (directed) path from node1 to node2.- Specified by:
existsDirectedPath
in interfaceGraph<T extends Node>
- Parameters:
node1
- some node.node2
- some node.- Returns:
- "true" if there is a directed path from node1 to node2.
-
getAdjacencyMatrix
public Matrix getAdjacencyMatrix()
Description copied from interface:Graph
Returns the adjacency matrix of this graph (the order of the nodes is the same as returned by "iterator()").- Specified by:
getAdjacencyMatrix
in interfaceGraph<T extends Node>
- Returns:
- the adjacency matrix of this graph
-
toString
public java.lang.String toString()
-
getComplementGraph
public Graph<T> getComplementGraph(int selfloops)
Description copied from interface:Graph
Returns the complement graph of this graph, i.e. the graph on the same set of vertices as this graph that connects two vertices v and w with an edge if and only if v and w are not connected in this graph.- Specified by:
getComplementGraph
in interfaceGraph<T extends Node>
- Parameters:
selfloops
- Indicates how to deal with selfloops:
IGNORE_SELFLOOPS - ignore self loops (don't add and don't remove)
INVERT_SELFLOOPS - deal with self loops like ordinary edges (add if not present and remove if present)
REMOVE_SELFLOOPS - simple remove self loops, but don't add new ones.- Returns:
- the complement graph of this graph.
-
hasSelfLoops
public boolean hasSelfLoops()
Description copied from interface:Graph
Returns "true" iff the graph has a self loop (an edge from a node to itself).- Specified by:
hasSelfLoops
in interfaceGraph<T extends Node>
- Returns:
- "true" iff the graph has a self loop (an edge from a node to itself).
-
isWeightedGraph
public boolean isWeightedGraph()
Description copied from interface:Graph
Checks whether this graph only contains weighted edges.- Specified by:
isWeightedGraph
in interfaceGraph<T extends Node>
- Returns:
- "true" if all edges are weighted in this graph.
-
getStronglyConnectedComponents
public java.util.Collection<java.util.Collection<T>> getStronglyConnectedComponents()
Description copied from interface:Graph
Returns the strongly connected components of this graph. A set of nodes is strongly connected, if there is a path from each node to each other. A set of nodes is called strongly connected component if it is strongly connected and maximal with respect to set inclusion.- Specified by:
getStronglyConnectedComponents
in interfaceGraph<T extends Node>
- Returns:
- the strongly connected components of this graph.
-
getStronglyConnectedComponents
public static <S extends Node> java.util.Collection<java.util.Collection<S>> getStronglyConnectedComponents(Graph<S> g)
Returns the strongly connected components of the given graph. A set of nodes is strongly connected, if there is a path from each node to each other. A set of nodes is called strongly connected component if it is strongly connected and maximal with respect to set inclusion. The strongly connected components are computed using Tarjan's algorithm- Parameters:
g
- some graph- Returns:
- the strongly connected components of the graph.
-
getSubgraphs
public java.util.Collection<Graph<T>> getSubgraphs()
Description copied from interface:Graph
Returns the set of sub graphs of this graph.- Specified by:
getSubgraphs
in interfaceGraph<T extends Node>
- Returns:
- the set of sub graphs of this graph.
-
getSubgraphs
public static <S extends Node> java.util.Collection<Graph<S>> getSubgraphs(Graph<S> g)
Returns the set of sub graphs of the given graph.- Type Parameters:
S
- the type of nodes- Parameters:
g
- a graph- Returns:
- the set of sub graphs of the given graph.
-
getRestriction
public DefaultGraph<T> getRestriction(java.util.Collection<T> nodes)
Description copied from interface:Graph
Returns copy of this graph consisting only of the given nodes and all corresponding edges.- Specified by:
getRestriction
in interfaceGraph<T extends Node>
- Parameters:
nodes
- a set of nodes- Returns:
- a graph.
-
existsDirectedPath
public static <S extends Node> boolean existsDirectedPath(Graph<S> g, S node1, S node2)
Checks whether there is a (directed) path from node1 to node2 in the given graph.- Parameters:
g
- some graph.node1
- some node.node2
- some node.- Returns:
- "true" if there is a directed path from node1 to node2.
-
containsCycle
public static <S extends Node> boolean containsCycle(Graph<S> g)
Checks whether there is at least one cycle in the given graph.- Parameters:
g
- some graph- Returns:
- "true" if there is a cycle in the graph, "false" if the graph is acyclic
-
containsBackEdge
public static <S extends Node> boolean containsBackEdge(Node parent, java.util.Map<Node,java.lang.Integer> states, Graph<S> g)
Helper method for detecting cycles using depth-first search.- Parameters:
parent
- current nodestates
- map of states of nodesg
- some graph- Returns:
- "true" if a back edge (cycle) was found in the DFS step, false otherwise
-
getCyclesExcludingSelfLoops
public static <S extends Node> java.util.Set<java.util.Stack<S>> getCyclesExcludingSelfLoops(Graph<S> g)
Finds the cycles of an graph order-sensitively, excluding self-loops (cycles of length one).- Parameters:
g
- The graph to be searched.- Returns:
- An stack of nodes with the order indicating the direction of the cycle (assuming an directed graph).
-
getCyclesIncludingSelfLoops
public static <S extends Node> java.util.Set<java.util.Stack<S>> getCyclesIncludingSelfLoops(Graph<S> g)
Finds the cycles of an graph order-sensitively, including self-loops (cycles of length one).- Parameters:
g
- The graph to be searched.- Returns:
- An stack of nodes with the order indicating the direction of the cycle (assuming an directed graph).
-
getComponents
public static <S extends Node> java.util.Collection<Graph<S>> getComponents(Graph<S> g)
Finds all components of a graph.- Parameters:
g
- The graph which components should be found.- Returns:
- A collection of the components as separate graphs.
-
-