I am trying to find an appropriate data structure for representing available navigations between a game’s screens.

• Using a linked list, a node can only have one node after it : inappropriate.

• Using a tree seems up to the job as nodes can have many children nodes but it’s inconsistent in the sense that a supposedly children item Options can have a parent Title as a children. Also how am I supposed to represent the infinite sequence of the case Title -> Race -> Title -> Race … without endlessly repeating it in my tree ? Still, this is the best structure I found to accomplish the job.

Here is an example of the possible sequences :

1. Title
   • Options
   • Race
2. Options
   • Title
   • Race
3. Race
   • Options
   • Title

Do you know whether a tree is the way to go or if there’s a better structure for this job ?

Edit:

There is a great library for creating graphs for C#/WPF : http://graphsharp.codeplex.com/

It uses http://quickgraph.codeplex.com/ internally.

Here’s a small example :

Code-behind:

using System.Collections.Generic;
using System.Windows;
using GraphSharp.Controls;
using QuickGraph;

namespace WpfApplication15graph
{
    internal class ScreenVertex
    {
        public string Hello { get; set; }
    }

    internal class ScreenEdge : Edge<ScreenVertex>
    {
        public ScreenEdge(ScreenVertex source, ScreenVertex target)
            : base(source, target)
        {
        }
    }

    internal class ScreenLayout : GraphLayout<ScreenVertex, ScreenEdge, ScreenGraph>
    {
    }

    internal class ScreenGraph : BidirectionalGraph<ScreenVertex, ScreenEdge>
    {
    }

    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
            Loaded += MainWindow_Loaded;
        }

        private void MainWindow_Loaded(object sender, RoutedEventArgs e)
        {
            // build graph
            var screenGraph = new ScreenGraph();
            var screenVertex1 = new ScreenVertex {Hello = "1"};
            var screenVertex2 = new ScreenVertex {Hello = "2"};
            var screenVertex3 = new ScreenVertex {Hello = "3"};
            screenGraph.AddVertex(screenVertex1);
            screenGraph.AddVertex(screenVertex2);
            screenGraph.AddVertex(screenVertex3);
            screenGraph.AddEdge(new ScreenEdge(screenVertex1, screenVertex2));
            screenGraph.AddEdge(new ScreenEdge(screenVertex2, screenVertex1));
            screenGraph.AddEdge(new ScreenEdge(screenVertex1, screenVertex3));
            screenGraph.AddEdge(new ScreenEdge(screenVertex3, screenVertex1));
            screenGraph.AddEdge(new ScreenEdge(screenVertex3, screenVertex2));
            ScreenLayout.Graph = screenGraph;

            // get connections for a particular vertex
            IEnumerable<ScreenEdge> inEdges = screenGraph.InEdges(screenVertex3);
            IEnumerable<ScreenEdge> outEdges = screenGraph.OutEdges(screenVertex3);
        }
    }
}

XAML :

<Window x:Class="WpfApplication15graph.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:controls="clr-namespace:WPFExtensions.Controls;assembly=WPFExtensions"
        xmlns:controls1="clr-namespace:GraphSharp.Controls;assembly=GraphSharp.Controls"
        xmlns:wpfApplication15Graph="clr-namespace:WpfApplication15graph"
        Title="MainWindow"
        Width="525"
        Height="350">
    <Window.Resources>
        <DataTemplate x:Key="SvTemplate" DataType="wpfApplication15Graph:ScreenVertex">
            <Grid>
                <TextBlock Text="{Binding Hello}" />
            </Grid>
        </DataTemplate>
        <Style TargetType="controls1:VertexControl">
            <Style.Setters>
                <Setter Property="Template">
                    <Setter.Value>
                        <ControlTemplate TargetType="controls1:VertexControl">
                            <Border CornerRadius="5" Width="50" Height="50" Background="LightBlue">
                                <ContentPresenter Content="{TemplateBinding Vertex}"
                                                  ContentTemplate="{DynamicResource SvTemplate}" />
                            </Border>
                        </ControlTemplate>
                    </Setter.Value>
                </Setter>
            </Style.Setters>
        </Style>
    </Window.Resources>
    <Grid>
        <controls:ZoomControl>
            <wpfApplication15Graph:ScreenLayout x:Name="ScreenLayout"
                                                HighlightAlgorithmType="Simple"
                                                LayoutAlgorithmType="Circular"
                                                OverlapRemovalAlgorithmType="FSA" />
        </controls:ZoomControl>
    </Grid>
</Window>