public class Graph extends NamedObject
Modifier and Type | Field and Description |
---|---|
protected java.util.Set<Edge> |
edges
The collection of edges in this graph.
|
protected java.util.List<Node> |
nodes
The nodes in this graph.
|
Constructor and Description |
---|
Graph()
Creates a new, empty graph.
|
Graph(Graph orig)
Creates a new graph which is a copy of another graph.
|
Graph(java.lang.String name)
Creates a new, empty graph with a given name.
|
Modifier and Type | Method and Description |
---|---|
Edge |
addEdge(Label label,
java.util.List<Node> nodes)
Adds a new edge to this graph.
|
Edge |
addEdge(Label label,
Node... nodes)
Adds a new edge to this graph.
|
Node |
addNode()
Adds a node to this graph.
|
Node[] |
addNodes(int n)
Adds a number of nodes to this graph.
|
long |
getAddCount()
Returns the number of times nodes or edges were added from this graph
since its creation.
|
long |
getDelCount()
Returns the number of times nodes or edges were deleted from this graph
since its creation.
|
java.util.Set<Edge> |
getEdges()
Returns the edges of this graph.
|
Morphism |
getInclusion(java.util.Collection<Edge> edges)
Returns an injective morphism whose image is a subgraph of this graph.
|
Morphism |
getInclusion(java.util.Collection<Node> nodes,
java.util.Collection<Edge> edges)
Returns an injective morphism whose image is a subgraph of this graph.
|
Morphism |
getInducedInclusion(java.util.Collection<Node> nodes)
Returns an injective morphism that has this graph as domain, whose
image is an induced subgraph of this graph.
|
int |
getIsoHash()
Returns the "isomorphism certificate" for this graph.
|
java.util.Set<Node> |
getIsolatedNodes()
Determines the set of isolated nodes of this graph.
|
long |
getModCount()
Returns the modification count of this Graph.
|
java.util.List<Node> |
getNodes()
Returns the set of nodes of this graph.
|
java.util.Set<Label> |
getSignature()
Returns the signature of this graph.
|
protected void |
increaseAddCount()
Increase the addition count of this graph.
|
protected void |
increaseDelCount()
Increases the deletion count of this graph.
|
boolean |
isBinary()
Determines if this graph is a binary graph.
|
boolean |
isDiscrete()
Determines if this graph is discrete.
|
boolean |
isEmpty()
Returns
true if this graph is an empty graph. |
boolean |
isIsomorphic(Graph other)
Determines if this graph is isomorphic to another graph.
|
void |
mergeNodes(java.util.Collection<Node> nodes)
Merge a number of nodes in the graph.
|
protected void |
mergeNodes(java.util.Collection<Node> mergedNodes,
Node target)
Merges a number of nodes in the graph.
|
void |
mergeNodes(Node... nodes)
Merge nodes in this graph.
|
void |
removeEdge(Edge edge)
Removes a single edge from this graph.
|
boolean |
removeNode(Node node)
Removes a node and all edges that are incident to it from this graph.
|
java.lang.String |
toString() |
java.lang.String |
toString(java.lang.String indent)
Returns a string representation of this graph with a user-defined
indentation string.
|
java.util.Set<Node> |
weaklyConnectedClosure(java.util.Collection<Node> nodes)
Calculates the weakly connected closure of a collection of nodes.
|
java.util.Set<Node> |
weaklyConnectedClosure(Node node)
Calculates the weakly connected closure of a node.
|
getName, hasName, setName
getAttribute, setAttribute
protected java.util.List<Node> nodes
protected java.util.Set<Edge> edges
public Graph()
public Graph(java.lang.String name)
public Graph(Graph orig)
orig
- the graph of which the new graph must be a copyprotected final void increaseAddCount()
protected final void increaseDelCount()
public boolean isEmpty()
true
if this graph is an empty graph.
A graph is empty if it does not contain any nodes or edges.true
if this graph is empty, false
otherwisepublic java.util.List<Node> getNodes()
public java.util.Set<Node> getIsolatedNodes()
The returned Set
is not part of the internal structure of this
graph, and can be modified by the caller.
public java.util.Set<Edge> getEdges()
public Node addNode()
Node
object which was added to this graphpublic Node[] addNodes(int n)
Note: the parameter n may be zero, in which case no nodes are added to the graph and an empty array is returned. This method never returns null.
n
- the number of nodes to add to this graphpublic boolean removeNode(Node node)
node
- the node which is to be removedtrue
if this graph was modified by this operationpublic Edge addEdge(Label label, Node... nodes)
label
- the label of the new graphnodes
- the nodes to which the new edge is adjacentpublic Edge addEdge(Label label, java.util.List<Node> nodes)
label
- the label of the new graphnodes
- the nodes to which the new edge is adjacentpublic void removeEdge(Edge edge)
edge
- the edge which is to be removed from the graphjava.lang.NullPointerException
- if edge
is null
java.lang.IllegalArgumentException
- when edge
does not belong to this graph.public void mergeNodes(java.util.Collection<Node> nodes)
Warning: Morphisms which have this graph as domain or codomain will still be morphisms after the completion of this method, but it is unspecified what mappings of the morphism remain.
nodes
- collection of nodes which must be mergedjava.lang.NullPointerException
- if nodes
is null
protected void mergeNodes(java.util.Collection<Node> mergedNodes, Node target)
Subclasses in which merging needs additional work, should override this method.
Typically, target
is an element of nodes
, although
that is not required for this method, and should neither be required
by methods that override it.
mergedNodes
- collection of nodes which must be mergedtarget
- the node into which all nodes will be mergedjava.lang.NullPointerException
- if nodes
or target
is null
java.lang.IllegalArgumentException
- when target
does not belong to this graphpublic void mergeNodes(Node... nodes)
Warning: Morphisms which have this graph as domain or codomain will still be morphisms after the completion of this method, but it is unspecified what mappings of the morphism remain.
nodes
- the nodes to be mergedpublic boolean isBinary()
true
if this graph is binary, false
otherwisepublic boolean isDiscrete()
true
if this graph is discrete, false
otherwisepublic long getModCount()
public long getDelCount()
public long getAddCount()
public int getIsoHash()
graph1
and graph2
have different
isomorphism certificates, then they cannot be isomorphismic.
(The converse does not hold: non-isomorphic graphs may have the same
isomorphism certificate.)public java.util.Set<Label> getSignature()
The returned set is a newly created, modifiable set. Modifications to the set are reflected in this graph.
public java.lang.String toString(java.lang.String indent)
indent
- indentation string of the string representationpublic java.lang.String toString()
toString
in class java.lang.Object
public Morphism getInclusion(java.util.Collection<Node> nodes, java.util.Collection<Edge> edges)
edges
, the nodes of nodes
and the nodes incident to edges
of edges
. The domain of the returned morphism is a new graph,
the codomain is this graph.nodes
- nodes of the image of the inclusionedges
- edges of the image of the inclusionnodes
and
edges
public Morphism getInclusion(java.util.Collection<Edge> edges)
edges
and the nodes which are incident to edges
of edges
. The domain of the returned morphism is a new graph,
the codomain is this graph.
A method call graph.getInclusion(edges)
is equivalent to
graph.getInclusion(null, edges)
.
edges
- edges of the image of the inclusionedges
and the nodes incident
to thempublic Morphism getInducedInclusion(java.util.Collection<Node> nodes)
nodes
and the edges which are only incident to nodes in nodes
.nodes
- the nodes of the image of the inclusionnodes
and all edges which are only incident to nodes in
nodes
public java.util.Set<Node> weaklyConnectedClosure(java.util.Collection<Node> nodes)
nodes
- the collection of nodes of which to calculate the weakly connected
closurenodes
public java.util.Set<Node> weaklyConnectedClosure(Node node)
nodes
- the node of which to calculate the weakly connected closurenode
public boolean isIsomorphic(Graph other)
Note: The Morphism
class defines more elaborate
methods to test isomorphism and obtain isomorphisms between graphs.
other
- the graph to check of, whether or not it is isomorphic to this
graphtrue
if this graph is isomorphic to other
,
false
otherwisejava.lang.NullPointerException
- if other
is null