stchang / graph Goto Github PK

edge-weight method should accept a default value to return when the edge does not exist. Currently, it always returns inf for non-existent edges but some algorithms might not want this.

I'm aware that this is a known issue, as they are marked allowed to fail on Travis, but perhaps they should be removed or fixed? I'm making an attempt.

The documentation for dag-shortest-paths should say whether or not it works on dags with negative edge weights.

And in the case that it doesn't handle them, should a version be added that does? Or would restricting to dags not give any advantage over bellman-ford for this?

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?

For people who are using racket-minimal it would be really nice if graph could depend on graph-lib and graph-doc, where only graph-lib would be necessary for compiling depending code, and only graph-doc would depend on the heavy and circular racket-doc.

When there's no explicit accumulator in the parameter list, the accum should be propagated without change.

In the description of do-bfs, the parameter list is really long, and it looks like it would love a linebreak. Also, it seems like there's some text behind maybe-return that's being hidden.

Hi, I would like to be able to tell if a graph is directed or undirected. Would it be possible to add this to the interface and implement it by:

• storing a boolean in the graph struct, initialized based on which constructor is used
• having add-directed-edge! set it to true

I will add it but wanted to make sure that this implementation would be acceptable.

From docs:
procedure
(add-edge! g u v [weight]) → void?
g : graph? u : any/c v : any/c weight : number? = 1
Imperatively adds an undirected edge and optional weight to a graph.
procedure
(add-directed-edge! g u v [weight]) → void?
g : graph? u : any/c v : any/c weight : number? = 0

Can only split repo into separate -lib, -doc, -test packages with Racket 6 or higher.

See:

• #37
• #35

To be consistent with the rest of Racket's in-* forms, in-vertices should return a sequence instead of a list.

For example, when generating .dot file, it will detect whether the vertex or edge has color attribute, and then draw graph based on the information.

By the way, will you consider adding define-graph-property? I think it can not only be used to better configure how to generate .dot files (For example, whether the edge is undirected, default color, etc.), but also provide some help to deal with different graphs.

The root-v argument isn't included in the mst-prim docs.

https://github.com/stchang/graph/blob/master/graph/graph.scrbl#L717
https://github.com/stchang/graph/blob/master/graph/graph-fns-minspantree.rkt#L68

See eb7f958

What do you think of adding a way to let the user set any set of attributes to their dot format output other than color. In my case I'd like box for the node shape.

For example: (source wikipedia)

graph graphname {
     // This attribute applies to the graph itself
     size="1,1";
     // The label attribute can be used to change the label of a node
     a [label="Foo"];
     // Here, the node shape is changed.
     b [shape=box];
     // These edges both have different line properties
     a -- b -- c [color=blue];
     b -- d [style=dotted];
     // [style=invis] hides a node.
   }

Right now, the in-neighbors sequence unnecessarily features a call to in-set, which wraps the set in an opaque sequence. Sets are sequences, so this isn't necessary, and makes everything slower.

The documentation for do-bfs says:

In the body of colon-suffixed keywords, implicit special identifiers refer to the vertices under consideration. Specifically, $v is bound to the current vertex and $from is its parent (when appropriate). A $to identifier has the same value as $v, in case that name makes more sense in the context of the program. The special $acc identifier represents the accumulator value.

This implies that all colon keyword bodies (that would otherwise take an argument), have $v, as well as $to as an alias. And ones that also have a from node (such as the enqueue one), also have a $from bound. (And finally $acc for ones with an acc parameter.)

The problem here is $to. It is not bound in cases where a $from node is not otherwise bound. This is misleading, as the docs imply that $to and $v are interchangeable.

Honestly either way is fine, but either the prose in the docs should be updated, or $to should be bound as $v in bodies such as #:visit.

For example:

  (do-bfs g* sink-node
          #:visit: (DIST-set!
                    $v
                    (for/fold ([offset +inf.0])
                              ([$from (in-neighbors $to)])
                     (min offset (+ (DIST $from)
                                    (OFFSET $to $from))))))

$to is unbound, but if we replace it to $v, it works as expected.

I'm assuming that the interface is imperative to avoid making increasingly large graph copies. Still, I'd hope to have (and am willing to contribute) a functional interface if there's a way to only use memory for added vertices, edges, and properties and reuse references to existing data.

I understand some could argue that defeats the purpose of functional code in the first place, but the imperative interface tends to make the code around it imperative too. I'd like to limit that.

Are there already any plans to do this?

There's what looks like a typeo or some kind of confusion in the description of do-dfs. I include the affected section below

"For some keywords, the accumulator may also be named. In the body of colon-suffixedThe special $acc identifier represents the accumulator value. "

This misuse of undirected-graph should raise an error about its argument but fails internally.

> (undirected-graph (list #f #t) (list 0 1))
. . apply: contract violation
  expected: list?
  given: #f

I've very much enjoyed using this library, thank you!

A graph that is allowed to have multiple edges between the same two vertices is a multigraph.
The graph library as it stands does not support multigraphs because of the use of sets for the adjacency lists.
It would be great to also support multigraphs. For example, I'm using graphs to represent control-flow
graphs, and its important to distinguish between a single edge versus multiple edges between two basic blocks.

Docs claim to provide a function called johnson, but

(require graph)
johnson

produces an "unbound identifier" error.

see valid-version? documentation

When a graph contains a bunch of structs (rather than just symbols or strings), the graphviz files produced by the graphviz call looks something like this:

digraph G {
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<sink-node>;
	#<source-node>;
	#<source-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	#<filter-node>;
	subgraph U {
		edge [dir=none];
	}
	subgraph D {
		#<filter-node> -> #<filter-node> [label=2];
		#<filter-node> -> #<filter-node> [label=1];
		#<filter-node> -> #<filter-node> [label=1];
		#<filter-node> -> #<filter-node> [label=+inf.0];
		#<filter-node> -> #<filter-node> [label=+inf.0];
		#<filter-node> -> #<filter-node> [label=+inf.0];
		#<filter-node> -> #<sink-node> [label=+inf.0];
		#<source-node> -> #<filter-node> [label=+inf.0];
		#<source-node> -> #<filter-node> [label=+inf.0];
		#<filter-node> -> #<filter-node> [label=+inf.0];
		#<filter-node> -> #<filter-node> [label=1];
		#<filter-node> -> #<filter-node> [label=+inf.0];
		#<filter-node> -> #<filter-node> [label=1];
		#<filter-node> -> #<filter-node> [label=2];
	}
}

This is particularly problematic because #<filter-node> is not a valid node identifier in graphviz. In particular, when I run it, I get this error:

Error: :2: syntax error near line 2 context: >>> # <<< ; 

What would be better is give each node a unique (graphviz complaint) identifier, and use the name field to name the node.

mrlib/graph provides a pastboard% and snip% mixin for creating interactive graphs. It would be great if a graph from this library could create an interactive graph editor using these. And/or being able to export the contents of one of these editors to a graph that this library can handle.

I noticed this project does not have a LICENSE file. Otherwise people technically can't download it from the packager catalog.

Two possible suggestions are the Apache v2.0 or the LGPL v2/3. I would be happy to make a PR to add a LICENSE.

Change the value held by an existing vertex (and also update any edges referring to that vertex). Raise error if new value would conflict with another vertex.

Use case: graphs where you want to change the vertex values but not the relationship between vertices, for example graphs in the Cartesian plane. Operations like shift, scale, skew can be accomplished by transforming vertex values.

(Could be expanded to map-vertices that applies a lambda to every vertex and returns a new graph: (define g2 (map-vertices (λ(v) (* 2 v)) g))

The documentation suggests that the graph library's graphviz function can be called with an optional #:colors keyword argument, and that the value should be a boolean, but calling it with the value #t results in unhappiness (and a bad error message):

#lang racket

(require graph)

(graphviz
 (unweighted-graph/directed
  '((a b)
    (c b)))
 #:colors #t)

==>

hash-values: contract violation
  expected: hash?
  given: #t
> 

The documentation says that it uses data/queue module. The documentation for that module says it is not thread safe. As such is this library thread safe? Either way, the docs should say if it is or is not.

Am I right in thinking that get-neighbors and in-neighbors return only outbound neighbors for directed graphs? That is, only neighbors with edges from the specified vertex.

1. This is not currently documented. I would be happy to draft a PR.
2. It would be useful to have a function like get-neighbors for directed graphs that returns inbound neighbors.

Test case:

#lang racket
(require graph)

;; Each vertex is a pair via a struct
(struct vtx (tag contents) #:transparent)

;; List of edges in an undirected graph
(define edges
  (list
   (list (vtx 0 (set 3)) (vtx 1 (set 3 2)))
   (list (vtx 0 (set 0)) (vtx 1 (set 3 0)))
   (list (vtx 0 (set 1)) (vtx 1 (set 1 2)))
   (list (vtx 0 (set 1)) (vtx 1 (set 1 3)))
   (list (vtx 0 (set 3 2)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 0)) (vtx 1 (set 0 2)))
   (list (vtx 0 (set 3)) (vtx 1 (set 1 3)))
   (list (vtx 0 (set 3)) (vtx 1 (set 3 0)))
   (list (vtx 0 (set 1)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 2)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 3 0)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 2)) (vtx 1 (set 0 2)))
   (list (vtx 0 (set 3)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 0)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 1 3)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 2)) (vtx 1 (set 3 2)))
   (list (vtx 0 (set 3)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 2)) (vtx 1 (set 1 2)))
   (list (vtx 0 (set 3 0)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 0)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 0 2)) (vtx 1 (set 3 0 2)))))

;; Perform maximum bipartite matching.
(pretty-print (maximum-bipartite-matching (undirected-graph edges)))

Results in:

(list
 (list (vtx 1 (set 1 3 0)) (vtx 0 (set 1 3)))
 (list (vtx 1 (set 1 3)) (vtx 0 (set 1)))
 (list (vtx 1 (set 0 2)) (vtx 0 (set 0)))
 (list (vtx 0 (set 1)) (vtx 1 (set 1 3 0)))
 (list (vtx 1 (set 3 2)) (vtx 0 (set 2)))
 (list (vtx 1 (set 3 0)) (vtx 0 (set 3)))
 (list (vtx 1 (set 1 2)) (vtx 0 (set 1)))
 (list (vtx 1 (set 3 0 2)) (vtx 0 (set 3 2)))
 (list (vtx 1 (set 1 3 0)) (vtx 0 (set 3 0))))

I believe this is wrong, since I see (vtx 0 (set 1)) included in two edges here. Given that this is a maximal bipartite graph matching, this should not occur, as long as vertices are compared using equal?. I did a quick test to ensure that (equal? (vtx 0 (set 1)) (vtx 0 set 1)) is true. Next, I dug into the source of the implementation, and it does seem that the implementation respects equal?. So I don't see an obvious reason why this should happen.

Thoughts?

I would to connect the generic graph library with Typed Racket code. I started a package here: https://git.marvid.fr/scolobb/typed-graph

Right now I'm trying to add matrix graphs to typed-graph, and I am somewhat stuck at the matrix-graph macro. I can import it without any problem, but since it expands to a constructor of the matrix-graph struct, Typed Racket wants to have a type for that struct, which I don't know how to produce, because graph does not export it.

I can see the following ways to go, in order of my preference:

1. Add a function to the graph library to create matrix graphs from a matrix, in addition to the matrix-graph macro. In this way, typed-graph can construct matrix graphs via an opaque function call, and even have a macro expanding to that function call, similarly to the original matrix-graph.

2. Omit matrix graphs from the typed interface. (I don't personally use them).

3. Export the matrix-graph struct. This is probably unwanted, because the struct seems to be part of the inner workings of the library.

4. Add types directly to the graph library code base. This would require serious changes to the architecture of the library, in particular because Typed Racket doesn't directly support generics AFAIK. This option is probably an overkill for anyone who just wants to casually use graph from Typed Racket code.

What do you think?

Clearly, I am willing to submit the corresponding pull requests.

Because the adjacency "list" representation uses a set instead of a list, only one self loop is currently allowed per vertex.

Does graph support serialization?
I'd like to write these graphs to disk and update them with time.
Is this not possible? I can't see it in the documentation.

I'd like to implement a modified topological sort that only builds up the result list from a specified root element. Given that the existing tsort is based on do-dfs, that seems like the obvious route to go, but the documentation is pretty unclear as to how I could specify the starting point for a traversal, so as to exclude vertices which aren't descended from a particular node.

I'm currently working with a graph where nodes have an ordered sequence of children, whereas the graph package seems to implement unordered sequences. I can work around this by giving children an ID, but this approach prevents me from using the provided BFS and DFS functions due to the use of in-neighbors. I believe that I would need a slight variant of these functions which uses get-neighbors and which provides a sorting hook.

I could implement this myself, but would you accept a pull request for code that adds something like do-dfs/eager and do-bfs/eager? If so, I'll make one.

Thanks @skbach.

1.) Adjacency lists are failing as graphs for many other functions.

(define adj (unweighted-graph/adj '((a b c) (b c d))))
(dag? adj) ; => crash

(bellman-ford adj 'a) ; => crash

2.) Destination vertices of an adjacency list aren't reported as vertices.

(define g (unweighted-graph/adj '((a b) (a c) (b c))))
(in-vertices g)
'(a b) ;; should have 'c

(sequence->list (in-edges g))
'((a c) (b c)) ;; should have '(a b)

Hi ,
Please add the racket topic to this repo - I think others will be interested and this will help them find it at https://github.com/topics/racket

https://help.github.com/en/articles/classifying-your-repository-with-topics

Kind regards,

Stephen

When I create an empty graph and compute the transitive closure, the result is #f even though the documentation does not list this as an option. There is no contract error.

How to reproduce:

(require graph)
(define my-graph (directed-graph (list)))
(transitive-closure my-graph)

I have a graph created using (weighted-graph/undirected '()) and add-edge!. When I do edge-weight I only get the weight for the direction I used when calling add-edge!. For the other dir I get +inf.0.
I ended up calling add-edge! twice for every edge to make my program work correctly. Is this OK and if so, what is the rationale?
Anyway, cool lib otherwise :) Makes graph-based algos short and sweet.

Many useful graphs have multiple edges between vertices, although it can complicate some algorithms. The alternative is to manage multiple edges manually, for example storing a count property on an edge, or a list of named properties that represent each alternative instance of that edge.

See Ubergraph for an implementation example in Clojure that supports multigraphs with both directed and undirected edges.