Graph¶

1

import "std/data/graph";

Vertex<T> struct¶

Implements: IHashable

A vertex (or node) of a graph, wrapping a single value of arbitrary type

Constructors¶

ctor¶

1

public p Vertex.ctor(const T& value)

Construct a vertex wrapping the given value

Parameters

Methods¶

getValue¶

1

public f<T&> Vertex.getValue()

Retrieve the value stored in the vertex

Returns: T& — Reference to the stored value

hash¶

1

public f<Hash> Vertex.hash()

Compute the hash of the vertex, derived from the hash of its wrapped value

Returns: Hash — Hash of the vertex

Graph<T> struct¶

Implements: IIterable<T>

A graph in Spice is a data structure consisting of a set of vertices and a set of edges connecting them. It is stored as an adjacency list, mapping each vertex to the list of its neighbors. The graph can be either directed or undirected, which is decided at construction time.

Time complexity (V = number of vertices, E = number of edges):
Add vertex: O(1) (average case)
Add edge: O(1) (average case)
Traversal (DFS/BFS): O(V + E)

The average case for adding vertices and edges assumes a good hash distribution in the underlying unordered map. In the worst case, hash collisions degrade these operations to O(V).

Constructors¶

ctor¶

1

public p Graph.ctor(bool directed = true)

Construct an empty graph

Parameters

Methods¶

addVertex¶

1

public f<Vertex<T>&> Graph.addVertex(const T& value)

Add a new vertex with the given value to the graph

Parameters

Returns: Vertex<T>& — Reference to the newly added vertex

addEdge¶

1

public p Graph.addEdge(const Vertex<T>& from, const Vertex<T>& to)

Add an edge between two vertices that are already part of the graph. For undirected graphs the caller is responsible for adding the reverse edge as well.

Parameters

hasCycles¶

1

public const f<bool> Graph.hasCycles()

Check whether the graph contains at least one cycle

Returns: bool — true if the graph contains a cycle, false otherwise

isDirected¶

1

public const f<bool> Graph.isDirected()

Check whether the graph is directed

Returns: bool — true if the graph is directed, false if it is undirected

isDAG¶

1

public const f<bool> Graph.isDAG()

Check whether the graph is a directed acyclic graph (DAG)

Returns: bool — true if the graph is directed and contains no cycles, false otherwise

toGraphviz¶

1

public const p Graph.toGraphviz(StringStream& ss)

Serialize the graph to the Graphviz DOT format and write it into the given string stream

Parameters

dfs¶

1

public f<GraphDFSIterator<T>> Graph.dfs(Vertex<T>* startVertex = nil<Vertex<T>*>)

Retrieve a depth-first iterator for the graph

Parameters

Returns: GraphDFSIterator<T>

bfs¶

1

public f<GraphBFSIterator<T>> Graph.bfs(Vertex<T>* startVertex = nil<Vertex<T>*>)

Retrieve a breadth-first iterator for the graph

Parameters

Returns: GraphBFSIterator<T>

getIterator¶

1

public f<GraphDFSIterator<T>> Graph.getIterator()

Retrieve a depth-first iterator for the graph

Returns: GraphDFSIterator<T>

GraphDFSIterator<T> struct¶

Implements: IIterator<Vertex<T>>

Iterator to iterate over a graph data structure in a depth-first manner.

Constructors¶

ctor¶

1

public p GraphDFSIterator.ctor<T>(Graph<T>& graph, Vertex<T>* startVertex = nil<Vertex<T>*>)

Construct a depth-first iterator over the given graph

Parameters

Methods¶

get¶

1

public inline f<Vertex<T>&> GraphDFSIterator.get()

Returns the current vertex of the graph

Returns: Vertex<T>& — Reference to the current vertex

getIdx¶

1

public inline f<Pair<unsigned long, Vertex<T>&>> GraphDFSIterator.getIdx()

Returns the current index and the current vertex of the graph

Returns: Pair<unsigned long, Vertex<T>&> — Pair of current index and reference to current vertex

isValid¶

1

public inline f<bool> GraphDFSIterator.isValid()

Check if the iterator is valid

Returns: bool — true or false

next¶

1

public inline p GraphDFSIterator.next()

Returns the current vertex of the graph iterator and moves the cursor to the next vertex

GraphBFSIterator<T> struct¶

Implements: IIterator<Vertex<T>>

Iterator to iterate over a graph data structure in a breadth-first manner.

Constructors¶

ctor¶

1

public p GraphBFSIterator.ctor<T>(Graph<T>& graph, Vertex<T>* startVertex = nil<Vertex<T>*>)

Construct a breadth-first iterator over the given graph

Parameters

Methods¶

get¶

1

public inline f<Vertex<T>&> GraphBFSIterator.get()

Returns the current vertex of the graph

Returns: Vertex<T>& — Reference to the current vertex

getIdx¶

1

public inline f<Pair<unsigned long, Vertex<T>&>> GraphBFSIterator.getIdx()

Returns the current index and the current vertex of the graph

Returns: Pair<unsigned long, Vertex<T>&> — Pair of current index and reference to current vertex

isValid¶

1

public inline f<bool> GraphBFSIterator.isValid()

Check if the iterator is valid

Returns: bool — true or false

next¶

1

public inline p GraphBFSIterator.next()

Returns the current vertex of the graph iterator and moves the cursor to the next vertex

Operators¶

operator==¶

1

public f<bool> operator==<T>(const Vertex<T>& v1, const Vertex<T>& v2)

Check if two vertices are equal, i.e. they wrap equal values

Parameters

Returns: bool — Equal or not equal