Package net.sf.tweety.graphs

Class DefaultGraph<T extends Node>

  • 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

    • 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>
      boolean      		 containsBackEdge​(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>
      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()").
      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>
      java.util.Collection<java.util.Collection<S>>      		 getStronglyConnectedComponents​(Graph<S> g)
      Returns the strongly connected components of the given graph.
      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)
      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>
      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()  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator

    • Field Detail

      • nodes

        private java.util.Set<T extends Node> nodes
        The set of nodes

      • edges

        private java.util.Set<Edge<T extends Node>> edges
        The set of edges

    • Constructor Detail

      • DefaultGraph

        public DefaultGraph()
        Creates an empty graph.

    • Method Detail

      • 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)
        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.

      • getNodes

        public java.util.Collection<T> getNodes()
        Description copied from interface: Graph
        Returns the nodes of this graph.
        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.

      • getEdges

        public java.util.Collection<Edge<T>> getEdges()
        Description copied from interface: Graph
        Returns the edges of this graph.
        Specified by:
        getEdges in interface Graph<T extends Node>
        Returns:
        the edges of this graph.

      • iterator

        public java.util.Iterator<T> iterator()
        Specified by:
        iterator in interface Graph<T extends Node>
        Specified by:
        iterator in interface java.lang.Iterable<T extends Node>

      • contains

        public boolean contains​(java.lang.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 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 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 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 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 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 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 java.lang.String toString()
        Specified by:
        toString in interface Graph<T extends Node>
        Overrides:
        toString in class java.lang.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 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 interface Graph<T extends Node>
        Returns:
        the strongly connected components of this graph.

      • getStronglyConnectedComponentsRec

        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)
        Main method for computing the strongly connected components using Tarjan's algorithm.
        Parameters:
        idx - the current node index
        v - the current node
        stack - the stack of nodes that need to be visited
        sccs - the set of SCCs that is computed
        g - the graph
        index - an index map for the vertices
        lowlink - the lowlink map for the vertices
        Returns:
        the updated idx

      • 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 interface Graph<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 interface Graph<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 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