Other equality predicates in scc

[dfeltey]

The scc function seems to allow a user specified equality predicate to be passed in as an optional second argument: https://github.com/stchang/graph/blob/master/graph/graph-fns-basic.rkt#L414

(define (scc G [=fn #f])
  (define eq (or =fn (λ (u v) (vertex=? G u v))))
  ...

This feature is neither documented, however, nor does it work for all equality predicates, in particular free-identifier=?:

#lang racket
(require graph)
(define g
  (unweighted-graph/directed
   (list (list #'x #'y)
         (list #'y #'z)
         (list #'z #'x)
         (list #'a #'x)
         (list #'y #'v)
         (list #'v #'w)
         (list #'w #'v))))
(scc g free-identifier=?)

Evaluates to:

'((.#<syntax:12:17 w>) (.#<syntax:12:21 v>) (.#<syntax:11:17 v>) (.#<syntax:11:21 w>) (.#<syntax:10:17 y>) (.#<syntax:10:21 v>) (.#<syntax:9:17 a>) (.#<syntax:9:21 x>) (.#<syntax:8:17 z>) (.#<syntax:8:21 x>) (.#<syntax:7:17 y>) (.#<syntax:7:21 z>) (.#<syntax:6:17 x>) (.#<syntax:6:21 y>))

Which is clearly not correct. Is there a way to make scc work with graphs whose vertices are identifiers?

[stchang]

Is there a way to make scc work with graphs whose vertices are identifiers?

Yes but not easily. You cant use any of the graph representions that come with the pkg bc they all use hash tables. But the algorithms are designed to be generic over graph representations so it should work if you create a new representation using freeid tables.