Package org.tweetyproject.graphs

Class DefaultGraph<T extends Node>

java.lang.Object

org.tweetyproject.graphs.DefaultGraph<T>

Type Parameters:

T - The type of the node.

All Implemented Interfaces:

Iterable<T>, GeneralGraph<T>, Graph<T>

Direct Known Subclasses:

ArgumentTree, Compilation, SimpleGraph

public class DefaultGraph<T extends Node>
extends Object
implements Graph<T>

Instance of this class represent graphs with nodes of type T

Author:

Matthias Thimm

Field Summary

Fields inherited from interface org.tweetyproject.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)	Return whether the operation was successful
boolean	add(GeneralEdge<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(Object obj)	Returns "true" when this graph contains the given node or edge.
static <S extends Node> boolean	containsBackEdge(Node parent, Map<Node,Integer> states, Graph<S> g)	Helper method for detecting cycles using depth-first search.
static <S extends Node> boolean	containsCycle(Graph<S> g)	Checks whether there is at least one cycle in the given graph.
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.
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()").
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> Collection<Graph<S>>	getComponents(Graph<S> g)	Finds all components of a graph.
static <S extends Node> Set<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> Set<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.
Collection<Edge<T>>	getEdges()	Returns the edges of this graph.
static <S extends Node> Collection<Graph<S>>	getInducedSubgraphs(Graph<S> g)	Finds all induced subgraphs.
Collection<T>	getNeighbors(T node)	Returns the set of neighbors of the given node.
Collection<T>	getNodes()	Returns the nodes of this graph.
int	getNumberOfEdges()	Returns the number of edges in this graph.
int	getNumberOfNodes()	Returns the number of nodes in this graph.
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(Collection<T> nodes)	Returns a copy of this graph that contains only the specified nodes and all corresponding edges between them.
Collection<Collection<T>>	getStronglyConnectedComponents()	Returns the strongly connected components of this graph.
static <S extends Node> Collection<Collection<S>>	getStronglyConnectedComponents(Graph<S> g)	* Returns the strongly connected components of the given graph.
Collection<Graph<T>>	getSubgraphs()	Returns the set of sub graphs of this graph.
static <S extends Node> Collection<Graph<S>>	getSubgraphs(GeneralGraph<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).
static <S extends Node> boolean	isBipartite(Graph<S> g)	checks whether the given graph is bipartite or not the algorithm starts at a random node and colors adjacent nodes in alternating colors if two adjacent nodes have the same color, the graph is no bipartite NOTE: This method only works if the given graph is connected
boolean	isWeightedGraph()	Checks whether this graph only contains weighted edges.
Iterator<T>	iterator()
String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

DefaultGraph

public DefaultGraph()

Creates an empty graph.

Method Details

add

public boolean add(T node)

Description copied from interface: Graph

Adds the given node to this graph.

Specified by:

add in interface Graph<T extends Node>

Parameters:

node - some node.

Returns:

"true" iff the edge has been added successfully.

add

public boolean add(Edge<T> edge)

Return whether the operation was successful

Parameters:

edge - an edge

Returns:

whether the operation was successful

getNodes

public Collection<T> getNodes()

Description copied from interface: Graph

Returns the nodes of this graph.

Specified by:

getNodes in interface GeneralGraph<T extends Node>

Specified by:

getNodes in interface Graph<T extends Node>

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 interface Graph<T extends Node>

Returns:

the number of nodes in this graph.

getNumberOfEdges

public int getNumberOfEdges()

Description copied from interface: Graph

Returns the number of edges in this graph.

Specified by:

getNumberOfEdges in interface Graph<T extends Node>

Returns:

the number of edges in this graph.

getEdges

public Collection<Edge<T>> getEdges()

Description copied from interface: Graph

Returns the edges of this graph.

Specified by:

getEdges in interface GeneralGraph<T extends Node>

Specified by:

getEdges in interface Graph<T extends Node>

Returns:

the edges of this graph.

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Graph<T extends Node>

Specified by:

iterator in interface Iterable<T extends Node>

contains

public boolean contains(Object obj)

Description copied from interface: Graph

Returns "true" when this graph contains the given node or edge.

Specified by:

contains in interface Graph<T extends Node>

Parameters:

obj - an object

Returns:

"true" if this graph contains the given node or edge.

getNeighbors

public Collection<T> getNeighbors(T node)

Description copied from interface: Graph

Returns the set of neighbors of the given node.

Specified by:

getNeighbors in interface Graph<T extends Node>

Parameters:

node - some node (must be in the graph).

Returns:

the set of neighbors of the given node.

getChildren

public 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 interface Graph<T extends Node>

Parameters:

node - some node (must be in the graph).

Returns:

the set of children of the given node.

getParents

public 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 interface Graph<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 interface Graph<T extends Node>

Parameters:

a - some node

b - 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.

Specified by:

getEdge in interface Graph<T extends Node>

Parameters:

a - some node

b - some node

Returns:

the edge (a,b) or 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 interface Graph<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 interface Graph<T extends Node>

Returns:

the adjacency matrix of this graph

toString

public String toString()

Specified by:

toString in interface Graph<T extends Node>

Overrides:

toString in class Object

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 interface Graph<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 interface Graph<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 interface Graph<T extends Node>

Returns:

"true" if all edges are weighted in this graph.

getStronglyConnectedComponents

public Collection<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 interface Graph<T extends Node>

Returns:

the strongly connected components of this graph.

getStronglyConnectedComponents

public static <S extends Node>
Collection<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

Type Parameters:

S - a Node

Parameters:

g - some graph

Returns:

the strongly connected components of the graph.

getSubgraphs

public Collection<Graph<T>> getSubgraphs()

Description copied from interface: Graph

Returns the set of sub graphs of this graph.

Specified by:

getSubgraphs in interface Graph<T extends Node>

Returns:

the set of sub graphs of this graph.

getSubgraphs

public static <S extends Node> Collection<Graph<S>> getSubgraphs(GeneralGraph<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(Collection<T> nodes)

Description copied from interface: GeneralGraph

Returns a copy of this graph that contains only the specified nodes and all corresponding edges between them.

This method generates a subgraph (or restricted graph) from the current graph by including only the given nodes and the edges that connect them. The returned graph is a new instance and does not modify the original graph.

Specified by:

getRestriction in interface GeneralGraph<T extends Node>

Parameters:

nodes - a collection of nodes to be included in the restricted graph.

Returns:

a `GeneralGraph` object representing the restricted 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.

Type Parameters:

S - a Node

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.

Type Parameters:

S - a Node

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,
 Map<Node,Integer> states,
 Graph<S> g)

Helper method for detecting cycles using depth-first search.

Type Parameters:

S - a Node

Parameters:

parent - current node

states - map of states of nodes

g - some graph

Returns:

"true" if a back edge (cycle) was found in the DFS step, false otherwise

getCyclesExcludingSelfLoops

public static <S extends Node> Set<Stack<S>> getCyclesExcludingSelfLoops(Graph<S> g)

Finds the cycles of an graph order-sensitively, excluding self-loops (cycles of length one).

Type Parameters:

S - a Node

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> Set<Stack<S>> getCyclesIncludingSelfLoops(Graph<S> g)

Finds the cycles of an graph order-sensitively, including self-loops (cycles of length one).

Type Parameters:

S - a Node

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> Collection<Graph<S>> getComponents(Graph<S> g)

Finds all components of a graph.

Type Parameters:

S - a Node

Parameters:

g - The graph which components should be found.

Returns:

A collection of the components as separate graphs.

getInducedSubgraphs

public static <S extends Node> Collection<Graph<S>> getInducedSubgraphs(Graph<S> g)

Finds all induced subgraphs.

Type Parameters:

S - a Node

Parameters:

g - The graph which induced subgraphs should be found.

Returns:

A collection of graphs representing the induced subgraphs.

isBipartite

public static <S extends Node> boolean isBipartite(Graph<S> g)

checks whether the given graph is bipartite or not the algorithm starts at a random node and colors adjacent nodes in alternating colors if two adjacent nodes have the same color, the graph is no bipartite NOTE: This method only works if the given graph is connected

Type Parameters:

S - the type of nodes

Parameters:

g - a graph

Returns:

"true" if g is bipartite

add

public boolean add(GeneralEdge<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.

Specified by:

add in interface Graph<T extends Node>

Parameters:

edge - some edge.

Returns:

"true" iff the edge has been added successfully.