PGX 20.1.1
Documentation

Topological Ordering Algorithms

Assign an order for visiting the vertices in the graph.


Topological Sort

Category structure evaluation

Algorithm ID pgx_builtin_s16a_topological_sort

Time Complexity O(V + E) with V = number of vertices, E = number of edges

Space Requirement O(2 * V) with V = number of vertices

Javadoc


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

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
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;
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

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

Category structure evaluation

Algorithm ID pgx_builtin_s16b_topological_schedule

Time Complexity O(k * (V + E)) with V = number of vertices, E = number of edges, k = size of the source set

Space Requirement O(V) with V = number of vertices

Javadoc


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

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
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());
      }
    }));
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

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();
      }
    }
  }
}