General definitions for mixed graphs? (degrees, connectivity, etc) 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.
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.