graph

Class Graph

java.lang.Object

la.la.Value

graph.Graph

All Implemented Interfaces:

java.lang.Comparable<Value>

Direct Known Subclasses:

Directed, Graph.Derived, Undirected

public abstract class Graph
extends Value

Core Graph operations and useful constants etc.. The minimum requirements to instantiate an unlabelled Graph are type(), vSize(), and isEdge(int, int). If the Graph is Vertex-labelled, specify vLabel(int). If the Graph is Edge-labelled, specify eLabel(int, int).
Note, testing whether a Graph is Directed or Undirected should be done via type(), isDirected() or isUndirected(), not by looking whether its class is Directed or Undirected. This is because there are common operations such as induced(int[]), renumbered(int[]) and so on, and it may be more "convenient" to define them in (and return a) Graph rather than duplicate them in Directed and Undirected, or even in Directed.Dense, Directed.Sparse, Undirected.Dense, and Undirected.Sparse.
Also see README.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	Graph.Canonical Canonical is mostly just class Graph.Renumbered except that it (i) declares 'this' to already be in a canonical vertex-numbering, and thus (ii) Canonical.canonical() returns 'this'.
class	Graph.Contraction A Vertex-Contraction of 'this' Graph, collapsing (identifying) Vertices [vs[0], vs[1], ...] onto the single Vertex vs[0].
static interface	Graph.Dense See Graph.Sparse, Directed.Dense and Undirected.Dense.
class	Graph.Derived this.new Derived() is just like 'this' Graph, but a Function on Graphs may return a sub-class of Derived — extend it — with one or two methods overridden.
class	Graph.Edge An Edge ⟨v0, v1⟩ (Directed), or (v0, v1) (Undirected, v0≤v1), of 'this' Graph.
class	Graph.Induced A SubGraph of 'this' Graph induced by selecting Vertices [vs[0], vs[1], ...], and the Edges between them.
class	Graph.Renumbered A version of 'this' Graph with the Vertices renumbered according to vs[].
static interface	Graph.Sparse See Graph.Dense, Directed.Sparse and Undirected.Sparse.
static interface	Graph.SubGraph A SubGraph of a Graph is a Child and must also provide a mapping from its Vertices to those of the parent Graph.
class	Graph.SubGraphs A Series of lo- to hi-sized, (weakly-) connected, Induced subGraphs of 'this' Graph.
protected class	Graph.ToDirected Provided 'this' Graph is in fact Directed, be an instance of that class.
protected class	Graph.ToUndirected Provided 'this' Graph is in fact Undirected, be an instance of that class.
class	Graph.Vertex A Vertex of 'this' Graph.

Nested classes/interfaces inherited from class la.la.Value

Value.Atomic, Value.Bool, Value.Char, Value.Chars, Value.Cts, Value.Defer, Value.Discrete, Value.Enum, Value.Inc_Or, Value.Int, Value.Lambda, Value.List, Value.Maybe, Value.Option, Value.Real, Value.Scannable, Value.Structured, Value.Triv, Value.Tuple

Field Summary

Fields inherited from class la.la.Value

C, comparator, CR, E, eight, ffalse, five, fiveR, four, fourR, half, negCR, negOne, negOneR, negTenR, nilVal, nine, None, one, oneR, PI, PIby2, point01, point1, point5, point9, quarter, seven, six, ten, tenR, three, threeR, triv, ttrue, two, twoR, zero, zeroR

Constructor Summary

Constructors

Constructor and Description
Graph()

Method Summary

Modifier and Type	Method and Description
Matrix.Ints	A() Return the Adjacency Matrix (of {0,1}s) of 'this' Graph.
boolean	adjacent(int v0, int v1) v0 and v1 are adjacent if ⟨v0, v1⟩ is an Edge (isEdge(v0,v1)) or if ⟨v1, v0⟩ is.
int[][]	arrayA() Return the Adjacency Matrix as a square int[][].
Graph	byDegree() Return 'this' Graph Renumbered with Vertices in decreasing order of degree.
Graph	byDegree(boolean descending) Return 'this' Graph Renumbered with Vertices in decreasing or increasing order of degree as 'descending' is true or false.
Graph.Canonical	canonical() Return a canonical Renumbering of 'this' Graph, that is the one yielding the largest adjacency matrix when it is read as a binary number, in a "certain order".
protected Graph	canonical1(RefInt nAuto) Like canonical() but also counting the number of automorphisms.
protected boolean	canonical1R(int level, int diff, java.util.BitSet free, Graph.Renumbered permG, Graph.Renumbered bestG, RefInt nAuto) Does the hard work of finding a 'bestG' -- 'this' Graph Renumbered -- for canonical1.
protected Graph.Canonical	canonical2(RefInt nAuto) Does the hard work of finding a 'bestG' -- 'this' Graph Renumbered -- for canonical().
protected boolean	canonical2R(int[] vs, int[] cut, int part, int level, int diff, java.util.BitSet free, Graph.Renumbered permG, Graph.Renumbered bestG, RefInt nAuto) Does the hard work of finding a 'bestG' -- 'this' Graph Renumbered -- for canonical2(nAuto).
boolean	checkProperties() Check type()'s properties hold for 'this' Graph.
Graph.Contraction	contraction(int[] vs) Convenience function.
int	degree(int v) Also see Directed.degree(int) and Undirected.degree(int).
static Graph	dense(Type t, int[][] A) Calls Directed.dense(Type,int[][]) or Undirected.dense(Type,int[][]) according to t.
static Graph	dense(Type t, Matrix A) Calls Directed.dense(Type,la.maths.Matrix) or Undirected.dense(Type,la.maths.Matrix) according to 't'.
Series.Int	directPredecessors(int v) Only applicable to Directed Graphs.
Series.Int	directSuccessors(int v) Only applicable to Directed Graphs.
int[][]	edges() Return the edges, [..., (e[i][0], e[i]][1]), ...] of 'this' Graph as a E×2 array suitable for Directed.Sparse or Undirected.Sparse, say.
boolean	edgesCorrespond(Graph g) Assumes this.vSize() = g.vSize() and gets on with checking Edge correspondence, this.vi : g.vi.
Value	eLabel(int v0, int v1) UnsupportedOperation, the default assumption is no Edge labels.
boolean	eLabelled() Are the Edges labelled? Also see eLabel(v0,v1).
Value[][]	eLabels() Return all Edge labels, or null if unlabelled.
int	eSize() The number of Edges in 'this' Graph, |E|≥0.
double[]	eStats() Return Edge statistics, [#non_Edges, #Edges], as doubles.
Graph	flatten() Return a Graph of equivalent structure but with any trail of inducing, renumbering, etc., fixed and the trail lost.
int	hashCode() Return some kind of hash-code invariant under Vertex-renumbering.
int	inDegree(int v) Only applicable to Directed Graphs.
Graph	induced(int[] vs) Convenience function.
boolean	isDirected()
abstract boolean	isEdge(int v0, int v1) Is ⟨v0, v1⟩ an Edge in 'this' Graph? Also see adjacent(v0,v1).
boolean	isomorphic(Graph g) Is 'this' Graph isomorphic to 'g' (in terms of the existence of Edges)? It makes use of canonical() and edgesCorrespond(g).
boolean	isUndirected() ¬isDirected().
Series.Int	joinedTo(int v) An increasing Series of those Vertices 'w' adjacent to v, that is (v,w) is an Edge or (w,v) is (includes v, once, if there is a loop (v,v)).
int	localHash(int v) Return an int that is "likely" to differ for different Vertices v and v', and that can be computed "quickly".
static void	main(java.lang.String[] argv) Calls Test.main(java.lang.String[]).
int	maxEdges() The maximum possible number of Edges in a Graph with 'this' Graph's type and vSize.
int	nAutomorphisms() The number of automorphisms of 'this' Graph.
int	outDegree(int v) Only applicable to Directed Graphs.
Graph	randomised() Return a randomised Graph with the same (in- and out-) degree distribution(s) as 'this' Graph.
Graph	renumbered(int[] vs) Convenience function.
boolean	selfLoops() Are self-loops ⟨v, v⟩ allowed? Not, does this Graph actually have any self-loops, but rather could it have a self-loop?
boolean	structurallyIdentical(Graph g) Is 'this' Graph structurally identical to 'g', this.vi : g.vi, in terms of the existence of Edges? Checks vSize() of 'this' and 'g' match, then calls edgesCorrespond(g).
Graph.SubGraphs	subGraphs(int hi) subGraphs(1, hi).
Graph.SubGraphs	subGraphs(int lo, int hi) Return a Series of all Vertex-size lo to hi, (weakly-) connected, Vertex-induced subgraphs of 'this' Graph.
Directed	toDirected() Provided 'this' Graph is in fact Directed, return it as an instance of that class.
Undirected	toUndirected() Provided 'this' Graph is in fact Undirected, return it as an instance of that class.
abstract Type	type() Note, type(), adjacent(int, int), vLabelled(), vLabel(int), eLabelled(), and eLabel(int, int) must be consistent.
Value	vLabel(int v) UnsupportedOperation, the default assumption is no Vertex labels.
boolean	vLabelled() Are the Vertices labelled? Also see vLabel(v).
Value[]	vLabels() Return all Vertex labels, or null if unlabelled.
int	vPair2n(int v0, int v1) Given Vertices v0 and v1 that could form a legitimate Edge, return a unique integer that is ≥0 and <maxEdges().
abstract int	vSize() The number of Vertices, |V|≥1, V = {v0, ..., v(vSize()-1)}, of 'this' Graph.

Methods inherited from class la.la.Value

AoM, apply, bOp, compareTo, cons, cts, elt, errMsg, error, force, isTuple, just, n, nElts, nlAoM, pair, print, quad, real, RTE, toString, triple, tuple, UOE, uOp, x

Methods inherited from class java.lang.Object

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

Constructor Detail

Graph

public Graph()

Method Detail

type

public abstract Type type()

Note, type(), adjacent(int, int), vLabelled(), vLabel(int), eLabelled(), and eLabel(int, int) must be consistent.

Specified by:

type in class Value

checkProperties

public boolean checkProperties()

Check type()'s properties hold for 'this' Graph.

isDirected

public boolean isDirected()

isUndirected

public final boolean isUndirected()

¬isDirected().

selfLoops

public boolean selfLoops()

Are self-loops ⟨v, v⟩ allowed? Not, does this Graph actually have any self-loops, but rather could it have a self-loop?

vSize

public abstract int vSize()

The number of Vertices, |V|≥1, V = {v₀, ..., v_(vSize()-1)}, of 'this' Graph. The "null Graph" (|V|=0) is usually considered not to be a Graph. Also see eSize().

eSize

public int eSize()

The number of Edges in 'this' Graph, |E|≥0. By the way, the "empty Graph" (|E|=0), for a given |V|≥1, is a perfectly good Graph. Also see vSize().

eStats

public double[] eStats()

Return Edge statistics, [#non_Edges, #Edges], as doubles. That is [maxEdges()-eSize(), eSize()], taking Directed or not, and loops or not, into account. E.g., useful for an edge-density model (hence doubles).

maxEdges

public int maxEdges()

The maximum possible number of Edges in a Graph with 'this' Graph's type and vSize.

vPair2n

public int vPair2n(int v0,
                   int v1)

Given Vertices v0 and v1 that could form a legitimate Edge, return a unique integer that is ≥0 and <maxEdges(). This can be done in an arbitrary (but consistent) way. For an Undirected Graph, vPair2n(v, w) = vPair2n(w, v).

localHash

public int localHash(int v)

Return an int that is "likely" to differ for different Vertices v and v', and that can be computed "quickly". These aims are in conflict, of course. If H is a renumbered G, and if w in H corresponds to v in G, then H.localHash(w) = G.localHash(v). Also see hashCode().

degree

public int degree(int v)

Also see Directed.degree(int) and Undirected.degree(int). A sub-class may have a more efficient implementation, e.g., see Undirected.Sparse.degree(int).

inDegree

public int inDegree(int v)

Only applicable to Directed Graphs. The in-degree of Vertex 'v'. Calls directPredecessors(int). A sub-class may have a more efficient implementation, e.g., see Directed.Sparse.inDegree(int).

outDegree

public int outDegree(int v)

Only applicable to Directed Graphs. The out-degree of Vertex 'v'. Calls directSuccessors(int). A sub-class may have a more efficient implementation, e.g., see Directed.Sparse.outDegree(int).

isEdge

public abstract boolean isEdge(int v0,
                               int v1)

Is ⟨v0, v1⟩ an Edge in 'this' Graph? Also see adjacent(v0,v1).

adjacent

public boolean adjacent(int v0,
                        int v1)

v0 and v1 are adjacent if ⟨v0, v1⟩ is an Edge (isEdge(v0,v1)) or if ⟨v1, v0⟩ is. (Which somewhat clashes with the term Adjacency Matrix for a Directed Graph.)

vLabelled

public boolean vLabelled()

Are the Vertices labelled? Also see vLabel(v).

eLabelled

public boolean eLabelled()

Are the Edges labelled? Also see eLabel(v0,v1).

vLabel

public Value vLabel(int v)

UnsupportedOperation, the default assumption is no Vertex labels. Also see vLabelled() and eLabel(v0,v1).

vLabels

public Value[] vLabels()

Return all Vertex labels, or null if unlabelled.

eLabel

public Value eLabel(int v0,
                    int v1)

UnsupportedOperation, the default assumption is no Edge labels. Also see eLabelled() and vLabel(v).

eLabels

public Value[][] eLabels()

Return all Edge labels, or null if unlabelled.

A

public Matrix.Ints A()

Return the Adjacency Matrix (of {0,1}s) of 'this' Graph. The Matrix is symmetric for an Undirected Graph but not in general for a Directed Graph (which somewhat clashes with adjacent(u,v) usage). Also see arrayA().

arrayA

public int[][] arrayA()

Return the Adjacency Matrix as a square int[][]. Also see A() and Undirected.upperRightA().

edges

public int[][] edges()

Return the edges, [..., (e[i][0], e[i]][1]), ...] of 'this' Graph as a E×2 array suitable for Directed.Sparse or Undirected.Sparse, say. The edges will be in increasing lexicographical order. Also see A().

randomised

public Graph randomised()

Return a randomised Graph with the same (in- and out-) degree distribution(s) as 'this' Graph. The result is efficient for Sparse Graphs.

joinedTo

public Series.Int joinedTo(int v)

An increasing Series of those Vertices 'w' adjacent to v, that is (v,w) is an Edge or (w,v) is (includes v, once, if there is a loop (v,v)). Note, this default is inefficient for sparse Graphs but also see Directed.Sparse.joinedTo(int) and Undirected.Sparse.joinedTo(int).

directPredecessors

public Series.Int directPredecessors(int v)

Only applicable to Directed Graphs. An increasing Series of those Vertices 'p' such that ⟨p,v⟩ is an Edge (includes v if there is a loop ⟨v,v⟩). Note, this default is inefficient for sparse Graphs but see Directed.Sparse.directPredecessors(int)

directSuccessors

public Series.Int directSuccessors(int v)

Only applicable to Directed Graphs. An increasing Series of those Vertices 's' such that ⟨v,s⟩ is an Edge (includes v if there is a loop ⟨v,v⟩). Note, this default is inefficient for sparse Graphs but see Directed.Sparse.directSuccessors(int).

subGraphs

public Graph.SubGraphs subGraphs(int hi)

subGraphs(1, hi).

subGraphs

public Graph.SubGraphs subGraphs(int lo,
                                 int hi)

Return a Series of all Vertex-size lo to hi, (weakly-) connected, Vertex-induced subgraphs of 'this' Graph.

dense

public static Graph dense(Type t,
                          Matrix A)

Calls Directed.dense(Type,la.maths.Matrix) or Undirected.dense(Type,la.maths.Matrix) according to 't'. Return an unlabelled Graph of Type 't' and Adjacency Matrix 'A'. For a Directed Graph, A must be square. For an Undirected Graph, A must be square symmetric.

dense

public static Graph dense(Type t,
                          int[][] A)

Calls Directed.dense(Type,int[][]) or Undirected.dense(Type,int[][]) according to t. For a Directed Graph, A must be square. For an Undirected Graph, A must be upper-right triangular.

flatten

public Graph flatten()

Return a Graph of equivalent structure but with any trail of inducing, renumbering, etc., fixed and the trail lost. This implementation is inefficient for large Sparse Graphs.

toDirected

public Directed toDirected()

Provided 'this' Graph is in fact Directed, return it as an instance of that class. Also see toUndirected().

toUndirected

public Undirected toUndirected()

Provided 'this' Graph is in fact Undirected, return it as an instance of that class. Also see toDirected().

structurallyIdentical

public boolean structurallyIdentical(Graph g)

Is 'this' Graph structurally identical to 'g', this.v_i : g.v_i, in terms of the existence of Edges? Checks vSize() of 'this' and 'g' match, then calls edgesCorrespond(g). Can be used to test for isomorphism of g1 and g2 provided g1 and g2 are both canonical.

edgesCorrespond

public boolean edgesCorrespond(Graph g)

Assumes this.vSize() = g.vSize() and gets on with checking Edge correspondence, this.v_i : g.v_i. Note, it relies on directSuccessors(int) and joinedTo(int) generating Vertices in ascending order. Time complexity "ought" to be O(|E|). Also see isomorphic(g) and structurallyIdentical(g).

isomorphic

public boolean isomorphic(Graph g)

Is 'this' Graph isomorphic to 'g' (in terms of the existence of Edges)? It makes use of canonical() and edgesCorrespond(g).

canonical

public Graph.Canonical canonical()

Return a canonical Renumbering of 'this' Graph, that is the one yielding the largest adjacency matrix when it is read as a binary number, in a "certain order". The renumbering is not unique if the Graph has non-trivial automorphisms. The implementation is adequate for small Graphs. Currently calls canonical2(.). Also see isomorphic(g) and nAutomorphisms().

nAutomorphisms

public int nAutomorphisms()

The number of automorphisms of 'this' Graph. Currently calls canonical2(.). Also see canonical().

canonical2

protected Graph.Canonical canonical2(RefInt nAuto)

Does the hard work of finding a 'bestG' -- 'this' Graph Renumbered -- for canonical(). It partitions the set of Vertices on their (quick) localHas(v) property so as to reduce the number of permutations considered. It then calls canonical2R(...) to do the really hard work. And, 'nAuto' returns the number of automorphisms discovered.

canonical2R

protected boolean canonical2R(int[] vs,
                              int[] cut,
                              int part,
                              int level,
                              int diff,
                              java.util.BitSet free,
                              Graph.Renumbered permG,
                              Graph.Renumbered bestG,
                              RefInt nAuto)

Does the hard work of finding a 'bestG' -- 'this' Graph Renumbered -- for canonical2(nAuto). Recursively enumerates renumberings, permG, in lexicographically increasing order while trying to "short cut" when it can. Hence, it comes across the lexicographically least representative of each equivalence class first.

canonical1

protected Graph canonical1(RefInt nAuto)

Like canonical() but also counting the number of automorphisms. Does some initialisation and then calls canonical1R(int, int, java.util.BitSet, graph.Graph.Renumbered, graph.Graph.Renumbered, la.util.RefInt). ???Superceded by canonical2(nA)???

canonical1R

protected boolean canonical1R(int level,
                              int diff,
                              java.util.BitSet free,
                              Graph.Renumbered permG,
                              Graph.Renumbered bestG,
                              RefInt nAuto)

Does the hard work of finding a 'bestG' -- 'this' Graph Renumbered -- for canonical1. Note, one might initialise bestG.vs[] with a "good bet" suggested by some heuristic - speeding the search? ???Superceded by canonical2R(nA)???

byDegree

public Graph byDegree()

Return 'this' Graph Renumbered with Vertices in decreasing order of degree. Also see byDegree(boolean).

byDegree

public Graph byDegree(boolean descending)

Return 'this' Graph Renumbered with Vertices in decreasing or increasing order of degree as 'descending' is true or false. Also see byDegree().

hashCode

public int hashCode()

Return some kind of hash-code invariant under Vertex-renumbering. If G1 and G2 are isomorphic then G1.hashCode() == G2.hashCode(), but equal hashCodes do not imply G1 and G2 are isomorphic.

Overrides:

hashCode in class java.lang.Object

induced

public Graph induced(int[] vs)

Convenience function. Can't(?) have the Graph.Induced return type because of Directed.Sparse.induced(int[]) and Undirected.Sparse.induced(int[]).

contraction

public Graph.Contraction contraction(int[] vs)

Convenience function.

renumbered

public Graph renumbered(int[] vs)

Convenience function.

main

public static void main(java.lang.String[] argv)

Calls Test.main(java.lang.String[]).