3 ms·

With an obvious notion of negation of graphs, wouldn't the `connect` operation be \g1 g2 -> not $ (not g1) `overlay` (not g2)? (I've already asked about lattic

by JadeNB 10y ago

With an obvious notion of negation of graphs, wouldn't the `connect` operation be \g1 g2 -> not $ (not g1) `overlay` (not g2)? (I've already asked about lattice theory elsewhere (https://news.ycombinator.com/item?id=13125334 https://news.ycombinator.com/item?id=13125334 ); this thought makes me wonder if there's any connection to modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic, where modalities are often defined in these sort of "de Morgan pairs".) EDIT: I originally typo'd and proposed the above as a definition of the `overlay` operation, which would be both a pointless circularity and wrong.

LolWolf 10y ago
I'm afraid I don't quite understand what the negation of a graph is in this case and what you mean by 'overlay,' perhaps elaborate a bit?
- taejo 10y ago
  overlay or + is the operation from the article; not is the graph with the complementary edge set (i.e. `not (V, E) = (V, E \ (V × V))`)
  - JadeNB 10y ago
    Yup, that's what I meant (except that I think your set complement is backwards). Sorry for not replying earlier; I was "submitting too fast."
    - taejo 10y ago
      > I think your set complement is backwards It is. Unfortunately I can't fix it now.
sn0wleopard 10y ago
JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. So, indeed there is a sort of de Morgan law: a -- b = !(!a + !b) where ! is the graph edge-complement, a and b do not have common vertices, and -- is a commutative version of ->. (Responding so late, because I was also "submitting too fast"!)
- JadeNB 10y ago
  > JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. Agreed; I thought that your `overlay` was the "(forced) disjoint union". I had missed that "(vertex x) `overlay` (vertex y)" was not isomorphic to "(vertex x) `overlay` (vertex x)". I don't even know what negation would mean for directed graphs. (By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. Since the displayed code only ever uses `Vertex g` in order to promote it immediately to `Graph g`, does it make sense just to have them as a separate type? (Maybe I'm misreading; it's been a while since I've Haskell'd.) Also, am I wrong to read `vertex` as a kind of `return`? (I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better.)) While we're talking: thanks for this article; I enjoyed it a lot. My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. https://en.wikipedia.org/wiki/Clique_(graph_theory) https://en.wikipedia.org/wiki/Clique_(graph_theory)
  - sn0wleopard 10y ago
    > By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. In fully polymorphic code (like clique) you indeed can't produce new inhabitants, or do anything else with the values of type `Vertex g`. However, if you know something about `Vertex g` then you can do certain things. For example, if we know that the type of vertices has `Ord` instance then we can compare them (as we do in `Relation`). And in very concrete code, e.g. operating on `Basic Int` values, you can create new inhabitants freely -- any number will do. > Also, am I wrong to read `vertex` as a kind of `return`? It is indeed very much like `return` or `pure`! We use it to inject a type into a sort of container type, in this case, into a graph type. > I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better Many `Graph` instances are `Monad`s. For example, `Basic` is a `Monad` (and many other things too). But on the other hand `Relation` is not a `Monad`, because it imposes the `Ord` constraint on the underlying type (and Haskell monads are not allowed that). > While we're talking: thanks for this article; I enjoyed it a lot. Thank you! I didn't expect so much interest to it, so I'm a bit overwhelmed to be honest :) > My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.

by JadeNB 10y ago

LolWolf 10y ago

I'm afraid I don't quite understand what the negation of a graph is in this case and what you mean by 'overlay,' perhaps elaborate a bit?

taejo 10y ago
overlay or + is the operation from the article; not is the graph with the complementary edge set (i.e. `not (V, E) = (V, E \ (V × V))`)
- JadeNB 10y ago
  Yup, that's what I meant (except that I think your set complement is backwards). Sorry for not replying earlier; I was "submitting too fast."
  - taejo 10y ago
    > I think your set complement is backwards It is. Unfortunately I can't fix it now.

sn0wleopard 10y ago

JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. So, indeed there is a sort of de Morgan law: a -- b = !(!a + !b) where ! is the graph edge-complement, a and b do not have common vertices, and -- is a commutative version of ->. (Responding so late, because I was also "submitting too fast"!)

JadeNB 10y ago
> JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. Agreed; I thought that your `overlay` was the "(forced) disjoint union". I had missed that "(vertex x) `overlay` (vertex y)" was not isomorphic to "(vertex x) `overlay` (vertex x)". I don't even know what negation would mean for directed graphs. (By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. Since the displayed code only ever uses `Vertex g` in order to promote it immediately to `Graph g`, does it make sense just to have them as a separate type? (Maybe I'm misreading; it's been a while since I've Haskell'd.) Also, am I wrong to read `vertex` as a kind of `return`? (I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better.)) While we're talking: thanks for this article; I enjoyed it a lot. My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. https://en.wikipedia.org/wiki/Clique_(graph_theory) https://en.wikipedia.org/wiki/Clique_(graph_theory)
- sn0wleopard 10y ago
  > By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. In fully polymorphic code (like clique) you indeed can't produce new inhabitants, or do anything else with the values of type `Vertex g`. However, if you know something about `Vertex g` then you can do certain things. For example, if we know that the type of vertices has `Ord` instance then we can compare them (as we do in `Relation`). And in very concrete code, e.g. operating on `Basic Int` values, you can create new inhabitants freely -- any number will do. > Also, am I wrong to read `vertex` as a kind of `return`? It is indeed very much like `return` or `pure`! We use it to inject a type into a sort of container type, in this case, into a graph type. > I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better Many `Graph` instances are `Monad`s. For example, `Basic` is a `Monad` (and many other things too). But on the other hand `Relation` is not a `Monad`, because it imposes the `Ord` constraint on the underlying type (and Haskell monads are not allowed that). > While we're talking: thanks for this article; I enjoyed it a lot. Thank you! I didn't expect so much interest to it, so I'm a bit overwhelmed to be honest :) > My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.