2
$\begingroup$

I'm writing a framework for some graph theorical tasks and am unsure about some definitions regarding mixed graphs. Degrees and connectivity in particular.

A mixed graph G is a graph in which some edges may be directed and some may be undirected.

I couldn't find any comprehensive definitions for mixed graphs on the web and am kind of stuck here as I don't want to unintentionally contradict general graph theoretical principles by just following my gut feelings of what feels right for me.


One of those uncertainties being:
How is in-degree (and out-degree respectively) defined in mixed graphs?

Is it this?:

inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    #undirected edges being ignored
    return directedEdgeCount

…or is it this?:

inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    undirectedEdgeCount = count(undirected incident edges)
    return directedEdgeCount + undirectedEdgeCount

I found some general graph definitions saying that:

degree():
    return inDegree() + outDegree()

Which makes perfect sense for strictly directed/undirected graphs if first version of inDegree() was to be used. It would count undirected edges twice though, if second version of inDegree() was to be used.
My gut says that undirected edges lacking any direction basically allow flow in both directions and thus should be included in inDegree()/outDegree(), shouldn't they?


And coming from the above I have to ask:

If this is correct:

isDirectNeighborOf(other):
    return (self has any edge connecting it to/from/between other)

…which it is, from my understanding.

Then which one of these is correct? Is it this?:

isDirectPredecessorOf(other):
    #ignoring undirected edges
    return (self has outgoing directed edge to other)

…or this?:

isDirectPredecessorOf(other):
    return (self has outgoing directed or undirected edge to other)

Concrete example:

multigraph

  • What is the in-degree of B? (my gut says 3)
  • What is the out-degree of C? (my gut says 3)
  • What is the in-degree of D? (my gut says 2)
  • What is the out-degree of D? (my gut says 2)
  • Is D direct predecessor of B? (my gut says YES)
  • Is D direct successor of B? (my gut says YES)

Does anybody here happen to have a comprehensive set
of definitions regarding mixed graphs?

As with many graph types the theoretical sonstruct mixed graph is ambiguously used.
Hence I'm not so much searching for a universally accepted definition, but rather looking for any at all.

$\endgroup$
  • 2
    $\begingroup$ I would be surprised if there is a single universally accepted definition for in- and out-degrees in mixed graphs. $\endgroup$ – Tsuyoshi Ito May 4 '11 at 16:36
  • $\begingroup$ I couldn't find any definition for mixed graphs. So even if there is no universal definition I'd be more than happy to at least have one based on which I then could implement a consistent mixed graph. No matter where I looked mixed graphs were always just merely mentioned à la "oh, and btw. there also graphs of some sort which are called mixed graphs", but none gave definitions (beyound ones along the one I quoted in my answer) whatsoever. $\endgroup$ – Regexident May 4 '11 at 16:53
  • 2
    $\begingroup$ If you need a definition in your paper (or library or whatever), define it and do not expect that readers (or users) already know the definition. Otherwise, do not care. $\endgroup$ – Tsuyoshi Ito May 4 '11 at 17:05
2
$\begingroup$

The definition I found in Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias (Section 2.1) is:

A mixed graph is a vertex-edge graph that can contain three kinds of edges: directed ($\rightarrow$), bi-directed ($\leftrightarrow$) and undirected ($-$), and at most one edge between any two vertices.

...

Two vertices are said to be adjacent in a mixed graph if there is an edge (of any kind) between them. Given a mixed graph $G$ and two adjacent vertices A,B therein, A is a parent of B and B is a child of A if A $\rightarrow$ B is in $G$; A is called a spouse of B (and B a spouse of A) if A $\leftrightarrow$ B is in $G$; A is called a neighbor of B (and B a neighbor of A) if A $-$ B is in $G$.

...

A directed path from $V_{0}$ to $V_{n}$ in $G$ is a sequence of distinct vertices such that for 0 $\leq$ i $\leq$ n-1, $V_{i}$ is a parent of $V_{i+1}$ in $G$. A is called an ancestor of B and B a descendant of A if A = B or there is a directed path from A to B.

Richardson and Spirtes give another nice and simple definition of mixed graphs in Ancestral Graph Markov Models (Section 2.2).

Note that the three edge types should be considered as distinct symbols, and in particular

A $-$ B $\neq$ A $\leftrightarrows$ B $\neq$ A $\leftrightarrow$ B.

However, none of them defines in and out degree.

$\endgroup$
  • $\begingroup$ Thanks, that's actually a pretty good starting point. For the time being I'll accept it. (First time I've heard about bidirected (vs. undirected) edges. Interesting.) $\endgroup$ – Regexident May 5 '11 at 9:11
  • $\begingroup$ I will be curious to investigate what the difference is between the two, as regards adjacency matrices/paths/walks. $\endgroup$ – Niel de Beaudrap May 6 '11 at 8:20
  • $\begingroup$ @Niel de Beaudrap: I've one quite a bit of searching in both literature and the web, but couldn't find a single notion of a graph utilizing bidirected edges in a way that would not have been possible to accomplish with simple undirected edges. In $\endgroup$ – Regexident May 13 '11 at 17:59
  • $\begingroup$ Treating bidirected and undirected edges differently seems unnecessary. You could also think of there being two distinct directed edges (A -> B and B -> A) with the same weight. All three notions seem the same. For example, as Niel asked, how would the adjacency matrix look any different? $\endgroup$ – Huck Bennett Jul 1 '11 at 5:46
  • $\begingroup$ Well, it depends on the problem. Usually you won't need to differentiate between them (which means you won't need mixed graphs at all), but there are problems which treat them differently (check the links). $\endgroup$ – George Jul 1 '11 at 12:25
2
$\begingroup$

A consistent and quite usable definition of mixed graphs, which I call general graphs, can be found in G.Stiege, General Graphs. A report is obtainable from http://www-bvs.informatik.uni-oldenburg.de/Literatur/Berichte/oib07-02.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.