AdjListHyperGraph

Usage

use AdjListHyperGraph;

A global-view, distributed, and parallel dual hypergraph.

The hypergraph maintains two distributed arrays, one for vertices and one for hyperedges. Both arrays contain objects that serve and act as adjacency, or incidence lists. For vertices, they contain the hyperedges they are contained in, and for hyperedges, they contain the vertices that are contained within itself. The graph is ‘global-view’ in that it allows the user to access the graph without regard for locality, while also being optimized locality. For example, all accesses to the hypergraph, whether it be in explicit on statements or ‘coforall’/forall distributed and parallel loops, all accesses to the graph are forwarded to a local instance.

Note

Documentation is currently a Work In Progress!

Usage

There are a few ways to create a AdjListHyperGraph

// Creates a shared-memory hypergraph
var graph = new AdjListHyperGraph(numVertices, numEdges);
// Creates a distributed-memory hypergraph
var graph = new AdjListHyperGraph(numVertices, numEdges, new Cyclic(startIdx=0));
var graph = new AdjListHyperGraph(numVertices, numEdges,
  new Block(boundingBox={0..#numVertices}, new Block(boundingBox={0..#numEdges})
);
// Creates a shared-memory hypergraph from Property Map
var graph = new AdjListHyperGraph(propertyMap);
// Creates a distributed hypergraph from Property Map
var graph = new AdjListHyperGraph(propertyMap, new Cyclic(startIdx=0));
config param AdjListHyperGraphDisableAggregation = false

Disable aggregation. This will cause all calls to addInclusionBuffered to go to addInclusion and all calls to flush to do a NOP.

config param AdjListHyperGraphDisablePrivatization = false

This will forward all calls to the original instance rather than the privatized instance. This will result in severe communication overhead.

record AdjListHyperGraph

AdjListHyperGraph privatization wrapper; all access to this will forward to the privatized instance, AdjListHyperGraphImpl.

proc init(numVertices: integral, numEdges: integral, param distributeVertices: bool = true, param distributeEdges: bool = true)

Create a new hypergraph with the desired number of vertices and edges. Uses the ‘DefaultDist’, which is normally the shared-memory ‘DefaultRectangularDist’.

proc init(numVertices: integral, numEdges: integral, mapping)

Create a new hypergraph with the desired number of vertices and edges, using the same distribution.

proc init(vPropMap: PropertyMap(?vPropType), numEdges)

Create a hypergraph with a vertex property map and desired number of edges, with a default distribution.

proc init(vPropMap: PropertyMap(?vPropType), numEdges, mapping)

Create a hypergraph with a vertex property map and desired number of edges, with the same distribution.

proc init(numVertices, ePropMap: PropertyMap(?ePropType))

Create a hypergraph with a edge property map and desired number of vertices, with a default distribution.

proc init(numVertices, ePropMap: PropertyMap(?ePropType), mapping)

Create a hypergraph with a edge property map and desired number of vertices, with the same distribution.

proc init(vPropMap: PropertyMap(?vPropType), ePropMap: PropertyMap(?ePropType))

Create a hypergraph with a edge and vertex property map with a default distribution.

proc init(vPropMap: PropertyMap(?vPropType), ePropMap: PropertyMap(?ePropType), mapping)

Create a hypergraph with a edge and vertex property map with the same distribution.

proc init(numVertices: integral, numEdges: integral, verticesMappings, edgesMappings, param distributeVertices: bool = true, param distributeEdges: bool = true)

Create a new hypergraph with the desired number of vertices and edges, and with their respective desired distributions.

Arguments:
  • numVertices – Number of vertices.
  • numEdges – Number of edges.
  • verticesMapping – Distribution of vertices.
  • edgesMapping – Distribution of edges.
proc init(vPropMap: PropertyMap(?vPropType), vertexMappings, numEdges, edgeMappings)

Create a new hypergraph where vertices are determined via the property map and with the desired number of edges, along with their respective desired distributions.

Arguments:
  • vPropMap – PropertyMap for vertices.
  • vertexMappings – Distribution for vertices.
  • numEdges – Number of edges.
  • edgeMappings – Distribution for edges.
proc init(numVertices, vertexMappings, ePropMap: PropertyMap(?ePropType), edgeMappings)

Create a new hypergraph with the desired number of vertices, where hyperedges are determined via the property map, along with their respective desired distributions. The number of vertices are determined from the number of properties for vertices.

Arguments:
  • numVertices – Number of vertices.
  • vertexMappings – Distribution for vertices.
  • ePropMap – PropertyMap for edges.
  • edgeMappings – Distribution for edges.
proc init(vPropMap: PropertyMap(?vPropType), vertexMappings, ePropMap: PropertyMap(?ePropType), edgeMappings)

Create a new hypergraph where hyperedges and vertices are determined via their property map, along with their respective desired distributions. The number of vertices are determined from the number of properties for vertices.

Arguments:
  • numVertices – Number of vertices.
  • vertexMappings – Distribution for vertices.
  • ePropMap – PropertyMap for edges.
  • edgeMappings – Distribution for edges.
proc init(other: AdjListHyperGraph)

Performs a shallow copy of ‘other’ so that both ‘this’ and ‘other’ both refer to the same privatized instance. :arg other: Other AdjListHyperGraph privatization wrapper.

proc destroy()

Destroys the privatized instance;

Warning

If multiple privatized wrappers refer to the same privatized instance, this will delete the privatized instance for all of them, and hence this operation is not thread-safe.

proc fromAdjacencyList(fileName: string, separator = ", ", map: ?t = new unmanaged DefaultDist()) throws

Creates a hypergraph from the passed file name with the delimitor indicated by ‘separator’. The hypergraph is given the provided distribution.

Arguments:
  • fileName – Name of file.
  • separator – Delimitor used in file.
  • map – Distribution.

..note

This reader is purely naive and sequential, and hence should _not_ be used to read in large files.
It is advised that instead that you use `BinReader`.
proc neq(a: ?t1NodeData?t2, b: t1NodeDatat2)
record ArrayWrapper
var dom = {0..-1}
var arr: [dom] int
proc ==(a: ArrayWrapper, b: ArrayWrapper)
proc !=(a: ArrayWrapper, b: ArrayWrapper)
proc chpl__defaultHash(r: ArrayWrapper): uint
record Wrapper
type nodeType
type idType
var id: idType
proc type null()
proc readWriteThis(f)
proc <(a: ?nodeTypeWrapper?idType, b: nodeTypeWrapperidType): bool
proc ==(a: ?nodeTypeWrapper?idType, b: nodeTypeWrapperidType): bool
proc !=(a: ?nodeTypeWrapper?idType, b: nodeTypeWrapperidType): bool
proc >(a: ?nodeTypeWrapper?idType, b: nodeTypeWrapperidType): bool
proc _cast(type t: ?nodeTypeWrapper?idType, id: integral)
proc _cast(type t: ?nodeTypeWrapper?idType, id: nodeTypeWrapperidType)
proc id(wrapper)
class AdjListHyperGraphImpl

Adjacency list hypergraph.

The storage is an array of NodeDatas. The edges array stores edges, and the vertices array stores vertices. The storage is similar to a bidirectional bipartite graph. Every edge has a set of vertices it contains, and every vertex has a set of edges it participates in. In terms of matrix storage, we store CSR and CSC and the same time. Storing strictly CSC or CSR would allow cutting the storage in half, but for now the assumption is that having the storage go both ways should allow optimizations of certain operations.

type vIndexType = index(_verticesDomain)
type eIndexType = index(_edgesDomain)
type vDescType = VertexWrappervIndexType
type eDescType = EdgeWrappereIndexType
proc verticesDomain

Obtain the domain of vertices; each index of the domain is a vertex id.

proc edgesDomain

Obtain the domain of hyperedges; each index of the domain is a hyperedge id.

proc numEdges

Obtain the number of edges in the graph.

proc numVertices

Obtain the number of vertices in the graph.

proc degree(vDesc: vDescType)

Obtain degree of the vertex.

proc degree(eDesc: eDescType)

Obtain degree of the hyperedge.

iter walk(eDesc: eDescType, s = 1, param isImmutable = false): eDescType

Iterator that yields all edges we can s-walk to. We can s-walk from an edge e to another edge e’ if the size of the intersection of both e and e’ is at least s.

Arguments:
  • eDesc – The edge to s-walk from.
  • isImmutable – Contract that the graph will not be modified during this operation.
iter walk(eDesc: eDescType, s = 1, param isImmutable = false, param tag: iterKind): eDescType
iter walk(vDesc: vDescType, s = 1, param isImmutable = false): vDescType

Iterator that yields all vertices we can s-walk to. We can s-walk from an vertex v to another vertex v’ if the size of the intersection of both v and v’ is at least s.

Arguments:
  • vDesc – The vertex to s-walk from.
  • isImmutable – Contract that graph will not change while iterating.
iter walk(vDesc: vDescType, s = 1, param tag: iterKind, param isImmutable = false): vDescType
iter getToplexes(param isImmutable = false)

Yield toplex hyperedges in the graph. A hyperedge e is a toplex if there exists no other hyperedge e’ such that e’ is a superset of e; that is, e is a hyperedge that is not a subset of any other edge.

Arguments:isImmutable – Contract that graph will not change while iterating.
iter getToplexes(param tag: iterKind, param isImmutable = false)
proc getProperty(vDesc: vDescType): _vPropType

Obtain the property associated with a vertex.

Arguments:vDesc – Vertex to obtain the property of.
proc getProperty(eDesc: eDescType): _ePropType

Obtain the property associated with a edge.

Arguments:eDesc – Edge to obtain the property of.
proc collapseVertices()

Simplify vertices in graph by collapsing duplicate vertices into equivalence classes. This updates the property map, if there is one, to update all references to vertices to point to the new candidate. This is an inplace operation. Must be called from Locale #0. Returns a histogram of duplicates.

proc collapseEdges()

Simplify edges in graph by collapsing duplicate edges into equivalence classes. This updates the property map, if there is one, to update all references to vertices to point to the new candidate. This is an inplace operation. Must be called from Locale #0. Returns a histogram of duplicates

proc collapseSubsets()

Collapses hyperedges into the equivalence class of the toplex they are apart of. This updates the property map, if there is one, to update all references to vertices to point to the new candidate. This is an inplace operation. Must be called from Locale #0. Returns a histogram representing the number of edges collapsed into toplexes.

proc collapse()

Equivalent to a call to collapseVertices and collapseEdges; returns the histogram of vertices and edges (vDuplicateHistogram, eDuplicateHistogram)

proc removeIsolatedComponents(): int

Removes components in the hypergraph where a hyperedge cannot ‘walk’ to another hyperedge; that is a hyperedge that is isolated from all other hyperedges. Returns the number of isolated components.

iter getToplexes(param tag: iterKind, param isImmutable = false): eDescType
proc isConnected(v1: vDescType, v2: vDescType, s, param isImmutable = false)

Check if we can s-walk from a source vertex to sink vertex.

Arguments:
  • v1 – Source vertex.
  • v2 – Sink vertex.
  • isImmutable – Contract that the graph will not be modified during this operation.
proc isConnected(e1: eDescType, e2: eDescType, s, param isImmutable = false)

Check if we can s-walk from a source edge to sink edge.

Arguments:
  • e1 – Source edge.
  • e2 – Sink edge.
  • isImmutable – Contract that the graph will not be modified during this operation.
proc getInclusions(): int

Obtains the sum of all degrees of all vertices.

proc getEdges(param tag: iterKind)

Yields all edges in the graph.

proc getEdges(param tag: iterKind, followThis)
iter getEdges(param tag: iterKind)
iter getEdges()
iter getVertices(param tag: iterKind)

Yields all vertices in the graph.

proc getVertices(param tag: iterKind)
proc getVertices(param tag: iterKind, followThis)
iter getVertices()
proc flushBuffers()

Flush all aggregation buffers.

proc startAggregation()

Activate automatic aggregation where all calls to addInclusion will be aggregated.

proc stopAggregation()

Ceases the implicit aggregation of all ‘addInclusion’ calls. Explicit calls to ‘addInclusionBuffered’ will still be aggregated.

proc addInclusionBuffered(vDesc: vDescType, eDesc: eDescType)

Explicitly aggregate the vertex and element.

Arguments:
  • vDesc – Vertex.
  • eDesc – Edge.
proc addInclusionBuffered(v: vIndexType, e: eIndexType)
proc addInclusionBuffered(vDesc: vDescType, e: eIndexType)
proc addInclusionBuffered(v: vIndexType, eDesc: eDescType)
proc addInclusion(vDesc: vDescType, eDesc: eDescType)

Adds ‘e’ as a neighbor of ‘v’ and ‘v’ as a neighbor of ‘e’. If aggregation is enabled via ‘startAggregation’, this will forward to the aggregated version, ‘addInclusionBuffered’.

Arguments:
  • vDesc – Vertex.
  • eDesc – Edge.
proc addInclusion(v: vIndexType, e: eIndexType)
proc addInclusion(vDesc: vDescType, e: eIndexType)
proc addInclusion(v: vIndexType, eDesc: eDescType)
proc hasInclusion(v: vIndexType, e: eIndexType, param isImmutable = false)

Check if the vertex ‘v’ is incident in edge ‘e’.

Arguments:
  • v – Vertex.
  • e – Edge.
proc hasInclusion(vDesc: vDescType, e: eIndexType, param isImmutable = false)
proc hasInclusion(v: vIndexType, eDesc: eDescType, param isImmutable = false)
proc hasInclusion(vDesc: vDescType, eDesc: eDescType, param isImmutable = false)
proc removeDuplicates()

Remove duplicates from incidence list both vertices and edges. Useful to invoke after graph generation.

proc toEdge(id: integral)

Obtains the edge descriptor for the integral edge id. If ‘boundsChecking’ is enabled, we verify that the id is a valid index (I.E compiling without –fast).

Arguments:id – Integer identifier for an edge.
proc toEdge(desc: eDescType)
proc toVertex(id: integral)

Obtains the vertex descriptor for the integral vertex id. If ‘boundsChecking’ is enabled, we verify that the id is a valid index (I.E compiling without –fast).

Arguments:id – Integer identifier for a vertex.
proc toVertex(desc: vDescType)
proc getVertexDegrees()

Returns vertex degree sequence as array.

proc getEdgeDegrees()

Returns hyperedge cardinality sequence as array.

proc getLocale(v: vDescType): locale

Obtain the locale that the given vertex is allocated on

Arguments:v – Vertex.
proc getLocale(e: eDescType): locale

Obtain the locale that the given edge is allocated on

Arguments:e – Edge.
proc intersectionSize(e1: eDescType, e2: eDescType, param isImmutable = false)

Obtain the size of the intersection of both hyperedges.

Arguments:
  • e1 – Hyperedge.
  • e2 – Hyperedge.
  • isImmutable – Contract that the graph will not be modified during this operation.
proc intersectionSize(v1: vDescType, v2: vDescType, param isImmutable = false)

Obtain the size of the intersection of both vertices.

Arguments:
  • v1 – Vertex.
  • v2 – Vertex.
  • isImmutable – Contract that the graph will not be modified during this operation.
iter intersection(e1: eDescType, e2: eDescType, param isImmutable = false)

Yield edges that are in the intersection of both vertices.

Arguments:
  • e1 – Hyperedge.
  • e2 – Hyperedge.
  • isImmutable – Contract that the graph will not be modified during this operation.
iter intersection(e1: eDescType, e2: eDescType, param isImmutable = false, param tag: iterKind)
iter intersection(v1: vDescType, v2: vDescType, param isImmutable = false)
iter intersection(v1: vDescType, v2: vDescType, param isImmutable = false, param tag: iterKind)
iter incidence(e: eDescType, param isImmutable = false)

Obtains the vertices incident in this hyperedge.

Arguments:
  • e – Hyperedge descriptor.
  • isImmutable – Contract that the graph will not be modified during this operation.
iter incidence(e: eDescType, param isImmutable = false, param tag: iterKind) ref
iter incidence(v: vDescType, param isImmutable = false) ref

Obtains the hyperedges this vertex is incident in.

Arguments:
  • v – Vertex descriptor.
  • isImmutable – Contract that the graph will not be modified during this operation.
iter incidence(v: vDescType, param isImmutable = false, param tag: iterKind) ref
iter these(param isImmutable = false): (vDescType, eDescType)

Iterate through pairs vertices along with the edges they are incident in.

iter these(param isImmutable = false, param tag: iterKind): (vDescType, eDescType)
proc this(v: vDescType)

Return the incidence list associated with a vertex.

Arguments:v – Vertex descriptor.
proc this(e: eDescType)

Return the incidence list associated with a hyperedge.

Arguments:e – Hyperedge descriptor.
proc +=(graph: AdjListHyperGraph, other)

Invokes ‘addInclusion’

proc +=(graph: unmanaged AdjListHyperGraphImpl, chpl__tuple_arg_temp: (graph.vDescType, graph.eDescType))
proc +=(graph: unmanaged AdjListHyperGraphImpl, chpl__tuple_arg_temp: (graph.eDescType, graph.vDescType))