de.up.ling.irtg.algebra.graph

Class SGraph

java.lang.Object

de.up.ling.irtg.algebra.graph.SGraph

public class SGraph
extends Object

An s-graph, in the sense of Courcelle & Engelfriet 2012. S-graphs are directed, node-labeled and edge-labeled graphs in which nodes can be designated as sources. For instance, an s-graph might have a node that is designated as the "root"-source and another that is designated as the "subject"-source. There can be at most one source node for each source name, but one node can be exported under multiple source names (i.e. the same node may be the "root"-source and the "subject"-source at the same time).

Author:

koller

Constructor Summary

Constructors

Constructor and Description
SGraph() Creates an empty s-graph.

Method Summary

Modifier and Type	Method and Description
GraphNode	addAnonymousNode(String label) Adds an "anonymous" node with the given label to the s-graph.
GraphEdge	addEdge(GraphNode src, GraphNode tgt, String label) Adds an edge with the given label between the two nodes to the s-graph.
GraphNode	addNode(String name, String label) Adds a node with the given name and label to the s-graph.
void	addSource(String sourceName, String nodename) Designates the node with the given name as the source for the given source name.
boolean	containsAsSubgraph(org.jgrapht.DirectedGraph<GraphNode,GraphEdge> subgraph, Map<String,String> nodeRenaming) Checks whether the s-graph contains the given graph as a sub-graph.
boolean	containsNode(String name) Checks if a node with the given name exists in this s-graph.
boolean	equals(Object obj) Checks whether this graph is equal to another.
void	foreachMatchingSubgraph(SGraph subgraph, Consumer<SGraph> fn) Applies the given function "fn" to all sub-s-graphs of this s-graph that match the given "subgraph".
SGraph	forgetSourcesExcept(Set<String> retainedSources) Forgets all sources except for the specified set.
Collection<String>	getAllNodeNames() Returns the collection of all node names in this s-graph.
Iterable<String>	getAllNonSourceNodenames() Returns the set of all node names of this s-graph that are not sources.
Iterable<String>	getAllSourceNodenames() Returns the set of all node names of this s-graph that are an "a"-source for any source "a".
Set<String>	getAllSources() Returns the set of all source names in this s-graph (e.g.
org.jgrapht.DirectedGraph<GraphNode,GraphEdge>	getGraph() Returns the graph underlying this s-graph.
List<SGraph>	getMatchingSubgraphs(SGraph subgraph) Returns a list of matching subgraphs.
GraphNode	getNode(String name) Returns the node in this s-graph with the given name.
String	getNodeForSource(String sourceName) Returns the node for the given source name.
String	getSourceLabel(String nodename) Returns a string representation of the source status of the given node.
Collection<String>	getSourcesAtNode(String nodename) Returns a collection containing all the source names for which the given node is a source.
static String	graphToString(org.jgrapht.DirectedGraph<GraphNode,GraphEdge> graph) Returns a string representation of the graph.
boolean	hasCommonSource(SGraph other) Checks whether two s-graphs have a source name in common.
int	hashCode() Computes a hash code for the s-graph.
boolean	hasLabelledNode() Returns true iff at least one node in the graph has a label.
boolean	isIdentical(SGraph other) Checks whether this graph is identical to the other graph.
boolean	isIdenticalExceptSources(SGraph other) Checks whether this graph is identical to the other graph, ignoring source assignments.
boolean	isIsomorphic(SGraph other) Checks whether two s-graphs are isomorphic.
boolean	isIsomorphicAlsoEdges(SGraph other) Checks whether two s-graphs are isomorphic.
boolean	isSourceNode(String nodename) Checks if the node with the given name is a source.
SGraph	merge(SGraph other) Merges this s-graph with another s-graph.
int	nodeCount()
boolean	nodenamesForSourcesAgree(SGraph other) Checks whether two s-graphs have consistent node names for the sources.
boolean	overlapsOnlyInSources(SGraph other) Checks whether two s-graphs have any nodes in common that are not sources.
SGraph	renameSource(String oldName, String newName) Renames a source in this s-graph to another source name.
void	setEqualsMeansIsomorphy(boolean equalsMeansIsomorphy) Controls whether equality on this s-graph should be checked using identity or isomorphy.
SGraph	swapSources(String sourceName1, String sourceName2)
String	toIsiAmrString() Returns a string representation of this s-graph in the format of the ISI AMR-Bank.
String	toString() Returns a string representation of this s-graph.
SGraph	withFreshNodenames() Returns a copy in this s-graph in which all node names have been assigned fresh names.

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

SGraph

public SGraph()

Creates an empty s-graph.

Method Detail

addNode

public GraphNode addNode(String name,
                         String label)

Adds a node with the given name and label to the s-graph. The label may be null to indicate that the node does not have a label (yet). If a node with the given name and a null label already exists in the graph, this method sets the label of that node.

Parameters:

name -

label -

Returns:

the newly created node

addAnonymousNode

public GraphNode addAnonymousNode(String label)

Adds an "anonymous" node with the given label to the s-graph. Anonymous nodes are assigned ad-hoc node names that start with "_u". It is therefore a good idea to avoid the use of explicitly named nodes whose names start with _u.

Parameters:

label -

Returns:

the newly created node

addEdge

public GraphEdge addEdge(GraphNode src,
                         GraphNode tgt,
                         String label)

Adds an edge with the given label between the two nodes to the s-graph.

Parameters:

src -

tgt -

label -

Returns:

the newly created edge

addSource

public void addSource(String sourceName,
                      String nodename)

Designates the node with the given name as the source for the given source name.

Parameters:

sourceName -

nodename -

getNodeForSource

public String getNodeForSource(String sourceName)

Returns the node for the given source name. If there is no source with this name, returns null.

Parameters:

sourceName -

Returns:

getNode

public GraphNode getNode(String name)

Returns the node in this s-graph with the given name. If there is no node with this name, returns null.

Parameters:

name -

Returns:

getAllNodeNames

public Collection<String> getAllNodeNames()

Returns the collection of all node names in this s-graph.

Returns:

containsNode

public boolean containsNode(String name)

Checks if a node with the given name exists in this s-graph.

Parameters:

name -

Returns:

hasLabelledNode

public boolean hasLabelledNode()

Returns true iff at least one node in the graph has a label.

Returns:

merge

public SGraph merge(SGraph other)

Merges this s-graph with another s-graph. The merge operation combines two s-graphs into one. The resulting s-graph contains all nodes that either of the two original graphs contained, with the same node labels and edges as in these. For each source "a" that exists in both original s-graphs, the a-source-nodes are fused into a single node in the new s-graph, which has all the adjacent edges of the two original a-sources. This source becomes the a-source of the new s-graph. See Courcelle & Engelfriet for details.

This method returns a new s-graph object; the two original s-graphs are not modified. It renames the nodes of the "other" s-graph to fresh node names to avoid accidental fusing of nodes.

Parameters:

other -

Returns:

a new s-graph representing the merge of the two original s-graphs

renameSource

public SGraph renameSource(String oldName,
                           String newName)

Renames a source in this s-graph to another source name. If the original s-graph had an "a"-source called "u", then in the s-graph that results from renaming "a" to "b", "u" is no longer an "a"-source, but a "b"-source. The resulting s-graph is the same as the original in all other ways.

This method returns a new s-graph object; the original s-graph is not modified.

Parameters:

oldName -

newName -

Returns:

swapSources

public SGraph swapSources(String sourceName1,
                          String sourceName2)

forgetSourcesExcept

public SGraph forgetSourcesExcept(Set<String> retainedSources)

Forgets all sources except for the specified set. All "a"-sources for "a" not in the retainedSources will lose their status as "a"-sources. The method returns a new s-graph object; the original s-graph is not modified.

Parameters:

retainedSources -

Returns:

getAllSources

public Set<String> getAllSources()

Returns the set of all source names in this s-graph (e.g. {"root", "subject"}).

Returns:

getAllSourceNodenames

public Iterable<String> getAllSourceNodenames()

Returns the set of all node names of this s-graph that are an "a"-source for any source "a". (E.g. {u17, u28}.)

Returns:

getAllNonSourceNodenames

public Iterable<String> getAllNonSourceNodenames()

Returns the set of all node names of this s-graph that are not sources. This set is the complement of getAllNonSourceNodenames().

Returns:

withFreshNodenames

public SGraph withFreshNodenames()

Returns a copy in this s-graph in which all node names have been assigned fresh names.

Returns:

getGraph

public org.jgrapht.DirectedGraph<GraphNode,GraphEdge> getGraph()

Returns the graph underlying this s-graph. This graph contains all the nodes, edges, node labels, and edge labels of the s-graph, but none of the source information. It can be processed further using the JGraphT graph library.

Returns:

See Also:

library at http://jgrapht.org/

isSourceNode

public boolean isSourceNode(String nodename)

Checks if the node with the given name is a source.

Parameters:

nodename -

Returns:

getSourceLabel

public String getSourceLabel(String nodename)

Returns a string representation of the source status of the given node. This representation contains all the source names for which this node is a source, separated by commas.

Parameters:

nodename -

Returns:

getSourcesAtNode

public Collection<String> getSourcesAtNode(String nodename)

Returns a collection containing all the source names for which the given node is a source. The method returns null if the node is not a source.

Parameters:

nodename -

Returns:

toIsiAmrString

public String toIsiAmrString()

Returns a string representation of this s-graph in the format of the ISI AMR-Bank.

Returns:

graphToString

public static String graphToString(org.jgrapht.DirectedGraph<GraphNode,GraphEdge> graph)

Returns a string representation of the graph.

Parameters:

graph -

nra -

Returns:

toString

public String toString()

Returns a string representation of this s-graph.

Overrides:

toString in class Object

Returns:

setEqualsMeansIsomorphy

public void setEqualsMeansIsomorphy(boolean equalsMeansIsomorphy)

Controls whether equality on this s-graph should be checked using identity or isomorphy.

Parameters:

equalsMeansIsomorphy -

See Also:

equals(java.lang.Object)

equals

public boolean equals(Object obj)

Checks whether this graph is equal to another. You can control what "equal" means by using setEqualsMeansIsomorphy(boolean). If "equals means isomorphy" is set to false, then equality is checked by verifying that the two s-graphs have the same set of node names, each node has the same label, any two nodes are connected by edges with the same edge label, and all the sources are the same.

If "equals means isomorphy" is set to true (the default), the equality check first looks for an isomorphic mapping between the node names of the two s-graphs, and then checks for node labels, edges, and sources relative to this mapping. In other words, this mode ignores node names.

Overrides:

equals in class Object

Parameters:

obj -

Returns:

isIdentical

public boolean isIdentical(SGraph other)

Checks whether this graph is identical to the other graph. This corresponds to evaluating equals(java.lang.Object) in the mode where "equals means isomorphy" is set to false.

Parameters:

other -

Returns:

isIdenticalExceptSources

public boolean isIdenticalExceptSources(SGraph other)

Checks whether this graph is identical to the other graph, ignoring source assignments.

Parameters:

other -

Returns:

overlapsOnlyInSources

public boolean overlapsOnlyInSources(SGraph other)

Checks whether two s-graphs have any nodes in common that are not sources. The method returns true if there is such an overlap, and false otherwise.

Parameters:

other -

Returns:

nodenamesForSourcesAgree

public boolean nodenamesForSourcesAgree(SGraph other)

Checks whether two s-graphs have consistent node names for the sources. The method checks for each source name "a" that exists in both s-graphs whether the "a"-sources in each s-graph have the same node name. It returns true if this is true for all shared source names, and false otherwise.

Parameters:

other -

Returns:

containsAsSubgraph

public boolean containsAsSubgraph(org.jgrapht.DirectedGraph<GraphNode,GraphEdge> subgraph,
                                  Map<String,String> nodeRenaming)

Checks whether the s-graph contains the given graph as a sub-graph. The map "nodeRenaming" is a mapping of node names in the subgraph to node names in the s-graph.

Parameters:

subgraph -

nodeRenaming -

Returns:

getMatchingSubgraphs

public List<SGraph> getMatchingSubgraphs(SGraph subgraph)

Returns a list of matching subgraphs.

Parameters:

subgraph -

Returns:

See Also:

foreachMatchingSubgraph(de.up.ling.irtg.algebra.graph.SGraph, java.util.function.Consumer)

foreachMatchingSubgraph

public void foreachMatchingSubgraph(SGraph subgraph,
                                    Consumer<SGraph> fn)

Applies the given function "fn" to all sub-s-graphs of this s-graph that match the given "subgraph". The sub-s-graphs to which "fn" is applied will all be isomorphic to the "subgraph", but with its nodes renamed to node names of this s-graph.

Parameters:

subgraph -

fn -

isIsomorphic

public boolean isIsomorphic(SGraph other)

Checks whether two s-graphs are isomorphic. This corresponds to evaluating equals(java.lang.Object) in the mode where "equals means isomorphy" is true. Does not check edge labels.

Parameters:

other -

Returns:

isIsomorphicAlsoEdges

public boolean isIsomorphicAlsoEdges(SGraph other)

Checks whether two s-graphs are isomorphic. This corresponds to evaluating equals(java.lang.Object) in the mode where "equals means isomorphy" is true. Also compares whether edges are labelled equally.

Parameters:

other -

Returns:

hashCode

public int hashCode()

Computes a hash code for the s-graph. This implementation of hashCode adds up generic label, edge, and source information for the nodes in this s-graph, and is therefore consistent with both variants of equals(java.lang.Object) in this class. However, it is a very weak implementation in that many s-graphs that are actually not equals will have the same hash code. One should therefore avoid actually using HashMaps or HashSets of s-graphs, because performance will be poor.

Overrides:

hashCode in class Object

Returns:

hasCommonSource

public boolean hasCommonSource(SGraph other)

Checks whether two s-graphs have a source name in common.

Parameters:

other -

Returns:

nodeCount

public int nodeCount()