Package de.saar.chorus.domgraph.graph

Class DomGraph

java.lang.Object
de.saar.chorus.domgraph.graph.DomGraph
All Implemented Interfaces:
Cloneable
public class DomGraph extends Object implements Cloneable
A dominance graph. Dominance graphs are directed graphs. Nodes are either labelled or unlabelled; edges are either dominance or tree edges. We say that a node is a root if it has no incoming tree edges; a leaf if it has no outgoing tree edges; and a hole if it is unlabelled.

Graph objects provide several basic methods for accessing nodes, edges, and node and edge data. In addition, they provide a number of methods for checking whether the graph belongs to one of the important graph classes, such as (weakly) normal and hypernormally connected graphs.

Several methods can take a subgraph of this graph as an argument. In this context, a subgraph is always a set of nodes.

While nodes are marked as labelled or unlabelled here, the actual node labels are not stored here, but in objects of the class NodeLabels.

Author:
Alexander Koller

  • Constructor Details

    • DomGraph

      public DomGraph()

  • Method Details

    • getRoot

      public String getRoot(String node)
      Computes the root of the fragment of the given node.
      Parameters:
      node - a node in the graph
      Returns:
      the root of this node's fragment, or null if the fragment is cyclic.

    • getHoles

      public List<String> getHoles(String node)
      Computes the holes below the given node.
      Parameters:
      node - a node in the graph
      Returns:
      the holes of this node's fragment.

    • getHoles

      public List<String> getHoles(Collection<String> fragment)
      Computes the holes out of a given collection of nodes.
      Parameters:
      fragment - a collection of nodes in this graph
      Returns:
      those nodes out of "fragment" which are holes.

    • getRelativeRightSibling

      public String getRelativeRightSibling(String node, Set<String> subgraph, EdgeType e)

    • getOpenHoles

      public List<String> getOpenHoles(String node)
      Computes the open holes below a given node. Open holes are holes without outgoing dominance edges.
      Parameters:
      node - a node in this graph
      Returns:
      the list of open holes below "node"

    • getFragment

      public Set<String> getFragment(String node)
      Computes the fragment of a given node. A fragment is a maximal set of nodes that are connected via tree edges.
      Parameters:
      node - a node of this graph
      Returns:
      the fragment of this node

    • reachable

      public boolean reachable(String upper, String lower)
      Checks whether there is a directed path from "upper" to "lower" in the graph.

      Parameters:
      upper - a node in the graph
      lower - a node in the graph
      Returns:
      true iff there is a directed path from upper to lower

    • clear

      public void clear()
      Removes all nodes and edges from this graph.

    • addNode

      public void addNode(String name, NodeData data)
      Adds a node with the given node name and node data to the graph.
      Parameters:
      name - the name of the new node
      data - the data for the new node

    • isRelativeLeaf

      public boolean isRelativeLeaf(String node, Set<String> subgraph)

    • isRelativeLeaf

      public boolean isRelativeLeaf(String node, Set<String> subgraph, EdgeType type)

    • isRelativeRoot

      public boolean isRelativeRoot(String node, Set<String> subgraph)

    • isRelativeRoot

      public boolean isRelativeRoot(String node, Set<String> subgraph, EdgeType type)

    • addEdge

      public void addEdge(String src, String tgt, EdgeData data)
      Adds an edge from "src" to "tgt" with the given edge data to the graph.
      Parameters:
      src - an existing node in the graph
      tgt - an existing node in the graph
      data - the data for the new edge

    • remove

      public void remove(String node)
      Removes a given node and all adjacent edges from the graph.
      Parameters:
      node - a node in this graph

    • remove

      public void remove(org._3pq.jgrapht.Edge edge)
      Removes a given edge from the graph.
      Parameters:
      edge - an edge in this graph

    • getAllNodes

      public Set<String> getAllNodes()
      Computes the set of all nodes in this graph.
      Returns:
      the set of all nodes

    • hasNode

      public boolean hasNode(String name)
      Checks whether the graph has a node with the given name.
      Parameters:
      name - a node name
      Returns:
      true iff "name" is a node of this graph.

    • getAllEdges

      public Set<org._3pq.jgrapht.Edge> getAllEdges()
      Computes the set of all edges in this graph.
      Returns:
      the set of all edges

    • getInEdges

      public List<org._3pq.jgrapht.Edge> getInEdges(String node, EdgeType type)
      Computes the set of all incoming edges of a node with a given type. You can select edges of all types by passing null as the "type" argument.
      Parameters:
      node - a node in the graph
      type - an edge type, or null for edges of all types
      Returns:
      the list of incoming edges of this type

    • getParents

      public List<String> getParents(String node, EdgeType type)
      Computes the set of parents of a node via edges of a given type. You can select parents via edges of all types by passing null as the "type" argument.
      Parameters:
      node - a node in the graph
      type - an edge type, or null for edges of all types
      Returns:
      the list of parents via edges of this type

    • getOutEdges

      public List<org._3pq.jgrapht.Edge> getOutEdges(String node, EdgeType type)
      Computes the set of all outgoing edges of a node with a given type. You can select edges of all types by passing null as the "type" argument.
      Parameters:
      node - a node in the graph
      type - an edge type, or null for edges of all types
      Returns:
      the list of outgoing edges of this type

    • getAdjacentEdges

      public List<org._3pq.jgrapht.Edge> getAdjacentEdges(String node, EdgeType type)
      Computes the set of all adjacent edges of a node with a given type. You can select edges of all types by passing null as the "type" argument.
      Parameters:
      node - a node in the graph
      type - an edge type, or null for edges of all types
      Returns:
      the list of adjacent edges of this type

    • getAdjacentEdges

      public List<org._3pq.jgrapht.Edge> getAdjacentEdges(String node)
      Computes the set of all adjacent edges of a node. This is equivalent to getAdjacentEdges(node,null).
      Parameters:
      node - a node in the graph
      Returns:
      the list of adjacent edges

    • getChildren

      public List<String> getChildren(String node, EdgeType type)
      Computes the set of children of a node via edges of a given type. You can select children via edges of all types by passing null as the "type" argument.
      Parameters:
      node - a node in this graph
      type - an edge type, or null for edges of all types
      Returns:
      the list of children via edges of this type

    • getData

      public NodeData getData(String node)
      Gets the data associated with the given node.
      Parameters:
      node - a node in this graph
      Returns:
      the node data

    • getData

      public EdgeData getData(org._3pq.jgrapht.Edge edge)
      Gets the data associated with the given edge.
      Parameters:
      edge - an edge in this graph
      Returns:
      the edge data

    • indeg

      public int indeg(String node)
      Computes the number of incoming edges of a given node. This is equivalent to indeg(node,null).
      Parameters:
      node - a node in this graph
      Returns:
      the indegree of the node

    • outdeg

      public int outdeg(String node)
      Computes the number of outgoing edges of a given node. This is equivalent to outdeg(node,null).
      Parameters:
      node - a node in this graph
      Returns:
      the outdegree of this node

    • indeg

      public int indeg(String node, EdgeType type)
      Computes the number of incoming edges of a given node with a given type. You can specify that you want to count edges of any type by passing null in the "type" argument.
      Parameters:
      node - a node in the graph
      type - the type of the in-edges you want to count, or null for edges of any type
      Returns:
      the number of in-edges of this type

    • indegOfSubgraph

      public int indegOfSubgraph(String node, EdgeType type, Set<String> subgraph)
      Computes the number of incoming edges of a given node, with a given edge type, and whose source nodes are in the given subgraph.
      Parameters:
      node - a node in the graph
      type - an edge type, or null for edges of any type
      subgraph - the subgraph (i.e. set of nodes) in which the parents must be
      Returns:
      the number of such in-edges

    • outdeg

      public int outdeg(String node, EdgeType type)
      Computes the number of outgoing edges of a given node with a given type. You can specify that you want to count edges of any type by passing null in the "type" argument.
      Parameters:
      node - a node in the graph
      type - the type of the out-edges you want to count, or null for edges of any type
      Returns:
      the number of out-edges of this type

    • isRoot

      public boolean isRoot(String node)
      Checks whether a node is a root. Roots are nodes with no incoming tree edges.
      Parameters:
      node - a node
      Returns:
      true iff the node has no incoming tree edges

    • isLeaf

      public boolean isLeaf(String node)
      Checks whether a node is a leaf. Leaves are nodes with no outgoing tree edges. In particular, all holes are leaves by definition (but not vice versa).
      Parameters:
      node - a node in the graph
      Returns:
      true iff the node has no outgoing tree edges

    • isHole

      public boolean isHole(String node)
      Checks whether a node is a hole, i.e. an unlabelled leaf.
      Parameters:
      node - a node in the graph
      Returns:
      true iff the node is a hole

    • getAllRoots

      public Set<String> getAllRoots(Collection<String> nodes)
      Collects all nodes in a given subgraph which are roots.
      Parameters:
      nodes - a collection of nodes (defining a subgraph)
      Returns:
      the set of all nodes among "nodes" which are roots

    • getAllRoots

      public Set<String> getAllRoots()
      Collects all roots in the graph. This is equivalent to getAllRoots(getAllNodes()).
      Returns:
      all roots in this graph

    • isCrossEdge

      public boolean isCrossEdge(org._3pq.jgrapht.Edge e)
      Checks whether an edge is a cross edge, i.e. a dominance edge from a root into a hole. Weakly normal graphs are characterized as having no cross edges.
      Parameters:
      e - an edge in the graph
      Returns:
      true iff e is a cross edge

    • hasCycle

      public boolean hasCycle(Set<String> subgraph, EdgeType type)
      Determines whether a subgraph has a directed cycle. You can specify the subgraph whose nodes can be used for the cycle (or pass null for the complete graph) and the edge type which can be used for the cycle (or pass null for edges of any type). The subgraph need not be (strongly) connected; the method will restart the DFS at unvisited nodes of the subgraph while any exist.
      Parameters:
      subgraph - the nodes which the DFS may visit, or null for the whole graph
      type - the edge types which the DFS may use, or null for any type
      Returns:
      true iff a cycle was found given these constraints

    • wccs

      public List<Set<String>> wccs()
      Computes the weakly connected components of the graph. A weakly connected component is a maximal subgraph which is connected via edges or inverse edges of any type. This is equivalent to wccs(getAllNodes()).
      Returns:
      the list of wccs; each wcc is a set of nodes.

    • wccs

      public List<Set<String>> wccs(Set<String> nodes)
      Computes the weakly connected components of a subgraph. A weakly connected component is a maximal subgraph which is connected via edges or inverse edges of any type.
      Parameters:
      nodes - the subgraph whose wccs we want
      Returns:
      the list of wccs; each wcc is a set of nodes.

    • computeWccMap

      public Map<String,Integer> computeWccMap(List<Set<String>> wccs)
      Computes a mapping of nodes to wcc indices from a list of wccs. Such a mapping assigns to each node in any of the wccs the index between 0 and wccs.size()-1 which contains this node.
      Parameters:
      wccs - a list of WCCs, as computed by the wccs methods.
      Returns:
      the mapping described above.

    • getAllDomEdges

      public List<DomEdge> getAllDomEdges()

    • makeSolvedForm

      public DomGraph makeSolvedForm(SolvedFormSpec spec)
      Returns a dominance graph that is just like the current graph, except that the dominance edges are replaced by those specified in domedges. The original graph is not modified. TODO fix documentation
      Parameters:
      spec - the dominance edges of the new graph
      Returns:
      a new dominance graph with these dominance edges

    • makeNormalBackbone

      public DomGraph makeNormalBackbone()
      Returns a dominance graph that is just like the current graph, except that all dominance edges that don't go from holes to roots have been deleted. The resulting graph is guaranteed to be normal. The original graph is not modified.
      Returns:
      the normal backbone of the original graph

    • makeWeaklyNormalBackbone

      public DomGraph makeWeaklyNormalBackbone()
      Returns a dominance graph that is just like the current graph, except that all cross edges, i.e. dominance edges that go from roots to holes, have been deleted. The resulting graph is guaranteed to be weakly normal. The original graph is not modified.
      Returns:
      the weakly normal backbone of the original graph

    • preprocess

      public DomGraph preprocess() throws DomGraph.PreprocessingException
      Brings a dominance graph into a normal form in which every dominance edge is either from a root to a hole or into a root, and there are no dominance edges within the same fragment. The method throws an exception if it encounters a dominance edge within the same fragment whose source doesn't dominate its target.
      Returns:
      a dominance graph with the same nodes and tree edges as this graph, and cleaned-up dominance edges
      Throws:
      Exception - if the graph contains a dominance edge within one fragment whose source doesn't dominate its target; such graphs are automatically unsolvable.
      DomGraph.PreprocessingException

    • isWeaklyNormal

      public boolean isWeaklyNormal()
      Checks whether this graph is weakly normal. A graph is weakly normal under the following conditions:
      • all holes are leaves;
      • fragments are trees (NB: acyclicity not yet implemented);
      • all dominance edges go into roots or come out of holes (the latter can be normalized into hole-to-root edges by DomGraph#preprocess).
      Returns:
      true iff the graph is weakly normal

    • isNormal

      public boolean isNormal()
      Checks whether this graph is normal. A graph is normal under the following conditions:
      • the graph is weakly normal;
      • dominance edges go from holes to roots.
      Returns:
      true iff the graph is normal.

    • isCompact

      public boolean isCompact()
      Checks whether this graph is compact. A graph is compact iff it only holes have incoming tree edges, i.e. every node is either a root or a hole (or both).
      Returns:
      true iff the graph is compact.

    • isCompactifiable

      public boolean isCompactifiable()
      Checks whether this graph can be compactified. A graph can be compactified iff all dominance edges go either out of holes or out of roots.

      Returns:
      true iff the graph can be compactified

    • isLeafLabelled

      public boolean isLeafLabelled()
      Checks whether the graph is leaf-labelled. A graph is leaf-labelled iff all nodes either have a label or an outgoing dominance edge.
      Returns:
      true iff the graph is leaf-labelled

    • isHypernormallyConnected

      public boolean isHypernormallyConnected()
      Checks whether the graph is hypernormally connected. A graph is hypernormally connected iff each pair of nodes is connected by a hypernormal path in its normal backbone.

      This method checks whether the graph is solvable, and then calls isHypernormallyConnectedFast (if it is) or isHypernormallyConnectedSlow (if it isn't). Its overall runtime is O(n(n+m)) for solvable graphs and O(n^2 (n+m)) for unsolvable ones.

      If the graph doesn't have a normal backbone (e.g. if it contains empty fragments), then this method returns false.

      Returns:
      true iff the graph is hnc

    • isSimpleSolvedForm

      public boolean isSimpleSolvedForm()
      Checks whether the graph is a simple solved form, i.e. if it is normal, a forest, and every node has at most one outgoing dominance edge.
      Returns:
      true iff the graph is a simple solved form.

    • isSolvedForm

      public boolean isSolvedForm()
      Checks whether the graph is in solved form, i.e. if it is a forest.
      Returns:
      true iff the graph is in solved form.

    • isWellFormed

      public boolean isWellFormed()
      Check whether the weakly normal graph is "well-formed" in the sense of Bodirsky et al. 04. This means that every root of a dominance edge dominates a hole of its fragment.

      Returns:
      true iff the graph is well-formed.

    • isLabellingConsistent

      public boolean isLabellingConsistent(NodeLabels labels)
      Checks whether the classification of nodes as labelled or unlabelled is consistent with the presence of labels in the labels argument.
      Parameters:
      labels - a NodeLabels object that labels this graph
      Returns:
      true iff the labelling information is consistent

    • hasEmptyFragments

      public boolean hasEmptyFragments()
      Checks whether the graph has an empty fragment. Utool considers a fragment empty if it contains a node that has an outgoing dominance edge, but no adjacent tree edges. This means that single-node fragments are ok as long as they have no outgoing dominance edges.
      Returns:
      true iff the graph has an empty fragment

    • isHypernormallyReachable

      public boolean isHypernormallyReachable(String source, String target)
      Checks whether there is a hypernormal path between two nodes. This method performs a modified depth-first search through the dominance graph, and thus takes time O(m+n).
      Parameters:
      source - one node in this graph
      target - another node in this graph
      Returns:
      true iff there is a hypernormal path connecting the two

    • isHypernormallyReachable

      public boolean isHypernormallyReachable(String source, String target, Set<String> avoidThese)
      Checks whether there is a hypernormal path between source and target which doesn't visit any of the nodes in avoidThese. This method performs a modified depth-first search through the dominance graph, and thus takes time O(m+n).

      The method will modify the contents of avoidThese; if you don't want this, you should pass new HashSet(...) as third argument.

      Parameters:
      source - one node in this graph
      target - another node in this graph
      avoidThese - nodes that must not be on a connecting hn path
      Returns:
      true iff there is a hn path connecting source and target which doesn't visit avoidThese.

    • compactify

      public DomGraph compactify(CompactificationRecord record)
      Computes a compact version of this graph. If the graph is already compact, the graph itself is returned. Otherwise, the compactified graph will consist of the roots and holes of the original graph; roots and holes of the same fragment are connected by new tree edges, and holes and roots of different fragments are connected by dominance edges.

      The compact graph and the original graph have corresponding solved forms.

      The result is only guaranteed to be compact if the graph is compactifiable according to the method isCompactifiable.

      Returns:
      a compact version of this graph.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • clone

      public Object clone()
      Overrides:
      clone in class Object

    • isEqual

      public static boolean isEqual(DomGraph graph1, NodeLabels labels1, DomGraph graph2, NodeLabels labels2)