A simple way to represent a graph is with a data structure of the form:
{1:[2,3],
2:[1,3],
3:[1,2]}
Where the keys in this dictionary are nodes, and the edges are represented by a list of other nodes they are connected to. This data structure could also easily represent a directed graph if the links are not symmetrical:
{1:[2],
2:[3],
3:[1]}
I don't know much about the graph-theory, so what I'm about to propose might already have a simple solution, but I don't know what to look for. I've encountered what I think is a situation where a graph is somewhat directed, depending on both the node you're at, and the node you came from. To illustrate, I have a drawing:
Imagine you're speeding along edge A in a go-kart and at node 1 you hang a left onto edge B. Since you're going so fast, when you hit node 3, you're forced to continue onto edge F. However, if you were coming from edge F, you would be able to go on to either edge E or B. It is clear that node three is connected to 1 and 2, but whether or not you can reach them from that node depends on which direction you came from.
I'm wondering if there is a graph theory concept that describes this and/or if there is a simple data structure to describe it. While I'll be writing my code in python, I'll take advice coming from any reasonably applicable language.
Edit: I tried to post an image to go along with this, but I'm not sure if it's showing up. If it isn't here's a link to the image
Edit 2: I should have been clear. The image posted is meant to be a portion of a complete graph, in which there are more nodes off screen from A, D, and F.
In Incidence matrix representation, graph can be represented using a matrix of size: Total number of vertices by total number of edges. It means if a graph has 4 vertices and 6 edges, then it can be represented using a matrix of 4X6 class. In this matrix, columns represent edges and rows represent vertices.
Following are the 17 different types of graph in the data structure explained below.
Data Structure - Graph Data Structure A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
This could be represented by a directed graph.
Nodes in your graph could be represented as two nodes in the graph. Think of the nodes as representing locations on particular sides of a street -- the edges being like inbound and outbound lanes.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With