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.