My understanding of the problem, as originally stated and then updated by comments under Macke's reply, includes the following: 1) both edge types (dependencies and conflicts) are directed; 2) if two nodes are connected by one edge, they must not be connected by another, even if it is of the other type or in reverse; 3) if a path between two nodes can be constructed by mixing edges of different types, then that is an error, rather than a circumstance that is ignored; 4) If there is a path between two nodes using edges of one type, then there may not be another path between them using edges of the other type; 5) cycles of either a single edge type or mixed edge types are not permitted (from a guess at the application, I am not sure that conflict-only cycles are an error, but this condition can be removed, if not.)
Furthermore, I will assume the data structure used does not prevent violations of these requirements being expressed (for example, a graph violating condition 2 could not be expressed in a map from node-pair to (type, direction) if the node-pair always has the least-numbered node first.) If certain errors cannot be expressed, it reduces the number of cases to be considered.
There are actually three graphs that can be considered here: the two of exclusively one edge type, and the mixed graph formed by the union of one of each of the two types. You can use this to systematically generate all graphs up to some number of nodes. First generate all possible graphs of N nodes having no more than one edge between any two ordered pairs of nodes (ordered pairs because these are directed graphs.) Now take all possible pairs of these graphs, one representing dependencies and the other representing conflicts, and form the union of each pair.
If your data structure cannot express violations of condition 2, you can significantly reduce the cases to be considered by only constructing all possible conflict graphs that fit within the spaces of the dependency graphs, or vice-versa. Otherwise, you can detect violations of condition 2 while forming the union.
On a breadth-first traversal of the combined graph from the first node, you can build the set of all paths to every reachable node, and as you do so, you can check for violations of all the conditions (for cycle detection, you could use Tarjan's algorithm.)
You only have to consider paths from the first node, even if the graph is disconnected, because paths from any other node will appear as paths from the first node in some other case.
If mixed-edge paths can simply be ignored, rather than being errors (condition 3), it is sufficient to consider the dependency and conflict graphs independently, and check that if a node is reachable in one, it is not in the other.
If you remember the paths found in examining graphs of N-1 nodes, you can use them as the starting point for generating and evaluating graphs of N nodes.
This does not generate multiple edges of the same type between nodes, but it could be extended to do so. This would greatly increase the number of cases however, so it would be better if the code being tested made this impossible to represent, or failing that, filtered out all such cases beforehand.
The key to writing an oracle like this is to keep it as simple as possible, even if that means being inefficient, so that you can establish trust in it (ideally through arguments for its correctness, backed up by testing.)
Once you have the means to generate test cases, and you trust the oracle you have created to accurately separate the good from the bad, you might use this to drive the automated testing of the target code. If that is not feasible, your next best option is to comb through the results for distinctive cases. The oracle can classify the errors it finds, and give you some information about the accepted cases, such as the number and length of paths of each type, and whether there are any nodes that are at the start of both types of path, and this could help you look for cases you have not seen before.