Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to represent a strange graph in some data structure

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:

Strangely Directional Graph

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.

like image 330
Wilduck Avatar asked Jun 16 '11 18:06

Wilduck


People also ask

How do you represent a graph in data structure?

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.

How many types of graphs are there in data structure?

Following are the 17 different types of graph in the data structure explained below.

What is a graph explain with example in data structure?

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.


1 Answers

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.

enter image description here

like image 128
unutbu Avatar answered Oct 04 '22 04:10

unutbu