 PGX 20.1.1
Documentation

# Topological Ordering Algorithms

Assign an order for visiting the vertices in the graph.

## Topological Sort

##### Categorystructure evaluationAlgorithm IDpgx_builtin_s16a_topological_sortTime ComplexityO(V + E) with V = number of vertices, E = number of edgesSpace RequirementO(2 * V) with V = number of verticesJavadocAnalyst#topologicalSort(PgxGraph graph) Analyst#topologicalSort(PgxGraph graph, VertexProperty topoSort)

Topological sort tries to set an order over the vertices in a graph using the direction of the edges. A directed graph has a topological order if and only if it has no cycles, i.e. it is a directed acyclic graph. The algorithm visits the vertices in a DFS-like fashion to set up their order. The order of the vertices is returned as a vertex property, and the values will be set to -1 if there is a cycle in the graph.

### Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
top_order nodeProp vertex property holding the topological order of each vertex.
Return Value Type Comment
bool true if the graph has a topological order, false otherwise.

### Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class TopologicalSort {
public boolean topologicalSort(PgxGraph g, @Out VertexProperty<Integer> topologicalOrder) {
boolean sorted = true;
VertexProperty<Long> deg = VertexProperty.create();
VertexSequence s = VertexSequence.create();
Scalar<Long> e = Scalar.create(g.getNumEdges());

g.getVertices().filter(n -> n.getInDegree() == 0).forSequential(s::pushBack);

topologicalOrder.setAll(-1);
deg.setAll(PgxVertex::getInDegree);
int visited = 0;

while (s.size() > 0) {
PgxVertex n = s.front();
topologicalOrder.set(n, visited);
visited++;
n.getNeighbors().forSequential(nbr -> {
deg.set(nbr, deg.get(nbr) - 1);
e.set(e.get() - 1);
if (deg.get(nbr) == 0) {
s.pushBack(nbr);
}
});
s.popFront();
}

if (e.get() > 0) {
topologicalOrder.setAll(-1);
sorted = false;
}
return sorted;
}
}
```
```/*
*/

procedure topological_sort(graph G; nodeProp<int> top_order) : bool {

bool sorted = true;
nodeProp<int> deg;
nodeSeq s;
long e = G.numEdges();

for (n: G.nodes) (n.inDegree() == 0) {
s.push(n);
}

G.top_order = -1;
G.deg = _.inDegree();
int visited = 0;

while (s.size() > 0) {
node n = s.front();
n.top_order = visited;
visited++;
for (nbr: n.nbrs) {
nbr.deg = nbr.deg - 1;
e = e - 1;
if (nbr.deg == 0) {
s.push(nbr);
}
}
s.popFront();
}

if (e > 0) {
G.top_order = -1;
sorted = false;
}
return sorted;
}
```

## Topological Schedule

##### Categorystructure evaluationAlgorithm IDpgx_builtin_s16b_topological_scheduleTime ComplexityO(k * (V + E)) with V = number of vertices, E = number of edges, k = size of the source setSpace RequirementO(V) with V = number of verticesJavadocAnalyst#topologicalSchedule(PgxGraph graph, VertexSet source) Analyst#topologicalSchedule(PgxGraph graph, VertexSet source, VertexProperty topoSched)

Topological schedule sets an order over the vertices in a graph based on the proximity these have to the vertices from the given source. The algorithm does a BFS travesarl for each vertex from the source set in order to assign the correct scheduling order to all the reachable, even if the graph is undirected or has cycles. The vertices that are not reachable will be assigned a value of -1.

### Signature

Input Argument Type Comment
G graph
source nodeSet set of vertices to be used as the starting points for the scheduling order.
Output Argument Type Comment
top_sched nodeProp vertex property holding the scheduled order of each vertex.

### Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class TopologicalSchedule {
public void topologicalSchedule(PgxGraph g, VertexSet source, @Out VertexProperty<Integer> schedule) {
schedule.setAll(-1);

source.forEach(n -> inBFS(g, n).forward(v -> {
if (schedule.get(v) > currentLevel() || schedule.get(v) == -1) {
schedule.set(v, currentLevel());
}
}));
}
}
```
```/*
*/

procedure topological_schedule(graph G, nodeSet source; nodeProp<int> top_sched) {

G.top_sched = -1;

for (n: source.items) {
inBFS (v: G.nodes from n) {
if (v.top_sched > currentBFSLevel() || v.top_sched == -1) {
v.top_sched = currentBFSLevel();
}
}
}
}
```