<p>The definition I found in <a href="http://portal.acm.org/citation.cfm?id=1414237" rel="nofollow">Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias</a> (Section 2.1) is:</p>

<blockquote>
  <p>A <strong>mixed graph</strong> 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.</p>
  
  <p>...</p>
  
  <p>Two vertices are said to be
  <strong>adjacent</strong> 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
  <strong>parent</strong> of B and B is a <strong>child</strong> of A if A $\rightarrow$ B is in $G$; A is called
  a <strong>spouse</strong> of B (and B a spouse of
  A) if A $\leftrightarrow$ B is in $G$; A is called a
  <strong>neighbor</strong> of B (and B a neighbor of A) if A $-$ B is in $G$. </p>
  
  <p>...</p>
  
  <p>A <strong>directed path from</strong> $V_{0}$
  <strong>to</strong> $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
  <strong>ancestor</strong> of B and B a <strong>descendant</strong> of A if A = B or there is a directed path from A to B.</p>
</blockquote>

<p>Richardson and Spirtes give another nice and simple definition of mixed graphs in <a href="http://www.google.gr/url?sa=t&amp;source=web&amp;cd=2&amp;ved=0CCYQFjAB&amp;url=http://www.hss.cmu.edu/philosophy/spirtes/annals2002.pdf&amp;rct=j&amp;q=ancestral%20graph%20markov%20models&amp;ei=QpDBTbybJ87usgb_48nDBQ&amp;usg=AFQjCNEDu4LLo95EYuE4qIXO-HtUmT6RJw&amp;sig2=JbvEH9C5wc3b2jxhS5lKvg&amp;cad=rja" rel="nofollow">Ancestral Graph Markov Models</a> (Section 2.2).</p>

<blockquote>
  <p>Note that the three edge types should be considered as distinct symbols, and in particular </p>
  
  <p>A $-$ B $\neq$ A $\leftrightarrows$ B $\neq$ A $\leftrightarrow$ B.</p>
</blockquote>

<p>However, none of them defines in and out degree.</p>

CC BY-SA 3.0
2011-05-05T09:11:29.397Z
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.)
Regexident
CC BY-SA 3.0
2011-05-06T08:20:53.517Z
I will be curious to investigate what the difference is between the two, as regards adjacency matrices/paths/walks.
Niel de Beaudrap
CC BY-SA 3.0
2011-05-13T17:59:36.540Z
@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
Regexident
CC BY-SA 3.0
2011-07-01T05:46:18.090Z
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?
Huck Bennett
CC BY-SA 3.0
2011-07-01T12:25:51.443Z
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).
George
CC BY-SA 3.0
2011-05-04T17:54:23.210Z
2011-05-04T17:54:23.210Z
George
<p>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
<a href="http://www-bvs.informatik.uni-oldenburg.de/Literatur/Berichte/oib07-02.html" rel="nofollow">http://www-bvs.informatik.uni-oldenburg.de/Literatur/Berichte/oib07-02.html</a></p>

CC BY-SA 3.0
2011-06-29T09:34:33.790Z
2011-06-29T09:34:33.790Z
G.Stiege
<p>I'm writing a framework for some graph theorical tasks and am unsure about some definitions regarding <strong>mixed graphs</strong>. Degrees and connectivity in particular.</p>

<blockquote>
  <p><a href="http://en.wikipedia.org/wiki/Mixed_graph#Mixed_graph" rel="nofollow noreferrer">A mixed graph G is a graph in which
  some edges may be directed and some
  may be undirected.</a></p>
</blockquote>

<p>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.</p>

<hr>

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

<p>Is it this?:</p>

<pre><code>inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    #undirected edges being ignored
    return directedEdgeCount
</code></pre>

<p>…or is it this?:</p>

<pre><code>inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    undirectedEdgeCount = count(undirected incident edges)
    return directedEdgeCount + undirectedEdgeCount
</code></pre>

<p>I found some general graph definitions saying that:</p>

<pre><code>degree():
    return inDegree() + outDegree()
</code></pre>

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

<hr>

<p>And coming from the above I have to ask:</p>

<p>If this is correct:</p>

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

<p>…which it is, from my understanding.</p>

<p>Then which one of these is correct? Is it this?:</p>

<pre><code>isDirectPredecessorOf(other):
    #ignoring undirected edges
    return (self has outgoing directed edge to other)
</code></pre>

<p>…or this?:</p>

<pre><code>isDirectPredecessorOf(other):
    return (self has outgoing directed or undirected edge to other)
</code></pre>

<hr>

<p>Concrete example:</p>

<p><img src="https://i.sstatic.net/acqHj.gif" alt="multigraph"></p>

<ul>
<li>What is the <strong>in-degree of B</strong>? <em>(my gut says <strong><code>3</code></strong>)</em></li>
<li>What is the <strong>out-degree of C</strong>? <em>(my gut says <strong><code>3</code></strong>)</em></li>
<li>What is the <strong>in-degree of D</strong>? <em>(my gut says <strong><code>2</code></strong>)</em></li>
<li>What is the <strong>out-degree of D</strong>? <em>(my gut says <strong><code>2</code></strong>)</em></li>
<li>Is <strong>D direct predecessor of B</strong>? <em>(my gut says <strong><code>YES</code></strong>)</em></li>
<li>Is <strong>D direct successor of B</strong>? <em>(my gut says <strong><code>YES</code></strong>)</em></li>
</ul>

<hr>

<p><strong>Does anybody here happen to have a comprehensive set<br>
of definitions regarding mixed graphs?</strong></p>

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

CC BY-SA 3.0
2011-05-04T16:36:36.380Z
I would be surprised if there is a single universally accepted definition for in- and out-degrees in mixed graphs.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-04T16:53:41.897Z
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.
Regexident
CC BY-SA 3.0
2011-05-04T17:05:41.093Z
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.
Tsuyoshi Ito
<graph-theory><co.combinatorics>
General definitions for mixed graphs? (degrees, connectivity, etc)
Regexident
# General definitions for mixed graphs? (degrees, connectivity, etc)

(Asked by: username_0 on 2011-05-04)

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:


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.

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: I would be surprised if there is a single universally accepted definition for in- and out-degrees in mixed graphs.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-05-04. Score: 2 | Accepted answer

The definition I found in [Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias](http://portal.acm.org/citation.cfm?id=1414237) (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](http://www.google.gr/url?sa=t&source=web&cd=2&ved=0CCYQFjAB&url=http://www.hss.cmu.edu/philosophy/spirtes/annals2002.pdf&rct=j&q=ancestral%20graph%20markov%20models&ei=QpDBTbybJ87usgb_48nDBQ&usg=AFQjCNEDu4LLo95EYuE4qIXO-HtUmT6RJw&sig2=JbvEH9C5wc3b2jxhS5lKvg&cad=rja) (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.

> **Comments:**
> **username_0**: 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.)  
> **username_3**: I will be curious to investigate what the difference is between the two, as regards adjacency matrices/paths/walks.  
> **username_0**: @username_3: 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  
> **username_4**: 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?  
> **username_2**: 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).  

---

### Answer by username_5 on 2011-06-29. Score: 2

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


---

