I believe you’ve wandered into the field of over-engineering, chasing abstract principles instead of focusing on get things done in the simplest and most pleasant way.

Your (*) is a clear giveaway. OO can provide great help in managing complexity, but only as long as it’s used as a tool to that goal. If instead you want to “write pure OO” instead of “solving my problem”, it becomes a burden.

SRP is a similar thing — it’s well worth thinking. And especially good use to drive “extract” or “split” type of refactorings when your current code is overburdened with too many tasks. After addressing DRY usually we still have a plenty of options on packaging, and it is a matter of balance. Too big class is bad, but having it single has benefits. If the same task is done by 5 classes it may be way harder to follow. Especially if none of them have a chance to work alone, they are coupled with cross-calls in all directions. Such split might look good on dumb statistics but is bad for practice anyway.

So much for the theory, what about your case? You picked a border problem; indeed the function may not fit either Node or Edge. Though even that is hard to tell without the content, knowing what those actually do. Can I walk the graph having just a Node or an Edge? If I can, then adjacent may fit to that same group of functions.

Actually as soon as you have implementation of the function, it should be a great help to see where it fits better — what data it had to fetch. Say, if it starts with getting the node and edge collections from Graph, why on earth is it not just member of Graph and play on the home ground?

A free function might also be fair game. A *Utils fake class that is really just a trash bin is probably the worst way, that hardly wins anything but adds to complexity. But a language or an ill-conceived policy may force that.

The answer is “neither.” The problem with both your proposed solutions is that neither is an Information Expert for what it needs to know (how a single node relates to all the other nodes).

The only way you can have a free function that could calculate this information is by passing in all the nodes as an argument to the function. Otherwise, you do not have a free function, but brittle global state. If you already have all the nodes at your fingertips, do you really need the function?

More importantly, why doesn’t the object that has all the nodes at its fingertips have this method? <–hint, hint

Now, you could conceivably have nodes that have access to this information, if they’re implemented something like a doubly-linked-list, but with more directions than just next and previous. In this case, it would be trivial for a node to tell you if a given node is in its nextNode, previousNode, upNode, or downNode. But I suspect that you didn’t code your nodes this way, or you wouldn’t be asking the question. So go with the hint ;).

TL;DR

This phrase would help remind one not to apply SRP prematurely:

A good separation of responsibilities is done only when the full picture of how the application should work is well understand.

Source: http://www.oodesign.com/single-responsibility-principle.html

API Requirements Phase

These are given as examples. Cross out ones that are not required for your application.
The rest of the answer assumes all are required. If your requirements are different, you will have to re-apply the principles in order to fit your unique requirements.

• As a library user, given that I have an instance of Edge, I should be able to query the two Nodes connected by the edge. This should take O(1) time.
• As a library user, given that I have an instance of Node, I should be able to query the list of Edges that connect to the node. This should take O(num_edges_of_node) time, the number of edges that are connected to that one node.
• As a library user, given that I have an instance of Node and an instance of Edge, I should be able to check whether the Edge and the Node are in direct contact. This should take O(1) time.
• Add any requirements as needed.

School of thoughts: between Naive-OO versus Library-Design-OO

In Naive OO design, a method is put on the object wherever the user wants to use that functionality. Examples:

• Node[] theTwoNodes = someEdge.getNodes()
  (returned array size must be 2)
• Edge[] allConnectedEdges = someNode.getEdges()
  (returned array size can be 0 or above; unbounded.)
• bool isThisConnectedToThat = thisNode.isConnectedTo(thatEdge)
bool isThatConnectedToThis = thatEdge.isConnectedTo(thisNode)
  Implement the first one, the second one, or both.

When implementing the methods in a Naive OO design, one is constrained by Information Expert – refer to Amy Blankenship’s answer.

• Namely, the API Requirements says the user would like to do this, but to implement the required functionality, the instance will have to ask another instance for information.
• “Information Expert” is a rule-of-thumb that you can write less code if you associate the method with that other instance – the instance that has the most information ready to serve that functionality.
• In your sample code, the location of the Information Expert depends on your choice of data structure and algorithms.
  Typically, it is either centralized in the Graph object, or is distributed among a large number of Node and Edge instances.
  Nevertheless, nothing in my answer would be invalidated even if the Information Expert is located differently.

However, in Pythonic-OO, the library writer has to remove one of the two isConnectedTo methods, because of this:

There should be one — and preferably only one — obvious way to do it.

Source: http://c2.com/cgi/wiki?PythonPhilosophy

Finally, in Library-design-OO (which is the school of thought that permeates SOLID), the library writer will:

• Give convenience to the user, i.e. implement all of the methods identified in the Naive-OO stage;
• But internally, if one method can be implemented in terms of another method, then the first method will simply call (i.e. “delegate to”) the other method to do the task.
  • If Naive-OO puts a method into a class that is not the Information Expert, in Library-design-OO the method will simply call some other methods on the relevant Information Experts to do the task.
• Suppress your Pythonic thoughts. Pythonic thoughts make the code writer’s life easier. As a library writer, you take care of all of the seemingly duplicated implementation work so as to make your library’s users’ lives easier.

“You haven’t answered my question: does it violate SRP?”

Answer: It is not a conclusive violation if you, as a library writer, hasn’t released your code to your users.

Four of the five guidelines in SOLID, namely excepting Liskov (LSP), are pre-release design checklist items for software libraries. (LSP is a correctness requirement that is basically logic (related to property (in philosophy)), and is inescapable unless you develop illogical software.)

You, as a library writer, are allowed to keep refactoring (www.refactoring.com) your code as you continuously improve its design and implementation.

Of course you are allowed to change your code, including the objects, interfaces, methods, and implementations. That is true until you release your library, and your library acquires its users. Once there are library users, the SOLID principles help you avoid breaking those library users’ code.

Therefore, given that you are still in the library design stage of the process, asking whether it is a SRP violation can only give you an inconclusive answer.

Of course we should pay attention to whether some prototype code will lapse into a violation when it is released. However, at the design stage, the very tongue-in-cheek phrase often associated with SRP, namely,

A class should have only one reason to change.

is unfortunately irrelevant.
_{Source (same as above): http://www.oodesign.com/single-responsibility-principle.html}

To fix that, one could say this instead:

To satisfy SRP, a library class should be designed to have as few reasons to change as possible, after the library has been released.

“Can you answer the second part of my question: Why?”

Please scroll up to the top and re-read every part of my answer.

You have brought up questions about two SOLID principles. The first is about the Single Reponsibility Principle.

And now I doubt if I should add a isAdjacentTo(Node) method to the GraphEdge class or I should create a GraphUtil class(*) and add static edgeIsAdjacentToNode(Edge,Node) method to it.

The question that you should ask yourself about this is “does it feel natural to query to GraphEdge class to find out whether it is adjacent to a node?” If you can answer “yes” to this question, you are probably not violating the SRP. It’s as simple as that really.

If I were designing these classes, I would place the isAdjacentTo method on the GraphEdge class. You are querying a class as to its relationship with something else. For me that feels like a very natural thing to do. What doesn’t feel natural is calling a static method in a utility class to answer a question about an object that you already have. Why not ask the object itself?

I tend to view Utility classes as a code smell. They sometimes have their uses but in 99% of cases they contain methods which belong on an existing class.

The second SOLID principle you talked about was the Open-Closed principle.

Also if I stick to the first option this will probably violate the Open-Close Principle. The GraphEdge is not closed for changes, since later I will need to add linksNodes(Node,Node) method to it and maybe some others later.

Adding methods to the class is extending the class, not modifying it. The Open-Closed principle is about protecting the internal machinery of the class from being fiddled with. You don’t want inheritors being able to modify the internal implementation details. This is what it means to be closed for modification. It has nothing to do with adding more functionality to a class. It means that the functionality that you add is protected from unexpected and undesired external modification.