I'm writing a framework for some graph theorical tasks and am unsure about some definitions regarding mixed graphs. Degrees and connectivity in particular.
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)
isDirectPredecessorOf(other): return (self has outgoing directed or undirected edge to other)
- What is the in-degree of B? (my gut says
- What is the out-degree of C? (my gut says
- What is the in-degree of D? (my gut says
- What is the out-degree of D? (my gut says
- Is D direct predecessor of B? (my gut says
- Is D direct successor of B? (my gut says
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.